論文の概要: Computing Pure-Strategy Nash Equilibria in a Two-Party Policy Competition: Existence and Algorithmic Approaches

• arxiv url: http://arxiv.org/abs/2512.22552v1
• Date: Sat, 27 Dec 2025 10:44:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-30 22:37:30.109927
• Title: Computing Pure-Strategy Nash Equilibria in a Two-Party Policy Competition: Existence and Algorithmic Approaches
• Title（参考訳）: 2部政策コンペティションにおけるPure-Strategy Nash Equilibriaの計算:存在とアルゴリズム的アプローチ
• Authors: Chuang-Chieh Lin, Chi-Jen Lu, Po-An Chen, Chih-Chieh Hung,
• Abstract要約: 我々は、二者間政策競争を二者間非協力ゲームとして定式化する。 政策の勝利確率は、全有権者にまたがって単調に増大する。 プレイヤーのペイオフは、サポーターが期待するユーティリティとして定義される。
• 参考スコア（独自算出の注目度）: 1.2609533046091317
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We formulate two-party policy competition as a two-player non-cooperative game, generalizing Lin et al.'s work (2021). Each party selects a real-valued policy vector as its strategy from a compact subset of Euclidean space, and a voter's utility for a policy is given by the inner product with their preference vector. To capture the uncertainty in the competition, we assume that a policy's winning probability increases monotonically with its total utility across all voters, and we formalize this via an affine isotonic function. A player's payoff is defined as the expected utility received by its supporters. In this work, we first test and validate the isotonicity hypothesis through voting simulations. Next, we prove the existence of a pure-strategy Nash equilibrium (PSNE) in both one- and multi-dimensional settings. Although we construct a counterexample demonstrating the game's non-monotonicity, our experiments show that a decentralized gradient-based algorithm typically converges rapidly to an approximate PSNE. Finally, we present a grid-based search algorithm that finds an $ε$-approximate PSNE of the game in time polynomial in the input size and $1/ε$.
• Abstract（参考訳）: 我々は、Lin et al's work (2021) を一般化し、2人プレイの非協調ゲームとして、2人プレイのポリシー競争を定式化する。 各党はユークリッド空間のコンパクト部分集合から実数値ポリシーベクトルを戦略として選択し、政策に対する投票者の効用は、その選好ベクトルを持つ内積によって与えられる。 競争の不確かさを捉えるため、政策の勝利確率は全投票者で一元的に増加すると仮定し、アフィン等方関数を用いてこれを定式化する。 プレイヤーのペイオフは、サポーターが期待するユーティリティとして定義される。 本研究は,まず,投票シミュレーションを用いて等調性仮説を検証し,検証する。 次に,1次元と多次元の両方で純粋定常ナッシュ均衡(PSNE)の存在を証明した。 我々はゲームの非単調性を示す反例を構築するが、この実験により、分散勾配に基づくアルゴリズムは通常、近似PSNEに急速に収束することを示した。 最後に、入力サイズが1/ε$の時間多項式でゲームの$ε$-approximate PSNEを求めるグリッドベースの探索アルゴリズムを提案する。

関連論文リスト

• Multiplayer Nash Preference Optimization [79.15013211640566]
  人間からのフィードバックからの強化学習(RLHF)は、大規模言語モデル(LLM)と人間の嗜好を整合させる標準パラダイムとして登場した。 最近の研究は、2人プレイのナッシュゲームとしてアライメントを再構築し、ナッシュの学習を人間のフィードバック(NLHF)から引き起こした。 マルチプレイヤーシステムにNLHFを一般化する新しいフレームワークであるMultiplayer Nash Preference Optimization (MNPO)を導入する。
  論文  参考訳（メタデータ） (2025-09-27T04:18:33Z)
• COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences [57.70902561665269]
  本稿では,言語モデルアライメントのためのメタアルゴリズムである Convergent Meta Alignment Algorithm (COMAL) を提案する。 我々は, メタアルゴリズムが最終回において正確なナッシュポリシーに収束する理論解析を行い, 一連の合成および選好最適化データセット上での有効性を実証する。
  論文  参考訳（メタデータ） (2024-10-30T17:13:02Z)
• Scalable and Independent Learning of Nash Equilibrium Policies in $n$-Player Stochastic Games with Unknown Independent Chains [1.0878040851638]
  独立な連鎖と未知の遷移行列を持つゲームについて研究する。 このクラスのゲームでは、プレイヤーは他のプレイヤーの状態や行動に依存しない内部マルコフ連鎖を制御する。 我々は、$epsilon$-NEポリシーを学ぶために、完全に分散化されたミラー降下アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-04T03:04:09Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic Games with Independent Chains [2.132096006921048]
  我々は、プレイヤーがペイオフ機能を介して結合されている間、内部の状態/行動空間を持つ、$n$プレイヤゲームのクラスを考える。 このクラスのゲームに対して、報奨関数を仮定せずに定常ナッシュ(NE)ポリシーを見つけることは、対話可能であることを示す。 我々は,2重平均化と2重ミラー降下に基づくアルゴリズムを開発し,これを$epsilon$-NEポリシーの集合に収束させる。
  論文  参考訳（メタデータ） (2022-01-28T16:27:21Z)
• Independent Policy Gradient Methods for Competitive Reinforcement Learning [62.91197073795261]
  2つのエージェントによる競争強化学習環境における独立学習アルゴリズムに対するグローバル・非漸近収束保証を得る。 本研究は,両選手がタンデムで政策勾配法を実行すると,学習率を2回ルールに従えば,その政策はゲームの最小均衡に収束することを示す。
  論文  参考訳（メタデータ） (2021-01-11T23:20:42Z)
• Provable Fictitious Play for General Mean-Field Games [111.44976345867005]
  静止平均場ゲームのための強化学習アルゴリズムを提案する。 目標は、ナッシュ均衡を構成する平均場状態と定常政策のペアを学ぶことである。
  論文  参考訳（メタデータ） (2020-10-08T18:46:48Z)

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

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