2025-11-17T18:43:12.758371

Fair and Efficient Allocation of Indivisible Mixed Manna

Barman, HV, Sethia et al.
We study fair division of indivisible mixed manna (items whose values may be positive, negative, or zero) among agents with additive valuations. Here, we establish that fairness -- in terms of a relaxation of envy-freeness -- and Pareto efficiency can always be achieved together. Specifically, our fairness guarantees are in terms of envy-freeness up to $k$ reallocations (EFR-$k$): An allocation $A$ of the indivisible items is said to be EFR-$k$ if there exists a subset $R$ of at most $k$ items such that, for each agent $i$, we can reassign items from within $R$ (in $A$) and obtain an allocation, $A^i$, which is envy-free for $i$. We establish that, when allocating mixed manna among $n$ agents with additive valuations, an EFR-$(n-1)$ and Pareto optimal (PO) allocation $A$ always exists. Further, the individual envy-free allocations $A^i$, induced by reassignments, are also PO. In addition, we prove that such fair and efficient allocations are efficiently computable when the number of agents, $n$, is fixed. We also obtain positive results focusing on EFR by itself (and without the PO desideratum). Specifically, we show that an EFR-$(n-1)$ allocation of mixed manna can be computed in polynomial time. In addition, we prove that when all the items are goods, an EFR-${\lfloor n/2 \rfloor}$ allocation exists and can be computed efficiently. Here, the $(n-1)$ bound is tight for chores and $\lfloor n/2 \rfloor$ is tight for goods. Our results advance the understanding of fair and efficient allocation of indivisible mixed manna and rely on a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) Theorem in discrete fair division. We utilize weighted welfare maximization, with perturbed valuations, to achieve Pareto efficiency, and overall, our techniques are notably different from existing market-based approaches.
academic

不可分割混合マナの公正かつ効率的配分

基本情報

  • 論文ID: 2507.03946
  • タイトル: Fair and Efficient Allocation of Indivisible Mixed Manna
  • 著者: Siddharth Barman (インド科学大学院)、Vishwa Prakash HV (チェンナイ数学研究所)、Aditi Sethia (インド科学大学院)、Mashbat Suzuki (UNSW Sydney)
  • 分類: cs.GT (コンピュータサイエンス - ゲーム理論)
  • 発表日: 2025年10月15日 (arXiv プレプリント第2版)
  • 論文リンク: https://arxiv.org/abs/2507.03946v2

要旨

本論文は、加法的評価を有するエージェント間における不可分割混合マナ(mixed manna)の公正配分問題を研究する。混合マナとは、価値が正、負、またはゼロである可能性のある物品を指す。論文は、公正性(嫉妬フリー性の緩和に基づく)とパレート効率が同時に達成可能であることの理論的保証を確立する。具体的には、公正性の保証は「k回の再配分による嫉妬フリー性」(EFR-k)の概念に基づいている。分配Aが EFR-k であるとは、最大k個の物品からなる部分集合Rが存在し、各エージェントiに対して、R内の物品を再配分することでエージェントiに対する嫉妬フリー配分A^iが得られる場合である。

研究背景と動機

問題定義

公正配分は、財産分割、タスク割り当て、境界紛争、債務配分など、現実のシナリオで頻繁に生じる問題である。参加するエージェントが個人的な選好を有する場合、「誰が何を得るか」という問題は、実用的な緊急性と理論的豊かさの両方を備えている。

研究上の課題

  1. 混合マナの複雑性: 純粋な商品(goods)または家事(chores)とは異なり、混合マナでは物品の価値の符号がエージェント間で異なる可能性があり、配分をより複雑にする。
  2. 公正性と効率のトレードオフ: 不可分割物品の設定では、従来の嫉妬フリー性(envy-freeness)の存在が保証されないため、適切な緩和条件を探す必要がある。
  3. 既存手法の限界:
    • 家事配分では、4つのエージェントの場合でさえ、EF1とパレート最適配分の存在性が未解決である
    • 混合マナの場合、この問題は3つのエージェントの場合でも開放されている
    • 既存の市場ベースの手法は、評価が負の場合に直接拡張できない

研究の動機

論文は、EFR-k概念の導入を通じて、混合マナの公正かつ効率的配分に対する理論的保証を提供し、効果的な計算アルゴリズムを開発することを目指している。

