公平なアイテムの割り当て

公平なアイテムの割り当ては、分割するアイテムが連続的ではなく離散的である公平な分割問題の一種です。アイテムは、異なる価値を持つ可能性のある複数のパートナー間で分割する必要があり、各アイテムは1人の人にまとめて渡される必要があります。^[1]この状況は、さまざまな現実のシナリオで発生します。

• 複数の相続人が、例えば家、車、ピアノ、絵画数点などを含む相続財産を分割したいと考えています。
• 複数の講師が自分の学部で開講するコースを分割したいと考えています。各講師は 1 つまたは複数のコース全体を教えることができます。
• ホワイトエレファントギフト交換パーティー

アイテムが分割不可能であるということは、公平な分割が不可能な場合があることを意味します。極端な例として、アイテムが 1 つしかない場合 (たとえば、家)、そのアイテムは 1 人のパートナーに渡される必要がありますが、これは他のパートナーにとって公平ではありません。これは、配当が分割可能で常に公平な分割が存在する公平なケーキカット問題とは対照的です。場合によっては、金銭の支払いや時間ベースのローテーションを導入するか、アイテムの一部を破棄することで、分割不可能な問題を軽減できます。^{[2] : 285}しかし、そのような解決策は常に利用できるとは限りません。

アイテム割り当て問題にはいくつかの要素があります。

1. パートナーは、さまざまなアイテムバンドルに対する好みを表明する必要があります。
2. グループは公平性の基準を決定する必要があります。
3. 優先順位と公平性の基準に基づいて、公平な割り当てアルゴリズムを実行し、公平な分割を計算する必要があります。

これらの成分については以下で詳しく説明します。

好みを決定する単純な方法は、各パートナーに、各可能なバンドルの数値を提供するように依頼することです。たとえば、分割するアイテムが車と自転車である場合、パートナーは車を 800、自転車を 200、バンドル {車、自転車} を 900 と評価するかもしれません (その他の例については、 「分割できない商品の効用関数」を参照してください)。このアプローチには 2 つの問題があります。

1. バンドルの正確な数値を計算することは難しいかもしれません。
2. 可能なバンドルの数は膨大になる可能性があります。アイテムがあれば、可能なバンドルの数も膨大になります。たとえば、アイテムが 16 個ある場合、各パートナーは 65536 個の数字を使用して自分の好みを提示する必要があります。${\displaystyle m}$${\displaystyle 2^{m}}$

最初の問題は、基数効用ではなく順序効用を使用する動機となります。順序モデルでは、各パートナーはさまざまなバンドルに対するランキング、つまりどのバンドルが最良で、どのバンドルが 2 番目に良いかなどのみを表現する必要があります。これは正確な数値を計算するよりも簡単かもしれませんが、アイテムの数が多い場合は依然として困難です。 ${\displaystyle 2^{m}}$

2 番目の問題は、バンドルではなく個々のアイテムを扱うことで対処されることがよくあります。

• カーディナルアプローチでは、各パートナーは各項目の数値評価を報告する必要があります。
• 順序アプローチでは、各パートナーは項目の順位、つまりどの項目が最も優れているか、どの項目が 2 番目に優れているかなどを報告する必要があります。

適切な仮定の下では、アイテムに対する選好をバンドルに対する選好に 引き上げることが可能である。 ^{[3] ：44〜48}次に、エージェントは個々のアイテムに対する評価/ランキングを報告し、アルゴリズムはバンドルに対する評価/ランキングを計算する。

品目割り当て問題をより簡単にするために、すべての品目が独立した財（代替財でも補完財でもない）であると仮定するのが一般的です。 ^[4] すると、

• カーディナルアプローチでは、各エージェントは加法的効用関数（モジュラー効用関数とも呼ばれます）を持ちます。エージェントが各アイテムの値を報告すると、そのアイテムの値を合計することで各バンドルの値を簡単に計算できます。
• 順序論的アプローチでは、加法性によってバンドル間の順位付けを推測することができます。たとえば、ある人が w を x より y より z を好む場合、その人は必然的に {w,x} を {w,y} または {x,y} より、また {w,y} を {x} より好みます。この推測は部分的なものであり、たとえば、エージェントが {w} を {x,y} より好むのか、あるいは {w,z} を {x,y} より好むのかを知ることはできません。^{[5] [6]}

