羨望のないアイテム割り当て

羨望のない（EF）アイテム割り当ては公平なアイテム割り当て問題であり、その公平性の基準は羨望のなさである。つまり、各エージェントは、他のエージェントのバンドルと少なくとも同等に良いと思われるバンドルを受け取るべきである。^{[1] ：296–297}

アイテムは分割できないため、EF 割り当ては存在しない可能性があります。最も単純なケースは、1 つのアイテムと少なくとも 2 つのエージェントがある場合です。アイテムが 1 つのエージェントに割り当てられると、他のエージェントがそれを羨みます。

公平性を実現する方法の 1 つは、金銭の送金を使用することです。金銭の送金が許可されていない、または望ましくない場合は、さまざまな種類の緩和を提供する割り当てアルゴリズムがあります。

アンダーカット手順は、そのような割り当てが存在する場合に限り、2 つのエージェントの完全な EF 割り当てを見つけます。エージェントはアイテムのバンドルをランク付けする必要がありますが、基数ユーティリティ情報は必要ありません。エージェントの選好関係が厳密に単調である場合はいつでも機能しますが、それらが応答選好であると想定する必要はありません。最悪の場合、エージェントはすべての可能なバンドルをランク付けする必要がある可能性があるため、実行時間はアイテムの数に対して指数関数的になる可能性があります。

通常、バンドルをランク付けするよりも、個々のアイテムをランク付けする方が簡単です。すべてのエージェントが応答性の高い好みを持っていると仮定すると、アイテムのランク付けを部分的なバンドルのランク付けに引き上げることができます。たとえば、アイテムのランク付けが w>x>y>z の場合、応答性は {w,x}>{y,z} および {w,y}>{x,z} を意味しますが、{w,z} と {x,y} の関係、{x} と {y,z} の関係などについては何も意味しません。アイテムのランク付けが与えられます。

• 割り当ては、項目ランキングと一致するすべての応答バンドルランキングに従って羨望フリーである場合、必然的に羨望フリー(NEF) です。
• 各エージェントiについて、 i のアイテムランキングと一致する応答バンドルランキングが少なくとも 1 つ存在し、 i がそれを羨望しない場合、割り当てはおそらく羨望フリー(PEF) です。
• エージェントi,jの各ペアについて、 i のアイテムランキングと一致する応答バンドルランキングが少なくとも 1 つ存在し、それによってi がj を羨ましがらない場合、割り当ては弱くおそらく羨望フリー(WPEF) である。
• 割り当ては、項目ランキングと一致するすべての応答バンドルランキングに従ってパレート最適である場合、必然的にパレート最適(NPE) です (順序パレート効率を参照)。
• 割り当ては、アイテムランキングと一致する少なくとも 1 つの応答バンドルランキングに従ってパレート最適である場合、おそらくパレート最適(PPE) です。

以下の結果がわかっています。

• Bouveret、Endriss、Lang ^[2]は、すべてのエージェントが厳格な好みを持っていると仮定しています。彼らは、追加の効率条件、特に完全性、NPE、PPEを備えたNEF / PEF割り当てを見つけるアルゴリズムの問​​題を研究しています。一般に、PEFは簡単ですが、NEFは困難です。NEF割り当てが存在するかどうかを確認することはNP完全ですが、WPEFの存在を確認することは多項式時間で行うことができます。
• Aziz、Gaspers、Mackenzie、Walsh ^{[3] は、エージェントが}弱い選好（無差別）を持つ可能性のある、より一般的な設定を研究しています。この設定では、WPEF の存在を確認することは NP 完全です。PEF 割り当てが存在するかどうかの決定は、厳密な選好または n=2 の場合は P に含まれますが、一般に NP 完全です。エージェントの数が一定の場合、NEF 割り当ての存在を決定することが P に含まれるかどうかは未解決の問題です。

空の割り当ては常にEFです。しかし、EFに加えて効率性も考慮したい場合、決定問題は計算的に困難になります。^{[1] : 300–310}

