論文の概要: Solving Graph-based Public Good Games with Tree Search and Imitation
Learning
- arxiv url: http://arxiv.org/abs/2106.06762v1
- Date: Sat, 12 Jun 2021 12:46:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-15 16:22:20.480968
- Title: Solving Graph-based Public Good Games with Tree Search and Imitation
Learning
- Title（参考訳）: 木探索と模倣学習によるグラフベース公共グッズゲームの解決
- Authors: Victor-Alexandru Darvariu, Stephen Hailes, Mirco Musolesi
- Abstract要約: 我々は,自己関心エージェントのネットワークをグローバルに捉えた中心的プランナーの視点と,ベストショットの公共商品ゲームにおける所望の資産の最大化を目標とする。
この既知のNP完全問題に対する既存のアルゴリズムは、社会福祉以外の基準に最適化できない準最適解を見つける。
提案手法は,グラフの平衡と最大独立集合(mIS)構造特性の対応性を直接活用する。
- 参考スコア（独自算出の注目度）: 4.499055111059408
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Public goods games represent insightful settings for studying incentives for
individual agents to make contributions that, while costly for each of them,
benefit the wider society. In this work, we adopt the perspective of a central
planner with a global view of a network of self-interested agents and the goal
of maximizing some desired property in the context of a best-shot public goods
game. Existing algorithms for this known NP-complete problem find solutions
that are sub-optimal and cannot optimize for criteria other than social
welfare.
In order to efficiently solve public goods games, our proposed method
directly exploits the correspondence between equilibria and the Maximal
Independent Set (mIS) structural property of graphs. In particular, we define a
Markov Decision Process, which incrementally generates an mIS, and adopt a
planning method to search for equilibria, outperforming existing methods.
Furthermore, we devise an imitation learning technique that uses demonstrations
of the search to obtain a graph neural network parametrized policy which
quickly generalizes to unseen game instances. Our evaluation results show that
this policy is able to reach 99.5% of the performance of the planning method
while being approximately three orders of magnitude faster to evaluate on the
largest graphs tested. The methods presented in this work can be applied to a
large class of public goods games of potentially high societal impact.
- Abstract（参考訳）: パブリックグッズゲームは、個々のエージェントがより広い社会に利益をもたらすように貢献するためのインセンティブを研究するための洞察に富んだ設定を表している。
本研究は,自己関心のあるエージェントのネットワークのグローバルな視点と,ベストショット・パブリックグッズゲームの文脈で所望の資産を最大化することを目的として,中央プランナーの視点を採用する。
この既知のNP完全問題に対する既存のアルゴリズムは、社会福祉以外の基準に最適化できない準最適解を見つける。
提案手法は, グラフの平衡と最大独立集合(mIS)構造特性の対応性を直接的に活用する。
特に,mISを漸進的に生成するマルコフ決定プロセスを定義し,既存の手法よりも優れた平衡探索のための計画手法を採用する。
さらに,探索のデモンストレーションを用いてグラフニューラルネットワークパラメータ化ポリシを得るための模倣学習手法を考案し,未発見のゲームインスタンスに素早く一般化する。
評価の結果,本手法は,最大値のグラフで評価するのとほぼ3桁の速さで,計画手法の性能の99.5%に到達できることがわかった。
この研究で提示された手法は、潜在的に社会的に高い影響を与える可能性のある大規模な公共グッズゲームに適用することができる。
関連論文リスト
- Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning [55.65738319966385]
我々は、新しいオンラインアルゴリズム、反復的ナッシュポリシー最適化(INPO)を提案する。
従来の方法とは異なり、INPOは個々の応答に対する期待される勝利率を推定する必要性を回避している。
LLaMA-3-8BベースのSFTモデルで、INPOはAlpacaEval 2.0で42.6%、Arena-Hardで37.8%の勝利率を達成した。
論文 参考訳（メタデータ） (2024-06-30T08:00:34Z) - Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
言語エージェントにおけるタスクプランニングは、大規模言語モデル(LLM)の開発とともに重要な研究トピックとして浮上している。
本稿では,課題計画のためのグラフ学習に基づく手法について検討する。
我々のグラフ学習への関心は、注意のバイアスと自己回帰的損失が、グラフ上の意思決定を効果的にナビゲートするLLMの能力を妨げているという理論的な発見に起因している。
論文 参考訳（メタデータ） (2024-05-29T14:26:24Z) - Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via
Planning and Learning [46.354187895184154]
マルチエージェントパスフィンディング(MAPF)問題は通常、グラフに制限されたエージェントの集合に対する競合のないパスの集合を見つけるよう要求する。
本研究では,エージェントの位置や目標に関する情報をすべて収集する中央制御器が存在しない場合の分散MAPF設定について検討する。
我々は,先行するエージェントに新たな目標を連続的に割り当てることを含むMAPFの実用上重要な寿命変化に焦点をあてる。
論文 参考訳（メタデータ） (2023-10-02T13:51:32Z) - The Update-Equivalence Framework for Decision-Time Planning [78.44953498421854]
本稿では,サブゲームの解決ではなく,更新等価性に基づく意思決定時計画のための代替フレームワークを提案する。
ミラー降下に基づく完全協調型ゲームに対する有効音声探索アルゴリズムと、磁気ミラー降下に基づく対戦型ゲームに対する探索アルゴリズムを導出する。
論文 参考訳（メタデータ） (2023-04-25T20:28:55Z) - Learning to Incentivize Information Acquisition: Proper Scoring Rules
Meet Principal-Agent Model [64.94131130042275]
インセンティブ付き情報取得問題について検討し、主治官がエージェントを雇って代理情報を収集する。
UCBアルゴリズムをモデルに適合させる,実証可能なサンプル効率の良いアルゴリズムを設計する。
本アルゴリズムは,主役の最適利益に対する微妙な推定手順と,所望のエージェントの行動にインセンティブを与える保守的な補正手法を特徴とする。
論文 参考訳（メタデータ） (2023-03-15T13:40:16Z) - Using Knowledge Graphs for Performance Prediction of Modular
Optimization Algorithms [4.060078409841919]
我々は知識グラフ埋め込み手法を用いて性能予測モデルを構築した。
与えられたアルゴリズムのインスタンスが特定の目標精度を達成できるかどうかを正確に予測できる3つの分類手法を示す。
論文 参考訳（メタデータ） (2023-01-24T09:28:57Z) - Sequential Information Design: Markov Persuasion Process and Its
Efficient Reinforcement Learning [156.5667417159582]
本稿では,逐次情報設計の新たなモデル,すなわちマルコフ説得過程(MPP)を提案する。
MPPのプランニングは、ミオピックレシーバーに同時に説得されるシグナルポリシーを見つけ、送信者の最適な長期累積ユーティリティを誘導する、というユニークな課題に直面している。
我々は,楽観主義と悲観主義の両原理の新たな組み合わせを特徴とする,実証可能な効率のよい非回帰学習アルゴリズム,Optimism-Pessimism Principle for Persuasion Process (OP4) を設計する。
論文 参考訳（メタデータ） (2022-02-22T05:41:43Z) - Probabilistic Case-based Reasoning for Open-World Knowledge Graph
Completion [59.549664231655726]
ケースベース推論(CBR)システムは,与えられた問題に類似した事例を検索することで,新たな問題を解決する。
本稿では,知識ベース(KB)の推論において,そのようなシステムが実現可能であることを示す。
提案手法は,KB内の類似エンティティからの推論パスを収集することにより,エンティティの属性を予測する。
論文 参考訳（メタデータ） (2020-10-07T17:48:12Z) - Beyond Individualized Recourse: Interpretable and Interactive Summaries
of Actionable Recourses [14.626432428431594]
本稿では,Actionable Recourse Agnostic (AReS) と呼ばれる新しいモデルフレームワークを提案する。
説明文の正当性と解釈可能性の両面を同時に最適化する新たな目的を定式化する。
当社のフレームワークは,ブラックボックスモデルに対応するリコースの包括的概要を意思決定者に提供する。
論文 参考訳（メタデータ） (2020-09-15T15:14:08Z) - A General Large Neighborhood Search Framework for Solving Integer Linear
Programs [46.62993477453986]
我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。
我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
論文 参考訳（メタデータ） (2020-03-29T23:08:14Z) - Goal-directed graph construction using reinforcement learning [3.291429094499946]
我々は、中央エージェントが試行錯誤によってトポロジを生成する決定過程としてグラフの構築を定式化する。
グラフ構築と改善戦略を学習するための強化学習とグラフニューラルネットワークに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-30T12:11:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。