加法性は、各パートナーがテーブル上のアイテムの集合から「好ましいアイテム」を常に選択できることを意味し、この選択はパートナーが持つ他のアイテムとは独立しています。この特性は、次に説明するいくつかの公平な割り当てアルゴリズムで使用されます。^{[2] : 287–288}

コンパクトな選好表現言語は、組み合わせ選好の完全な表現力と加法選好の単純さの間の妥協点として開発されました。これらは、加法効用よりも一般的な（ただし、組み合わせ効用ほど一般的ではない）効用関数のいくつかの自然なクラスを簡潔に表現します。いくつかの例を以下に示します。^{[2] : 289–294}

• 2 加法嗜好: 各パートナーは、最大 2 のサイズの各バンドルの値を報告します。バンドルの値は、バンドル内の個々のアイテムの値を合計し、バンドル内のペアの値を加算することによって計算されます。通常、代替アイテムがある場合、ペアの値は負になり、補完アイテムがある場合、ペアの値は正になります。この考え方は、すべての正の整数kに対するk 加法嗜好に一般化できます。
• グラフィカル モデル: 各パートナーには、異なる項目間の依存関係を表すグラフがあります。カーディナル アプローチでは、GAI ネット(一般化加法独立性) が共通のツールです。順序アプローチでは、CP ネット(条件付き好み) とその拡張であるTCP ネット、UCP ネット、CP 理論、CI ネット(条件付き重要度)、およびSCI ネット(CI ネットの簡略化) が共通のツールです。
• ロジックベースの言語: 各パートナーは、 1 階の論理式を使用していくつかのバンドルを記述し、各式に値を割り当てることができます。たとえば、パートナーは次のように言うことができます: 「(x または (y および z)) の場合、私の値は 5 です」。これは、エージェントがバンドル x、xy、xz、yz、xyz のいずれかに対して 5 の値を持つことを意味します。
• 入札言語:組み合わせオークションの文脈では、組み合わせの好みを表現するための多くの言語が研究されてきました。これらの言語のいくつかは、アイテムの割り当て設定に適応できます。

個人保証基準とは、パートナーが自分の好みを正直に申告する限り、各パートナーに適用される基準である。以下に5つの基準を示す。これらは、最も弱いものから最も強いものの順に並べられている（評価は加算的であると仮定）。^[7]

エージェントの最大最小シェア（最大最小公平シェア保証とも呼ばれる）は、敵対的な相手に対して分割選択において分割者として保証できる最も好ましいバンドルである。すべてのエージェントが自分のMMSよりも弱く好むバンドルを受け取る場合、その割り当てはMMS公平と呼ばれる。^[8]

エージェントの比例公平分配は、アイテムセット全体からの効用の 1/ nです。すべてのエージェントが少なくとも比例公平分配の価値があるバンドルを受け取る場合、 割り当ては比例的であると呼ばれます。

エージェントの最小最大公平シェアとは、他のすべてのエージェントが彼女と同じ好みを持ち、常に最高のシェアを受け取る場合に、そのエージェントが割り当てから得ることが期待できる最小の効用である。これは、割り当てゲーム「誰かがカットしたら、私が最初に選択する」でエージェントが確実に得ることができる最小の効用でもある。すべてのエージェントが自分の mFS よりも弱く好むバンドルを受け取る場合、割り当てはmFS 公平である。 ^[7] mFS 公平性は、次の交渉プロセスの結果として説明できます。特定の割り当てが提案されます。各エージェントは、別のエージェントに別の割り当てが行われ、最初に選択できるように要求することで、それに異議を唱えることができます。したがって、エージェントは、すべてのパーティションで現在のバンドルよりも強く好むバンドルがある場合のみ、割り当てに異議を唱えます。割り当てが mFS 公平であるためには、どのエージェントもそれに異議を唱えない場合、つまり、すべてのエージェントについて、すべてのバンドルが現在のシェアよりも弱く悪いパーティションが存在する必要があります。

