論文の概要: How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?
- arxiv url: http://arxiv.org/abs/2611.01234v1
- Date: Sat, 31 Oct 2026 20:01:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-13 00:35:43.016767
- Title: How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?
- Title(参考訳): 自尊心の社会的コストはどの程度変化できるか?
- Abstract要約: 非原子的混雑ゲームにおける近似的ナッシュ平衡について検討する。
我々は、各プレイヤーが最低利用可能な最低コストの1ドル+$の戦略を使用する場合、$$$-approximate Nash equilibria($-NE)を考える。
- 参考スコア(独自算出の注目度): 8.014553987852924
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed. We consider $ε$-approximate Nash equilibria ($ε$-NE), in which each player uses a strategy whose cost is at most $1 + ε$ times the minimum available cost. We compare the social costs of $ε$-NE and exact Nash equilibria. This lets us quantify, for example, how much a navigation app can reduce total travel time when drivers tolerate routes slightly slower than the fastest available route. For degree-$d$ polynomial latencies in both general nonatomic congestion games and single-commodity routing games on series-parallel networks, we give tight lower and upper bounds on the relative change in social cost from an exact Nash equilibrium to any $ε$-NE, with matching instances for every $ε$. For small $ε$, the largest possible relative reduction and increase in general congestion games are both $Θ(\sqrt{dε})$, independently of the number of resources and populations. In contrast, on series-parallel networks of depth $h$, the largest possible relative reduction is $Θ(hε)$, while the largest possible relative increase is known to be $ε$. For the classes of games we study, these results give a tight and quantitative characterization of the possible changes in social cost and establish a separation between general and series-parallel networks.
- Abstract(参考訳): 非原子的混雑ゲームにおけるナッシュ平衡の近似について検討し、平衡条件が緩和された場合の社会的コストがどの程度変化するかを理解することを目的とする。
ε$-approximate Nash equilibria (ε$-NE) を考えると、各プレイヤーは最低利用可能な最低コストの1ドル+ε$の戦略を使用する。
我々は、ε$-NEと正確なナッシュ均衡の社会的コストを比較する。
これにより、例えばナビゲーションアプリが、ドライバーが最速のルートよりわずかに遅いルートを許容するときの総走行時間をどれだけ削減できるかを定量化できます。
一般の非原子共役ゲームと直列並列ネットワーク上の単一商品ルーティングゲームの両方における次数-$$多項式のレイテンシに対して、我々は、正確なナッシュ平衡から任意の$ε$-NEへの相対的な社会的コストの変化について、ε$毎の一致インスタンスを含む、厳密な下限と上限を与える。
小さな$ε$の場合、一般的な混雑ゲームにおける最大の相対的減少と増加は、資源と人口の個数とは独立に$(\sqrt{dε})$である。
対照的に、深度$h$の直列並列ネットワークでは、最大の相対的還元は$(hε)$であり、最大の相対的増加は$ε$である。
本研究は,ゲームクラスにおいて,社会的コストの変化の可能性について,厳密かつ定量的に評価し,汎用ネットワークとシリーズ並列ネットワークの分離を確立することを目的とする。
関連論文リスト
- Scale-Invariant Fast Convergence in Games [67.02769061793619]
我々は,スケールフリーでもスケール不変でも,高速収束を実現する学習力学を開発した。
2プレーヤゼロサムゲームに対しては、$tildeO(A_mathrmdiff)$で有界な外部後悔を伴うスケールフリーかつスケール不変のダイナミクスが得られる。
マルチプレイヤーの汎用ゲームでは、過去の観測に基づいて観察された勾配をクリップする2倍のクリッピングと呼ばれる手法によって、スケールフリーの学習も可能となる。
論文 参考訳(メタデータ) (2026-02-12T11:57:20Z) - Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。
我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
論文 参考訳(メタデータ) (2025-10-20T00:45:47Z) - Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。
また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
論文 参考訳(メタデータ) (2025-02-24T20:20:06Z) - On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
非コンケーブゲームにおいて、抽出可能な$Phi$-equilibriaについて検討する。
Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2024-03-13T01:51:30Z) - Multi-Leader Congestion Games with an Adversary [0.5914780964919123]
本研究では,複数のユーザ(リーダ)がリソースセットから1つのリソースを選択するマルチリーダシングルフォロワ・コングリゲーションゲームについて検討する。
純粋なナッシュ平衡は存在せず、従って近似平衡を考える。
与えられたインスタンスのすべての$alpha$-approximate equilibriaの中で、最小の$alpha$で、最適な近似平衡を効率的に計算する方法を示す。
論文 参考訳(メタデータ) (2021-12-14T14:47:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。