論文の概要: EFX Allocation In (Multi)Hypergraphs

• arxiv url: http://arxiv.org/abs/2608.03171v1
• Date: Tue, 04 Aug 2026 06:02:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-05 15:30:23.056532
• Title: EFX Allocation In (Multi)Hypergraphs
• Title（参考訳）: EFXアロケーション in (Multi)Hypergraphs
• Authors: Thanasis Lianeas, Alkmini Sgouritsa, Minas Marios Sotiriou,
• Abstract要約: EFX(envy-free-to-any-good)のアロケーションについて検討する。 EFXアロカ-イオンが常に存在するかどうかを見つけることは、加法的評価を持つエージェントに対しても、フェアディビジョンにおいて大きな問題である。
• 参考スコア（独自算出の注目度）: 3.702284004959709
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX alloca- tions always exist, even for agents with additive valuations, is a major open problem in Fair Division. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph, respectively, and only the endpoints of an edge may have non-zero marginal value for it. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose incident edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time.
• Abstract（参考訳）: 不均一な単調な単調な評価を行うエージェント間での異種商品の公平な割り当てについて検討する。 公平に見れば、EFX(Evy-free-up-any-good)のアロケーションについて考えます。 EFXアロカ-イオンが常に存在するかどうかを見つけることは、加法的評価を持つエージェントに対しても、フェアディビジョンにおいて大きな問題である。 Christodoulou et al (2023) は、エージェントと商品をそれぞれグラフの頂点と辺で表し、エッジの終端だけがそれに対してゼロの限界値を持たないような、多重ハイパーグラフの設定を導入した。 ガース値が 4 以上のハイパーグラフと一般的な単調値を持つエージェントに対して、常に EFX 割り当てが存在し、多項式時間で構築可能であることを示す。 我々は,少なくとも 4 個のガースを持つ多重ハイパーグラフが常に EFX の割り当てを許容していることを示すためのアプローチを一般化する。

関連論文リスト

• Estimating Fair Graphs from Graph-Stationary Data [58.94389691379349]
  グループレベルとノードレベルの定義に対応するグラフに対する群と個性を考える。 与えられたグラフの公平性を評価するために、スペクトル領域における新しい測定を含む複数のバイアス指標を提供する。 FairSpecTempの1つの変種は、直接バイアスを拘束しながらグラフ定常性の可換性を利用する。 もう一方は、グラフスペクトルのバイアスを制限することによって、公正な推定を暗黙的に奨励し、したがってより柔軟である。
  論文  参考訳（メタデータ） (2025-10-08T20:51:57Z)
• On Approximate MMS Allocations on Restricted Graph Classes [0.31457219084519]
  本研究では,接続制約のある不特定商品群を公平に分割する問題について検討する。 完備グラフ、サイクル、固定された$d$に対する$d$-claw-freeグラフのようなグラフのクラスが実際に存在することは知られている。 このようなアロケーションは、ブロックグラフ、cacti、完全多部グラフ、分割グラフなど、よく研究されているクラスに存在していることを示す。
  論文  参考訳（メタデータ） (2025-08-08T14:17:44Z)
• Pruning Spurious Subgraphs for Graph Out-of-Distribution Generalization [90.74916553208153]
  PrunEは,OODの一般化性を改善するために急激なエッジを除去する最初のプルーニングベースグラフOOD法である。 PrunE は2つの正規化項を使い、1) グラフサイズ制約は非形式的なスパイラスエッジを除外し、2) スパイラスエッジの発生をさらに抑制するために、$epsilon$-probability アライメントを使用する。
  論文  参考訳（メタデータ） (2025-06-06T10:34:48Z)
• Understanding EFX Allocations: Counting and Variants [0.8287206589886881]
  好ましくないもの(EFX)へのエンビーフリーネス(envy-freeness)は、不特定商品の公平な割り当てにおいて人気があり重要な公正性である。 このアプローチは、EFXアロケーションの存在と計算に関する貴重な洞察をもたらすかもしれない、と我々は主張する。
  論文  参考訳（メタデータ） (2025-04-04T21:36:09Z)
• On the existence of EFX allocations in multigraphs [0.8057006406834466]
  商品の集合上で評価セット機能を持つ複数のエージェントに対して、分割不可能な商品を分割する問題について検討する。 公平に見れば、いかなる善(EFX)までうらやましくないアロケーション、すなわち、他のエージェントに与えられた商品の適切なサブセットを敵視するエージェントはいない。
  論文  参考訳（メタデータ） (2025-02-13T21:16:27Z)
• Polynomial-Time Algorithms for Fair Orientations of Chores [1.0312968200748118]
  本稿では,雑用グラフの公平な配向を求める問題に対処する。 グラフのEF1 と EFX 配向は、たとえ自己ループが存在するとしても、そのグラフが存在するときのみコレを含む。 また、マルチグラフの EF1 と EFX の配向問題もNP完全であることを示す。
  論文  参考訳（メタデータ） (2025-01-23T08:53:18Z)
• Graph Sparsification via Mixture of Graphs [67.40204130771967]
  そこで我々はMixture-of-Graphs (MoG)を導入し、各ノードに対して動的に調整されたプルーニングソリューションを選択する。 MoGには複数のスパシファイアの専門家が組み込まれており、それぞれが独自のスパーシリティレベルとプルーニング基準によって特徴付けられ、各ノードに対して適切な専門家を選択する。 5つのGNNを備えた4つの大規模OGBデータセットと2つのスーパーピクセルデータセットの実験により、MoGはより高い空間レベルのサブグラフを識別することを示した。
  論文  参考訳（メタデータ） (2024-05-23T07:40:21Z)
• GraphMETRO: Mitigating Complex Graph Distribution Shifts via Mixture of Aligned Experts [75.51612253852002]
  GraphMETROは、自然多様性をモデル化し、複雑な分散シフトをキャプチャするグラフニューラルネットワークアーキテクチャである。 GraphMETROはGOODベンチマークから4つのデータセットに対して最先端の結果を得る。
  論文  参考訳（メタデータ） (2023-12-07T20:56:07Z)
• Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
  学習ノード表現は、コミュニティ検出やノード分類などのグラフ解析において、さまざまな下流タスクの恩恵を受ける。 教師なしの方法でノード表現を学習するための幾何学グラフ表現学習(G2R)を提案する。 G2R は異なるグループ内のノードを異なる部分空間にマッピングし、各部分空間はコンパクトで異なる部分空間が分散される。
  論文  参考訳（メタデータ） (2022-02-13T07:46:24Z)

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

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