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

平等主義的アイテム割り当ては、最大最小アイテム割り当てとも呼ばれ、公平なアイテム割り当て問題であり、公平性の基準は平等主義ルールに従います。目標は、エージェントの最小値を最大化することです。つまり、すべての可能な割り当ての中で、エージェントの最小値が可能な限り大きくなる割り当てを見つけることが目標です。同じ最小値を持つ割り当てが2つ以上ある場合、目標は、これらの割り当ての中から、2番目に小さい値が可能な限り大きくなる割り当てを選択することです。以下同様に続きます（レキシミン順序による）。そのため、平等主義的アイテム割り当ては、レキシミンアイテム割り当てと呼ばれることもあります。

各エージェントにとって各アイテムjの価値が0 または定数v _{j の}いずれかである特殊なケースは、サンタクロース問題と呼ばれます。サンタクロースは固定された贈り物のセットを持っており、最も不幸な子供が可能な限り幸せになるように子供たちに贈り物を分配したいと考えています。

関連する問題は次のとおりです。

• 最大最小目的を持つ多方向数分割は、すべてのエージェントが同じ評価を持つ特殊なケースに対応します。さらに特殊なケースは、2 つのエージェントの場合に対応する分割問題です。この特殊なケースでさえ、一般にNP 困難です
• 無関係なマシンのスケジューリングは、最大値を最小化することを目的とする二重問題です。
• マキシミンシェアアイテム割り当ては別の問題であり、その目的は最適なソリューションを達成することではなく、各エージェントが特定のしきい値を超える値を受け取るソリューションを見つけることです。

平等主義のルールには2つのバリエーションがある: ^[1]

• 絶対平等主義（または絶対レキシミン）、最大化にはエージェントの名目値を使用する。
• 相対的平等主義（または相対的語彙目録）では、最大化には正規化された値（バンドル値をすべての項目の値で割った値）が使用されます。

エージェントの評価がすでに正規化されている場合、つまりすべてのエージェントがすべてのアイテムのセットに同じ値を割り当てる場合、2 つのルールは同等です。ただし、正規化されていない評価では異なる場合があります。たとえば、アイテムが 4 つあり、アリスがそれらを 1,1,1,1 と評価し、ジョージがそれらを 3,3,3,3 と評価する場合、この場合の効用プロファイルは (3,3) であり最適であるため、絶対語彙ルールはアリスに 3 つのアイテムを、ジョージに 1 つのアイテムを与えます。対照的に、相対語彙ルールは各エージェントに 2 つのアイテムを与えます。この場合の正規化された効用プロファイルは、両方のエージェントの合計値が 1 に正規化され、最適であるため、(0.5,0.5) です。

一般的な問題は NP 困難ですが、小さなインスタンスは制約プログラミング技術によって正確に解決できます。

• BouveretとLemaîtreは、離散制約充足問題に対するレキシミン最適解を見つけるための5つの異なるアルゴリズムを提示しています。 ^[2]彼らは、最大最小項目割り当てを特別なケースとして提示しています。
• Dall'AglioとMosca ^[3]は、調整勝者手順の適応に基づいて、2つのエージェントのための正確な分岐限定アルゴリズムを提示した。

デムコとヒル^[4]は、期待値において平等なアイテム割り当てを達成するランダム化アルゴリズムを提示している。

以下、nはエージェントの数、m はアイテムの数です。

サンタクロース問題の特殊なケースの場合:

• BansalとSviridenko ^[5]は線形計画法の丸めに基づく近似アルゴリズムを提示した。${\displaystyle O(\log {\log {n}}/\log {\log {\log {n}}})}$
• Feige ^[6]は多項式時間定数因子近似アルゴリズムが存在することを証明したが、その証明はLovászの局所補題を使用しており非構成的であった。
• Asadpour、Feige、Saberi ^[7]はハイパーグラフマッチングを用いた定数係数近似アルゴリズムを提示した。彼らはそれが有限数のステップで収束することを証明できなかった。
• Annamalai、Kalaitzis、Svensson ^[8]は多項式時間13近似アルゴリズムを提示した。
• Davies、Rothvoss、Zhang ^[9]は、基本線形計画にマトロイド制約を導入することで近似係数を4に改善した。

一般的なケースでは、加法的な評価を持つエージェントの場合、