• EFと完全な割り当てが存在するかどうかを判断することはNP完全です。これは、エージェントが2つしかない場合でも、またそれらの効用が加算的で同一の場合でも当てはまります。なぜなら、この場合、EF割り当てを見つけることは、パーティション問題を解決することと同等だからです。^[4]
• 公平な割り当てが存在するかどうかを判断するには、2人以上のエージェントがいる場合、指数関数的なコミュニケーション（商品の数）が必要になります。エージェントが2人の場合、コミュニケーションの複雑さは特定のパラメータの組み合わせに依存します。^[5]
• EFとパレート効率的な割り当てが存在するかどうかの決定はNPより上です。二値効用^[6]や加法効用^[7]でも-完全です。（NPで任意の問題を解くことができるオラクルがあれば、非決定論的時間で解くことができる問題のクラスです）。${\displaystyle \Sigma _{2}^{\textrm {P}}}$${\displaystyle \Sigma _{2}^{\textrm {P}}}$

問題のいくつかのパラメータを固定された小さな定数とみなすと、決定問題は扱いやすくなる可能性がある。^[8]

• オブジェクトの数mをパラメータとして考えると、加法的または二分法的効用の場合、実行時間は まで低下します。効用がバイナリおよび/または同一の場合、実行時間は まで低下します。ここで、表記法は、他のパラメータ (エージェントの数など) で多項式となる式を隠します。${\displaystyle O^{*}(m^{2m})}$${\displaystyle O^{*}(m^{m})}$${\displaystyle O^{*}}$
• エージェントの数nをパラメータとして考えると、PE+EF 割り当ての存在は依然として困難なままです。二値ユーティリティでは、n =2 の場合でも NP 困難です。^[6]しかし、これは現在 NP であり、NP オラクル (例: SAT ソルバー) で効率的に解決できます。エージェントでは、そのようなオラクルで実行でき、P=NP でない限り少なくともオラクルが必要です。加法ユーティリティでは、n =2 の場合でも NP 困難です。^[6]さらに、すべてのユーティリティが同一で単項でエンコードされている場合でも、エージェントの数に関してW[1] 完全です。${\displaystyle n\geq 5}$${\displaystyle 2^{n+1}}$${\displaystyle 2^{n-4}}$
• エージェントの数nと最大効用Vの両方をパラメータとして考慮すると、動的計画法を使用して、加法効用に対してPE+EF割り当ての存在を時間内に決定できます。${\displaystyle O^{*}((m\cdot V+1)^{n^{2}}\cdot mn^{2})}$
• エージェントの数nと効用レベルの数zの両方をパラメータとして考慮すると、同一の加法効用に対するPE+EF割り当ての存在は、変数を含む整数線形計画法を使用して決定できます。Lenstraのアルゴリズムを使用すると、このようなILPを時間内に解くことができます。${\displaystyle d=n\cdot z^{n}}$${\displaystyle O^{*}(d^{2.5d})}$

多くの手順では、「ほぼ」嫉妬のない割り当て、つまり嫉妬のレベルが制限されている割り当てを見つけます。「ほぼ」嫉妬のない割り当てにはさまざまな概念があります。

2人のエージェントAとBごとに、Bの束から最大で1つのアイテムを削除した場合、AがBを羨ましく思わない場合、その割り当てはEF1と呼ばれます。^[9] EF1割り当ては常に存在し、さまざまな手順、特に次の手順によって効率的に見つけることができます。

• すべてのエージェントが弱加法的な効用を持つ場合、ラウンドロビン プロトコルは完全な EF1 割り当てを見つけます。各エージェントはそれぞれの状況で「最適なアイテム」を選択できる必要があるため、弱加法性が必要です。
• より一般的なケースでは、すべてのエージェントの効用が単調に増加する場合、羨望グラフ手順は完全な EF1 割り当てを見つけます。唯一の要件は、エージェントがアイテムのバンドルをランク付けできることです。エージェントの評価がカーディナル効用関数によって表される場合、EF1 保証には追加の解釈があります。各エージェントの数値羨望レベルは、最大限界効用、つまりそのエージェントの単一アイテムの最大限界効用以下です。
• エージェントが任意の効用 (必ずしも加法的または単調ではない) を持つ場合、A-CEEI メカニズムは部分的な EF1 割り当てを返します。唯一の要件は、エージェントがアイテムのバンドルをランク付けできることです。少数のアイテムは割り当てられないままになる可能性があり、少数のアイテムを追加する必要がある可能性があります。割り当ては、割り当てられたアイテムに関してパレート効率的です。
• 最大ナッシュ福祉アルゴリズムは、効用の積を最大化する完全な割り当てを選択する。このアルゴリズムでは、各エージェントが各項目の数値評価を提供することを要求し、エージェントの効用は加算的であると仮定する。結果として得られる割り当ては、EF1とパレート効率の両方である。^[10]
• 他のさまざまなアルゴリズムも、パレート効率的な EF1 割り当てを返します。「効率的でほぼ公平なアイテム割り当て」を参照してください。
• 任意の単調評価を持つ2つのエージェント、または加法評価を持つ3つのエージェントの場合、EF1割り当てはアイテム数の対数クエリ数を使用して計算できます。^[11]
• 任意の効用関数（必ずしも単調ではない）を持つ2つのエージェントの場合、EF1割り当ては多項式時間で見つけることができます。^[12]
• 任意の単調評価を持つ最大 4 人のエージェント、または同一の単調評価を持つn 人のエージェントに対して、EF1 割り当てが常に存在し、これは連結されている(アイテムが線上に事前に順序付けられている場合、たとえば通りの家など)。証明には、シモンズ-スー プロトコルに似たアルゴリズムが使用される。n > 4 のエージェントが存在する場合、連結された EF1 割り当てが存在するかどうかは不明であるが、連結されたEF2割り当ては常に存在する。^[13]

