技術要約：オプション付き販売を伴う公平な配分

問題の定義

本論文は、エージェントが財に対して主観的な評価関数を持つ一方で、財に外生的な市場価格が存在する設定における、不可分な財の公平な配分問題に取り組んでいる。従来の不可分な財の配分モデルでは、財は厳密に不可分であるが、この設定では「外部オプション」が導入されている。すなわち、エージェントは財を市場価格で売却することを選択できる。これらの売却から得られる収益は分割可能であり、すべてのエージェントに対して一様な加法的な価値を持つ。

核心となる課題は、以下の事項を同時に決定する配分メカニズムを設計することである：

1. どの財のサブセットを売却するか。
2. 残りの未販売の財をどのように配分するか。
3. 売却された財からの金銭的収益をどのように分配するか。

目的は、このハイブリッドな環境に合わせて標準的なシェアベースおよびエンヴィーベースの保証を適応させた公平性の概念を満たすことである。著者らは、財と金銭の両方に対して加法的な評価を仮定している。

公平性の概念

本論文は、2つのカテゴリーの公平性の定義を適応させている：

1. シェアベースの概念（Share-Based Notions）:

   • 最大最小シェア (MMS): エージェントが、どの財を売却するかを最適に決定し、その上で残りの財と収益を $n$ 個の束に分割した際、自身が受け取る最も価値の低い束の最大値として定義される。標準的なMMSとは異なり、エージェントは売却の決定と分割の両方を最適化する。
   • 切断比例シェア (TPS): 不可分な設定におけるTPSの概念を拡張したもので、すべての財について $\max\{p(g), \min\{v(g), t\}\}$ の和を $n$ で割った値が $t$ となるような最大の値 $t$ として定義される。

2. エンヴィーベースの概念（Envy-Based Notions）:

   • SEF1 および SEFX (Strong/Sellable Envy-Free): これらは EF1 および EFX の適応版である。配分が SEFX であるとは、任意のエージェント $i$ と他のエージェント $j$ について、$j$ が自身の持つ財の一つを保持する代わりに売却して市場価格を受け取ったとしても、$i$ が $j$ の束に対して羨望（エンヴィー）を感じないことを意味する。形式的には、すべての財 $g \in A_j$ について、$\bar{v}_i(A_i) + P_i \ge \bar{v}_i(A_j \setminus \{g\}) + p(g)$ が成立することである。ここで $\bar{v}_i(g) = \max\{v_i(g), p(g)\}$ である。

手法とアルゴリズム

著者らは、「カット＆チューズ（Cut & Choose）」、「バッグ・フィリング（Bag-Filling）」、「ローン・ディバイダー（Lone Divider）」パラダイムの変種を含む、多様なアルゴリズム的手法を用いている。これらは、オプション付きの販売による複雑さを扱うために修正されている。

• カット＆ギブ (n=2): 2人のエージェントの場合、著者らは「カット＆ギブ」プロトコルを導入している。一方のエージェント（カッター）が自身の MMS に基づいて分割案を提示する。もう一方のエージェント（ギバー）がその束を受け入れ可能であると判断すれば、それを受け取る。もし受け入れられない場合、ギバーは自身の意図していた財を売却し、カッターの売却を取り消すことで、両者の MMS と SEFX を満たす新しい束を作成し、分割を修正する。
• 仮想財を用いたバッグ・フィリング (TPS): $n/(2n-1)$-TPS を達成するために、アルゴリズムは「動くナイフ」のアプローチを使用する。市場価格が高い財は、エージェントの最小シェア要件を満たすために即座に売却される。残りの収益は「仮想的な財」として扱われる。その後、バッグ・フィリングの手順によって、エージェントが要求される閾値に達するまで束が配分される。
• 標準的な分割 (MMSのためのローン・ディバイダー): 一般的な $n$ に対して、著者らはローン・ディバイダー法を適応させている。主要な革新は、「最も高い MMS を持つエージェント」によって提案される「標準的な分割（canonical partitions）」の構築である。これらの分割は、「純粋な束（金銭なし）」、「シングルトン束（一つの財と、最大でもう一つの売却された財からの収益）」、および単一の「残り物（leftovers）」の束で構成される。この構造は、拒否された束が他の誰かに割り当てられた場合にエージェントが被る損失を制限し、強制的な売却による損失を限定的にする。
• 高価値アイテムの処理: アルゴリズムには、MMS 閾値を大幅に超える財を扱うための予備フェーズが含まれている。これらは、特定のエージェントを満たすために売却されるか、直接割り当てられ、残りの問題が近似フレームワークに適合するようにする。