• BezakovaとDani ^[10]は2つのアルゴリズムを提示した。最初のアルゴリズムは、最適平等価値の 因子近似値を与える。2番目は、1つの財まで平等な割り当てを求める。つまり、各エージェントは、最適平等割り当てから最大で1つの品目を差し引いた価値を受け取る。彼らのアルゴリズムは、Lenstra、Shmoys、およびTardosによる以前のアルゴリズム^{[11]に基づいており、基本的には1つの}雑用まで平等な割り当てを求める。両方のアルゴリズムは同様のアイデアに基づいている。彼らは、部分平等割り当てを求めるための線形計画法の基本的な実行可能解を求め、各エージェントが最大で1つの財を失うか、最大で1つの雑用を得るようにそれを丸める。${\displaystyle (m-n+1)}$
• AsadpourとSaberi ^[12]は近似アルゴリズムを提示した。彼らのアルゴリズムは、木上の分数マッチングを丸める反復法を使用する。彼らはまた、問題から少数の人々を除外することが許される場合、より良い境界を提供する。${\displaystyle O({\sqrt {n}}\cdot \log ^{3}n)}$

• Chakrabarty、Chuzoy、Khanna ^[13]は、任意のに対して、実行時間が の近似アルゴリズムを与えた。各アイテムが最大2人のエージェントに対して非ゼロの効用を持つ特殊なケースでは、彼らは2因子近似アルゴリズムを与え、それより良い因子に近似することは難しいことを証明した。${\displaystyle O(m^{\varepsilon })}$${\displaystyle O(m^{1/\バレプシロン })}$${\displaystyle \varepsilon \in \Omega \left({\frac {\log \log m}{\log m}}\right)}$
• ゴロビン^[14]は、任意の整数 に対して、エージェントの一部が少なくとも の効用を得るアルゴリズムを提示した。この結果は、問題の適切な線形計画緩和から得られるもので、この線形計画の最良の結果である。彼はまた、2つの財のクラスを持つ特殊なケースに対する近似アルゴリズムも提示した。${\displaystyle k}$${\displaystyle (1-1/k)}$${\displaystyle OPT/k}$${\displaystyle O({\sqrt {n}})}$
• エージェントの数が一定の場合、Woeginger法を用いたFPTASがある。^[15]

サブモジュラー効用関数を持つエージェントの場合:

• ゴロビン^[14]は、近似アルゴリズムと、一般的な効用関数に対するいくつかの近似不可能性の結果を示した。${\displaystyle (m-n+1)}$
• ゴーマンス、ハーヴェイ、岩田、ミルコニ^[16]は、近似アルゴリズムを提示している。${\displaystyle O({\sqrt {m}}\cdot n^{1/4}\cdot \log n\cdot \log ^{3/2}m)}$
• Nguyen、Roos、Rothe ^{[17] [18]}は、より強い硬度の結果を示しています。

標準的な平等主義ルールでは、各エージェントが各オブジェクトに数値を割り当てる必要があります。多くの場合、エージェントは順序効用のみを持ちます。順序設定に対する平等主義ルールの一般化は 2 つあります。

1. エージェントがバンドルの集合上で順序付けされていると仮定します。任意の離散割り当てが与えられた場合、任意のエージェントiについて、エージェント i のバンドルの順位を r(i) と定義します。つまり、 i が最良のバンドルを取得した場合は r(i)=1、2 番目に良いバンドルを取得した場合は r(i)=2 となります。このrは、サイズがn (エージェントの数)のベクトルです。順序的平等割り当ては、r の最大要素を最小化する割り当てです。需要減少手順は、バンドルの順序が任意のエージェント数に対して、順序的平等割り当てを見つけます。

2. エージェントがアイテムの集合に対して順序付けされた順位を持っていると仮定する。離散的または分数的な割り当てが与えられた場合、任意のエージェントiと正の整数kに対して、エージェントi がk 個の最上位の無差別クラスから受け取る合計の割合としてt ( i , k ) を定義する。このt は最大でn * mのサイズのベクトルであり、nはエージェントの数、m はアイテムの数である。順序的平等主義の割り当ては、レキシミン順序でベクトルtを最大化する割り当てである。食べる速度が等しい同時摂食アルゴリズムは、順序的平等主義の割り当てを返す唯一のルールである。^[19]

オンライン設定では、アイテムは 1 つずつ届きます。各アイテムは到着したらすぐに割り当てる必要があります。

川瀬と澄田^[20]は2つの変種を研究した。敵対的変種では、競争比率1/nのアルゴリズムを提示し、それが最良であることを示した。iid変種では、ほぼ最適なアルゴリズムを提示した。