劣加法的な効用を持つすべてのエージェントにとって、mFS は少なくとも の 価値があります。したがって、すべての mFS 公平な割り当ては比例的です。超加法的な効用を持つすべてのエージェントにとって、MMS は最大 の価値があります。したがって、すべての比例割り当ては MMS 公平です。すべてのエージェントが加法的な効用を持つ場合でも、両方の包含は厳密です。これは次の例で示されています。^[7]${\displaystyle 1/n}$ ${\displaystyle 1/n}$

エージェントは 3 つ、アイテムは 3 つあります。

• アリスはアイテムを 2,2,2 と評価します。彼女にとって、MMS=PFS=mFS=2 です。
• ボブはアイテムを 3、2、1 と評価します。彼にとって、MMS=1、PFS=2、mFS=3 です。
• カールは、項目を 3、2、1 と評価します。彼にとって、MMS=1、PFS=2、mFS=3 です。

可能な割り当ては次のとおりです。

• 各エージェントにアイテムを与えるすべての割り当ては MMS 公平です。
• 最初の項目と 2 番目の項目を Bob と Carl に、3 番目の項目を Alice に与えるすべての割り当ては比例します。
• どの割り当ても mFS 公平ではありません。

上記の意味合いは、エージェントの評価が部分加法/超加法的でない場合は当てはまりません。^[9]

すべてのエージェントは、自分のバンドルを他のバンドルよりも弱く好みます。すべてのアイテムの羨望のない割り当ては、mFS公平です。これは順序定義から直接導かれ、​​加法性に依存しません。評価が加法性である場合、EF割り当ても比例的でMMS公平です。そうでない場合、EF割り当ては比例的ではなく、MMSでもない可能性があります。^[9]

EFの弱いバージョンには以下のものがある: ^[10]

• 羨望フリーネス 例外 1 (EF1) : 2 人のエージェント A と B それぞれについて、B のバンドルから A にとって最も価値のあるアイテムを削除すると、A は B を羨ましがらなくなります (言い換えると、B における A の「羨望レベル」は、最大で 1 つのアイテムの価値です)。単調性の下では、EF1 割り当てが常に存在します。
• 最も安いもの以外は羨望の的にならないこと (EFx) : 2 人のエージェント A と B それぞれについて、B のバンドルからA にとって最も価値のないアイテムを削除すると、A は B を羨ましがらなくなります。EFx は EF1 よりも厳密に強力です。EFx の割り当てが常に存在するかどうかは不明です。

この基準は、次のような議論に基づいています。割り当てプロセスは、供給（それぞれが公的な価格を持つオブジェクトのセット）と需要（エージェントの欲求、各エージェントがオブジェクトを購入するための同じ予算を持っている）の間の均衡の探索として考えるべきである。供給が需要に一致すると、競争均衡が達成されます。公平性の議論は単純明快です。価格と予算は誰にとっても同じです。CEEIは、加法性に関係なくEFを意味します。エージェントの好みが加法的で厳密な場合（各バンドルが異なる価値を持つ）、CEEIはパレート効率性を意味します。^[7]

グローバル最適化基準は、与えられた社会福祉関数に基づいて分割を評価します。

• 平等主義的社会福祉は、単一のエージェントの最小効用です。アイテムの割り当ては、最大限の平等主義的福祉を達成する場合、つまり最も貧しいエージェントの効用を最大化する場合、平等主義最適と呼ばれます。最小の効用を最大化する割り当ては複数存在する可能性があるため、平等主義最適性は、多くの場合、レキシミン最適性に洗練されます。つまり、最小の効用を最大化する割り当てのサブセットから、2 番目に小さい効用を最大化する割り当てを選択し、次に 3 番目に小さい効用を最大化する割り当てを選択します。
• ナッシュ社会福祉は、エージェントの効用の積です。効用の積を最大化する割り当ては、ナッシュ最適または最大ナッシュ福祉と呼ばれます。ナッシュ最適割り当てには、いくつかの優れた公平性があります。^[10]

全体最適化基準が個別基準よりも優れている点は、福祉を最大化する配分がパレート効率的であることです。

公平なアイテム割り当てのためのさまざまなアルゴリズムについては、特定の公平性基準に関するページで調査されています。

