Journal of Artificial Intelligence Resarch: Volume 63の論文一覧

Journal of Artificial Intelligence Resarch Vol. 63 (2018)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。

論文

Human-Machine Collaborative Optimization via Apprenticeship Scheduling

Human-Machine Collaborative Optimization via Apprenticeship Scheduling / 見習いスケジューリングによる人間と機械の協調最適化

Coordinating agents to complete a set of tasks with intercoupled temporal and resource constraints is computationally challenging, yet human domain experts can solve these difficult scheduling problems using paradigms learned through years of apprenticeship. A process for manually codifying this domain knowledge within a computational framework is necessary to scale beyond the “single-expert, single-trainee” apprenticeship model. However, human domain experts often have difficulty describing their decision-making processes. We propose a new approach for capturing this decision-making process through counterfactual reasoning in pairwise comparisons. Our approach is model-free and does not require iterating through the state space. We demonstrate that this approach accurately learns multifaceted heuristics on a synthetic and real world data sets. We also demonstrate that policies learned from human scheduling demonstration via apprenticeship learning can substantially improve the efficiency of schedule optimization. We employ this human-machine collaborative optimization technique on a variant of the weapon-to-target assignment problem. We demonstrate that this technique generates optimal solutions up to 9.5 times faster than a state-of-the-art optimization algorithm.



時間的制約とリソース制約が相互に絡み合った一連のタスクを完了するためにエージェントを調整することは計算的に困難ですが、人間のドメインエキスパートは長年の見習い期間を通じて習得したパラダイムを用いて、これらの困難なスケジューリング問題を解決することができます。「単一の専門家と単一の訓練生」という見習いモデルを超えて拡張するには、このドメイン知識を計算フレームワーク内に手動でコード化するプロセスが必要です。しかし、人間のドメインエキスパートは、意思決定プロセスを記述することがしばしば困難です。本稿では、一対比較における反事実的推論を通して、この意思決定プロセスを捉える新しいアプローチを提案します。本アプローチはモデルフリーであり、状態空間の反復処理を必要としません。このアプローチは、合成データセットと実世界のデータセットにおいて、多面的なヒューリスティックを正確に学習することを実証します。また、見習い学習を通じて人間のスケジューリングデモンストレーションから学習したポリシーが、スケジュール最適化の効率を大幅に向上させることも実証します。本稿では、この人間と機械の協調的最適化手法を、兵器とターゲットの割り当て問題の変種に適用します。この手法は、最先端の最適化アルゴリズムよりも最大9.5倍高速に最適解を生成できることを実証します。

Efficient Computation of Semivalues for Game-Theoretic Network Centrality

Efficient Computation of Semivalues for Game-Theoretic Network Centrality / ゲーム理論的ネットワーク中心性のための半値の効率的な計算

Some game-theoretic solution concepts such as the Shapley value and the Banzhaf index have recently gained popularity as measures of node centrality in networks. While this direction of research is promising, the computational problems that surround it are challenging and have largely been left open. To date there are only a few positive results in the literature, which show that some game-theoretic extensions of degree-, closeness- and betweenness-centrality measures are computable in polynomial time, i.e., without the need to enumerate the exponential number of all possible coalitions. In this article, we show that these results can be extended to a much larger class of centrality measures that are based on a family of solution concepts known as semivalues. The family of semivalues includes, among others, the Shapley value and the Banzhaf index. To this end, we present a generic framework for defining game-theoretic network centralities and prove that all centrality measures that can be expressed in this framework are computable in polynomial time. Using our framework, we present a number of new and polynomial-time computable game-theoretic centrality measures.



シャプレー値やバンザフ指数といったゲーム理論的解概念は、ネットワークにおけるノード中心性の尺度として近年注目を集めています。この研究分野は有望ですが、それに伴う計算上の問題は困難であり、未解決のままとなっています。これまでの文献には、次数中心性、近接中心性、媒介中心性といったゲーム理論的拡張が多項式時間で計算可能であることを示す肯定的な結果がわずかしかありません。つまり、すべての可能な提携の指数数を列挙する必要がないということです。本稿では、これらの結果が、半値として知られる解概念の族に基づく、はるかに広範な中心性尺度に拡張できることを示します。半値族には、シャプレー値やバンザフ指数などが含まれます。この目的のために、我々はゲーム理論的ネットワーク中心性を定義するための一般的な枠組みを提示し、この枠組みで表現できるすべての中心性尺度が多項式時間で計算可能であることを証明します。この枠組みを用いて、我々はいくつかの新しい、かつ多項式時間で計算可能なゲーム理論的中心性尺度を提示します。

Query Answering with Transitive and Linear-Ordered Data

Query Answering with Transitive and Linear-Ordered Data / 推移的および線形順序データを用いたクエリ応答

We consider entailment problems involving powerful constraint languages such as frontier-guarded existential rules in which we impose additional semantic restrictions on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural variants of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in these conditions lead to undecidability.



我々は、区別された関係の集合に追加的な意味的制約を課すフロンティアガード存在規則などの強力な制約言語を伴う含意問題を考察します。関係を推移的と制限すること、関係を別の関係の推移閉包と制限すること、関係を線形順序と制限することを検討します。我々は、それぞれの場合において推論が決定可能となるようなガード性の自然な変種をいくつか示し、対応する決定問題の複雑さを分離します。最後に、これらの条件のわずかな変化が決定不能性につながることを示す。

Revisiting the Approximation Bound for Stochastic Submodular Cover

Revisiting the Approximation Bound for Stochastic Submodular Cover / 確率的劣モジュラー被覆の近似境界の再考

Deshpande et al. presented a k(ln R + 1) approximation bound for Stochastic Submodular Cover, where k is the state set size, R is the maximum utility of a single item, and the utility function is integer-valued. This bound is similar to the ln Q/(eta+1) bound given by Golovin and Krause, whose analysis was recently found to have an error. Here Q >= R is the goal utility and eta is the minimum gap between Q and any attainable utility Q’ < Q. We revisit the proof of the k(ln R + 1) bound of Deshpande et al., fill in the details of the proof of a key lemma, and prove two bounds for real-valued utility functions: k(ln R_1 + 1) and (ln R_E + 1). Here R_1 equals the maximum ratio between the largest increase in utility attainable from a single item, and the smallest non-zero increase attainable from that same item (in the same state). The quantity R_E equals the maximum ratio between the largest expected increase in utility from a single item, and the smallest non-zero expected increase in utility from that same item. Our bounds apply only to the stochastic setting with independent states.