比例割り当てが存在する場合は常に、相対的語彙割り当ては比例します。これは、比例割り当てでは、エージェントの最小相対値は少なくとも 1/ nであるため、最小相対値を最大化する場合も同じことが当てはまるためです。ただし、上記の例に示すように、絶対的語彙割り当ては比例しない場合があります。

1. すべてのエージェントが非ゼロの限界効用を持つ同一の評価を持っている場合、相対的レキシミン配分はPOとEFXです。

• leximin++と呼ばれるleximinの改良版は、一般的な同一の評価でEFX（POではない）を保証します。^[21]

2. 加法的評価を持つ2人のエージェントの場合、相対的レキシミン割り当てはEF1である。^{[21] : Thm.5.5}ただし、

• 絶対的レキシミン配分は、加法的評価を持つ2人のエージェントに対してもEF1ではない可能性がある。例えば、4つの財があり、それらを{0,1,1,1}と{3,3,3,3}と評価する2人のエージェントがいるとしよう。唯一の絶対的レキシミン配分は、最初のエージェントに{1,1,1}を与え、2番目のエージェントに{3}を与えるが、2番目のエージェントは羨望の念を抱く。^{[22] : 32}
• 相対的レキシミン配分は、3 人以上のエージェントに対しては EF1 にならない可能性がある。たとえば、4 つの財があり、3 人のエージェントがそれらの財を {30,0,0,0}、{20,5,5,0}、{0,12,12,6} と評価しているとしよう。評価は正規化されている (合計値は 30) ことに注意する。レキシミン配分では、最初の財はエージェント 1 に割り当てられる必要がある。次に、2 番目と 3 番目の財はエージェント 2 に割り当てられ、財はエージェント 3 に残る。しかし、エージェント 3 は、財を 1 つ取り除いた後でもエージェント 2 を羨望する。^{[23] : 22}

3. すべてのエージェントがマトロイドランク関数（つまり、バイナリ周辺を持つサブモジュラー）である評価を持つ場合、絶対レキシミン割り当ての集合は最大積割り当ての集合と同等であり、そのような割り当てはすべて最大和とEF1である。^[22]

4.家事（負の効用を持つ項目）の不可分な割り当ての文脈では、加法的な評価を持つ3人または4人のエージェントがいる場合、任意のレキシミン最適割り当てはPROP1とPOである。一般的に同一の評価を持つn人のエージェントがいる場合、任意のレキシミン最適割り当てはEFXである。^[24]

すべてのエージェントが同一の評価を持っている場合、平等主義的割り当ては、定義により、各エージェントに少なくとも最大のシェアを与えます。

しかし、エージェントが異なる評価を持つ場合、問題は異なります。最大シェア割り当ては満足度の問題です。目標は、各エージェントが同一評価しきい値を超える価値を受け取ることを保証することです。対照的に、平等主義割り当ては最適化の問題です。目標は、各エージェントに可能な限り高い価値を与えることです。場合によっては、結果として生じる割り当てが大きく異なる場合があります。たとえば、4 つの商品があり、それらを {3,0,0,0}、{3-2 ε,ε,ε ,0}、および {1-2 ε ,1,1,2 ε } ( εは小さな正の定数) と評価する 3 人のエージェントがいるとします。評価は正規化されている (合計値は 3) ため、絶対レキシミンと相対レキシミンは同等であることに注意してください。

• レキシミン割り当てにより、効用プロファイル (3, 2ε, 2ε ) が生成されます。最初のアイテムはエージェント 1 に渡される必要があります。そうでない場合、最小の効用は 0 になります。次に、2 番目と 3 番目のアイテムはエージェント 2 に渡される必要があります。そうでない場合、次に小さい効用はε以下になります。そのため、エージェント 3 は最後のアイテムのみを取得します。
• エージェントの最大シェア値は0、ε 、1です。したがって、最大シェア割り当てでは、エージェント3に最初の3つの項目のうちの1つを与える必要があります。この場合の可能な効用プロファイルは、( 0、2ε、1)または(3、ε、1+ 2ε )です。

この例は、 k > 3 の任意のkに対して 1-out-of- k MMSに拡張できます。k +1 個の財があり、それらの財を { k , 0, ..., 0}、{ k -( k -1) ε , ε, ..., ε , 0}、および {1- kε , 1, 1, ..., k ε } と評価する 3 人のエージェントがいます。レキシミン効用プロファイルは ( k , kε, kε )である必要があり、エージェント 3 の 1-out-of- k MMS は 1 です。

レキシミンルールは、公立学校の未使用の教室をチャータースクールに公平に割り当てるために使用されてきた。^[25]