• 最大シェアアイテム割り当て;
• 比例項目割り当て;
• ミニマックスシェアアイテム割り当て：エージェントのmFSを計算する問題はcoNP完全です。mFS割り当てが存在するかどうかを決定する問題は にありますが、その正確な計算量はまだ不明です。^[7]${\displaystyle NP^{NP}}$
• 羨望のないアイテム割り当て;
• 効率的でほぼ公平なアイテム割り当て。
• 平等なアイテム割り当て;
• ナッシュ最適配分：^[11]と^[12]は、功利最適配分とナッシュ最適配分を計算することの難しさを証明している。^[13]は、ナッシュ最適配分の近似手順を提示している。
• 選択シーケンス: エージェントが事前に指定された順番に基づいて順番にアイテムを選択する単純なプロトコル。目標は、エージェントの評価に関するいくつかの確率的仮定の下で、社会福祉関数 (平等主義または功利主義など) の期待値を最大化する方法で選択シーケンスを設計することです。
• 競争均衡: CE 割り当てを見つけるためのさまざまなアルゴリズムについては、 Fisher 市場に関する記事で説明されています。

公平な配分に関する従来の論文では、すべての項目が分割可能であるか、またはすべての項目が分割不可能であるかのいずれかを前提としています。最近の論文の中には、分割可能と分割不可能の区別がより曖昧な設定を研究しているものもあります。

いくつかの研究では、すべてのオブジェクトは必要に応じて分割できると想定されています (たとえば、共有所有権またはタイムシェアリング)。しかし、共有はコストがかかったり、望ましくない場合があります。したがって、共有オブジェクトまたは共有の数を最小限に抑えた公平な割り当てを見つけることが望まれます。n エージェント間のさまざまな種類の公平な割り当てに必要な共有オブジェクト / 共有の数には、厳しい上限があります。

• 比例的、嫉妬のない、公平で平等な分配では、 n −1の共有/共有オブジェクトは常に十分であり、必要となる場合もある。^[14]
• コンセンサスをk個の部分に分割する場合、n（n −1）個の共有/共有オブジェクトで十分であり、必要になる場合もある。^[15]

これにより、最悪の上限よりも少ない共有で公平な割り当てを達成できるかどうかという疑問が生じます。

• Sandomirskiy と Segal-Halevi ^{[14]は、公平かつ}部分的パレート効率(fPO)な割り当てにおける共有の最小化を研究しています。彼らは、エージェントの評価が非退化である場合、fPO 割り当ての数はオブジェクトの数の多項式であることを証明しています (エージェントの数は固定されています)。したがって、多項式時間でそれらすべてを列挙し、共有数が最小の公平で fPO な割り当てを見つけることができます。対照的に、評価が退化している場合、問題は NP 困難になります。彼らは、現実的なケースでは、最悪のケースの境界よりも共有数が大幅に少ない割り当てが頻繁に存在するという経験的証拠を示しています。
• ミスラとセシア^[16]は、 nが固定されていない場合、非退化評価であっても、共有数が0のfPO羨望のない割り当てが存在するかどうかを判断することはNP困難であることを証明することで、彼らの結果を補完しています。彼らはまた、共有数が少ない割り当てに対して、異なる消費グラフを列挙する別のアプローチを示しています。
• Goldberg、Hollender、Igarashi、Manurangsi、およびSuksompong ^[15]は、コンセンサス分割における共有最小化を研究している。彼らは、加法的な効用を持つエージェントの場合、最大でnの共有でコンセンサス半減を計算する多項式時間アルゴリズムと、最大で( k −1) nのカットを持つコンセンサスk分割を計算するアルゴリズムが存在することを証明している。しかし、共有最小化はNP困難である。つまり、任意の固定されたnに対して、 nの共有を必要とするインスタンスと0の共有を必要とするインスタンスを区別することはNP困難である。確率的には、エージェントの効用が確率分布から引き出されるとき、コンセンサス半減にはnの共有がほぼ確実に必要である。非加法的な単調な効用を持つエージェントの場合、コンセンサス半減はPPAD困難であるが、固定数のエージェントに対しては多項式時間アルゴリズムが存在する。
• Bismuth、Makarov、Shapira、Segal-Halevi ^{[17]は、同一評価による公平な割り当てを研究している。これは、}同一マシン スケジューリングと同等であり、より一般的な設定の均一マシン スケジューリングでもある。彼らは、s 個の共有または共有オブジェクトによる公平な割り当ての存在を決定する実行時の複雑性を研究している。ここで、s は最悪の上限であるn −1 より小さい。彼らは、共有の場合、問題はs ≤ n −2 に対して NP 困難であることを証明している。しかし、共有オブジェクトとn ≥ 3の場合、問題はs = n −2 に対して多項式であり、 s ≤ n −3に対して NP 困難である 。nが固定されていない場合、問題は強く NP 困難である。

