論文の概要: Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

• arxiv url: http://arxiv.org/abs/2109.08644v1
• Date: Fri, 17 Sep 2021 16:57:20 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-20 16:38:15.100147
• Title: Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
• Title（参考訳）: 不特定商品を戦略エージェントに割り当てる:純ナッシュ均衡と公正
• Authors: Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenh\"auser
• Abstract要約: 付加価値関数を持つ戦略エージェントの集合に、分割不可能な商品の集合をかなり割り当てるという問題を考察する。 我々の主なゴールは、全てのインスタンスに純粋なナッシュ平衡を持つメカニズムが存在するかどうかを探ることである。 対応するアロケーションは EFX だけでなく、最大シェアフェアネスも満足していることを示します。
• 参考スコア（独自算出の注目度）: 15.465300967700193
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefore, a mechanism in our setting is an algorithm that takes as input the reported -- rather than the true -- values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely envy-freeness up to one good (EF1), and envy-freeness up to any good (EFX), and we positively answer the above question. In particular, we study two algorithms that are known to produce such allocations in the non-strategic setting: Round-Robin (EF1 allocations for any number of agents) and a cut-and-choose algorithm of Plaut and Roughgarden [SIAM Journal of Discrete Mathematics, 2020] (EFX allocations for two agents). For Round-Robin we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while for the algorithm of Plaut and Roughgarden we show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria which all induce EFX allocations.
• Abstract（参考訳）: 我々は,付加価値関数を持つ戦略エージェント群に対して,不可分な商品群を公平に割り当てる問題を考える。 したがって、私たちの設定のメカニズムは、エージェントの本当の値ではなく、報告された値を入力するアルゴリズムであると仮定します。 私たちの主な目標は、すべてのインスタンスに対して純粋なnash平衡を持つメカニズムが存在するか、同時に、これらの平衡に対応する割り当てに対する公平性保証を提供するかを検討することです。 本研究は,1つの善(EF1)まで,1つの善(EFX)まで,うらやましい自由(EF1)の2つの緩和に焦点を合わせ,上記の疑問に肯定的に答える。 特に,非ストラテジックな設定でそのようなアロケーションを生成することが知られているアルゴリズムとして,ラウンドロビン (EF1 のエージェントの割り当て) とプラウトとラフガーデンのカット・アンド・チョースアルゴリズム (SIAM Journal of Discrete Mathematics, 2020) がある。 ラウンドロビンでは、全ての純粋なナッシュ平衡が、根底にある真の値に関してEF1であるアロケーションを誘導するのに対し、プラウトとラフガーデンのアルゴリズムでは、対応するアロケーションは EFX だけでなく、非ストラテジックな設定では、このアルゴリズムには当てはまらない最大シェアフェアネスを満たすことを示す。 さらに、後者の結果の弱いバージョンは、すべてのefx割り当てを誘導する純粋なnash平衡を常に有する2つのエージェントの任意のメカニズムを保持できることを示した。

関連論文リスト

• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。 低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。 上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
  論文  参考訳（メタデータ） (2023-02-20T16:05:04Z)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  我々は、強い比例性は動機が良く基本的な公理であるが、その性質を満たす決定論的戦略防御機構は存在しないことを示した。 次に、予測において強い比例性を満たすランダムランクと呼ばれるランダム化メカニズムを同定する。 我々の主な特徴はランダムランクを、普遍的真理性、普遍的匿名性、期待における強い比喩性を達成するユニークなメカニズムとして特徴づけている。
  論文  参考訳（メタデータ） (2022-05-30T00:51:57Z)
• Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games [3.441021278275805]
  ゲームにおける学習は、多エージェント強化学習(MARL)における最も標準的で基本的な設定であることは間違いない。 汎用近似ゲーム(SG)の重要なクラスにおいて、完全分散Q-ラーニングアルゴリズムの有限サンプル複雑性を確立する。 我々は,各エージェントが報酬や他のエージェントの行動を観察できないような,完全に分散化されたMARLの実践的かつ挑戦的な設定に焦点をあてる。
  論文  参考訳（メタデータ） (2021-12-15T03:33:39Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  エージェント値の積を最大化するナッシュ福祉規則は,多様性の制約が導入されたとき,一意にロバストな位置にあることを示す。 また, ナッシュ・ウェルズによる保証は, 広く研究されているアロケーション・ルールのクラスにおいて, ほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2021-09-30T11:09:31Z)
• Algorithmic Stability in Fair Allocation of Indivisible Goods Among Two Agents [8.66798555194688]
  正当性の概念や近似効率の弱さとともに、正確な安定性を達成することは不可能であることを示す。 本稿では,安定性,すなわち近似安定性と弱近似安定性の2つの緩和法を提案する。 本稿では、ペアワイズ最大値の割り当てに関する一般的な特徴付けを行い、それを用いてほぼ安定なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-07-30T03:09:02Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。 まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
  論文  参考訳（メタデータ） (2020-04-19T18:00:58Z)
• Finding Fair and Efficient Allocations When Valuations Don't Add Up [25.962505544590947]
  エージェント評価がマトロイドのランク関数である場合、社会的に最適な(実用的社会福祉の最大化)手法は、1つの項目(EF1)までのうらやましい自由度が存在し、計算的に抽出可能であることを示す。 これは、ナッシュの福祉を最大化する割り当てがEF1であると確立された付加的評価によって仮定されない最初の評価関数クラスである。
  論文  参考訳（メタデータ） (2020-03-16T07:42:27Z)

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

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