論文の概要: Equilibrium Design for Concurrent Games

• arxiv url: http://arxiv.org/abs/2106.10192v1
• Date: Fri, 18 Jun 2021 15:45:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-21 17:24:27.736887
• Title: Equilibrium Design for Concurrent Games
• Title（参考訳）: コンカレントゲームのための平衡設計
• Authors: Julian Gutierrez, Muhammad Najib, Giuseppe Perelli, Michael Wooldridge
• Abstract要約: ゲーム理論において、メカニズム設計は、ゲームの望ましい結果を達成するためのインセンティブの設計に関係している。 インセンティブの設計について検討し、例えば、所与の時間論理的性質を満たす平衡を求める。 応用として、平衡設計は、並列ゲームに対する合理的な合成と検証問題の代替解として用いられる。
• 参考スコア（独自算出の注目度）: 5.9873770241999
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In game theory, mechanism design is concerned with the design of incentives so that a desired outcome of the game can be achieved. In this paper, we study the design of incentives so that a desirable equilibrium is obtained, for instance, an equilibrium satisfying a given temporal logic property -- a problem that we call equilibrium design. We base our study on a framework where system specifications are represented as temporal logic formulae, games as quantitative concurrent game structures, and players' goals as mean-payoff objectives. In particular, we consider system specifications given by LTL and GR(1) formulae, and show that implementing a mechanism to ensure that a given temporal logic property is satisfied on some/every Nash equilibrium of the game, whenever such a mechanism exists, can be done in PSPACE for LTL properties and in NP/$\Sigma^{P}_{2}$ for GR(1) specifications. We also study the complexity of various related decision and optimisation problems, such as optimality and uniqueness of solutions, and show that the complexities of all such problems lie within the polynomial hierarchy. As an application, equilibrium design can be used as an alternative solution to the rational synthesis and verification problems for concurrent games with mean-payoff objectives whenever no solution exists, or as a technique to repair, whenever possible, concurrent games with undesirable rational outcomes (Nash equilibria) in an optimal way.
• Abstract（参考訳）: ゲーム理論において、メカニズム設計は、ゲームの望ましい結果を達成するためのインセンティブの設計に関係している。 本稿では,例えば,与えられた時相論理特性を満たす平衡が,我々が平衡設計と呼ぶ問題となるような,望ましい平衡が得られるようにインセンティブの設計について検討する。 本研究は,システム仕様を時間論理式として,ゲームを定量的に同時ゲーム構造として,プレイヤーのゴールを平均支払い目的として表現する枠組みに基づく。 特に、ltl と gr(1) の式で与えられるシステム仕様を検討し、与えられた時相論理特性がゲームのある/すべての nash 平衡で満たされることを保証するメカニズムを実装することは、そのような機構が存在する場合には、ltl 特性の pspace と gr(1) 仕様の np/$\sigma^{p}_{2}$ で行えることを示す。 また、解の最適性や一意性などの様々な関連する決定および最適化問題の複雑さについて検討し、これらの問題の複雑さが多項式階層内にあることを示す。 アプリケーションとして、均衡設計は、平均払い目標が存在しない同時ゲームの合理的な合成と検証の問題に対する代替ソリューションとして、あるいは可能な限り、望ましくない合理的結果(nash平衡)を持つ同時ゲームを最適な方法で修正するテクニックとして使用できる。

関連論文リスト

• Synthesis of Reward Machines for Multi-Agent Equilibrium Design (Full Version) [2.2099217573031678]
  報酬機として知られる動的インセンティブ構造を用いた平衡設計の問題点を考察する。 設計者の目標を最適化する方法で報酬を割り当てる動的インセンティブを表現するために、報酬マシンをどのように利用できるかを示す。 我々は,NPオラクルを備えたチューリングマシンを用いて,両問題を時間内に解くことができることを示す。
  論文  参考訳（メタデータ） (2024-08-19T15:17:58Z)
• The Computational Complexity of Single-Player Imperfect-Recall Games [37.550554344575]
  本研究では,不完全なリコールを伴う広義のゲーム,例えばスリーピングビューティー問題やAbsent Driverゲームについて検討する。 そのようなゲームに対して、2つの自然な平衡概念が、最適解の代替概念として提案されている。
  論文  参考訳（メタデータ） (2023-05-28T19:41:25Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。 低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。 上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
  論文  参考訳（メタデータ） (2023-02-20T16:05:04Z)
• Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
  Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。 この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。 これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
  論文  参考訳（メタデータ） (2023-01-22T16:54:06Z)
• How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games [64.71476526716668]
  我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。 我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。 提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
  論文  参考訳（メタデータ） (2022-10-24T09:32:40Z)
• Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers [22.85979978964773]
  Nash Equilibria、Correlated Equilibria、Coarse Correlated Equilibriaといったソリューション概念は多くのマルチエージェント機械学習アルゴリズムに有用なコンポーネントである。 本稿では, ニューラルネットワークアーキテクチャを応用して, 固定形状, 購入速度, 決定性のすべてのゲームの空間を大まかに解決するニューラル平衡解法を提案する。
  論文  参考訳（メタデータ） (2022-10-17T17:00:31Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。 これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2022-03-14T15:21:18Z)
• Inducing Equilibria via Incentives: Simultaneous Design-and-Play Finds Global Optima [114.31577038081026]
  本稿では,デザイナーとエージェントの問題を同時に1ループで解くための効率的な手法を提案する。 設計者は平衡問題を何度も解決しないが、エージェントに対するインセンティブの全体的な影響を予測できる。 このアルゴリズムは,幅広い種類のゲームに対して,サブ線形速度で大域的最適値に収束することを示す。
  論文  参考訳（メタデータ） (2021-10-04T06:53:59Z)
• Rational Verification for Probabilistic Systems [2.4254101826561847]
  我々は確率的システムにおける合理的な検証の理論とアルゴリズムを開発する。 複雑なマルチエージェント環境における不確実性とランダム性をモデル化するための並列ゲーム(CSG)に焦点を当てる。
  論文  参考訳（メタデータ） (2021-07-19T19:24:16Z)

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

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