主要な貢献

  1. 理論的存在性保証: 加法的評価を有するn個のエージェントの混合マナ配分に対して、EFR-(n-1)かつパレート最適な配分が常に存在することを証明した。
  2. アルゴリズム計算可能性: エージェント数nが固定されている場合、多項式時間内でEFR-(n-1)かつパレート最適な配分を計算できる。
  3. 独立したEFR結果:
    • 混合マナのEFR-(n-1)配分は多項式時間内で計算可能
    • すべての物品が商品である場合、EFR-⌊n/2⌋配分が存在し、効率的に計算可能
  4. タイト性結果:
    • 家事の場合、(n-1)の界はタイトである
    • 商品の場合、⌊n/2⌋の界はタイトである
  5. 技術的革新: 離散公正配分において、Knaster-Kuratowski-Mazurkiewicz (KKM)定理を初めて適用した。

方法論の詳細

タスク定義

入力:

  • n個のエージェント、記号n = {1,...,n}
  • m個の不可分割物品、記号m = {1,...,m}
  • 加法的評価関数{vi}i∈n、ここでvi(t) ∈ ℝはエージェントiの物品tに対する評価

出力: 配分A = (A1,...,An)、ここでAi ⊆ mはエージェントiに配分された物品の集合

目標: EFR-kとパレート最適性の両方を満たす配分を見つける

中核概念

EFR-k の定義

配分AがEFR-kであるとは、当且つ当該の場合のみ、大きさが最大kである部分集合R ⊆ mが存在し、各エージェントiに対して、R内の物品を再配分することでエージェントiに対する嫉妬フリー配分A^iが得られる。

主要な技術的構成要素

  1. 評価の摂動: 非退化条件を得るため、与えられた評価に十分に小さい加法的摂動を追加する:
    v̄i(t) = vi(t) - εi,t

    ここでεi,tは(0,ε)から均一にランダムに抽出される。
  2. 重み付けオフセット: 各重みベクトルw ∈ Δn-1に対して、各成分をオフセットパラメータη > 0でシフトする:
    SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
  3. KKM被覆: 各エージェントiに対して、集合を定義する
    Ci := {w ∈ Δn-1 : ある配分Xi ∈ Oη(w)が存在し、iはXiの下で嫉妬フリーである}

主要なアルゴリズムフレームワーク

定理3.1の証明戦略

  1. 摂動評価の構成: 非退化性質を確保する
  2. KKM被覆の定義: KKM条件を満たす閉集合族{Ci}を構成する
  3. KKM定理の適用: 交集合w* ∈ ∩i Ciを得る
  4. 計数論証: 再配分集合Rのサイズが最大n-1であることを証明する

アルゴリズム1: 商品の競合認識選択シーケンス

純粋な商品の場合、ラウンドロビンベースのアルゴリズムが設計されている:

  • 競合解決フェーズ: 複数のエージェントが最も好む同じ商品を特定し、再配分集合Rに追加する
  • 選択フェーズ: アクティブなエージェントが辞書順で最も好む商品を選択する

技術的革新点

  1. KKM定理の新しい応用: 古典的なKKM定理を離散公正配分問題に初めて適用し、既存の市場ベースの手法とは完全に異なる技術的経路を提供した。
  2. 摂動技術: 慎重に設計された評価摂動を通じて非退化性を確保し、加重社会福祉最大化問題が良好な性質を持つようにする。
  3. 計数論証: 二部グラフの非環性を利用して、再配分集合のサイズ界限を証明する。

実験設定

理論分析フレームワーク

これは理論論文であるため、主に経験的実験ではなく数学的証明を通じて結果を検証する。論文は以下の分析フレームワークを採用している:

  1. 存在性証明: KKM定理を使用してEFR-(n-1)とPO配分の存在性を証明する
  2. タイト性分析: 反例を構成して界限のタイト性を証明する
  3. アルゴリズム複雑性: アルゴリズムの時間複雑性を分析する

複雑性分析

  • 固定エージェント数: EFR-(n-1)とPO配分はm^poly(n)時間内で計算可能
  • 一般的な場合: EFR-(n-1)配分は多項式時間内で計算可能
  • 商品の場合: EFR-⌊n/2⌋配分は多項式時間内で計算可能

実験結果

主要な理論的結果

定理3.1 (主要な存在性結果)

不可分割混合マナと加法的評価を有するすべての公正配分インスタンスは、EFR-(n-1)かつパレート最適な配分が存在する。

定理4.1 (計算可能性結果)

固定数のエージェントを有する混合マナ配分インスタンスに対して、多項式時間内でEFR-(n-1)かつパレート最適な配分を計算できる。

定理5.1 (EFR独立結果)

混合マナと加法的評価を有する公正配分インスタンスに対して、EFR-(n-1)とEF1の両方である配分が常に存在し、多項式時間内で計算可能である。