• Bei、Li、Liu、Liu、およびLu ^{[18]は、分割不可能な}財と分割可能な財（正の効用を持つオブジェクト）の混合を研究しています。彼らは、 EFM （混合アイテムの羨望のなさ）と呼ばれる羨望のなさの近似を定義し、これは分割可能な財の羨望のなさおよび分割不可能な財のEF1の両方を一般化します。彼らは、加算的評価を持つエージェントの数に関係なく、EFM割り当てが常に存在することを証明しています。彼らは、一般的な加算的評価を持つ2つのエージェントと、分割可能な財に対して区分線形評価を持つn人のエージェントのEFM割り当てを計算する効率的なアルゴリズムを提示しています。また、イプシロン近似のEFM割り当てを見つける効率的なアルゴリズムも提示しています。
• Bei、Liu、Lu、Wang ^[19]は、同じ設定で、最大シェア公平性に焦点を当てて研究しています。彼らは、任意の数のエージェントに対してアルファ近似MMS割り当てを計算するアルゴリズムを提案しています。ここで、アルファは1/2から1の間の定数であり、MMS値に対する分割可能財の価値とともに単調に増加します。
• Bhaskar、Sricharan、Vaish ^[20]は、分割不可能な家事（負の効用を持つオブジェクト）と分割可能なケーキ（正の効用を持つ）の混合を研究しています。彼らは、2つの特別なケース、つまり各エージェントが家事セットに対して同じ優先順位を持っている場合と、アイテムの数が最大でエージェントの数に1を加えた数である場合のEFM割り当てを見つけるためのアルゴリズムを提示しています。
• Li、Liu、Lu、Tao ^{[21]は、EFMの}誠実なメカニズムを研究している。彼らは、一般に、分割不可能な財と分割可能な財が1つしかなく、エージェントが2人しかいない場合でも、誠実なEFMアルゴリズムは存在しないことを示している。しかし、エージェントが分割不可能な財に対して2値評価を持ち、単一の分割可能な財に対して同一の評価を持つ場合、EFMと誠実なメカニズムが存在する。エージェントが分割可能財と分割不可能な財の両方に対して2値評価を持つ場合、エージェントが2人だけの場合、または分割可能な財が1つの場合は、EFMと誠実なメカニズムが存在する。
• 西村と澄田^[22]は、混合財に対する最大ナッシュ福祉配分（MNW）の特性を研究している。彼らは、すべてのエージェントの評価が各財に対して2値かつ線形である場合、MNW配分はEFMよりも強い特性を満たすことを証明しており、これを「混合財に対するあらゆる財に対する羨望のなさ」と呼んでいる。彼らの結果は、最大ナッシュ福祉だけでなく、対称な厳密な凸関数を最小化することに基づく一般的な公平性の概念にも当てはまる。一般的な加法的な評価については、MNW配分はEFMよりも弱いEF近似を満たすことを証明している。
• 川瀬、西村、澄田^{[23]は、混合財の}最適配分を研究しており、ここで効用ベクトルは対称な厳密凸関数を最小化する必要がある（これは平等主義的アイテム配分と最大ナッシュ福祉の一般化である）。彼らは、すべてのエージェントが2値評価を持っていると仮定している。分割可能な財のみ、または分割不可能な財のみが存在する場合、この問題は多時間で解けることが知られている。彼らは、混合財の場合、分割不可能な財がすべて同一であっても、問題はNP困難であることを示している。対照的に、分割可能な財がすべて同一である場合、多時間アルゴリズムが存在する。
• Bei、Liu、Lu ^[24]は、同じオブジェクトが一部のエージェントにとっては分割可能で、他のエージェントにとっては分割不可能である可能性がある、より一般的な設定を研究しています。彼らは、MMSの最良の近似値は、エージェントが2つの場合でも2/3であることを示し、2つまたは3つのエージェントでこの境界を達成するアルゴリズムを提示しています。エージェントの数に関係なく、彼らは1/2-MMS近似値を提示しています。彼らはまた、EFMが無駄のなさと一致しないことも示しています。
• Li、Li、Liu、Wu ^[25]は、各エージェントが異なる「不可分比率」（= 不可分なアイテムの割合）を持つ可能性がある設定を研究しています。各エージェントには、アイテムの一部までEF/PROPの割り当てが保証され、その部分はエージェントの不可分比率に依存します。結果は、EFについては定数までタイトで、PROPについては漸近的にタイトです。
• Li、Liu、Lu、Tao、Tao ^[26]は、不可分なアイテム割り当てと混合アイテム割り当ての両方における公平性の価格を研究しています。彼らはEF1、EFx、EFM、EFxMの価格の境界を示しています。彼らは、スケールされた効用とスケールされていない効用の両方について、2人のエージェントに対しては厳密な境界を、 n人のエージェントに対しては漸近的に厳密な境界を示しています。

