論文の概要: On the existence of EFX allocations in multigraphs

• arxiv url: http://arxiv.org/abs/2502.09777v1
• Date: Thu, 13 Feb 2025 21:16:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-17 14:44:45.208327
• Title: On the existence of EFX allocations in multigraphs
• Title（参考訳）: 多重グラフにおけるEFXアロケーションの存在について
• Authors: Alkmini Sgouritsa, Minas Marios Sotiriou,
• Abstract要約: 商品の集合上で評価セット機能を持つ複数のエージェントに対して、分割不可能な商品を分割する問題について検討する。 公平に見れば、いかなる善(EFX)までうらやましくないアロケーション、すなわち、他のエージェントに与えられた商品の適切なサブセットを敵視するエージェントはいない。
• 参考スコア（独自算出の注目度）: 0.8057006406834466
• License:
• Abstract: We study the problem of "fairly" dividing indivisible goods to several agents that have valuation set functions over the sets of goods. As fair we consider the allocations that are envy-free up to any good (EFX), i.e., no agent envies any proper subset of the goods given to any other agent. The existence or not of EFX allocations is a major open problem in Fair Division, and there are only positive results for special cases. [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023] introduced a restriction on the agents' valuations according to a graph structure: the vertices correspond to agents and the edges to goods, and each vertex/agent has zero marginal value (or in other words, they are indifferent) for the edges/goods that are not adjacent to them. The existence of EFX allocations has been shown for simple graphs with general monotone valuations [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023], and for multigraphs for restricted additive valuations [Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei 2024]. In this work, we push the state-of-the-art further, and show that the EFX allocations always exists in multigraphs and general monotone valuations if any of the following three conditions hold: either (a) the multigraph is bipartite, or (b) each agent has at most $\lceil \frac{n}{4} \rceil -1$ neighbors, where $n$ is the total number of agents, or (c) the shortest cycle with non-parallel edges has length at least 6.
• Abstract（参考訳）: 本研究では, 商品集合上の評価セット機能を有する複数のエージェントに対して, 不特定商品を「公平に」分割する問題について検討する。 公平に見れば、いかなる善(EFX)までうらやましくないアロケーション、すなわち、他のエージェントに与えられた商品の適切なサブセットを敵視するエージェントはいない。 EFXアロケーションの存在の有無は、フェアディビジョンの主要なオープンな問題であり、特別な場合にのみ肯定的な結果が得られる。 [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023] は、グラフ構造に従ってエージェントのバリュエーションを制限した: 頂点はエージェントと商品の縁に対応し、各頂点/エージェントは、隣り合わないエッジ/商品に対してゼロの限界値(つまり、それらは無関心)を持つ。 EFXアロケーションの存在は、一般的なモノトン評価を持つ単純なグラフ(George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023)と、制限付加法評価のためのマルチグラフ(Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei 2024)で示されている。 本研究では, 現状をさらに推し進めるとともに, 以下の3つの条件のいずれかが成立すれば, EFXアロケーションが常に多グラフおよび一般単調な評価において存在することを示す。 a) 多重グラフは二分数である、または (b)各エージェントは、少なくとも$\lceil \frac{n}{4} \rceil -1$ neighborsを持ち、$n$はエージェントの総数である。 (c) 平行でない辺を持つ最短周期は、少なくとも6。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• A Polynomial-Time Algorithm for EFX Orientations of Chores [0.0]
  品物件と雑用件との間には意外な分離が見られる。 また、多重グラフがNP完全であるような類似的な決定問題も示している。
  論文  参考訳（メタデータ） (2025-01-23T08:53:18Z)
• Resource Allocation under the Latin Square Constraint [3.8028747063484585]
  我々は、$n$のラウンドで$n$のエージェント間で$n$の分割不可能なアイテムを割り当てる問題を提起する。 この制約は、各エージェントがラウンド毎に1つ以上のアイテムを受信し、各アイテムを最大1回受信することを保証します。 スケジューリング、リソース管理、実験的設計のような現実世界のアプリケーションは、アロケーションにおける公平性やバランス性を満たすためにラテン四角い制約を必要とする。
  論文  参考訳（メタデータ） (2025-01-11T10:53:48Z)
• Partial Identifiability in Inverse Reinforcement Learning For Agents With Non-Exponential Discounting [64.13583792391783]
  逆強化学習は、エージェントの振る舞いを観察することから、エージェントの好みを推測することを目的としている。 IRLの主な課題の1つは、複数の選好が同じ観察行動を引き起こす可能性があることである。 一般にIRLは、正しい最適ポリシーを特定するのに、$R$に関する十分な情報を推測できないことを示す。
  論文  参考訳（メタデータ） (2024-12-15T11:08:58Z)
• Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
  我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。 UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
  論文  参考訳（メタデータ） (2024-10-08T09:49:47Z)
• Pushing the Frontier on Approximate EFX Allocations [14.101164748526159]
  本研究では, 付加的評価関数を持つエージェント群に対して, 分割不可能な商品群を割り当てる問題について検討する。 正確なEFXアロケーションが存在することが分かっている設定の厳密な一般化のために、我々は存在結果を得る。 この結果から, 近似EFXアロケーションの存在と計算のフロンティアを推し進めることができた。
  論文  参考訳（メタデータ） (2024-06-18T09:01:37Z)
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
  マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである 本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。 マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-02-11T01:51:15Z)
• 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)
• (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna [10.933894827834825]
  エージェントの集合に分割不可能な項目の集合を公平かつ効率的に割り当てることの課題について検討する。 公平性の概念として、エンビーフリーネスと比例性の最も強い緩和性を考える。
  論文  参考訳（メタデータ） (2022-02-06T01:29:50Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  エージェント値の積を最大化するナッシュ福祉規則は,多様性の制約が導入されたとき,一意にロバストな位置にあることを示す。 また, ナッシュ・ウェルズによる保証は, 広く研究されているアロケーション・ルールのクラスにおいて, ほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2021-09-30T11:09:31Z)
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness [16.187873844872637]
  付加価値関数を持つ戦略エージェントの集合に、分割不可能な商品の集合をかなり割り当てるという問題を考察する。 我々の主なゴールは、全てのインスタンスに純粋なナッシュ平衡を持つメカニズムが存在するかどうかを探ることである。 対応するアロケーションは EFX だけでなく、最大シェアフェアネスも満足していることを示します。
  論文  参考訳（メタデータ） (2021-09-17T16:57:20Z)

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

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