定理5.4 (商品の改善された界限)

純粋な商品の公正配分インスタンスに対して、アルゴリズム1は多項式時間内でEFR-⌊n/2⌋配分を計算する。

タイト性結果

定理5.2 (家事のタイト性)

EFR-(n-2)配分が存在しない家事配分インスタンスが存在し、(n-1)の界がタイトであることを証明する。

定理5.5 (商品のタイト性)

EFR-(⌊n/2⌋-1)配分が存在しない商品配分インスタンスが存在し、⌊n/2⌋の界がタイトであることを証明する。

計算複雑性結果

定理A.1 (判定問題の複雑性)

配分Aと正整数k < n-2が与えられたとき、AがEFR-kであるかどうかを判定することはNP完全である。

関連研究

公正配分の古典的理論

  • 可分割の場合: VarianとWellerの古典的結果は、嫉妬フリー性とPOが同時に実現可能であることを示している
  • 不可分割商品: EF1とPOの同時実現についての成熟した理論が存在する(Nash社会福祉最大化)

家事と混合マナの課題

  • 家事配分: 4つのエージェントの場合でさえEF1+POの存在性が未解決である
  • 混合マナ: 3つのエージェントのEF1+POの存在性は依然として開放問題である
  • 方法論的相違: 家事のEF1を保証するNash社会福祉のような関数は存在しない

関連する緩和概念

  • EF1: 1つの物品を除去することで嫉妬を排除する
  • EFX: 任意の物品を除去することで嫉妬を排除する
  • 分数配分: 最大(n-1)個の物品の分数配分による嫉妬フリー性

結論と考察

主要な結論

  1. 理論的ブレークスルー: 一般的な混合マナ設定に対して、公正性と効率の同時保証を初めて提供した
  2. 技術的革新: 離散公正配分におけるKKM定理の新しい応用は、新しい研究方向を切り開いた
  3. 実用的価値: アルゴリズム結果は実際の応用に対する計算基礎を提供する

限界

  1. 界限: EFR-(n-1)の界限は相対的に大きく、平均してエージェントあたり約2つの物品の再配分が必要である
  2. 固定エージェント仮定: 多項式時間アルゴリズムはエージェント数の固定を必要とする
  3. 加法的評価の制限: 結果は加法的評価関数にのみ適用可能である

今後の方向性

  1. 界限の改善: より小さい再配分集合Rを探索する
  2. 評価タイプの拡張: 非加法的評価関数を考慮する
  3. 実際の応用: 理論的結果を具体的な配分シナリオに適用する

深い評価

利点

  1. 理論的貢献が重大: 混合マナの公正かつ効率的配分の基本的問題を解決した
  2. 技術手段が新奇: KKM定理の応用は深い数学的洞察を示している
  3. 結果が包括的: 存在性とアルゴリズムの両方、上界と下界の両方を有する
  4. 証明が厳密: 数学的導出が完全で、技術的詳細が適切に処理されている

不足

  1. 実用性が限定的: EFR-(n-1)の界限は実際の応用では過度に大きい可能性がある
  2. 経験的評価の欠如: 理論論文として、実データでのパフォーマンス評価が不足している
  3. アルゴリズム効率: 固定エージェント数時のm^poly(n)複雑性は実践では高い可能性がある

影響力

  1. 学術的影響: 公正配分理論に重要な貢献をし、広く引用されることが予想される
  2. 方法論的価値: KKM定理の応用は、より多くの関連研究にインスピレーションを与える可能性がある
  3. 実用的見通し: 実際の配分システム設計に対する理論的基礎を提供する

適用シナリオ

  1. 遺産分割: 資産と債務を含む複雑な分割シナリオ
  2. タスク割り当て: 魅力的なタスクと魅力的でないタスクの両方を含む割り当て
  3. リソース管理: 収益と費用を同時に考慮する必要があるリソース配分問題

参考文献

論文は公正配分分野の重要な文献を引用しており、以下を含む:

  • Budish (2011): EF1概念の導入
  • Caragiannis et al. (2019): Nash社会福祉とEF1+POの関係
  • Aziz et al. (2022): 混合マナのEF1存在性
  • Sandomirskiy & Segal-Halevi (2022): 分数配分の関連結果

総評: これは高品質な理論論文であり、EFR概念の導入とKKM定理の適用を通じて、混合マナの公正かつ効率的配分に対する重要な理論的保証を提供している。実用性の面で一定の限界があるものの、その理論的貢献と技術的革新により、公正配分分野における重要な進展となっている。