Liu、Lu、Suzuki、Walsh ^[27]は、混合項目に関する最近の研究結果を調査し、いくつかの未解決の疑問を特定した。

1. EFM はパレート効率と互換性がありますか?
2. EFM 配分の中で功利主義的社会福祉を最大化するための効率的なアルゴリズムはありますか?
3. Robertson–Webb クエリ モデルで EFM 割り当てを計算するための、制限付きまたは有限のアルゴリズムはありますか?
4. 分割できない家事とケーキがある場合、常に EFM 割り当てが存在するのでしょうか?
5. より一般的には、分割可能な項目と分割不可能な項目の両方が一部のエージェントにとってはプラスで、他のエージェントにとってはマイナスになる可能性がある場合、EFM 割り当ては常に存在するのでしょうか。
6. バイナリ加法評価を持つエージェントに真実の EFM アルゴリズムはありますか?

このバリエーションでは、異なるエージェントが異なる割合の資源を受け取る権利を持つ。一般的な使用例は、連立政権内の政党間で内閣の省庁を分割することである。^[28]各政党は議会での議席数に応じて省庁を受け取るべきであると想定するのが一般的である。さまざまな公平性の概念はそれに応じて適応されなければならない。いくつかの種類の公平性の概念が検討された。

• 加重競争均衡に基づく概念^{[29] [30]}
• 重み付けされた嫉妬のなさに基づく概念。^{[31] [32] [33]}
• 加重公平配分に基づく概念^[34]

このバリアントでは、バンドルは個々のエージェントではなく、エージェントのグループに与えられます。一般的な使用例は、家族間での相続の分割、または大学の部門間での施設の分割です。同じグループ内のすべてのエージェントは同じバンドルを消費しますが、その価値は異なる場合があります。従来のアイテム割り当て設定は、すべてのグループがシングルトンである特殊なケースに対応します。

グループの場合、全員一致の公平性（各グループのすべてのエージェントの目から見た公平性）を保証することは不可能な場合があり、そのため、民主的な公平性（各グループの少なくとも半数のエージェントの目から見た公平性）に緩和されることが多い。^[35]

このバリエーションでは、各アイテムは単一のエージェントだけでなくすべてのエージェントに効用を提供します。異なるエージェントは、同じアイテムに異なる効用を付与する場合があります。グループは、次のようないくつかの制約を満たすアイテムのサブセットを選択する必要があります。

• 選択できるのは最大でk個の項目です。この変種は複数勝者投票と密接に関連していますが、複数勝者投票では選出される候補者の数が通常投票者の数よりはるかに少ないのに対し、公共財の配分では選択される財の数が通常エージェントの数よりはるかに多いという点が異なります。一例として、読者の好みを尊重してどの本を購入するかを決定する必要がある公共図書館が挙げられます。この場合、本の数は読者の数より通常はるかに多くなります。^[36]
• すべての項目の合計コストは、固定予算を超えてはなりません。この方法は、参加型予算編成としてよく知られています。
• アイテムの数は可能な限り少なくする必要がありますが、選択されたセットは選択されなかったセットよりも優れていることにすべてのエージェントが同意する必要があります。このバリエーションは、合意可能なサブセット問題として知られています。
• 選択された集合には、一般的なマトロイド制約、マッチング制約、ナップサック制約が存在する可能性がある。 ^[37]

