論文の概要: Algorithmic Information Design in Multi-Player Games: Possibility and
Limits in Singleton Congestion
- arxiv url: http://arxiv.org/abs/2109.12445v1
- Date: Sat, 25 Sep 2021 22:02:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-30 08:05:55.081301
- Title: Algorithmic Information Design in Multi-Player Games: Possibility and
Limits in Singleton Congestion
- Title（参考訳）: マルチプレイヤーゲームにおけるアルゴリズム情報設計:シングルトン混雑の可能性と限界
- Authors: Chenghan Zhou and Thanh H. Nguyen and Haifeng Xu
- Abstract要約: 本稿では, 負の外部性を持つゲームにおいて, 共用信号と共用信号の両方のアルゴリズム情報設計を開始する。
公開信号とプライベート信号の両方に対して、資源の数が一定である場合に最適な情報設計を効率的に計算できることが示される。
- 参考スコア（独自算出の注目度）: 10.817873935576412
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Most algorithmic studies on multi-agent information design so far have
focused on the restricted situation with no inter-agent externalities; a few
exceptions investigated special game classes such as zero-sum games and
second-price auctions but have all focused only on optimal public signaling and
exhibit sweepingly negative results. This paper initiates the algorithmic
information design of both \emph{public} and \emph{private} signaling in a
fundamental class of games with negative externalities, i.e., atomic singleton
congestion games, with wide application in today's digital economy, machine
scheduling, routing, etc.
For both public and private signaling, we show that the optimal information
design can be efficiently computed when the number of resources is a constant.
To our knowledge, this is the first set of computationally efficient algorithms
for information design in succinctly representable many-player games. Our
results hinge on novel techniques such as developing ``reduced forms'' to
compactly represent players' marginal beliefs. When there are many resources,
we show computational intractability results. To overcome the challenge of
multiple equilibria, here we introduce a new notion of
equilibrium-\emph{oblivious} NP-hardness, which rules out any possibility of
computing a good signaling scheme, irrespective of the equilibrium selection
rule.
- Abstract（参考訳）: これまでのマルチエージェント情報設計に関するアルゴリズム研究のほとんどは、エージェント間外部性のない制限された状況に焦点を当ててきたが、ゼロサムゲームやセカンドプライスオークションのような特別なゲームクラスを調査した例も少なくない。
本稿では,負の外部性を持つゲーム,すなわち,今日のデジタル経済,マシンスケジューリング,ルーティングなどにおいて広く応用されたアトミックシングルトン混雑ゲームにおいて,\emph{public} と \emph{private} のシグナリングのアルゴリズム的情報設計を開始する。
公開信号とプライベート信号の両方に対して,資源数が一定であれば最適な情報設計を効率的に計算できることを示す。
我々の知る限り、これは簡潔に表現可能な多人数ゲームにおける情報設計のための計算効率の良いアルゴリズムの最初のセットである。
われわれは,プレイヤーの限界信念をコンパクトに表現する「還元形式」の開発など,新しい手法を取り入れた。
資源が多ければ計算不能な結果が得られる。
多重平衡の課題を克服するために、平衡選択規則によらず、良いシグナリングスキームを計算できる可能性を除外する平衡-\emph{oblivious} NP-hardnessという新しい概念を導入する。
関連論文リスト
- Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。
この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。
これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
論文 参考訳（メタデータ） (2023-01-22T16:54:06Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Learning in Congestion Games with Bandit Feedback [45.4542525044623]
我々は、良質な理論構造と広い実世界の応用を持つゲームのクラスである混雑ゲームについて検討する。
まず,渋滞ゲームにおける不確実性原理に直面する楽観性に基づく集中型アルゴリズムを提案する。
次に,Frank-Wolfe法とG-Optimal設計を組み合わせた分散アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-04T02:32:26Z) - Public Information Representation for Adversarial Team Games [31.29335755664997]
対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。
本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。
この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
論文 参考訳（メタデータ） (2022-01-25T15:07:12Z) - Revisiting Game Representations: The Hidden Costs of Efficiency in
Sequential Decision-making Algorithms [0.6749750044497732]
不完全な情報の下でのシーケンシャルな意思決定アルゴリズムの進歩は、大きなゲームで顕著な成功を収めている。
これらのアルゴリズムは伝統的に広義のゲーム形式を用いてゲームを形式化する。
プレイヤー固有の情報状態木に基づく特殊表現の使用が,一般的な回避策であることを示す。
論文 参考訳（メタデータ） (2021-12-20T22:34:19Z) - Model-Free Online Learning in Unknown Sequential Decision Making
Problems and Games [114.90723492840499]
大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。
私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。
エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
論文 参考訳（メタデータ） (2021-03-08T04:03:24Z) - Signaling in Bayesian Network Congestion Games: the Subtle Power of
Symmetry [66.82463322411614]
本論文は, 最適遠点透過型シグナリング方式の問題点に焦点をあて, 対称性がその解法において重要な性質であることを示す。
プレイヤーが対称でアフィンコスト関数を持つとき,最適なエクアント説得スキームが計算可能であることを示す。
論文 参考訳（メタデータ） (2020-02-12T19:38:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。