論文の概要: Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division

• arxiv url: http://arxiv.org/abs/2507.14957v2
• Date: Wed, 30 Jul 2025 16:51:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-31 14:05:51.365527
• Title: Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division
• Title（参考訳）: PMMSによるEFXの探索:(Non-)離散フェアディビジョンにおける存在結果
• Authors: Jarosław Byrka, Franciszek Malinka, Tomasz Ponitka,
• Abstract要約: 我々は,3つの重要な特別事例に対する公平な割り当ての存在を証明した。 EFXアロケーションは、パーソナライズされた2値評価のために存在することを示す。 また、PMMSアロケーションがバイナリ値のMMS実現可能な評価のために存在することも証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the fair division of indivisible items and provide new insights into the EFX problem, which is widely regarded as the central open question in fair division, and the PMMS problem, a strictly stronger variant of EFX. Our first result constructs a three-agent instance with two monotone valuations and one additive valuation in which no PMMS allocation exists. Since EFX allocations are known to exist under these assumptions, this establishes a formal separation between EFX and PMMS. We prove existence of fair allocations for three important special cases. We show that EFX allocations exist for personalized bivalued valuations, where for each agent $i$ there exist values $a_i > b_i$ such that agent $i$ assigns value $v_i(\{g\}) \in \{a_i, b_i\}$ to each good $g$. We establish an analogous existence result for PMMS allocations when $a_i$ is divisible by $b_i$. We also prove that PMMS allocations exist for binary-valued MMS-feasible valuations, where each bundle $S$ has value $v_i(S) \in \{0, 1\}$. Notably, this result holds even without assuming monotonicity of valuations and thus applies to the fair division of chores and mixed manna. Finally, we study a class of valuations called pair-demand valuations, which extend the well-studied unit-demand valuations to the case where each agent derives value from at most two items, and we show that PMMS allocations exist in this setting. Our proofs are constructive, and we provide polynomial-time algorithms for all three existence results.
• Abstract（参考訳）: 本研究では,不特定項目の公平な分割について検討し,公平な分割において中心的なオープンな問題とみなされるEFX問題と,より強いEFXの変種であるPMMS問題に新たな洞察を与える。 最初の結果は,PMMSアロケーションが存在しない2つの単調な評価値と1つの付加的評価値を持つ3エージェントのインスタンスを構築した。 EFX の割り当てはこれらの前提の下で存在することが知られているので、これは EFX と PMMS の正式な分離を確立する。 我々は,3つの重要な特別事例に対する公平な割り当ての存在を証明した。 それぞれのエージェント $i$ に対して $a_i > b_i$ が存在し、エージェント $i$ が $v_i(\{g\}) \in \{a_i, b_i\}$ をそれぞれ$g$ に割り当てる。 a_i$ が $b_i$ で割り切れるとき、PMMSアロケーションに類似した存在結果を確立する。 また、PMMSアロケーションがバイナリ値のMMS実現可能な評価値に存在し、それぞれのバンドル$S$が$v_i(S) \in \{0, 1\}$を持つことを示す。 特に、この結果はバリュエーションの単調性を仮定することなく成り立つので、コレと混合マンナの公平な分割にも当てはまる。 最後に、各エージェントが少なくとも2つの項目から価値を導出するケースまで、よく研究された単価評価を拡張したペアオンデマンド評価と呼ばれる評価のクラスについて検討し、PMMSアロケーションがこの設定に存在することを示す。 証明は構成的であり、3つの実測結果すべてに対して多項式時間アルゴリズムを提供する。

関連論文リスト

• Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
  オンラインフェアディビジョン(オンラインフェアディビジョン)では,商品が一度に1つずつ到着し,定額のエージェントが配置されている。 善が現れると、各エージェントの持つ値が明らかになり、エージェントの1つに即時かつ不可逆的に割り当てられなければならない。 我々は、よく知られた公平性の概念に関して、最悪の場合の保証を得る方法を示す。
  論文  参考訳（メタデータ） (2025-05-28T09:48:16Z)
• Understanding EFX Allocations: Counting and Variants [0.8287206589886881]
  好ましくないもの(EFX)へのエンビーフリーネス(envy-freeness)は、不特定商品の公平な割り当てにおいて人気があり重要な公正性である。 このアプローチは、EFXアロケーションの存在と計算に関する貴重な洞察をもたらすかもしれない、と我々は主張する。
  論文  参考訳（メタデータ） (2025-04-04T21:36:09Z)
• Benchmarking Multi-modal Semantic Segmentation under Sensor Failures: Missing and Noisy Modality Robustness [61.87055159919641]
  マルチモーダルセマンティックセグメンテーション(MMSS)は、モーダル間で補完情報を統合することで、単一モーダルデータの制限に対処する。 顕著な進歩にもかかわらず、マルチモーダルデータ品質の変動と不確実性により、研究と実世界の展開の間に大きなギャップが持続する。 Intire-Missing Modality (EMM)、Random-Missing Modality (RMM)、Noisy Modality (NM)の3つのシナリオでMMSSモデルを評価する頑健性ベンチマークを導入する。
  論文  参考訳（メタデータ） (2025-03-24T08:46:52Z)
• FinTSB: A Comprehensive and Practical Benchmark for Financial Time Series Forecasting [58.70072722290475]
  ファイナンシャル・タイム・シリーズ(FinTS)は、人間の脳を増強した意思決定の行動を記録する。 FinTSBは金融時系列予測のための総合的で実用的なベンチマークである。
  論文  参考訳（メタデータ） (2025-02-26T05:19:16Z)
• Pushing the Frontier on Approximate EFX Allocations [14.101164748526159]
  本研究では, 付加的評価関数を持つエージェント群に対して, 分割不可能な商品群を割り当てる問題について検討する。 正確なEFXアロケーションが存在することが分かっている設定の厳密な一般化のために、我々は存在結果を得る。 この結果から, 近似EFXアロケーションの存在と計算のフロンティアを推し進めることができた。
  論文  参考訳（メタデータ） (2024-06-18T09:01:37Z)
• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。 適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
  論文  参考訳（メタデータ） (2024-05-24T11:22:19Z)
• EFX Allocations Exist for Binary Valuations [0.0]
  公正な分割問題と公平な基準を満たす割り当ての存在について、あらゆる項目(EFX)まで検討する。 全く異なる手法を用いることで、この存在を必ずしも部分モジュラーでない一般二項評価にまで拡張する。 EFXアロケーションを計算するための時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-10T11:28:31Z)
• Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations [20.774185319381985]
  本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。 我々は、レキシミンとMNWの割り当てが1つの利益まで自由になされることは保証されていないことを示す。
  論文  参考訳（メタデータ） (2023-02-06T19:41:28Z)

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

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