Deshpandeらは、確率的劣モジュラ被覆のk(ln R + 1)近似境界を提示した。ここで、kは状態集合のサイズ、Rは単一アイテムの最大効用、効用関数は整数値です。この境界は、GolovinとKrauseによって示されたln Q/(eta+1)境界に類似しているが、彼らの分析には最近誤りがあることが判明した。ここで、Q >= Rは目標効用であり、etaはQと達成可能な効用Q’ < Qとの間の最小ギャップです。Deshpandeらによるk(ln R + 1)境界の証明を再検討し、重要な補題の証明の詳細を補足し、実数値効用関数の2つの境界k(ln R_1 + 1)と(ln R_E + 1)を証明します。ここで、R_1は、単一のアイテムから達成可能な最大の効用増加と、同じアイテム(同じ状態)から達成可能な最小の非ゼロ増加との間の最大比率に等しくなります。量R_Eは、単一のアイテムからの期待される最大の効用増加と、同じアイテムからの期待される最小の非ゼロ効用増加との間の最大比率に等しくなります。私たちの境界は、独立した状態を持つ確率的設定にのみ適用されます。

Watching and Acting Together: Concurrent Plan Recognition and Adaptation for Human-Robot Teams

Watching and Acting Together: Concurrent Plan Recognition and Adaptation for Human-Robot Teams / 共に見て行動する：人間とロボットのチームのための同時計画認識と適応

There is huge demand for robots to work alongside humans in heterogeneous teams. To achieve a high degree of fluidity, robots must be able to (1) recognize their human co-worker’s intent, and (2) adapt to this intent accordingly, providing useful aid as a teammate. The literature to date has made great progress in these two areas — recognition and adaptation — but largely as separate research activities. In this work, we present a unified approach to these two problems, in which recognition and adaptation occur concurrently and holistically within the same framework. We introduce Pike, an executive for human-robot teams, that allows the robot to continuously and concurrently reason about what a human is doing as execution proceeds, as well as adapt appropriately. The result is a mixed-initiative execution where humans and robots interact fluidly to complete task goals.Key to our approach is our task model: a contingent, temporally-flexible team-plan with explicit choices for both the human and robot. This allows a single set of algorithms to find implicit constraints between sets of choices for the human and robot (as determined via causal link analysis and temporal reasoning), narrowing the possible decisions a rational human would take (hence achieving intent recognition) as well as the possible actions a robot could consistently take (hence achieving adaptation). Pike makes choices based on the preconditions of actions in the plan, temporal constraints, unanticipated disturbances, and choices made previously (by either agent).Innovations of this work include (1) a framework for concurrent intent recognition and adaptation for contingent, temporally-flexible plans, (2) the generalization of causal links for contingent, temporally-flexible plans along with related extraction algorithms, and (3) extensions to a state-of-the-art dynamic execution system to utilize these causal links for decision making.



異種のチームで人間と一緒に働くロボットに対する需要は非常に高くなっています。高度な流動性を実現するために、ロボットは(1)人間の同僚の意図を認識し、(2)それに応じてこの意図に適応し、チームメイトとして有用な援助を提供できなければなりません。これまでの文献では、認識と適応というこの2つの分野で大きな進歩が遂げられてきましたが、大部分は別々の研究活動でした。本研究では、認識と適応が同じフレームワーク内で同時かつ全体的に行われる、この2つの問題に対する統一的なアプローチを提示します。人間とロボットのチームのための実行プログラムであるPikeを紹介します。これにより、ロボットは実行の進行中に人間が何をしているかを継続的かつ同時進行的に推論し、適切に適応することができます。その結果、人間とロボットがタスクの目標を達成するために流動的に相互作用する、混合イニシアチブの実行が実現します。このアプローチの鍵となるのは、人間とロボットの両方に明示的な選択肢がある、偶発的で時間的に柔軟なチームプランであるタスク モデルです。これにより、単一のアルゴリズム セットで、人間とロボットの選択肢セット間の暗黙の制約(因果関係分析と時間的推論によって決定)を見つけることが可能になり、合理的な人間が行う可能性のある決定(したがって意図認識の実現)とロボットが一貫して実行できる可能性のあるアクション(したがって適応の実現)が絞り込まれます。Pikeは、計画内のアクションの前提条件、時間的制約、予期しない障害、および以前に行われた選択(いずれかのエージェントによる)に基づいて選択を行います。この研究の革新には、(1)条件付きで時間的に柔軟なプランの同時意図認識および適応のフレームワーク、(2)条件付きで時間的に柔軟なプランの因果関係の一般化と関連抽出アルゴリズム、および(3)これらの因果関係を意思決定に利用するための最先端の動的実行システムの拡張が含まれます。

Cooperative, Dynamics-based, and Abstraction-Guided Multi-robot Motion Planning

Cooperative, Dynamics-based, and Abstraction-Guided Multi-robot Motion Planning / 協調的、ダイナミクスベース、抽象化に基づくマルチロボット動作計画

This paper presents an effective, cooperative, and probabilistically-complete multi-robot motion planner that enables each robot to move to a desired location while avoiding collisions with obstacles and other robots. The approach takes into account not only the geometric constraints arising from collision avoidance, but also the differential constraints imposed by the motion dynamics of each robot. This makes it possible to generate collision-free and dynamically-feasible trajectories that can be executed in the physical world.The salient aspect of the approach is the coupling of sampling-based motion planning to handle the complexity arising from the obstacles and robot dynamics with multi-agent search to find solutions over a suitable discrete abstraction. The discrete abstraction is obtained by constructing roadmaps to solve a relaxed problem that accounts for the obstacles but not the dynamics. Sampling-based motion planning expands a motion tree in the composite state space of all the robots by adding collision-free and dynamically-feasible trajectories as branches. Efficiency is obtained by using multi-agent search to find non-conflicting routes over the discrete abstraction which serve as heuristics to guide the motion-tree expansion. When little or no progress is made, the routes are penalized and the multi-agent search is invoked again to find alternative routes. This synergistic coupling makes it possible to effectively plan collision-free and dynamically-feasible motions that enable each robot to reach its goal. Experiments using vehicle models with nonlinear dynamics operating in complex environments, where cooperation among robots is required, show significant speedups over related work.



