論文の概要: An algorithmic solution to the Blotto game using multi-marginal couplings

• arxiv url: http://arxiv.org/abs/2202.07318v1
• Date: Tue, 15 Feb 2022 11:07:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-16 22:18:24.717028
• Title: An algorithmic solution to the Blotto game using multi-marginal couplings
• Title（参考訳）: マルチマルジナルカップリングを用いたBlottoゲームに対するアルゴリズム的解法
• Authors: Vianney Perchet and Philippe Rigollet and Thibaut Le Gouic
• Abstract要約: ヘテロジニアスな値を持つn個の戦場での一般2人プレイヤBlottoゲームに対する解を計算するための効率的なアルゴリズムについて述べる。 提案アルゴリズムは,予算と戦場価値とは無関係に,時間O(n2 + eps-4)のeps最適解から抽出する。 最適解が存在しない非対称値の場合、ナッシュ平衡は、同様の複雑さを持つeps-Nash平衡からアルゴリズムをサンプリングする。
• 参考スコア（独自算出の注目度）: 27.35514815248438
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We describe an efficient algorithm to compute solutions for the general two-player Blotto game on n battlefields with heterogeneous values. While explicit constructions for such solutions have been limited to specific, largely symmetric or homogeneous, setups, this algorithmic resolution covers the most general situation to date: value-asymmetric game with asymmetric budget. The proposed algorithm rests on recent theoretical advances regarding Sinkhorn iterations for matrix and tensor scaling. An important case which had been out of reach of previous attempts is that of heterogeneous but symmetric battlefield values with asymmetric budget. In this case, the Blotto game is constant-sum so optimal solutions exist, and our algorithm samples from an \eps-optimal solution in time O(n^2 + \eps^{-4}), independently of budgets and battlefield values. In the case of asymmetric values where optimal solutions need not exist but Nash equilibria do, our algorithm samples from an \eps-Nash equilibrium with similar complexity but where implicit constants depend on various parameters of the game such as battlefield values.
• Abstract（参考訳）: 本稿では,n個の戦場における2人プレイのブロットゲームに対する解の計算アルゴリズムについて述べる。 そのような解に対する明示的な構成は、特定の、ほとんど対称または均質な設定に限定されているが、このアルゴリズムによる解決は、現在最も一般的な状況、すなわち非対称予算の値非対称ゲームをカバーする。 提案アルゴリズムは、行列とテンソルスケーリングのシンクホーン反復に関する最近の理論的進歩に基づいている。 以前の試みから外れていた重要なケースは、非対称な予算を持つ不均一だが対称な戦場値である。 この場合、ブロットゲームは定数サムであり、最適解が存在し、我々のアルゴリズムは予算と戦場の値とは独立に、時間 O(n^2 + \eps^{-4}) における \eps-optimal solution からサンプリングする。 最適解が存在しないがnash平衡が存在しない非対称値の場合、同様の複雑性を持つが、暗黙定数が戦場の値のようなゲームの様々なパラメータに依存する場合、アルゴリズムは \eps-nash平衡からサンプルする。

関連論文リスト

• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Learning in Multi-Player Stochastic Games [1.0878040851638]
  有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。 ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。 我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
  論文  参考訳（メタデータ） (2022-10-25T19:02:03Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Alternating Mirror Descent for Constrained Min-Max Games [44.46086335474311]
  制約付き戦略空間を持つ2プレイヤー双線形ゼロサムゲームについて検討する。 我々は,各プレイヤーが交互に行動する交互ミラー降下アルゴリズムを,制約付き最適化のためのミラー降下アルゴリズムに従って解析する。
  論文  参考訳（メタデータ） (2022-06-08T20:48:16Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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