私的財の配分は、公共財の配分の特別なケースと見ることができます。つまり、n人のエージェントとm個のアイテムを持つ私的財の問題が与えられ、エージェントiはアイテムjをv _{ijと評価するとします。次に、} n · m 個のアイテムを持つ公共財の問題を構築します。ここで、エージェントi は各アイテムi,j をv _ijと評価し、他のアイテムを 0 と評価します。アイテムi,j は、基本的にアイテムj をエージェントiに与える決定を表します。この考え方は、最大ナッシュ福祉配分を維持する私的財の配分から公共財の配分への一般的な縮小、およびレキシミン最適配分を維持する同様の縮小を示すために形式化できます。^[36]

公共財配分の一般的な解決概念としては、中核安定性（パレート効率と比例性の両方を意味する）^{[37] 、最大ナッシュ福祉、レキシミン最適性、1つの品目までの比例性[36]など}がある。

このバリアントでは、複数のエージェントが複数の問題についての決定を受け入れなければなりません。一般的な使用例は、毎日行う活動を決定する必要がある家族です (ここでは、各問題は 1 日です)。各エージェントは、各問題のさまざまなオプションに異なる効用を割り当てます。古典的なアイテム割り当て設定は、各問題がアイテムに対応し、各決定オプションがそのアイテムを特定のエージェントに与えることに対応し、アイテムが他の誰かに与えられるすべてのオプションについてエージェントの効用がゼロになるという特別なケースに対応します。この場合、比例性とは、各エージェントの効用が少なくとも「独裁効用」の 1/ nであることを意味します。つまり、各問題で最良のオプションを選択することで得られる効用です。比例性は達成できないかもしれませんが、ラウンドロビンアイテム割り当てによって PROP1 は達成できます。^[38]

同じアイテムが繰り返し割り当てられることがよくあります。たとえば、家事の繰り返しです。繰り返し回数がエージェントの数の倍数であれば、嫉妬のない完全な割り当てシーケンスを多項式時間で見つけ、比例的でパレート最適なシーケンスを指数時間で見つけることができます。しかし、嫉妬のないパレート最適なシーケンスは存在しない可能性があります。エージェントが2人の場合、繰り返し回数が偶数であれば、嫉妬のないパレート最適なシーケンスを見つけることは常に可能です。^[39]

不可分財の確率的配分^[40]は公平な財の配分の一種であり、その解は決定論的配分の集合上の 確率分布を記述する。

m 個のアイテムをn 個のエージェントに分配する必要があると仮定します。正式には、決定論的設定では、ソリューションはエージェントへのアイテムの実現可能な割り当て、つまりアイテムのセットをn個のサブセット (エージェントごとに 1 つ) に分割することを記述します。すべての決定論的割り当てのセットは、次のように記述できます。

${\displaystyle {\mathcal {A}}=\{(A^{1},\dots ,A^{n})\mid \forall i\in [n]\colon A^{i}\subseteq [m],\quad \forall i\neq j\in [n]\colon A^{i}\cap A^{j}=\emptyset ,\quad \cup _{i=1}^{n}A^{i}=[m]\}}$

確率論的な設定では、解は集合 上の確率分布です。つまり、すべての確率的割り当て（つまり、問題に対するすべての実行可能な解）の集合は次のように記述できます。 ${\displaystyle {\mathcal {A}}}$

${\displaystyle {\mathcal {D}}=\{d\mid p_{d}\colon {\mathcal {A}}\to [0,1],\sum _{A\in {\mathcal {A}}}p_{d}(A)=1\}}$

各エージェントに関連する関数は 2 つあります。決定論的割り当て${\displaystyle u_{i}\colon {\mathcal {A}}\to \mathbb {R} _{+}}$に関連する効用関数と、次のように定義される確率論的割り当てに関連する期待効用関数です。 ${\displaystyle E_{i}\colon {\mathcal {D}}\to \mathbb {R} _{+}}$${\displaystyle u_{i}}$