本論文では、各ロボットが障害物や他のロボットとの衝突を回避しながら目的の位置に移動することを可能にする、効果的で協調的かつ確率的に完全なマルチロボット動作プランナーを提示します。このアプローチは、衝突回避から生じる幾何学的制約だけでなく、各ロボットの動作ダイナミクスによって課される差分制約も考慮します。これにより、物理世界で実行可能な、衝突のない動的実行可能な軌道を生成することが可能となります。このアプローチの顕著な特徴は、障害物とロボットのダイナミクスから生じる複雑さに対処するためのサンプリングベースの動作計画と、適切な離散的抽象化に基づく解を見つけるためのマルチエージェント探索を結合することです。この離散的抽象化は、障害物を考慮しながらもダイナミクスを考慮しない緩和問題を解くためのロードマップを構築することによって得られます。サンプリングベースの動作計画は、衝突のない動的実行可能な軌道を枝として追加することにより、すべてのロボットの複合状態空間における動作ツリーを拡張します。マルチエージェント探索を用いて離散抽象化上の衝突しない経路を見つけ出すことで効率性が向上し、これらの経路は動作ツリーの拡張を導くヒューリスティックとして機能します。ほとんどまたは全く進展が見られない場合、経路はペナルティを受け、代替経路を見つけるためにマルチエージェント探索が再度呼び出されます。この相乗的な結合により、各ロボットが目的地に到達できるように、衝突がなく動的に実行可能な動作を効果的に計画することが可能になります。ロボット間の協力が必要な複雑な環境で動作する非線形ダイナミクスを備えた車両モデルを使用した実験では、関連研究と比較して大幅な高速化が示されています。

Robust Text Classification under Confounding Shift

Robust Text Classification under Confounding Shift / 交絡シフト下におけるロバストなテキスト分類

As statistical classifiers become integrated into real-world applications, it is important to consider not only their accuracy but also their robustness to changes in the data distribution. Although identifying and controlling for confounding variables Z – correlated with both the input X of a classifier and its output Y – has been assiduously studied in empirical social science, it is often neglected in text classification. This can be understood by the fact that, if we assume that the impact of confounding variables does not change between the time we fit a model and the time we use it, then prediction accuracy should only be slightly affected. We show in this paper that this assumption often does not hold and that when the influence of a confounding variable changes from training time to prediction time (i.e. under confounding shift), the classifier accuracy can degrade rapidly. We use Pearl’s back-door adjustment as a predictive framework to develop a model robust to confounding shift under the condition that Z is observed at training time. Our approach does not make any causal conclusions but by experimenting on 6 datasets, we show that our approach is able to outperform baselines 1) in controlled cases where confounding shift is manually injected between fitting time and prediction time 2) in natural experiments where confounding shift appears either abruptly or gradually 3) in cases where there is one or multiple confounders. Finally, we discuss multiple issues we encountered during this research such as the effect of noise in the observation of Z and the importance of only controlling for confounding variables.



統計的分類器が実際のアプリケーションに統合されるにつれて、その精度だけでなく、データ分布の変化に対する堅牢性も考慮することが重要になります。分類器の入力Xと出力Yの両方に相関する交絡変数Zの特定と制御は、経験社会科学では熱心に研究されてきましたが、テキスト分類ではしばしば無視されています。これは、交絡変数の影響がモデルをフィッティングする時点とそれを使用する時点の間で変化しないと仮定すると、予測精度はわずかにしか影響を受けないはずであるという事実から理解できます。本稿では、この仮定は多くの場合成り立たないこと、および交絡変数の影響がトレーニング時点から予測時点に変化すると（つまり、交絡シフト下）、分類器の精度が急速に低下する可能性があることを示します。トレーニング時にZが観測されるという条件下で、交絡シフトに対してロバストなモデルを開発するために、予測フレームワークとしてPearlのバックドア調整を使用します。私たちのアプローチは因果的な結論は導き出しません。しかし、6つのデータセットで実験することにより、1)フィッティング時点と予測時点の間に交絡シフトが手動で挿入される制御されたケース、2)交絡シフトが突然または徐々に現れる自然実験、3) 1つまたは複数の交絡因子がある場合に、私たちのアプローチがベースラインを上回ることができることを示します。最後に、Zの観測におけるノイズの影響や、交絡変数のみを制御することの重要性など、本研究で遭遇した複数の問題について議論します。

Graphical Model Market Maker for Combinatorial Prediction Markets

Graphical Model Market Maker for Combinatorial Prediction Markets / 組み合わせ予測市場のためのグラフィカルモデルマーケットメーカー

We describe algorithms for use by prediction markets in forming a crowd consensus joint probability distribution over thousands of related events. Equivalently, we describe market mechanisms to efficiently crowdsource both structure and parameters of a Bayesian network. Prediction markets are among the most accurate methods to combine forecasts; forecasters form a consensus probability distribution by trading contingent securities. A combinatorial prediction market forms a consensus joint distribution over many related events by allowing conditional trades or trades on Boolean combinations of events. Explicitly representing the joint distribution is infeasible, but standard inference algorithms for graphical probability models render it tractable for large numbers of base events. We show how to adapt these algorithms to compute expected assets conditional on a prospective trade, and to find the conditional state where a trader has minimum assets, allowing full asset reuse. We compare the performance of three algorithms: the straightforward algorithm from the DAGGRE (Decomposition-Based Aggregation) prediction market for geopolitical events, the simple block-merge model from the SciCast market for science and technology forecasting, and a more sophisticated algorithm we developed for future markets.



予測市場が数千の関連イベントにわたって群衆合意の同時確率分布を形成するために使用するアルゴリズムについて説明します。同様に、ベイジアンネットワークの構造とパラメータの両方を効率的にクラウドソーシングするための市場メカニズムについても説明します。予測市場は予測を組み合わせる最も正確な方法の一つであり、予測者は条件付き証券を取引することで合意確率分布を形成します。組み合わせ予測市場は、条件付き取引またはイベントのブール組み合わせに基づく取引を許可することで、多くの関連イベントにわたって合意同時分布を形成します。同時分布を明示的に表現することは不可能だが、グラフィカル確率モデルの標準的な推論アルゴリズムを用いることで、多数の基本イベントに対しても扱いやすくなります。これらのアルゴリズムを適応させて、将来の取引を条件として期待資産を計算する方法、そしてトレーダーが最小資産を持つ条件付き状態を見つけ、資産を完全に再利用できるようにする方法を示す。地政学的イベントの予測市場であるDAGGRE (Decomposition-Based Aggregation)からの単純なアルゴリズム、科学技術予測市場であるSciCastからの単純なブロックマージ モデル、そして将来の市場向けに私たちが開発したより洗練されたアルゴリズムの3つのアルゴリズムのパフォーマンスを比較します。

Proximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity

Proximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity / 近似勾配時間差学習：多項式サンプル複雑度を持つ安定強化学習

In this paper, we introduce proximal gradient temporal difference learning, which provides a principled way of designing and analyzing true stochastic gradient temporal difference learning algorithms. We show how gradient TD (GTD) reinforcement learning methods can be formally derived, not by starting from their original objective functions, as previously attempted, but rather from a primal-dual saddle-point objective function. We also conduct a saddle-point error analysis to obtain finite-sample bounds on their performance. Previous analyses of this class of algorithms use stochastic approximation techniques to prove asymptotic convergence, and do not provide any finite-sample analysis. We also propose an accelerated algorithm, called GTD2-MP, that uses proximal “mirror maps” to yield an improved convergence rate. The results of our theoretical analysis imply that the GTD family of algorithms are comparable and may indeed be preferred over existing least squares TD methods for off-policy learning, due to their linear complexity. We provide experimental results showing the improved performance of our accelerated gradient TD methods.



本稿では、真の確率的勾配時間差分学習アルゴリズムを設計および解析するための原理的な方法を提供する、近似勾配時間差分学習（Proximal Gradient Temporal Difference Learning）を紹介します。本稿では、勾配TD（GTD）強化学習法が、これまで試みられてきたように元の目的関数からではなく、主双対鞍点目的関数から形式的に導出される方法を示す。また、鞍点誤差解析を行い、その性能の有限サンプル境界を得る。このクラスのアルゴリズムに関するこれまでの解析では、漸近収束を証明するために確率的近似手法が用いられており、有限サンプル解析は提供されていない。本稿ではさらに、近似「ミラーマップ」を用いて収束速度を向上させる高速アルゴリズム、GTD2-MPを提案します。本理論解析の結果は、GTDアルゴリズム群が既存の最小二乗TD法と同等であり、線形複雑度の観点から、オフポリシー学習において実際に優位性を持つ可能性があることを示唆しています。加速勾配TD法の性能向上を示す実験結果を示す。

Approximation and Parameterized Complexity of Minimax Approval Voting

Approximation and Parameterized Complexity of Minimax Approval Voting / 近似ミニマックス承認投票の計算量とパラメータ化計算量

We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance d from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time O*(2o(d log d)), unless the Exponential Time Hypothesis (ETH) fails. This means that the O*(d2d) algorithm of Misra, Nabeel and Singh is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O*((3/ε)2d), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for Minimax Approval Voting, which runs in time nO(1/ε2⋅log(1/ε))⋅poly(m), where n is a number of voters and m is a number of alternatives. It almost matches the running time of the fastest known PTAS for Closest String due to Ma and Sun.



ミニマックス承認投票の計算量に関する3つの結果を示す。まず、解から投票までのハミング距離dでパラメータ化されたミニマックス承認投票を考察します。指数時間仮説（ETH）が成立しない限り、ミニマックス承認投票ではO*(2o(d log d))で実行されるアルゴリズムは存在しないことを示す。これは、Misra、Nabeel、SinghによるO*(d2d)アルゴリズムが本質的に最適であることを意味します。これに基づき、ETHを仮定した場合、本質的にタイトな、O*((3/ε)2d)で実行されるパラメータ化された近似スキームを示す。最後に、ミニマックス承認投票のための新しい多項式時間ランダム近似スキームを得る。これはnO(1/ε2⋅log(1/ε))⋅poly(m)の時間で実行されます。ここで、nは投票者数、mは選択肢の数です。これは、MaとSunによるClosest Stringの既知の最速PTASの実行時間とほぼ一致します。

A Core Method for the Weak Completion Semantics with Skeptical Abduction

A Core Method for the Weak Completion Semantics with Skeptical Abduction / 懐疑的アブダクションを用いた弱完了意味論のコア手法

The Weak Completion Semantics is a novel cognitive theory which has been successfully applied to the suppression task, the selection task, syllogistic reasoning, the belief bias effect, spatial reasoning as well as reasoning with conditionals. It is based on logic programming with skeptical abduction. Each program admits a least model under the three-valued Lukasiewicz logic, which can be computed as the least fixed point of an appropriate semantic operator. The semantic operator can be represented by a three-layer feed-forward network using the core method. Its least fixed point is the unique stable state of a recursive network which is obtained from the three-layer feed-forward core by mapping the activation of the output layer back to the input layer. The recursive network is embedded into a novel network to compute skeptical abduction. This paper presents a fully connectionist realization of the Weak Completion Semantics.



弱完了意味論は、抑制課題、選択課題、三段論法推論、信念バイアス効果、空間推論、条件付き推論にうまく適用されてきた新しい認知理論です。これは懐疑的帰納法を用いた論理プログラミングに基づいています。各プログラムは、3値Lukasiewicz論理の下で最小モデルを許容し、これは適切な意味演算子の最小不動点として計算できます。意味演算子は、コア法を用いた3層フィードフォワードネットワークで表すことができます。最小不動点は、出力層の活性化を入力層にマッピングすることで得られる、3層フィードフォワードコアから得られる再帰ネットワークの唯一の安定状態です。この再帰ネットワークは、懐疑的アブダクションを計算するための新しいネットワークに埋め込まれています。本論文では、弱完了意味論の完全なコネクショニスト実現を提示します。

A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences

A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences / 条件付き辞書式選好に基づくコア選択交換の計算量アプローチ

Core-selection is a crucial property of rules in the literature of resource allocation. It is also desirable, from the perspective of mechanism design, to address the incentive of agents to cheat by misreporting their preferences. This paper investigates the exchange problem where (i) each agent is initially endowed with (possibly multiple) indivisible goods, (ii) agents’ preferences are assumed to be conditionally lexicographic, and (iii) side payments are prohibited. We propose an exchange rule called augmented top-trading-cycles (ATTC), based on the original TTC procedure. We first show that ATTC is core-selecting and runs in polynomial time with respect to the number of goods. We then show that finding a beneficial misreport under ATTC is NP-hard. We finally clarify relationship of misreporting with splitting and hiding, two different types of manipulations, under ATTC.



