論文の概要: Multi-Leader Congestion Games with an Adversary
- arxiv url: http://arxiv.org/abs/2112.07435v1
- Date: Tue, 14 Dec 2021 14:47:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-15 16:56:19.288856
- Title: Multi-Leader Congestion Games with an Adversary
- Title（参考訳）: 対戦相手によるマルチレーダ混雑ゲーム
- Authors: Tobias Harks, Mona Henle, Max Klimm, Jannik Matuschke, Anja Schedel
- Abstract要約: 本研究では,複数のユーザ(リーダ)がリソースセットから1つのリソースを選択するマルチリーダシングルフォロワ・コングリゲーションゲームについて検討する。
純粋なナッシュ平衡は存在せず、従って近似平衡を考える。
与えられたインスタンスのすべての$alpha$-approximate equilibriaの中で、最小の$alpha$で、最適な近似平衡を効率的に計算する方法を示す。
- 参考スコア（独自算出の注目度）: 0.5914780964919123
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a multi-leader single-follower congestion game where multiple users
(leaders) choose one resource out of a set of resources and, after observing
the realized loads, an adversary (single-follower) attacks the resources with
maximum loads, causing additional costs for the leaders. For the resulting
strategic game among the leaders, we show that pure Nash equilibria may fail to
exist and therefore, we consider approximate equilibria instead. As our first
main result, we show that the existence of a $K$-approximate equilibrium can
always be guaranteed, where $K \approx 1.1974$ is the unique solution of a
cubic polynomial equation. To this end, we give a polynomial time combinatorial
algorithm which computes a $K$-approximate equilibrium. The factor $K$ is
tight, meaning that there is an instance that does not admit an
$\alpha$-approximate equilibrium for any $\alpha<K$. Thus $\alpha=K$ is the
smallest possible value of $\alpha$ such that the existence of an
$\alpha$-approximate equilibrium can be guaranteed for any instance of the
considered game. Secondly, we focus on approximate equilibria of a given fixed
instance. We show how to compute efficiently a best approximate equilibrium,
that is, with smallest possible $\alpha$ among all $\alpha$-approximate
equilibria of the given instance.
- Abstract（参考訳）: 本研究では,複数のユーザ(リーダ)がリソースセットから1つのリソースを選択するマルチリーダシングルフォローア・コングリゲーションゲームについて検討し,実負荷を観測した結果,敵(シングルフォローア)が最大負荷でリソースを攻撃し,リーダにさらなるコストをかけた。
リーダー間の戦略ゲームの結果について、純粋なナッシュ均衡は存在せず、従って近似均衡を考慮すべきであることを示す。
最初の主要な結果として、$K$-近似平衡の存在は常に保証され、$K \approx 1.1974$は立方多項式方程式のユニークな解である。
この目的のために、多項式時間組合せアルゴリズムが与えられ、k$-approximate equilibrium が計算される。
つまり、任意の$\alpha<K$に対して$\alpha$-approximate平衡を認めないインスタンスが存在することを意味する。
したがって、$\alpha=k$ は$\alpha$ の最小値であり、$\alpha$-approximate 平衡の存在が考慮されたゲームの任意の例に対して保証される。
第二に、与えられた固定インスタンスの近似平衡に焦点をあてる。
与えられたインスタンスのすべての$\alpha$-approximate equilibriaの中で、最小の$\alpha$で、最適な近似平衡を効率的に計算する方法を示す。
関連論文リスト
- Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。
特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
論文 参考訳（メタデータ） (2024-11-04T00:34:56Z) - Games played by Exponential Weights Algorithms [0.0]
各プレイヤーは、初期混合動作と固定学習率を特徴とする指数重み付けアルゴリズムを使用する。
厳密なナッシュ均衡が存在するときは常に、次の段階で厳密なナッシュ均衡を行う確率は、ほぼ確実に0または1に収束することを示す。
論文 参考訳（メタデータ） (2024-07-09T08:49:51Z) - The complexity of approximate (coarse) correlated equilibrium for incomplete information games [16.96984593866157]
不完全情報ゲームにおける近似平衡の分散学習の複雑さについて検討する。
我々の下限は、$epsilon$-approximate $mathitco$ correlation equilibriumというより簡単な解の概念にも当てはまる。
論文 参考訳（メタデータ） (2024-06-04T14:35:27Z) - On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。
Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
また,オンライングラディエントDescentは,非自明な状況下で効率よく$Phi$-equilibriaを近似できることを示した。
論文 参考訳（メタデータ） (2024-03-13T01:51:30Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
非定常マルチエージェントシステムにおける平衡の学習について検討する。
単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
論文 参考訳（メタデータ） (2023-06-12T23:48:24Z) - Equilibrium Bandits: Learning Optimal Equilibria of Unknown Dynamics [23.722837647516357]
未知のシステムを制御するために、$K$アクションのうちの1つを選ぶことができる意思決定者を考えてみましょう。
システムのダイナミクスは意思決定者にとって未知であり、各ターンの最後にノイズの多い報酬しか観測できない。
既存のバンディットアルゴリズムは、逆数でも、この問題に対して線形な(タウ)後悔を達成する。
均衡に達するまで待つ価値がなければ、素早くアクションを切り替えることを知っている新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-27T10:47:15Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Safe Equilibrium [1.7132914341329848]
標準的なゲーム理論解の概念であるナッシュ均衡は、すべてのプレイヤーが合理的に振る舞うことを仮定する。
我々は,特定の確率で合理的に行動する相手をモデル化する,セーフ均衡と呼ばれる新しい解の概念を提案する。
我々は、全ての戦略形式ゲームに安全な平衡が存在することを証明し、その計算がPPADハードであることを証明する。
論文 参考訳（メタデータ） (2022-01-12T01:45:51Z) - When Can We Learn General-Sum Markov Games with a Large Number of
Players Sample-Efficiently? [10.397170312149067]
本稿では,m$-player General-sum Markovゲームの設定において,学習目標がより優れたサンプル複雑性を許容するものについて検討する。
まず,$epsilon$-Coarse Correlated Equilibrium (CCE)を$widetildemathcalO(H5Smax_ile m A_i / epsilon2)$ episodesで学習するアルゴリズムを設計する。
第二に、マルコフポテンシャルゲームの重要な特別な場合を考え、$widet内で$epsilon$-approximate Nash平衡を学ぶアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-10-08T15:06:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。