主な結果

1. シェアとエンヴィーの結合保証

• 2人のエージェント ($n=2$): MMS と SEFX を同時に満たす配分が常に存在する。これは強力な結果である。なぜなら、$n \ge 3$ の標準的な設定では完全な MMS を達成することは一般に不可能であるが、ここでは SEFX という強いエンヴィーフリーの概念とともに MMS が達成されているためである。
• 一般のエージェント ($n \ge 2$): $n/(2n-1)$-TPS と SEFX を同時に満たす配分が存在する。比率 $n/(2n-1)$ は、SEFX の要件がない場合でも TPS の近似として最善であることが証明されている。

2. MMS 近似境界

• 3人のエージェント ($n=3$): 本論文は、販売がある設定とない設定の間の定量的なギャップを確立している。標準的な不可分設定（販売なし）では $n=3, m=8$ のアイテムに対して完全な MMS が保証される（既知の最良の境界は $39/40$）一方で、販売がある設定では、$11/12$-MMS を超える保証ができないインスタンスが存在する。
• 一般のエージェント ($n \ge 4$): 著者らは $2/3$-MMS 配分を提供する。これは、標準的な不可分設定（一部の先行研究で見られる $O(1/n)$ の加法的項がない設定）における既知の最良の近似比と一致している。
• 特殊なケース ($n=3$): 一般的な $n$ のアプローチと $n=2$ の完全 MMS アルゴリズムを組み合わせることで、著者らは 3 人のエージェントに対して $3/4$-MMS 配分を実現している。

3. 計算量

• MMS の計算: 正確な MMS 値を計算することは、$n=2$ では弱 NP 困難であり、一般的な $n$ では強 NP 困難である。しかし、本論文は以下を提供する：
  • 固定された $n$ に対する疑似多項式時間アルゴリズム。
  • MMS 値および分割を計算するための多項式時間近似スキーム (PTAS)。
• TPS の計算: TPS は多項式時間で効率的に計算可能である。
• 結合保証: $n/(2n-1)$-TPS かつ $\epsilon$-SEFX である配分に対する FPTAS が存在する。

4. 拡張

• 等価な収益: 本論文では、売却収益がすべてのエージェント間で等しく分配されなければならないという制限された設定を分析している。この場合、近似保証は $1/n$-TPS に低下し、MMS の保証は無制限の場合よりも著しく弱くなる可能性がある。
• アウトソーシングを伴う不快な仕事 (Chores): モデルは、エージェントが市場コストでタスクを「アウトソース」できる不快な仕事（負の評価）へと拡張されている。結果は財の設定を反映しており、2-MMS 近似が可能であるが、標準的な不可分な chores 設定よりも近似のギャップは大きくなっている。

意義と主張

本論文は、市場の選択肢が利用可能な場合の公平な配分に関する「両者の最善（Best of Both Worlds）」の枠組みを提供することを主張している。その主な貢献は以下の通りである：

1. 理論的ギャップの特定: 販売オプションの導入は、実現可能な結果の集合を拡大させる一方で、純粋な不可分設定と比較して、特定の公平性の保証（特に MMS）の近似をより困難にすること（具体的には $n=3$ の場合）を実証している。
2. 堅牢なアルゴリズム: 販売の決定を最適化するという追加の複雑さがあるにもかかわらず、最良の MMS 近似比を回収することに成功した、新しいアルゴalgorithmic手法（標準的な分割、修正されたローン・ディバイダー）を開発している。
3. 統一された公平性: 高品質なシェア近似が、この設定において強いエンヴィーフリーの概念を排除しないことを示し、シェアベースの保証（MMS/TPS）と強いエンヴィーフリーの概念（SEFX）を単一の配分の中に統合することに成功している。

著者らは、彼らの結果がいくつかのケース（例：TPS における $n/(2n-1)$ の境界）においてタイトであることを強調しており、負の結果（例：$n=3$ における $11/12$ のギャップ）は、現在のアルゴリズムの限界ではなく、モデル自体の証明可能な限界であることを示している。