資源配分の文献において、コア選択はルールの重要な特性です。メカニズム設計の観点からは、エージェントが選好を偽って不正行為を行うインセンティブに対処することも望ましい。本稿では、(i)各エージェントが（場合によっては複数の）分割不可能な財を初期に付与され、(ii)エージェントの選好は条件付き辞書式であると仮定され、(iii)サイドペイメントが禁止されている交換問題を考察します。我々は、オリジナルのTTC手順に基づく、拡張トップトレーディングサイクル（ATTC）と呼ばれる交換ルールを提案します。まず、ATTCがコア選択的であり、財の数に関して多項式時間で実行されることを示す。次に、ATTCの下で有益な誤報告を見つけることがNP困難であることを示す。最後に、ATTCの下での誤報告と、分割と隠蔽という2つの異なる種類の操作との関係を明らかにします。

LTL on Finite and Process Traces: Complexity Results and a Practical Reasoner

LTL on Finite and Process Traces: Complexity Results and a Practical Reasoner / 有限およびプロセストレース上のLTL：計算量結果と実用的な推論システム

Linear temporal logic (LTL) is a modal logic where formulas are built over temporal operators relating events happening in different time instants. According to the standard semantics, LTL formulas are interpreted on traces spanning over an infinite timeline. However, applications related to the specification and verification of business processes have recently pointed out the need for defining and reasoning about a variant of LTL, which we name LTLp, whose semantics is defined over process traces, that is, over finite traces such that, at each time instant, precisely one propositional variable (standing for the execution of some given activity) evaluates true.The paper investigates the theoretical underpinnings of LTLp and of a related logic formalism, named LTLf, which had already attracted attention in the literature and where formulas have the same syntax as in LTLp and are evaluated over finite traces, but without any constraint on the number of variables simultaneously evaluating true. The two formalisms are comparatively analyzed, by pointing out similarities and differences. In addition, a thorough complexity analysis has been conducted for reasoning problems about LTLp and LTLf, by considering arbitrary formulas as well as classes of formulas defined in terms of restrictions on the temporal operators that are allowed. Finally, based on the theoretical findings of the paper, a practical reasoner specifically tailored for LTLp and LTLf has been developed by leveraging state-of-the-art SAT solvers. The behavior of the reasoner has been experimentally compared with other systems available in the literature.



線形時相論理（LTL）は、異なる時点に発生するイベントを関連付ける時相演算子に基づいて論理式が構築される様相論理です。標準的な意味論によれば、LTLの論理式は無限の時間軸にまたがるトレースに基づいて解釈されます。しかしながら、ビジネスプロセスの仕様策定と検証に関連するアプリケーションにおいて、近年、LTLの変種であるLTLpの定義と推論の必要性が指摘されています。LTLpの意味論はプロセストレース、つまり有限のトレースに基づいて定義され、各時点において、特定のアクティビティの実行を表す命題変数が1つだけ真と評価されます。本論文では、LTLpと、文献で既に注目を集めているLTLfと呼ばれる関連論理形式論の理論的根拠を検証します。LTLfの論理式はLTLpと同じ構文を持ち、有限のトレースに基づいて評価されますが、同時に真と評価される変数の数には制約がありません。これら2つの形式論は、類似点と相違点を指摘することで比較分析されます。さらに、LTLpおよびLTLfに関する推論問題に対して、任意の式だけでなく、許容される時間演算子の制約に基づいて定義された式のクラスも考慮することにより、徹底的な計算量分析が行われました。最後に、本論文の理論的発見に基づき、最先端のSATソルバーを活用することで、LTLpおよびLTLfに特化した実用的な推論システムが開発されました。推論システムの動作は、文献で利用可能な他のシステムと実験的に比較されました。

Consequence-Based Reasoning for Description Logics with Disjunctions and Number Restrictions

Consequence-Based Reasoning for Description Logics with Disjunctions and Number Restrictions / 選言と数値制限を伴う記述論理のための結果ベース推論

Classification of description logic (DL) ontologies is a key computational problem in modern data management applications, so considerable effort has been devoted to the development and optimisation of practical reasoning calculi. Consequence-based calculi combine ideas from hypertableau and resolution in a way that has proved very effective in practice. However, existing consequence-based calculi can handle either Horn DLs (which do not support disjunction) or DLs without number restrictions. In this paper, we overcome this important limitation and present the first consequence-based calculus for deciding concept subsumption in the DL ALCHIQ+. Our calculus runs in exponential time assuming unary coding of numbers, and on ELH ontologies it runs in polynomial time. The extension to disjunctions and number restrictions is technically involved: we capture the relevant consequences using first-order clauses, and our inference rules adapt paramodulation techniques from first-order theorem proving. By using a well-known preprocessing step, the calculus can also decide concept subsumptions in SRIQ—a rich DL that covers all features of OWL 2 DL apart from nominals and datatypes. We have implemented our calculus in a new reasoner called Sequoia. We present the architecture of our reasoner and discuss several novel and important implementation techniques such as clause indexing and redundancy elimination. Finally, we present the results of an extensive performance evaluation, which revealed Sequoia to be competitive with existing reasoners. Thus, the calculus and the techniques we present in this paper provide an important addition to the repertoire of practical implementation techniques for description logic reasoning.



記述論理（DL）オントロジーの分類は、現代のデータ管理アプリケーションにおける重要な計算問題であるため、実用的な推論計算の開発と最適化に多大な努力が費やされてきました。結果ベース計算は、ハイパータブローとレゾリューションのアイデアを組み合わせ、実際に非常に効果的であることが証明されています。ただし、既存の結果ベース計算は、Horn DL（選言をサポートしない）または数値制限のないDLのいずれかを処理できます。本稿では、この重要な制限を克服し、DL ALCHIQ+における概念包含を決定するための、初めての結果ベース計算を提示します。この計算は、数の単項符号化を仮定して指数時間で実行され、ELHオントロジーでは多項式時間で実行されます。選言と数的制約への拡張は技術的に複雑です。我々は関連する結果を一階述語節を用いて捕捉し、推論規則は一階述語定理証明のパラモジュレーション技法を採用します。周知の前処理ステップを用いることで、この計算はSRIQ（名詞とデータ型を除くOWL 2 DLのすべての機能をカバーするリッチDL）における概念包含を決定することもできます。我々はこの計算をSequoiaという新しい推論エンジンに実装した。この推論エンジンのアーキテクチャを紹介し、節インデックス作成や冗長性除去といったいくつかの新しく重要な実装技法について説明します。最後に、Sequoiaが既存の推論エンジンと競合できることが明らかになった広範なパフォーマンス評価の結果を示す。したがって、本論文で紹介する計算と手法は、記述論理推論の実用的な実装手法のレパートリーに重要な追加要素を提供します。