2人のエージェントAとBのそれぞれについて、Bの束から任意のアイテムを削除してもAがBを羨ましがらない場合、その割り当てはEFxと呼ばれます。^[14] EFxはEF1よりも厳密に強力です。EF1では、 Bの束から最も価値のあるアイテム（Aにとって）を削除することで羨望を解消できますが、EFxでは、最も価値の低いアイテム（Aにとって）を削除することで羨望を解消する必要があります。EFx割り当ては、いくつかの特別な場合に存在することが知られています。

• エージェントが2人いる場合、または同一の評価を持つエージェントがn人いる場合。この場合、leximin最適割り当てはEFxとパレート最適である。しかし、計算には指数関数的に多くのクエリが必要になる。^{[15] [12]}
• 加法的評価を持つn人のエージェントがいるが、財に対する異なる価値は最大で2つしかない場合。この場合、任意の最大ナッシュ福祉配分はEFxである。さらに、EFx配分を計算するための効率的なアルゴリズムが存在する（必ずしも最大ナッシュ福祉ではないが）。^[16]
• 加法的評価を持つn人のエージェントがいるが、評価の種類は最大で2つである。^[17]
• 加法的な評価を持つエージェントが3人いる場合、多項式時間アルゴリズムが存在する。^{[18] [19]}

いくつかの近似値が知られています:

• 1/2近似EFx割り当て（これはMaximin Awareと呼ばれる別の近似公平性の概念も満たす）は多項式時間で見つけることができます。^[20]
• 0.618近似のEFx割り当て（これはEF1でもあり、グループワイズマキシミンシェアとペアワイズマキシミンシェアと呼ばれる他の公平性の概念を近似する）は多項式時間で見つけることができます。^[21]
• 部分的なEFx 割り当ては常に存在し、その場合、ナッシュ福祉は最大可能ナッシュ福祉の少なくとも半分になります。言い換えれば、いくつかのアイテムを慈善団体に寄付した後、残りのアイテムを EFx 方式で割り当てることができます。この境界は可能な限り最善です。エージェントのすべてのアイテムに対する評価が比較的小さい大規模な市場では、アルゴリズムはほぼ最適なナッシュ福祉で EFx を達成します。^[22] n -1 個のアイテムを寄付するだけで十分であり、寄付されたアイテムのセットを羨むエージェントはいません。^[23]

EFx の割り当てが一般的に存在するかどうかは未解決の問題です。最小の未解決ケースは、加算評価を持つ 4 つのエージェントです。

EF1ではアイテム数の対数的なクエリ数が必要であるのに対し、EFxの割り当てを計算するには、同一の加法的な評価を持つエージェントが2人いる場合でも、線形の数のクエリが必要になる場合があります。^[11]

EF1とEFxのもう一つの違いは、EFXの割り当て数は（アイテムの数に関係なく）2と少ないのに対し、EF1の割り当て数は常にアイテムの数に対して指数関数的であることです。^[24]

いくつかの分割シナリオでは、分割可能な土地と分割不可能な家屋など、分割可能な項目と分割不可能な項目の両方が関係します。2人のエージェントAとBに対して次の条件が満たされる場合、その割り当てはEFmと呼ばれます。 ^[25]

