論文の概要: Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria

• arxiv url: http://arxiv.org/abs/2609.22757v1
• Date: Sat, 19 Sep 2026 04:38:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-22 20:29:00.543448
• Title: Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
• Title（参考訳）: アルゴリズムの衝突と情報量自由平衡の複雑度
• Abstract要約: co)相関平衡(CE)は、プレーヤーが一定の行動にコミットすることで、レコメンデーションから得られるペイオフにマッチできる場合、情報バリューフリー(IVF)である。 集中型モデルにおいても,IVFCEは難易度が高いことを示し,効率的な学習力学の存在を除外する。
• 参考スコア（独自算出の注目度）: 20.970167059062693
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing to a fixed action. Motivated by the problem of regulating algorithmic collusion, this refinement was introduced by Hartline, Wang, and Zhang [EC'26], who showed that it can be computed in polynomial time in explicitly represented normal-form game. In this paper, we examine the complexity of IVF(C)CEs in succinct games, which model more realistic strategic interactions that feature either many players or exponentially many pure strategies. We first show that computing an information-value-free CE is PPAD-complete in many-player polymatrix games or two-player Bayesian games, even when the approximation is a constant. We also prove an unconditional exponential query lower bound. Our results establish that IVFCEs are intractable, even in the centralized model, and rule out the existence of any efficient learning dynamics. This significantly strengthens the impossibility result of Hartline, Wang, and Zhang, which concerns a particular class of learning algorithms, and furnishes strong computational critiques of recent regulation on algorithmic collusion. To sidestep these hardness results, we examine the complexity of information-value-free CCE. Certain no-regret algorithms---such as regret matching or FTRL---provide a fully polynomial-time approximation scheme (FPTAS) for this problem. The complexity when the approximation is exponentially small turns out to be nuanced. On the one hand, leveraging no-regret dynamics, we establish membership in $\text{CLS} = \text{PPAD} \cap \text{PLS}$. On the other hand, we show that it is at least as hard as the P-matrix linear complementarity problem, and hence as hard as simple stochastic games. This shows that even IVFCCEs are unlikely to admit a polynomial-time algorithm barring a major breakthrough.
• Abstract（参考訳）: (粗い)相関平衡(CE)は、プレイヤーが一定の行動にコミットすることで、レコメンデーションから得られる利益と一致できる場合、情報価値のない(IVF)である。 アルゴリズムの共謀を規制する問題に触発されたこの改良は、ハートライン、ワン、張[EC'26]によって導入され、明らかに表現された正規形式ゲームにおいて多項式時間で計算可能であることを示した。 本稿では,多くのプレイヤーと指数関数的に多くの純粋な戦略を特徴とする,より現実的な戦略相互作用をモデル化する,簡潔なゲームにおけるIVF(C)CEの複雑さについて検討する。 まず、情報値のないCEの計算は、近似が一定であっても、多人数のポリマトリクスゲームや2人のプレイヤーのベイズゲームではPPAD完全であることを示す。 また、非条件の指数的クエリを低い境界で証明する。 その結果、集中型モデルにおいてもIVFCEは難易度が高く、効率的な学習力学の存在を排除できることがわかった。 これはHartline、Wang、Zhangといった特定の学習アルゴリズムのクラスに関する不合理性の結果を著しく強化し、アルゴリズムの共謀に関する最近の規制に対する強力な計算的批判を与える。 これらの難易度の結果を横取りするために,情報価値のないCCEの複雑さについて検討する。 後悔マッチング(英語版)やFTRL(英語版)のように、この問題に対する完全多項式時間近似スキーム(FPTAS)を提供するアルゴリズムは存在しない。 近似が指数関数的に小さいときの複雑さはニュアンス化される。 一方、no-regret dynamicsを活用することで、$\text{CLS} = \text{PPAD} \cap \text{PLS}$のメンバシップを確立します。 一方、P行列線型相補性問題と同程度の難易度を示し、従って単純な確率ゲームと同じくらい難しい。 このことは、IVFCCEでさえ多項式時間アルゴリズムが大きなブレークスルーを許さないことを示している。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [77.76727425995186]
  変分不等式(SVIs)の解決は、最適化の中心にある基礎的な問題である。 ほとんどの研究は、その難易度を損なう特定のサブクラスを彫刻することに重点を置いている。
  論文  参考訳（メタデータ） (2025-04-04T13:24:41Z)
• Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
  そこで我々は,Stackelbergの大規模相関平衡の計算アルゴリズムを提案する。 また,大域的相関平衡を近似計算するアルゴリズムも提案する。 ほぼ最適なEFCEのアルゴリズムは、私たちの知る限り、3つのデシラタを同時に達成した最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2024-12-22T09:12:05Z)
• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
  我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。 ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
  論文  参考訳（メタデータ） (2020-06-05T13:48:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。