Data-driven Conceptual Spaces: Creating Semantic Representations For Linguistic Descriptions Of Numerical Data

Data-driven Conceptual Spaces: Creating Semantic Representations For Linguistic Descriptions Of Numerical Data / データ駆動型概念空間：数値データの言語記述のための意味表現の作成

There is an increasing need to derive semantics from real-world observations to facilitate natural information sharing between machine and human. Conceptual spaces theory is a possible approach and has been proposed as mid-level representation between symbolic and sub-symbolic representations, whereby concepts are represented in a geometrical space that is characterised by a number of quality dimensions. Currently, much of the work has demonstrated how conceptual spaces are created in a knowledge-driven manner, relying on prior knowledge to form concepts and identify quality dimensions. This paper presents a method to create semantic representations using data-driven conceptual spaces which are then used to derive linguistic descriptions of numerical data. Our contribution is a principled approach to automatically construct a conceptual space from a set of known observations wherein the quality dimensions and domains are not known a priori. This novelty of the approach is the ability to select and group semantic features to discriminate between concepts in a data-driven manner while preserving the semantic interpretation that is needed to infer linguistic descriptions for interaction with humans. Two data sets representing leaf images and time series signals are used to evaluate the method. An empirical evaluation for each case study assesses how well linguistic descriptions generated from the conceptual spaces identify unknown observations. Furthermore, comparisons are made with descriptions derived on alternative approaches for generating semantic models.



機械と人間の間で自然な情報共有を促進するため、現実世界の観察から意味を導出する必要性が高まっています。概念空間理論は、記号表現とサブ記号表現の中間レベルの表現として提案されており、概念は複数の品質次元によって特徴付けられる幾何学的空間で表現されます。現在、多くの研究は、概念空間が知識駆動型でどのように構築されるかを示しており、概念形成と品質次元の特定には事前知識が利用されています。本論文では、データ駆動型の概念空間を用いて意味表現を作成し、それを用いて数値データの言語的記述を導出する手法を提示します。本論文の貢献は、品質次元とドメインが事前に不明な既知の観察集合から概念空間を自動的に構築する、原理に基づいたアプローチです。このアプローチの新規性は、人間とのインタラクションのための言語的記述を推論するために必要な意味的解釈を維持しながら、データ駆動型で概念を区別するための意味的特徴を選択およびグループ化できる点にあります。この手法を評価するために、葉の画像と時系列信号を表す2つのデータセットが使用されます。各ケーススタディの経験的評価では、概念空間から生成された言語的記述が未知の観測をどの程度正確に識別するかが評価されます。さらに、意味モデルを生成するための代替アプローチから得られた記述と比較されます。

From Word To Sense Embeddings: A Survey on Vector Representations of Meaning

From Word To Sense Embeddings: A Survey on Vector Representations of Meaning / 単語から意味埋め込みへ：意味のベクトル表現に関するサーベイ

Over the past years, distributed semantic representations have proved to be effective and flexible keepers of prior knowledge to be integrated into downstream applications. This survey focuses on the representation of meaning. We start from the theoretical background behind word vector space models and highlight one of their major limitations: the meaning conflation deficiency, which arises from representing a word with all its possible meanings as a single vector. Then, we explain how this deficiency can be addressed through a transition from the word level to the more fine-grained level of word senses (in its broader acceptation) as a method for modelling unambiguous lexical meaning. We present a comprehensive overview of the wide range of techniques in the two main branches of sense representation, i.e., unsupervised and knowledge-based. Finally, this survey covers the main evaluation procedures and applications for this type of representation, and provides an analysis of four of its important aspects: interpretability, sense granularity, adaptability to different domains and compositionality.



過去数年間にわたり、分散意味表現は、下流のアプリケーションに統合される事前知識を効果的かつ柔軟に保持することが証明されています。この調査では、意味の表現に焦点を当てます。まず、単語ベクトル空間モデルの理論的背景から始め、その主要な限界の1つである意味の融合欠陥に焦点を当てます。これは、単語をそのすべての可能な意味とともに単一のベクトルとして表現することから生じます。次に、明確な語彙意味をモデル化する方法論として、単語レベルからよりきめの細かいレベルの語義（広義での）への移行を通じて、この欠陥にどのように対処できるかを説明します。本稿では、意味表現の2つの主要な分野、すなわち教師なし表現と知識ベース表現における幅広い技術について、包括的な概要を提示します。最後に、このタイプの表現における主要な評価手順と応用を網羅し、解釈可能性、意味の粒度、異なる領域への適応性、そして構成性という4つの重要な側面を分析します。

State-Space Abstractions for Probabilistic Inference: A Systematic Review

State-Space Abstractions for Probabilistic Inference: A Systematic Review / 確率推論のための状態空間抽象化：系統的レビュー

Tasks such as social network analysis, human behavior recognition, or modeling biochemical reactions, can be solved elegantly by using the probabilistic inference framework. However, standard probabilistic inference algorithms work at a propositional level, and thus cannot capture the symmetries and redundancies that are present in these tasks.Algorithms that exploit those symmetries have been devised in different research fields, for example by the lifted inference-, multiple object tracking-, and modeling and simulation-communities. The common idea, that we call state space abstraction, is to perform inference over compact representations of sets of symmetric states. Although they are concerned with a similar topic, the relationship between these approaches has not been investigated systematically.This survey provides the following contributions. We perform a systematic literature review to outline the state of the art in probabilistic inference methods exploiting symmetries. From an initial set of more than 4,000 papers, we identify 116 relevant papers. Furthermore, we provide new high-level categories that classify the approaches, based on common properties of the approaches. The research areas underlying each of the categories are introduced concisely. Researchers from different fields that are confronted with a state space explosion problem in a probabilistic system can use this classification to identify possible solutions. Finally, based on this conceptualization, we identify potentials for future research, as some relevant application domains are not addressed by current approaches.