• B のバンドルに分割可能な商品が含まれている場合、A は B を羨ましがりません (EF 割り当ての場合と同様)。
• B のバンドルに分割できない商品のみが含まれている場合、A は B のバンドルから最大 1 つのアイテムを削除した後は B を羨むことはありません (EF1 割り当ての場合と同様)。

EFm 割り当ては、任意の数のエージェントに対して存在します。ただし、それを見つけるには、ケーキを正確に分割するためのオラクルが必要です。このオラクルがない場合、EFm 割り当ては、一般的な加法評価を持つ 2 つのエージェント、または区分線形評価を持つ任意の数のエージェントという 2 つの特殊なケースで多項式時間で計算できます。

パレート最適性と互換性のある EF1 とは対照的に、EFm はパレート最適性と互換性がない可能性があります。

嫉妬の量に最悪の場合の限界を使用するのではなく、それぞれの特定のインスタンスで嫉妬の量を最小限に抑えるようにすることができます。詳細と参考文献については、嫉妬の最小化を参照してください。

AL手順は、 2 つのエージェントの EF 割り当てを見つけます。一部の項目は破棄される可能性がありますが、最終的な割り当ては次の意味でパレート効率的です。つまり、一方にとってより優れ、他方にとって弱くより優れている EF 割り当ては他にありません。AL 手順では、エージェントは個々の項目をランク付けすることだけが必要です。エージェントが応答性の高い好みを持っていると想定し、必然的に羨望のない 割り当て (NEF) を返します。

調整された勝者手順は、 2人のエージェントに対して完全かつ効率的な EF 割り当てを返しますが、1 つのアイテムを削減する必要がある可能性があります (または、1 つのアイテムが共有所有権のままになります)。エージェントは各アイテムの数値を報告する必要があり、加法的効用があると想定されます。

各エージェントが最大で1つのアイテムしか入手できず、評価がバイナリ（各エージェントが各アイテムを好きか嫌いかのどちらか）である場合、最大濃度の嫉妬のないマッチングを見つける多項式時間アルゴリズムが存在します。^[26]

エージェントが何らかの独立基準を満たす確率分布から導き出された加法的な効用関数を持ち、アイテムの数がエージェントの数に比べて十分に大きい場合、EF 割り当てが高確率で存在します。特に、

• アイテム数が十分に大きい場合: 、EF割り当てが存在する(mが無限大に近づくにつれて確率は1に近づく)、ラウンドロビンプロトコルによって見つけることができます。^[27]${\displaystyle m=\Omega (n\log n/\log \log n)}$
• ならば、whp EF配分が存在し、社会福祉を最大化することで見つけることができます。^{[28]この境界は}クーポン収集者の問題との関連により厳密です。${\displaystyle m=\Omega (n\log n)}$
• かつmがnで割り切れる場合、EF割り当てが存在し、マッチングベースのアルゴリズムによって見つけることができます。^[29]${\displaystyle m\geq 2n}$

一方、アイテム数が十分に大きくない場合、EF 割り当てが存在しない可能性が高くなります。

• アイテム数が十分に大きくない場合、つまり、 の場合、EF割り当ては存在しません。^[28]${\displaystyle m=n+o(n)}$
• mがnで「ほぼ割り切れない」場合、EF割り当ては存在しません。 ^[29]${\displaystyle m=o(n\log n/\log \log n)}$

• すべての EF 割り当ては、最小最大公平です。これは順序定義から直接導かれ、​​加法性に依存しません。
• すべてのエージェントが加法的効用関数を持っている場合、EF 割り当ても比例的かつ最大最小公平になります。そうでない場合、EF 割り当ては比例的ではなく、最大最小公平でもない可能性があります。
• 平等な所得からの競争的均衡の配分も嫉妬の影響を受けない。これは加法性に関係なく当てはまる。^[9]
• すべてのナッシュ最適割り当て（効用の積を最大化する割り当て）はEF1である。^[14]
• 集団の嫉妬のなさは嫉妬のなさの強化であり、分割可能な対象と分割不可能な対象の両方に適用されます。

詳細と参考資料については、公正なアイテム割り当てを参照してください。

以下では、次の略語が使用されています。

• ${\displaystyle n}$= 部門に参加しているエージェントの数。
• ${\displaystyle m}$= 分割する項目の数;
• EF = 羨望なし、EF1 = 1 つの項目を除いて羨望なし (EF より弱い)、MEF1 = 1 つの項目を除いて限界羨望なし (EF1 より弱い)。
• PE = パレート効率的。