論文の概要: Synthesis of Reward Machines for Multi-Agent Equilibrium Design (Full Version)

• arxiv url: http://arxiv.org/abs/2408.10074v1
• Date: Mon, 19 Aug 2024 15:17:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-20 15:43:09.856813
• Title: Synthesis of Reward Machines for Multi-Agent Equilibrium Design (Full Version)
• Title（参考訳）: マルチエージェント平衡設計のためのリワードマシンの合成(フルバージョン)
• Authors: Muhammad Najib, Giuseppe Perelli,
• Abstract要約: 報酬機として知られる動的インセンティブ構造を用いた平衡設計の問題点を考察する。 設計者の目標を最適化する方法で報酬を割り当てる動的インセンティブを表現するために、報酬マシンをどのように利用できるかを示す。 我々は,NPオラクルを備えたチューリングマシンを用いて,両問題を時間内に解くことができることを示す。
• 参考スコア（独自算出の注目度）: 2.2099217573031678
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mechanism design is a well-established game-theoretic paradigm for designing games to achieve desired outcomes. This paper addresses a closely related but distinct concept, equilibrium design. Unlike mechanism design, the designer's authority in equilibrium design is more constrained; she can only modify the incentive structures in a given game to achieve certain outcomes without the ability to create the game from scratch. We study the problem of equilibrium design using dynamic incentive structures, known as reward machines. We use weighted concurrent game structures for the game model, with goals (for the players and the designer) defined as mean-payoff objectives. We show how reward machines can be used to represent dynamic incentives that allocate rewards in a manner that optimises the designer's goal. We also introduce the main decision problem within our framework, the payoff improvement problem. This problem essentially asks whether there exists a dynamic incentive (represented by some reward machine) that can improve the designer's payoff by more than a given threshold value. We present two variants of the problem: strong and weak. We demonstrate that both can be solved in polynomial time using a Turing machine equipped with an NP oracle. Furthermore, we also establish that these variants are either NP-hard or coNP-hard. Finally, we show how to synthesise the corresponding reward machine if it exists.
• Abstract（参考訳）: メカニズムデザインは、望まれる結果を達成するためのゲーム設計のための、十分に確立されたゲーム理論パラダイムである。 本稿では、密接に関連するが、異なる概念である平衡設計について論じる。 メカニズム設計とは異なり、デザイナーの均衡設計の権威はより制約され、ゲーム内のインセンティブ構造を変更して、スクラッチからゲームを作成する能力のない特定の結果を達成することができる。 報酬機として知られる動的インセンティブ構造を用いた平衡設計の問題点を考察する。 我々はゲームモデルに重み付けされたゲーム構造を使用し、ゴール(プレイヤーとデザイナ)を平均ペイオフ目標と定義した。 設計者の目標を最適化する方法で報酬を割り当てる動的インセンティブを表現するために、報酬マシンをどのように利用できるかを示す。 また、当社のフレームワークの主な決定問題であるペイオフ改善問題も導入しています。 この問題は基本的に、与えられた閾値以上の値でデザイナの支払を改善する動的インセンティブ(報酬機によって表現される)が存在するかどうかを問うものである。 我々はその問題の2つの変種を提示する: 強いと弱い。 NPオラクルを備えたチューリングマシンを用いて多項式時間で解けることを示す。 さらに、これらの変種は NP-hard あるいは coNP-hard であることを示す。 最後に、それが存在する場合、対応する報酬機を合成する方法を示す。

関連論文リスト

• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。 不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
  論文  参考訳（メタデータ） (2024-06-23T00:27:28Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• 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)
• How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games [64.71476526716668]
  我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。 我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。 提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
  論文  参考訳（メタデータ） (2022-10-24T09:32:40Z)
• Assisted Robust Reward Design [33.55440481096258]
  実際には、報酬デザインは反復的なプロセスであり、デザイナーは報酬を選択し、最終的には報酬が間違った行動にインセンティブを与え、報酬を修正し、繰り返す「エッジケース」環境に遭遇する。 我々は,ロボットが与えられた報酬を受け取らず,むしろ不確実性を持ち,将来の設計の繰り返しを将来の証拠として考慮することを提案する。 本研究では,この手法を簡易な自律運転タスクでテストし,現在の報酬に対して「エッジケース」である環境を提案することにより,保留環境における自動車の挙動をより迅速に改善することを確認する。
  論文  参考訳（メタデータ） (2021-11-18T18:59:33Z)
• Inducing Equilibria via Incentives: Simultaneous Design-and-Play Finds Global Optima [114.31577038081026]
  本稿では,デザイナーとエージェントの問題を同時に1ループで解くための効率的な手法を提案する。 設計者は平衡問題を何度も解決しないが、エージェントに対するインセンティブの全体的な影響を予測できる。 このアルゴリズムは,幅広い種類のゲームに対して,サブ線形速度で大域的最適値に収束することを示す。
  論文  参考訳（メタデータ） (2021-10-04T06:53:59Z)
• Equilibrium Design for Concurrent Games [5.9873770241999]
  ゲーム理論において、メカニズム設計は、ゲームの望ましい結果を達成するためのインセンティブの設計に関係している。 インセンティブの設計について検討し、例えば、所与の時間論理的性質を満たす平衡を求める。 応用として、平衡設計は、並列ゲームに対する合理的な合成と検証問題の代替解として用いられる。
  論文  参考訳（メタデータ） (2021-06-18T15:45:45Z)
• Deep Policy Networks for NPC Behaviors that Adapt to Changing Design Parameters in Roguelike Games [137.86426963572214]
  例えばRoguelikesのようなターンベースの戦略ゲームは、Deep Reinforcement Learning(DRL)にユニークな課題を提示する。 複雑なカテゴリ状態空間をより適切に処理し、設計決定によって強制的に再訓練する必要性を緩和する2つのネットワークアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2020-12-07T08:47:25Z)
• Metagame Autobalancing for Competitive Multiplayer Games [0.10499611180329801]
  ゲーム設計において,マルチプレイヤーゲームのバランスをとるためのツールを提案する。 我々のアプローチでは,設計者がメタゲームターゲットの直感的なグラフィカル表現を構築する必要がある。 このツールの能力は、Rock-Paper-Scissors から継承された例や、より複雑な非対称戦闘ゲームにおいて示す。
  論文  参考訳（メタデータ） (2020-06-08T08:55:30Z)

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

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