ソーシャルネットワーク分析、人間の行動認識、生化学反応のモデリングといったタスクは、確率推論のフレームワークを用いることで簡潔に解決できます。しかしながら、標準的な確率推論アルゴリズムは命題レベルで動作するため、これらのタスクに見られる対称性や冗長性を捉えることができません。こうした対称性を活用するアルゴリズムは、リフト推論、複数物体追跡、モデリングおよびシミュレーションといった様々な研究分野で考案されてきました。状態空間抽象化と呼ぶ共通の考え方は、対称的な状態集合のコンパクトな表現上で推論を行うというものです。これらは同様のトピックを扱っているにもかかわらず、これらのアプローチ間の関係性は体系的に調査されていません。本調査は、以下の貢献を提供します。対称性を活用した確率推論手法の最新状況を概説するために、体系的な文献レビューを実施しました。4,000件を超える論文群から、116件の関連論文を特定しました。さらに、我々は、各アプローチの共通特性に基づいて、アプローチを分類する新しい高レベルカテゴリを提供します。各カテゴリの基礎となる研究分野を簡潔に紹介します。確率システムにおける状態空間爆発問題に直面しているさまざまな分野の研究者は、この分類を用いて可能な解決策を特定することができます。最後に、この概念化に基づいて、現在のアプローチでは対応されていない関連応用領域があるため、将来の研究の可能性を特定します。

Grounding Language for Transfer in Deep Reinforcement Learning

Grounding Language for Transfer in Deep Reinforcement Learning / 深層強化学習における転移のためのグラウンディング言語

In this paper, we explore the utilization of natural language to drive transfer for reinforcement learning (RL). Despite the wide-spread application of deep RL techniques, learning generalized policy representations that work across domains remains a challenging problem. We demonstrate that textual descriptions of environments provide a compact intermediate channel to facilitate effective policy transfer. Specifically, by learning to ground the meaning of text to the dynamics of the environment such as transitions and rewards, an autonomous agent can effectively bootstrap policy learning on a new domain given its description. We employ a model-based RL approach consisting of a differentiable planning module, a model-free component and a factorized state representation to effectively use entity descriptions. Our model outperforms prior work on both transfer and multi-task scenarios in a variety of different environments. For instance, we achieve up to 14% and 11.5% absolute improvement over previously existing models in terms of average and initial rewards, respectively.



本稿では、強化学習（RL）における転移を促進するための自然言語の利用について検討します。深層RL技術は広く応用されているものの、領域を超えて機能する一般化されたポリシー表現の学習は依然として困難な問題です。我々は、環境のテキスト記述が、効果的なポリシー転移を促進するためのコンパクトな中間チャネルを提供することを示す。具体的には、テキストの意味を遷移や報酬などの環境のダイナミクスに根ざすことを学習することにより、自律エージェントは、その記述が与えられた新しいドメインでポリシー学習を効果的にブートストラップすることができます。微分可能な計画モジュール、モデルフリーコンポーネント、および因数分解された状態表現からなるモデルベース強化学習（RL）アプローチを採用し、エンティティ記述を効果的に利用します。本モデルは、様々な環境における転移シナリオとマルチタスクシナリオの両方において、先行研究を上回る性能を発揮します。例えば、平均報酬と初期報酬に関して、それぞれ既存モデルと比較して最大14%と11.5%の絶対値改善を達成しました。

Belief Integration and Source Reliability Assessment

Belief Integration and Source Reliability Assessment / 信念統合と情報源信頼性評価

Merging beliefs requires the plausibility of the sources of the information to be merged. They are typically assumed equally reliable when nothing suggests otherwise. A recent line of research has spun from the idea of deriving this information from the revision process itself. In particular, the history of previous revisions and previous merging examples provide information for performing subsequent merging operations.Yet, no examples or previous revisions may be available. In spite of the apparent lack of information, something can still be inferred by a try-and-check approach: a relative reliability ordering is assumed, the sources are integrated according to it and the result is compared with the original information. The final check may contradict the original ordering, like when the result of merging implies the negation of a formula coming from a source initially assumed reliable, or it implies a formula coming from a source assumed unreliable. In such cases, the reliability ordering assumed in the first place can be excluded from consideration.Such a scenario is proved real under the classifications of source reliability and definitions of belief integration considered in this article: sources divided in two, three or multiple reliability classes; integration is mostly by maximal consistent subsets but also weighted distance is considered. Other results mainly concern the integration by maximal consistent subsets and partitions of two and three reliability classes.



信念の統合には、統合する情報源の妥当性が必要です。通常、他に何も示唆がない場合、それらは同等に信頼できると仮定されます。最近の研究は、この情報を改訂プロセス自体から導き出すというアイデアから派生しています。特に、以前の改訂履歴と以前のマージ例は、後続のマージ操作を実行するための情報を提供します。しかし、過去の例や改訂が利用できない場合もあります。一見情報が不足しているように見えても、試行錯誤的なアプローチによって何かを推測することができます。相対的な信頼性の順序を仮定し、それに従って情報源を統合し、結果を元の情報と比較します。最終チェックは、マージの結果が当初信頼できると想定されていた情報源からの式の否定を意味する場合や、信頼できないと想定されていた情報源からの式を意味する場合など、元の順序付けと矛盾する場合があります。このような場合、最初に想定された信頼性の順序付けは考慮から除外できます。このようなシナリオは、本稿で検討されている情報源の信頼性の分類と信念統合の定義に基づいて実証されています。情報源は2つ、3つ、または複数の信頼性クラスに分割され、統合は主に最大一貫性サブセットによって行われますが、重み付け距離も考慮されます。その他の結果は、主に最大一貫性サブセットによる統合と、2つおよび3つの信頼性クラスの分割に関するものです。

AND/OR Search for Marginal MAP

AND/OR Search for Marginal MAP / 周辺MAPのためのAND/OR探索

Mixed inference such as the marginal MAP query (some variables marginalized by summation and others by maximization) is key to many prediction and decision models. It is known to be extremely hard; the problem is NPPP-complete while the decision problem for MAP is only NP-complete and the summation problem is #P-complete. Consequently, approximation anytime schemes are essential. In this paper, we show that the framework of heuristic AND/OR search, which exploits conditional independence in the graphical model, coupled with variational-based mini-bucket heuristics can be extended to this task and yield powerful state-of-the-art schemes. Specifically, we explore the complementary properties of best-first search for reducing the number of conditional sums and providing time-improving upper bounds, with depth-first search for rapidly generating and improving solutions and lower bounds. We show empirically that a class of solvers that interleaves depth-first with best-first schemes emerges as the most competitive anytime scheme.