${\displaystyle E_{i}(d)=\sum _{A\in {\mathcal {A}}}p_{d}(A)\cdot u_{i}(A)}$

決定論的設定に提案されているのと同じ基準を確率論的設定でも考慮できます。

• 功利主義ルール：このルールは、社会は効用合計を最大化する解決策を選択すべきであるとしています。つまり、功利的福祉を最大化する確率的配分を選択することです。 川瀬と澄田^{[40]は、確率的設定での功利的福祉の最大化は常に}決定論的配分によって達成できることを示しました。その理由は、決定論的配分 の功利的価値は少なくとも次の功利的価値であるためです。${\displaystyle d^{*}\in {\mathcal {D}}}$${\displaystyle d^{*}={\underset {d\in {\mathcal {D}}}{\operatorname {argmax} }}\sum _{i=1}^{n}\sum _{A\in {\mathcal {A}}}\left(p_{d}(A)\cdot u_{i}(A)\right)}$${\displaystyle A^{*}={\underset {A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}{\operatorname {argmax} }}\sum _{i=1}^{n}u_{i}(A)}$${\displaystyle d^{*}}$${\displaystyle \sum _{i=1}^{n}\sum _{A\in {\mathcal {A}}}\left(p_{d^{*}}(A)\cdot u_{i}(A)\right)=\sum _{A\in {\mathcal {A}}}p_{d^{*}}(A)\sum _{i=1}^{n}u_{i}(A)\leq \max _{A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}\sum _{i=1}^{n}u_{i}(A)}$
• 平等主義ルール：このルールは、社会は最も貧しい人々の効用を最大化する解決策を選択すべきであるとしています。つまり、平等な福祉を最大化する確率的配分を選択することです。 功利主義ルールとは対照的に、ここでは確率的設定により社会はより高い価値を達成することができます^[40] — 例として、2人の同一のエージェントと、その価値を持つ1つのアイテムのみがある場合を考えてみましょう。${\displaystyle d^{*}\in {\mathcal {D}}}$${\displaystyle d^{*}={\underset {d\in {\mathcal {D}}}{\operatorname {argmax} }}\min _{i=1,\ldots ,n}\sum _{A\in {\mathcal {A}}}\left(p_{d}(A)\cdot u_{i}(A)\right)}$100 . 決定論的な設定では平等主義の価値は0 であるが、確率的設定では50 .
  • 困難性：川瀬と澄田^{[40]は、たとえエージェントの効用がすべて}予算加法的な場合でも、平等主義的福祉を最大化する確率的配分を見つけることはNP困難であること、また、たとえすべてのエージェントが同じサブモジュラ効用関数を持つ場合でも、平等主義的福祉をより良い係数に近似することはNP困難であることを証明している。${\displaystyle 1-{\tfrac {1}{e}}}$
  • アルゴリズム：川瀬と澄田^[40]は、功利主義的福祉を係数αに近似する決定論的配分を見つけるアルゴリズムが与えられた場合に、平等主義的福祉を同じ係数αに近似する確率的配分を見つけるアルゴリズムを提示している。

• ビンカバーリング問題とビンパッキング問題は、それぞれ分割不可能な財の割り当てと分割不可能な雑用の割り当ての特殊なケースとして見ることができる、よく研究された 2 つの最適化問題です。これらの問題に使用される多くの手法は、公平なアイテムの割り当ての場合にも役立ちます。
• 公平な分割実験- 公平なアイテムの割り当てに関連するいくつかのケーススタディとラボ実験が含まれます。
• 賃貸料の調和- 分割不可能な項目と固定総費用を同時に分割しなければならない公平な分割問題。
• 公平なランダム割り当て- ランダム化によって公平性が達成される、金銭を使わない公平な分割問題。
• 住宅割り当て問題- 金銭の移転やランダム化を行わずに、各エージェントが正確に 1 つのオブジェクトを取得する公平な分割問題。
• コース割り当て-大学のコースの座席を学生間で公平に分割する問題。
• 公平性の価格- 公平性と効率性のトレードオフの一般的な尺度であり、アイテムの割り当て設定に関するいくつかの結果が含まれています。
• 公平な部分集合和問題
• 17匹の動物の継承パズル