周辺MAPクエリ（一部の変数は加法によって周辺化され、他の変数は最大化によって周辺化される）のような混合推論は、多くの予測モデルや意思決定モデルの鍵となります。これは極めて困難であることが知られています。問題自体はNPPP完全であるのに対し、MAPの意思決定問題はNP完全のみで、加法問題は#P完全です。したがって、いつでも近似可能なスキームが不可欠です。本稿では、グラフィカルモデルにおける条件付き独立性を利用するヒューリスティックAND/OR探索のフレームワークと、変分ベースのミニバケットヒューリスティックを組み合わせることで、このタスクに拡張でき、強力な最先端のスキームを生成できることを示す。具体的には、条件付き和の数を削減し、時間を改善する上限値を提供するベストファースト探索と、解と下限値を迅速に生成・改善する深さ優先探索の相補的な特性を探求します。深さ優先スキームとベストファーストスキームを交互に組み合わせたソルバーのクラスが、最も競争力のあるいつでもスキームとなることを経験的に示す。

Transition-Based Neural Word Segmentation Using Word-Level Features

Transition-Based Neural Word Segmentation Using Word-Level Features / 単語レベル特徴を用いた遷移ベースのニューラル単語セグメンテーション

Character-based and word-based methods are two different solutions for Chinese word segmentation, the former exploiting sequence labeling models over characters and the latter using word-level features. Neural models have been exploited for character-based Chinese word segmentation, giving high accuracies by making use of external character embeddings, yet requiring less feature engineering. In this paper, we study a neural model for word-based Chinese word segmentation, by replacing the manually-designed discrete features with neural features in a transition-based word segmentation framework. Experimental results demonstrate that word features lead to comparable performance to the best systems in the literature, and a further combination of discrete and neural features obtains top accuracies on several benchmarks.



文字ベースと単語ベースの手法は、中国語単語分割における2つの異なるソリューションです。前者は文字のシーケンスラベリングモデルを利用し、後者は単語レベルの特徴を利用します。ニューラルモデルは文字ベースの中国語単語分割に活用されており、外部文字埋め込みを利用することで高い精度を実現しながらも、特徴エンジニアリングの必要性が少なくなっています。本稿では、遷移ベースの単語分割フレームワークにおいて、手動で設計された離散的特徴をニューラル特徴に置き換えることで、単語ベースの中国語単語分割のためのニューラルモデルを研究します。実験結果から、単語特徴は文献に記載されている最高のシステムに匹敵する性能をもたらし、離散的特徴とニューラル特徴をさらに組み合わせることで、いくつかのベンチマークで最高の精度が得られることが実証されています。

Optimal Torpedo Scheduling

Optimal Torpedo Scheduling / 最適トルピードスケジューリング

We consider the torpedo scheduling problem in steel production, which is concerned with the transport of hot metal from a blast furnace to an oxygen converter. A schedule must satisfy, amongst other considerations, resource capacity constraints along the path and the locations traversed as well as the sulfur level of the hot metal. The goal is first to minimize the number of torpedo cars used during the planning horizon and second to minimize the time spent desulfurizing the hot metal. We propose an exact solution method based on Logic based Benders Decomposition using Mixed-Integer and Constraint Programming, which optimally solves and proves, for the first time, the optimality of all instances from the ACP Challenge 2016 within 10 minutes. In addition, we adapted our method to handle large-scale instances and instances with a more general rail network. This adaptation optimally solved all challenge instances within one minute and was able to solve instances of up to 100,000 hot metal pickups.



本稿では、鉄鋼生産におけるトーピードスケジューリング問題、つまり高炉から酸素転炉への溶銑の輸送を対象とする問題を考察します。スケジュールは、経路に沿った資源容量制約、通過地点、そして溶銑の硫黄濃度など、様々な考慮事項を満たす必要があります。目標は、第一に計画期間中に使用されるトーピードカーの数を最小限に抑えること、第二に溶銑の脱硫処理にかかる時間を最小化することです。本研究では、混合整数および制約プログラミングを用いた論理ベースのベンダー分解に基づく厳密解法を提案します。この手法は、ACPチャレンジ2016のすべてのインスタンスを10分以内に最適解として証明し、初めて最適性を証明することに成功しました。さらに、この手法を大規模なインスタンスやより一般的な鉄道網を持つインスタンスにも対応できるように改良しました。この改良により、すべてのチャレンジインスタンスを1分以内に最適解として、最大10万台の溶銑ピックアップを含むインスタンスを解くことができました。

Bounds on the Cost of Stabilizing a Cooperative Game

Bounds on the Cost of Stabilizing a Cooperative Game / 協力ゲームの安定化コストの上限

A key issue in cooperative game theory is coalitional stability, usually captured by the notion of the core—the set of outcomes that are resistant to group deviations. However, some coalitional games have empty cores, and any outcome in such a game is unstable. We investigate the possibility of stabilizing a coalitional game by using subsidies. We consider scenarios where an external party that is interested in having the players work together offers a supplemental payment to the grand coalition, or, more generally, a particular coalition structure. This payment is conditional on players not deviating from this coalition structure, and may be divided among the players in any way they wish. We define the cost of stability as the minimum external payment that stabilizes the game. We provide tight bounds on the cost of stability, both for games where the coalitional values are nonnegative (profit-sharing games) and for games where the coalitional values are nonpositive (cost-sharing games), under natural assumptions on the characteristic function, such as superadditivity, anonymity, or both. We also investigate the relationship between the cost of stability and several variants of the least core. Finally, we study the computational complexity of problems related to the cost of stability, with a focus on weighted voting games.



協力ゲーム理論における重要な問題は、連合の安定性であり、これは通常、コア（集団の逸脱に対して抵抗力を持つ結果の集合）という概念で捉えられます。しかし、一部の連合ゲームにはコアが空であり、そのようなゲームではいかなる結果も不安定となります。我々は、補助金を用いて連合ゲームを安定化させる可能性を検証します。プレイヤーの協力に関心を持つ外部の当事者が、大連合、あるいはより一般的には特定の連合構造に対して補助金を支払うシナリオを考える。この補助金は、プレイヤーがこの連合構造から逸脱しないことを条件とし、プレイヤー間で任意の方法で分配することができます。我々は、安定性のコストを、ゲームを安定化させる最小の外部支払いと定義します。我々は、連合値が非負であるゲーム（利益分配ゲーム）と、連合値が非正であるゲーム（費用分配ゲーム）の両方について、特性関数に関する自然な仮定（超加法性、匿名性、あるいはその両方）の下で、安定性のコストに厳密な上限を与える。また、安定性のコストと最小コアのいくつかの変種との関係についても調査します。最後に、重み付き投票ゲームに焦点を当て、安定性のコストに関連する問題の計算複雑性を研究します。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 63 (2018)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