マキシミンシェア

マキシミンシェア (MMS)は、公平なアイテム割り当ての基準です。異なる価値を持つアイテムのセットが与えられた場合、1-out-n マキシミンシェアは、アイテムを複数の部分に分割し、最小の価値の部分を取得することで得られる最大の値です。異なる評価を持つエージェント間でのアイテムの割り当ては、各エージェントが少なくとも自分の 1-out- nマキシミンシェアと同じかそれ以上のバンドルを取得する場合、 MMS 公平と呼ばれます。MMS 公平性は比例性の基準を緩和したものです。つまり、各エージェントは、少なくとも均等分割 (すべてのリソース) と同じかそれ以上のバンドルを取得します。比例性は、アイテムが分割可能な場合は保証できますが、分割できない場合は、すべてのエージェントの評価が同一であっても保証されません。対照的に、MMS 公平性は常に同一のエージェントに保証できるため、エージェントが異なる場合でも比例性の自然な代替手段となります。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle 1/n}$

同一のアイテム。まず、同一のアイテムを人々の間で公平に分配する必要があると仮定します。理想的には、各人がアイテムを受け取る必要がありますが、アイテムが分割不可能であるため、 が で割り切れない場合は不可能です。自然な次善の公平性基準は、最も近い整数に切り捨て、各人に少なくとも個のアイテムを与えることです。 個未満のアイテムを受け取ることは「不公平すぎる」です。これは、アイテムの分割不可能性によって正当化されない不公平です。 ${\displaystyle m}$${\displaystyle n}$${\displaystyle m/n}$${\displaystyle m}$${\displaystyle n}$${\displaystyle m/n}$${\displaystyle \lfloor m/n\rfloor }$${\displaystyle \lfloor m/n\rfloor }$

異なるアイテム。ここで、アイテムが異なり、各アイテムの値が異なるとします。たとえば、とがあり、アイテムの値が で、合計すると になるとします。アイテムが割り切れる場合は、各人に の値(または、前の段落のように整数値にしか割り切れない場合は、少なくとも) を与えますが、これは不可能です。3 人のエージェント全員に保証できる最大値は、 で割った 7 です。非公式には、は合計値を「最も近いアイテムに切り捨てた値」で割ったものです。 ${\displaystyle n=3}$${\displaystyle m=5}$${\displaystyle 1,3,5,6,9}$${\displaystyle 24}$${\displaystyle 24/3=8}$${\displaystyle \lfloor 24/3\rfloor =8}$${\displaystyle \{1,6\},\{3,5\},\{9\}}$${\displaystyle 7}$${\displaystyle n}$

この最大最小値を達成するセットは「1-out-of-3 最大最小シェア」と呼ばれます。これは、元のセットをいくつかの部分に分割し、最も価値の低い部分を取ることによって構築できるアイテムの最良のサブセットです。したがって、この例では、割り当てが MMS 公平であるのは、各エージェントに少なくとも の値を与える場合のみです。 ${\displaystyle \{1,6\}}$${\displaystyle 3}$${\displaystyle 7}$

異なる評価。各エージェントが各アイテムに異なる値を割り当てるとします。例:

• アリスはそれらを次のように評価します。${\displaystyle 1,3,5,6,9}$
• ジョージはそれらを次のように評価しています。${\displaystyle 1,7,2,6,8}$
• ディナはそれらを と評価しています。${\displaystyle 1,1,1,4,17}$

現在、各エージェントには異なる MMS があります。

• アリスの MMS は上記の通りです。${\displaystyle 7}$
• ジョージの MMS は、分割によって です(これらすべてのバンドルは彼にとって同値です)。${\displaystyle 8}$${\displaystyle \{1,7\}、\{2,6\}、\{8\}}$
• Dina の MMS は、パーティションによってです。${\displaystyle 3}$${\displaystyle \{1,1,1\},\{4\},\{17\}}$

ここで、割り当てが MMS 公平であるのは、Alice に少なくとも の値が、George に少なくとも の値が、Dina に少なくとも の値が与えられる場合です。たとえば、George に最初の 2 つの項目を、Alice に次の 2 つの項目を、Dina に最後の項目を与えることは、MMS 公平です。 ${\displaystyle 7}$${\displaystyle 8}$${\displaystyle 3}$${\displaystyle \{1,7\}}$${\displaystyle \{5,6\}}$${\displaystyle \{17\}}$

解釈。エージェントの1-out-of- MMS は、他のすべてのエージェントが同じ好みを持ち、常に最悪のシェアを受け取る場合に、エージェントが割り当てから得ることを期待できる最大の効用として解釈できます。これは、次の議論に基づいて、エージェントが権利があると感じることができる最小の効用です。他のすべてのエージェントが私と同じ好みを持っている場合、この効用を私に与え、他のすべてのエージェントを (弱く) 良くする割り当てが少なくとも 1 つあります。したがって、私にそれより少ないものを与える理由はない。 ${\displaystyle n}$

別の解釈は、エージェントが敵対的な相手に対して分割と選択で分割者として保証できる最も好ましいバンドルです。エージェントは最適な割り当てを提案し、残りの 1 つを取得する前に他のすべてのエージェントに 1 つのシェアを選択させます。

MMS 公平性は、次の交渉プロセスの結果としても説明できます。特定の割り当てが提案されます。各エージェントは、アイテムの代替パーティションを提案することで、これに異議を唱えることができます。ただし、そうする際には、自分より先に他のすべてのエージェントが自分のシェアを選択できるようにする必要があります。したがって、エージェントは、すべてのバンドルが現在のバンドルよりも優れているパーティションを提案できる場合にのみ、割り当てに異議を唱えます。割り当てが MMS 公平であるためには、それに異議を唱えるエージェントがいない、つまり、すべてのエージェントについて、すべてのパーティションに現在のシェアよりも弱く劣るバンドルが存在する必要があります。

セオドア・ヒル^[1] は1987年にマキシミニシェアを研究した。彼は、エージェントの最大アイテム価値の関数としてマキシミニシェアの下限を提示し、各エージェントが少なくともこの下限を受け取る割り当てが常に存在することを証明した。実際のマキシミニシェアは下限よりも高い場合があり、ヒルの方法で見つかった割り当てはMMS公平ではない可能性があることに注意してください。

Budish ^[2]は2011年にコース配分の文脈でMMS公平性を研究した。彼は、いくつかの財の追加が許可されている場合にほぼMMS公平な配分を達成するA-CEEIメカニズムを提示した。2014年にProcacciaとWang ^[3]は、3人以上のエージェント間での正確なMMS公平な配分は存在しない可能性があることを証明した。

が割り当てられるリソースを表す集合を とします。 をのサブセット上の任意の実数値関数とし、それらの「値」を表します。からの1 対n の最大シェアは次のように定義されます。${\displaystyle C}$${\displaystyle v}$${\displaystyle C}$${\displaystyle v}$${\displaystyle C}$

${\displaystyle \operatorname {MMS} _{v}^{1{\text{-out-of-}}n}(C):=~~~\max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {パーティション} (C,n)}~~~\min _{j\in [n]}~~~v(Z_{j})}$

ここで、最大値は を互いに素な部分集合に分割するすべての部分集合にわたっており、最小値はの分割内のすべての部分集合にわたっています。上記の例では、は整数の集合であり、 は和関数、つまり は内の整数の和として定義されています。たとえば、 を示しました。ここで、最大化分割は です。典型的な公平な割り当て問題では、同じリソース に対して異なる価値関数を持つ複数の異なるエージェントが存在します。エージェントの1-out-of- MMS 値は で表されます。割り当ては、 のn 個のペアワイズ互いに素な部分集合のベクトルです(エージェントごとに 1 つの部分集合) 。割り当ては、すべてのエージェント に対して、${\displaystyle C}$${\displaystyle n}$${\displaystyle n}$${\displaystyle C}$${\displaystyle v}$${\displaystyle v(Z)}$${\displaystyle Z}$${\displaystyle \operatorname {MMS} _{v}^{1{\text{-out-of-}}3}(\{1,3,5,6,9\}):=7}$${\displaystyle \{1,6\},\{3,5\},\{9\}}$${\displaystyle n}$${\displaystyle v_{1},\dots ,v_{n}}$${\displaystyle C}$${\displaystyle n}$${\displaystyle i}$${\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C):=\operatorname {MMS} _{v_{i}}^{1{\text{-out-of-}}n}(C)}$${\displaystyle C}$ ${\displaystyle Z_{1},\dots ,Z_{n}}$${\displaystyle i}$

${\displaystyle v_{i}(Z_{i})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}$。

すべての に対してが成り立つ場合、割り当てはエージェントの MMS 分割 と呼ばれます。つまり、割り当てはの MMS の式を最大化する分割の 1 つです。${\displaystyle i}$${\displaystyle v_{i}(Z_{j})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}$${\displaystyle j}$${\displaystyle i}$

ヒル^[1]は、エージェントのすべてのアイテムの価値が最大で全アイテムの価値の倍である場合、そのエージェントの1-out- n MMSは少なくとも であることを証明しました。ここで、 は次の区分線形関数です。${\displaystyle \alpha}$${\displaystyle V_{n}(\alpha )}$${\displaystyle V_{n}(\alpha )}$

${\displaystyle V_{n}(\alpha )=1-k\cdot (n-1)\cdot \alpha }$ みんなのために 、みんなのために。${\displaystyle \alpha \in \left[{\frac {1}{k(n-1/(k+1))}},{\frac {1}{k(n-1/k)}}\right]}$${\displaystyle k\geq 1}$

は の連続かつ非増加関数であり、およびであることに注意する（およびのプロットについては論文を参照）。 ${\displaystyle V_{n}(\alpha )}$${\displaystyle \alpha }$${\displaystyle V_{n}(0)=1/n}$${\displaystyle V_{n}(1)=0}$${\displaystyle V_{2}(\alpha )}$${\displaystyle V_{3}(\alpha )}$

ヒルはまた、すべてのnおよびに対して、および各アイテムを合計値の最大 倍の価値で評価する任意のn人のエージェントに対して、各エージェントが少なくとも の価値を受け取るパーティションが存在することを証明しました。さらに、この保証は厳密です。すべてのnおよびに対して、すべての評価が同一であっても、全員に を超える金額を保証することが不可能な場合があります。 ${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle V_{n}(\alpha )}$${\displaystyle \alpha }$${\displaystyle V_{n}(\alpha )}$

MarkakisとPsomas ^[4]はHillの保証を強化し、このより強力な保証を満たす割り当てを計算するための多項式時間アルゴリズムを提供した。彼らはまた、いかなる誠実なメカニズムもこの保証の2/3近似を得ることができないことを示し、限られた数の財に対する誠実な定数係数近似を提示した。Gourves、Monnot、およびTlilane ^{[5]はMarkakisとPsomasのアルゴリズムを拡張して、より厳密な公平性保証を獲得し、}マトロイドの基底を割り当てるというより一般的な問題に適用できるようにした。

Li、Moulin、Sun、Zhou ^[6]は、Hillの下限値をbadsに拡張し、 badsの数にも依存するより正確な上限値を提示した。彼らはまた、この上限値を達成する多項式時間アルゴリズムも提示した。

MMS 公平な割り当ては存在しない可能性があります。Procaccia と Wang ^[3]および Kurokawa ^[7]は、エージェントとアイテムを含むインスタンスを構築しました。このインスタンスでは、割り当てによって各エージェントに 1-out of 3 MMS が保証されることはありません。すべてのエージェントの MMS は Hill の下限 よりも厳密に大きい可能性があるため、これは Hill の結果と矛盾しないことに注意してください。彼らのインスタンスには、およびでインデックス付けされたオブジェクトがあります。各エージェントは、各オブジェクトを次のように評価します。${\displaystyle n=3}$${\displaystyle m=12}$${\displaystyle V_{n}(\alpha )}$${\displaystyle 12}$${\displaystyle i\in [3]}$${\displaystyle j\in [4]}$${\displaystyle k}$${\displaystyle (i,j)}$

${\displaystyle v_{k}(i,j)=1,000,000+1,000\cdot T_{i,j}+E_{i,j}^{(k)}}$

ここで、 はより小さい値を持つ特定の 3 行 4 列の行列です。彼らは、すべてのエージェントがオブジェクトをオブジェクトのサブセットに分割して、各サブセットの値の合計が 4,055,000 になり、それがすべてのエージェントの MMS になることを証明しています。彼らは、すべての MMS 割り当てがすべてのエージェントに正確に 4 つの特定のオブジェクトを与える必要があることを証明していますが、そのような割り当ては存在しません。したがって、すべての割り当ては少なくとも 1 つのエージェントに最大 4,054,999 の値を与えます。彼らはこのインスタンスを一般化し、すべての に対してアイテムを持つそのようなインスタンスが存在することを示しました。 ${\displaystyle T,E^{(1)},E^{(2)},E^{(3)}}$${\displaystyle 100}$${\displaystyle 3}$${\displaystyle 4}$${\displaystyle n\geq 3}$${\displaystyle 3n+4}$

Feige、Sapir、および Tauber ^[8]は、エージェントとアイテムを含むインスタンスを構築し、MMS 割り当てが存在しないという結果を改善しました。このインスタンスでは、各エージェントの MMS は 40 ですが、最悪のエージェント アイテムの合計値が 39 になることしか保証できません。彼らはまた、任意の に対して、 MMS 割り当てが存在しないアイテムを含むインスタンスが存在することを示しています。が偶数の場合、彼らはアイテムへの境界を改善します。これらのインスタンスでは、最悪のエージェントは最大でも MMS の一部しか受け取ることができません。 ${\displaystyle n=3}$${\displaystyle m=9}$${\displaystyle n\geq 3}$${\displaystyle 3n+3}$${\displaystyle n}$${\displaystyle 3n+1}$${\displaystyle 1-1/n^{4}}$

MMS割り当てが存在することは保証されていないが、ランダムなインスタンスではMMS割り当てが高確率で存在することが証明されている。黒川、プロカッチャ、王^[9]は、これが2つのケースに当てはまることを示しました。

• アイテムは多数存在します。これは確率分布に依存する定数です。以前の結果^{[10]によれば、}羨望のないアイテムの割り当てが高確率で存在し、そのような割り当ては常にMMSです。${\displaystyle m\geq \alpha \cdot n\ln {n}}$${\displaystyle \alpha }$
• アイテムはいくつかあります。 [このケースは前のケースと部分的に重複していることに注意してください]。このケースでは、matched draftと呼ばれるアルゴリズムが提示されています。これは、エージェント対アイテムの二部グラフを構築し、その中で完全なマッチングを見つけることに基づいています。彼らは、(1) matched draft が成功する確率は、が無限大に近づくにつれて 1 に近づくことを証明しています。(2) matched draft が成功した場合、各エージェントの価値は少なくともそのエージェントの MMS になります。${\displaystyle m<n^{8/7}}$${\displaystyle n}$

アマナティディス、マルカキス、ニクザド、サベリ^[11]も、ランダムに生成されたインスタンスでは、MMS公平な割り当てが高確率で存在することを証明しています。

多くのインスタンス クラスでは、MMS 割り当てが常に存在することが証明されています。すべてのnエージェントが同一の評価を持つ場合、定義により MMS 割り当てが常に存在します (すべてのエージェントが同じ MMS パーティションを持ちます)。MMS 割り当てが存在するもう少し一般的なケースは、一部のエージェントが同一の評価を持つ場合です。MMS 割り当ては、分割と選択によって見つけることができます。同一のエージェントは、それぞれが少なくとも MMS と同等の品質のバンドルにアイテムを分割します。n番目のエージェントは、最も高い値のバンドルを選択します。同一のエージェントは、残りのバンドルを取得します。特に、エージェントが 2 つの場合、MMS 割り当てが常に存在します。 ${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n-1}$

BouveretとLemaître ^[12]は、MMS割り当てが以下の場合に存在することを証明した。

• バイナリ評価- 各エージェントはアイテムを好き（ で評価）か嫌い（ で評価）のいずれかです。${\displaystyle 1}$${\displaystyle 0}$
• 同一のマルチセット- エージェントはアイテムを異なる値で評価する場合がありますが、エージェントの値のマルチセットは同じです。
• いくつかのアイテム– 。${\displaystyle m\leq n+3}$

後者の結果は、後に黒川、プロカッチャ、ワン^[9]とフェイジ、サピア、タウバー^[8]によって改善されました。3つのエージェントと9つのアイテムの負の例のため、これは存在する最大の定数であり、の値に関係なく、エージェントとアイテムを持つすべてのインスタンスには常にMMS割り当てがあります。フンメル^[13]はさらに、次の場合にMMS割り当てが存在することを示しました。 ${\displaystyle m\leq n+4}$${\displaystyle m\leq n+5}$${\displaystyle c}$${\displaystyle n}$${\displaystyle m\leq n+c}$${\displaystyle n}$

• アイテムとエージェントがあります。${\displaystyle m\leq n+6}$${\displaystyle n\neq 3}$
• アイテムとエージェントがあります。${\displaystyle m\leq n+7}$${\displaystyle n\geq 8}$
• アイテムとエージェントがあります。${\displaystyle m\leq n+c}$${\displaystyle n\geq \lfloor 0.6597c(c!)\rfloor }$

アマナティディス、マルカキス、ニクザド、サベリ^[11]は、MMS割り当てが存在し、各項目が0、1、または2の値を持つ 3値評価の場合には多項式時間で見つけることができることを示しました。

ウリエル・ファイギ^[14]は、MMS配分は常に2つの値aとbが存在し、各エージェントはすべてのアイテムをaまたはbのいずれかで評価する二値インスタンスに存在することを証明しました。

Budish ^[2]は、1-of -n MMSの近似値である1-of-(${\displaystyle n+1}$ ) MMSを導入した。これは、各エージェントが少なくともn +1個のバンドルに分割して最も悪いバンドルを取得した場合に得られる量と同じ量を受け取るというものである。一般に、任意のd > nに対して、1-of-d MMSを1-of -n MMSの近似値と見なし、各エージェントiに対して次の割り当てを求めることができる。

${\displaystyle V_{i}(Z_{i})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}d}(C)}$

1-of-d MMSの値はdの弱減少関数であることに注意してください。これは、バンドルの順位にのみ依存し、バンドルの正確な値には依存しないため、順序近似と呼ばれます。Procaccia と Wang ^{[3] は、 MMS の}乗法近似という別の種類の近似を導入しました。割り当ては、[0,1] 内の何らかの分数 r に対してr 分数 MMS公平であり、各エージェントの価値が少なくともその MMS の値の分数rである場合、つまり各エージェントiに対して次のようになります。

${\displaystyle V_{i}(Z_{i})\geq r\cdot \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}$

2 つのアルゴリズムから選択できるとします。最初のアルゴリズムは乗法近似 (例: 3/4 分数 MMS) を保証し、2 番目のアルゴリズムは順序近似 (例: 1-out-of-(3 n /2) MMS) を保証します。どちらの保証の方が高いでしょうか。答えは値によって異なります。

• たとえば、値が 1 である同一の商品がn 個ある場合、乗法近似値は高くなります。この場合、 d > n のいずれの場合も1-of-${\displaystyle d}$ MMS は 0 になりますが、1-of- MMS は 1 になるため、その正の乗法近似値はより適切になります。${\displaystyle n}$
• たとえば、{ n +1,...,2n - 1}内のいずれかのdに対して、値が 1 である同一の商品がd個ある場合、順序近似は高くなります。この場合、 1-of-d MMS は 1 になり、1-of- MMS も 1 になるため、r <1のr乗法近似はより悪くなります。${\displaystyle n}$

一般に、任意の整数kに対して、1-of- n MMS は1-of- nk MMSの少なくともk倍です。つまり、最適な 1-of- nk MMS パーティションを取り、バンドルをn 個のスーパーバンドルにグループ化します。各スーパーバンドルにはk個の元のバンドルが含まれます。これらのスーパーバンドルのそれぞれは、最小の元のバンドルの少なくともk 倍の価値があります。したがって、1/ k乗法近似は、1-of- nk順序近似と少なくとも同じ大きさですが、上記の例のように、1-of-( nk- 1) 順序近似よりも小さくなる可能性があります。特に、r ≥ 1/2 のr乗法近似は、1-of-(2 n ) 順序近似と少なくとも同じくらい優れていますが、1-of-(2 n -1) 順序近似 よりも劣る可能性があります。

プロカシアとワン^{[3]は、常に}r _n分数MMSを見つけるアルゴリズムを提示した。

${\displaystyle r_{n}:={\frac {2\cdot {\text{oddfloor}}(n)}{3\cdot {\text{oddfloor}}(n)-1}}={\begin{cases}{\frac {2n}{3n-1}}&n~{\text{ odd}}\\{\frac {2n-2}{3n-4}}&n~{\text{ even}}\end{cases}}}$

ここで oddfloor( n ) はn以下の最大の奇数です。特に、r ₃ = r ₄ = 3/4 はnが増加すると減少し、常に 2/3 より大きくなります。このアルゴリズムは、 nが定数の場合、 mの多項式時間で実行されますが、 nの指数関数的に実行される場合があります。

Amanatidis、Markakis、Nikzad、Saberi ^{[11] は、}いくつかの改良されたアルゴリズムを提示しました。

• シンプルで高速な 1/2 分数 MMS アルゴリズム。
• mとn の両方で多項式時間で実行される 2/3 分数 MMS アルゴリズム。
• 3 エージェント用の 7/8 分数 MMS アルゴリズム。

バーマンとクリシュナムルシー^{[15] [16]}は以下を発表した。

• 加法的な評価を伴う 2/3 分数 MMS のシンプルで高速なアルゴリズム。このアルゴリズムは、インスタンスを「順序付け」 (つまり、すべてのエージェントが商品の順位付けに同意するインスタンスにインスタンスを減らす) し、最も価値のある商品から羨望グラフ手順を実行することに基づいています。このアルゴリズムは、異なる評価を持つエージェントに対する最長処理時間優先スケジューリングアルゴリズムの適応と見ることができます。このアルゴリズムは、結果が EFX であり、各エージェントに少なくとも 2/3 である MMS を保証することを証明しています。${\displaystyle {\frac {2n}{3n-1}}}$
• ラウンドロビン項目割り当てに基づく、より困難なサブモジュラー評価の場合の 1/10 分数 MMS のシンプルなアルゴリズム。

Ghodsi、Hajiaghayi、Seddighin、Seddighin、Yami ^[17]は次のように発表しました。

• 加法評価の場合: 3/4 分数 MMS 公平性の存在証明。
• n =4 添加剤の場合: 4/5 フラクション MMS 公平性のアルゴリズム。
• サブモジュラ評価の場合: 1/3 分数の MMS 公平性のための多項式時間アルゴリズムと、3/4 分数の上限。
• XOS 評価の場合: 1/8 分数 MMS 公平性の多項式時間アルゴリズム、1/5 分数の存在証明、および 1/2 分数の上限。
• 劣加法的評価の場合：log( m )/10分数MMS公平性の存在証明と1/2分数の上限。

Garg、McGlaughlin、Taki ^[18]は、 2/3分数MMS公平性のための単純なアルゴリズムを提示し、その解析も単純であった。

ガーグとタキ^[19]は以下を発表した。

• 3/4 分数 MMS のシンプルなアルゴリズム。MMS 値を知る必要がなく、したがって強力な多項式時間で実行されます。
• -分数 MMSの存在の証明。${\displaystyle ({\frac {3}{4}}+{\frac {1}{12n}})}$

Akrami、Garg、Sharma、Taki ^[20]は、GargとTakiによって提示されたアルゴリズムの解析を改善し、解析を簡素化し、存在保証を改善しました。 ${\displaystyle {\frac {3}{4}}+\min \left({\frac {1}{36}},{\frac {3}{16n-4}}\right)}$

現在までに、 r分数の MMS 割り当てが常に存在するような最大のrが何であるかはわかっていません。これは、 ～の間の任意の数値になります。 ${\displaystyle 3/4}$${\displaystyle 39/40}$

Budish ^[2]は、等所得からの近似競争均衡が常に1-of-(${\displaystyle n+1}$ ) MMSを保証することを示しました。しかし、この割り当ては供給過剰、そしてさらに重要なことに需要過剰になる可能性があります。つまり、すべてのエージェントに割り当てられたバンドルの合計が、すべてのアイテムのセットよりもわずかに大きくなる可能性があります。このようなエラーはコース割り当てでは合理的です。なぜなら、わずかな供給過剰は少数の座席を追加することで修正できるからです。しかし、古典的な公平な分割問題では、アイテムが追加されない可能性があると想定されています。

過剰な供給と需要がなければ、次の近似値がわかります。

• 嫉妬のないマッチングを用いた、 1-out-of(2 n -2) MMSの財貨配分と1-out-of(2 n /3) MMSの家事配分。^[23]
• 1-out-of-( 3n /2)MMS財配分^[24]は、 n <6の場合には多項式時間で計算できる。
• 多項式時間での1-out-of-( 3n /2) MMS商品の割り当てと、L -out-of-([ L +1/2] n ) MMS割り当ての存在結果。^[16]
• 1-out-of-(3n / 4) MMS家事割り当て。^[25]

現在までに、 1-out- d MMS 割り当てが常に存在する最小のdが何であるかはわかっていません。これはn +1 から 3 n/ 2までの任意の数値になります。最小の未解決ケースはn =4 です。

積の最大化：Caragiannis、Kurokawa、Moulin、Procaccia、Shah、Wang ^[26]は、最大ナッシュ福祉配分（効用の積を最大化する配分）は常に分数MMS公平であり、緊密であること を示した。${\displaystyle {\frac {2}{1+{\sqrt {4n-3}}}}}$

真実性：アマナティディス、バームパス、マルカキス^[27]は、 MMSに公平な近似配分のための真実性の高いメカニズムを提示した（戦略的公平分割も参照）。

• nエージェントの場合: 1/O( m )分数MMS。
• 2 つのエージェントの場合: 1/2 分数の MMS、および真実のメカニズムは 1/2 を超える値を達成できないという証明。

カーディナリティ制約: アイテムはカテゴリに分割され、各エージェントは各カテゴリhから最大k _{h 個の}アイテムを取得できます。言い換えると、バンドルはパーティションマトロイドの独立したセットである必要があります。

• BarmanとBiswas ^{[28] :10は}、問題を制約のないサブモジュラ評価の問題に縮小するアルゴリズムを提示し、次に^[17]のアルゴリズムを使用して1/3分数MMS公平性を達成した。
• HummelとHetland ^[29]は、1/2分数MMS公平性のための改良された多項式時間アルゴリズムを提示している。彼らは、制約のない設定から制約のある設定への標準的な手法と削減を適用し、次にバッグフィリング手順の変形を適用している。

競合グラフ: HummelとHetland ^[30]は、アイテム間に競合グラフが存在する別の設定を研究している(例えば、アイテムはイベントを表し、エージェントは2つのイベントに同時に参加できない)。彼らは、競合グラフの次数がdで、それが(2, n )にある場合、1/ d分数のMMS割り当ては多項式時間で見つけることができ、1/3分数のMMS割り当ては常に存在することを示している。

接続性: 項目はグラフ上に配置され、各部分は接続されたサブグラフである必要があります。

• Bouveret、Cechlarova、Elkind、Igarashi、Peters ^[31]は、グラフが非巡回である場合、MMS公平な割り当てが常に存在し、効率的に見つけることができることを証明しています。一般的なグラフでは、MMS公平な割り当てが存在しない可能性があり、見つけるのはNP困難である可能性があります。
• LoncとTruszczynski ^[32]はグラフがサイクルである場合に焦点を当て、MMSにほぼ公平な割り当てのためのアルゴリズムを提示している。

アジズ、ラウチェッカー、シュリーエン、ウォルシュ^[33]はMMSの概念を家事（負の効用を持つ項目）に拡張した。家事の場合、乗法近似係数は1より大きく（家事の数が少なければ少ないほど効用が高くなるため）、順序近似係数はnより小さいことに注意する。彼らは以下を示した。

• 雑用のための MMS 割り当てが存在しない可能性があることの証明。
• 家事のための 2 分割 MMS アルゴリズム。
• 多元数分割アルゴリズムに基づいて、特定のインスタンスの最適な MMS 近似値を見つけるアルゴリズム。

BarmanとKrishnamurthy ^[16]は4/3分数MMS（正確には）を達成するアルゴリズムを提示した。このアルゴリズムは、同一機械スケジューリングのための LPTアルゴリズムの一般化と見ることができる。${\displaystyle {\frac {4n-1}{3n}}}$

HuangとLu ^[34]は、雑用に対する11/9分率MMS公平割り当てが常に存在し、5/4分率MMS割り当ては多項式時間で見つけられることを証明した。彼らのアルゴリズムは、同一機械スケジューリングのためのマルチフィットアルゴリズムの一般化と見なすことができます。

クルカルニ、メータ、タキ^[35]は、混合評価、つまり財と家事の両方がある場合 のMMS公平な配分を研究している。彼らは次のことを証明している。

• 乗法近似は不可能です。彼らは、Procaccia と Wang ^[3]の例を拡張して、値が -4,054,999.75 の家事を 3 つ追加しました。各エージェントの 1-out-of-3 MMS は 0.25 です (各 MMS バンドルには、合計が 4,055,000 の 4 つの商品と 1 つの家事が含まれています)。ただし、商品の割り当てごとに、少なくとも 1 人のエージェントに、商品から最大 4,054,999 の値が割り当てられます。各エージェントに 1 つの家事を割り当てる必要があるため、少なくとも 1 人のエージェントは負の値を持ちます。
• また、特定のインスタンスで可能な限り最良の α を得るために、α-MMS とパレート最適割り当てを多項式時間で計算できる条件も提示します。

エバディアン、ピーターズ、シャー^{[36]は、各エージェント}iが仕事を「簡単」（全員に対して1と評価）または「難しい」（ある整数p _i > 1と評価）に分割する場合、MMS割り当ては常に二値インスタンスに存在することを証明している。

さまざまな正規化を元の問題に適用しても、解決策は変わりません。以下では、O はすべてのオブジェクトの集合です。

各エージェント i について、すべての評価が係数(エージェントごとに異なる可能性がある) でスケーリングされると、各エージェントの MMS は同じ係数でスケーリングされます。したがって、元のインスタンスのすべての MMS 割り当ては、スケーリングされたインスタンスの MMS 割り当てになります。各エージェントの MMS が正確に になるように評価をスケーリングするのが一般的です。このスケーリングの後、MMS 近似問題は次のように表すことができます。 ${\displaystyle k_{i}}$${\displaystyle 1}$

• ${\displaystyle r}$-分数 MMS : の合計値は少なくとも です。各エージェントに少なくとも の価値があるバンドルを与える必要があります。${\displaystyle O}$${\displaystyle n}$${\displaystyle n}$${\displaystyle r}$
• 1-of-d MMS : の合計値は少なくとも です。各エージェントに少なくとも の価値があるバンドルを与える必要があります。${\displaystyle O}$${\displaystyle d}$${\displaystyle n}$${\displaystyle 1}$

上記のスケーリングでは、各エージェントのMMSを計算する必要がありますが、これはNP困難問題（多元数分割）です。より高速に実行できる代替スケーリングは次のとおりです。^[18]

• ${\displaystyle r}$-分数 MMS : の合計値はちょうど です。MMS は最大で です。各エージェントに少なくとも の価値があるバンドルを与える必要があります。${\displaystyle O}$${\displaystyle n}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle r}$
• 1-of-d MMS : の合計値はちょうど です。MMS は最大でも です。各エージェントに少なくとも の価値があるバンドルを与える必要があります。${\displaystyle O}$${\displaystyle d}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle 1}$

からオブジェクトを 1 つ取り除くと、各エージェントに対して、残りのセットに関する-out-of-( ) MMS は、元のセットに関する-out-of -MMS以上になります。これは、元の MMS 分割では、パーツがそのまま残るためです。^[12]ここで、各エージェントに の値を与えることを目指すとします。あるオブジェクトが少なくとも1 人のエージェントにとって 以上の価値がある場合、そのようなエージェントの 1 人に を任意に与え、残りのオブジェクトを残りのエージェントに割り当てることができます。したがって、次のことを想定できます。 ${\displaystyle o}$${\displaystyle O}$${\displaystyle 1}$${\displaystyle n-1}$${\displaystyle O\setminus o}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle O}$${\displaystyle n-1}$${\displaystyle r}$${\displaystyle o_{1}}$${\displaystyle r}$${\displaystyle o_{1}}$

• ${\displaystyle r}$-fraction MMS  : すべてのエージェントの各オブジェクトの値が 未満です。${\displaystyle r}$
• ${\displaystyle 1}$-of- MMS  : すべてのエージェントの各オブジェクトの値が 未満です。${\displaystyle d}$ ${\displaystyle 1}$

この正規化は高速スケーリングでも機能し、任意の単調評価（非加法性も含む）でも機能します。^[17]

すべてのエージェントによって最大で だけ価値があるオブジェクトを「-small オブジェクト」と表記します。すべてのオブジェクトが-small であると仮定します。空のバッグを取り、バッグが少なくとも 1 人のエージェントにとって少なくとも だけ価値があるまで、オブジェクトを次々と詰めていきます。次に、バッグをそのようなエージェントの 1 人に任意に渡します。すべてのオブジェクトが-small であるため、残りのエージェントはバッグに最大で だけ価値を見出します。この値が十分に小さい場合、残りの値は十分に大きいため、再帰的に処理を進めることができます。^[18]特に、バッグフィリングでは次のソリューションが得られます。 ${\displaystyle s}$${\displaystyle s}$${\displaystyle s}$${\displaystyle r}$${\displaystyle s}$${\displaystyle r+s}$

• 1/2分数MMS  : を取る。前の正規化により、すべてのオブジェクトが-小さいと仮定できることに注意。最初はn人のエージェントがいて、それらの合計値は少なくとも である。バッグが割り当てられた後、残りのエージェントは残りのオブジェクトを少なくとも と評価するため、再帰的に進めることができます。^[17]${\displaystyle s=r=1/2}$${\displaystyle 1/2}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n-(r+s)=n-1}$
• 1-of-(2n) MMS  : を取ります。前の正規化により、すべてのオブジェクトが -small であると想定できることに注意してください。最初はエージェントが存在し、エージェントの合計値は少なくとも です。バッグが割り当てられた後、残りのエージェントは残りのオブジェクトを少なくとも と評価するため、再帰的に進めることができます。${\displaystyle s=r=1}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle 2n}$${\displaystyle n-1}$${\displaystyle 2n-(r+s)=2n-2=2(n-1)}$

これらのバッグフィリングアルゴリズムは高速スケーリングでも機能するため、多項式時間で実行され、正確なMMS値を知る必要はありません。^[18]実際、両方のアルゴリズムはMMSについてまったく言及せずに記述することができます。

• 各オブジェクトの価値が合計価値の最大限であるすべてのエージェントは、合計価値の少なくとも一部を受け取ります。${\displaystyle 1/(2n)}$${\displaystyle 1/(2n)}$

修正されたバッグフィリング: すべてのオブジェクトが -small であるという条件は、次のように緩和できます。^[18]いくつかの を取ります。 -small ではないオブジェクト(つまり、少なくとも 1 人のエージェントによって少なくとも の価値がある) を「-large オブジェクト」と示します。最大で のオブジェクトが-large であるとします。1 つの-large オブジェクトを取り、それをバッグに入れ、1 人のエージェントが少なくとも の価値があると示すまで、-small オブジェクトでバッグを満たします。一部のエージェントはで評価するため、そのようなエージェントが少なくとも 1 人いる必要があります。このエージェントにとって、最大で の -large オブジェクトが残ります。前の正規化により、これらのオブジェクトはまだ-small であるため、 に対するそれらの合計値は最大で となり、残りの -small オブジェクトの値は少なくとも になります。${\displaystyle s}$${\displaystyle s<r}$${\displaystyle s}$${\displaystyle s}$${\displaystyle s}$${\displaystyle n}$${\displaystyle s}$${\displaystyle s}$${\displaystyle o_{1}}$${\displaystyle s}$${\displaystyle r}$${\displaystyle i}$${\displaystyle o_{1}}$${\displaystyle x>s}$${\displaystyle n-1}$${\displaystyle s}$${\displaystyle r}$${\displaystyle i}$${\displaystyle r(n-1)}$${\displaystyle s}$${\displaystyle n-r(n-1)-x=r(n-1)+r-x\geq r-x}$

インスタンスが順序付けられているとは、すべてのエージェントがオブジェクトに対して同じ順序順位を持っている場合、つまり、各エージェント に対して となるようにオブジェクトに番号を付けることができる場合です。直感的には、順序付けられたインスタンスは、エージェント間の衝突が最大となるため、最も困難です。実際、^[3]の負のインスタンスは順序付けられています。オブジェクトの順序は、すべてのエージェントに対して同じである行列 によって決定されます。これは、形式的に証明することもできます。順序付けられたすべてのインスタンスに対して、分数 MMS 割り当てを見つけるアルゴリズムがあるとします。ここで、一般的なアイテム割り当てインスタンス が与えられています。これを次のように解きます。^{[12] [15]}${\displaystyle o_{1},\dots ,o_{m}}$${\displaystyle i}$${\displaystyle v_{i}(o_{1})\geq \dots \geq v_{i}(o_{m})}$${\displaystyle T}$${\displaystyle r}$${\displaystyle P}$

1. 次のように順序付けられたインスタンスを構築します。すべてのエージェントiについて、を におけるエージェントの値の集合の中で - 番目に高い値として定義します。 これには時間がかかります。${\displaystyle \mathrm {ord} (P)}$${\displaystyle v_{i}(o_{j})}$${\displaystyle \mathrm {ord} (P)}$${\displaystyle j}$${\displaystyle i}$${\displaystyle P}$${\displaystyle O(nm\lg m)}$
2. 内の- 分数 MMS 割り当てを見つけます。${\displaystyle r}$${\displaystyle \mathrm {ord} (A)}$${\displaystyle \mathrm {ord} (P)}$
3. 受け取ったエージェントが最初に選択し、受け取ったエージェントが2 番目に選択する、というように選択シーケンスを構築します。${\displaystyle o_{1}}$${\displaystyle \mathrm {ord} (A)}$${\displaystyle o_{2}}$${\displaystyle \mathrm {ord} (A)}$
4. エージェントが選択順序に従って最適なアイテムを選択するようにします。が結果として生じる割り当てであるとします。 では、各エージェントは とまったく同じ数のアイテムを受け取ります。 さらに、でアイテムを受け取った各エージェントは、で自分のトップアイテムの 1 つを受け取ります。 したがって、 で受け取った各アイテムの価値は、の対応するアイテムの価値と少なくとも同じ大きさです。したがって、 のすべてのエージェントの価値は、におけると少なくとも同じ大きさです。 順序付けによって MMS 値が変わらないため、新しい割り当ては依然として-fraction MMS です。${\displaystyle A}$${\displaystyle A}$${\displaystyle \mathrm {ord} (A)}$${\displaystyle o_{j}}$${\displaystyle \mathrm {ord} (A)}$${\displaystyle j}$${\displaystyle A}$${\displaystyle A}$${\displaystyle \mathrm {ord} (A)}$${\displaystyle A}$${\displaystyle \mathrm {ord} (A)}$${\displaystyle A}$${\displaystyle r}$

したがって、分数 MMS 割り当て を探すときは、次のことを想定できます。${\displaystyle r}$

• オブジェクトの順序順位はすべてのエージェントに対して同じです。

2 つのオブジェクトo ₁とo _{2 を}見つけたとします。エージェントi の1 人が少なくともr を評価し、他のエージェントが最大で 1 を評価するとします。この場合、これらの 2 つのオブジェクトはiに割り当てられます。他のエージェントにとって、残りのセットに対する1-out-of-( n -1) MMS は、元のセットOに対する 1-out-of- n MMS と少なくとも同じです。これは、元の MMS パーティションでは、少なくとも n -2 個の部分がそのまま残り、そのままではない 2 つの部分を組み合わせて、少なくとも 1 の値を持つ単一の部分を形成できるためです。この正規化は、加法的な評価でのみ機能します。^{[17] : Lem.3.2}

さらに、インスタンスが順序付けられていると仮定し、Oから2 つのオブジェクトo _n、o _{n +1} (つまり、n番目と ( n +1) 番目に価値の高いアイテム) を削除するとします。すると、各エージェントにとって、残りのセットに対する 1-out-of-( n -1) MMS は、元のセットOに対する 1-out-of- n MMS以上になります。これは、ピジョンホール原理により、各エージェントの少なくとも 1 つの MMS 部分に、セット { o ₁、...、o _{n +1} } からの 2 つ以上のオブジェクトが含まれていなければならないためです。これらのアイテムを使用して、譲渡されたオブジェクトを置き換えることができます。その結果、値が少なくとも 1 であるn -1 個の部分が生成されます。つまり、オブジェクト o _n、o _{n +1が、あるエージェント}iに対して少なくとも MMS の値を持つ場合、それらをiに渡して、残りのオブジェクトを残りのエージェントに割り当てることができます。したがって、次のことを想定できます。

• r 分数 MMS : すべてのエージェントのo _n、o _{n +1}の合計値がr未満です。特に、o _{n +1と、順序付けでそれ以降のすべてのオブジェクトの値は}r /2未満です。
• 1-of-d MMS : すべてのエージェントのod、o _{d +1} の合計値は1 未満です。特に、o _{d +1}と、順序付けでそれ以降のすべてのオブジェクトの値は 1/2 未満です。

この正規化は高速スケーリングでも機能します。これを修正バッグフィリングと組み合わせると、2/3分率MMSの次の単純なアルゴリズムが得られます。^[18]

• 単一のオブジェクトが何らかのエージェントにとって少なくとも 2/3 の価値がある限り、それを割り当てます。
• インスタンスを注文します。
• o _n、o _{n +1 が}何らかのエージェントにとって少なくとも 2/3 の価値がある限り、それらを割り当てます。
• 最後に、値が少なくとも 1/3 であるオブジェクトは最大でn個あります。修正されたバッグフィリングを使用してそれらを割り当てます。

このアルゴリズムの保証は、MMS について言及しなくても次のように述べることができます。

• o _{1 の}価値が合計値の2/(3 n ) 以下であり、 o _n + o _{n+1 の}価値を合計しても合計値の 2/(3 n ) 以下であるすべてのエージェントは、合計値の少なくとも 2/(3 n ) を受け取ります。

MMS に関連するいくつかの基本的なアルゴリズムは次のとおりです。

• 特定のエージェントの1-of- n MMS を計算します。これは NP 困難な最適化問題ですが、近似アルゴリズムがいくつかあります。Multiway number パーティショニングおよびIdentical-machines scheduling を参照してください。
• 与えられた割り当てがMMS公平であるかどうかを判断することは、加法的な評価を持つエージェントにとってco- NP完全である（エージェントの1人のMMSパーティションが与えられれば、そのエージェントのMMS値が与えられた割り当てにおけるそのエージェントの値よりも大きいことを示し、与えられた割り当てがMMS公平ではないことを多項式時間で証明することができるので、co-NPである）。[ ^37]
• すべてのエージェントの MMS 値が与えられた場合、特定のインスタンスが MMS 割り当てを許可するかどうかを決定します。割り当てが与えられた場合、多項式時間で検証できるため、NP に属します。正確な実行時の複雑さは不明です。
  • したがって、与えられたインスタンスが任意のMMS割り当てを許可するかどうかを決定することは、NP問題へのオラクルを使用して非決定性多項式時間で解決できます（オラクルはエージェントのMMSを計算するために必要です）。ただし、この問題の正確な計算複雑性はまだ不明です。多項式階層のレベル2または1、あるいは0である可能性があります。^[12]${\displaystyle NP^{NP}}$
• 最小最大シェア配分が存在するかどうかを確認する決定問題はNP 困難です。エージェントの数が固定されていると仮定すると、両方の問題はPTASで近似できます。エージェントの評価がバイナリまたは加法的で、ボルダスコアに基づいている場合、最大最小シェア配分は常に効率的に見つけることができます。エージェントの評価が非加法的である場合、任意の正のrに対してr分数 MMS 配分が存在しない場合があります。ただし、対称サブモジュラー効用クラスでは、タイトな 1/2 分数 MMS 配分が存在し、1/4 の係数内で近似できます。^[38]

エージェントiの割り当ては、他のすべてのエージェントjについて、 jのバンドルから削除された場合にi が残りのアイテムを羨まない最大c 個のアイテムのセットが存在する場合、羨望フリー(EF c ) と呼ばれます。 EF0 割り当ては単に羨望フリーと呼ばれます。 EF1 割り当ては、たとえば、ラウンドロビン アイテム割り当てまたは羨望グラフ手順によって見つけることができます。

エージェントiのバンドルの外側に最大 c 個のアイテムのセットが存在し、そのセットがすべてのアイテムのセットから削除された場合、i がそのバンドルを残りの少なくとも 1/ n と評価する場合、その割り当ては、c個以外のアイテムに対して比例( PROP * c )と呼ばれます。PROP*0 割り当ては、単に比例と呼ばれます。

EF0はPROP*0を意味し、EF1はPROP*( n -1)を意味する。さらに、任意の整数c0に対して、EFcはPROP*(( n -1) c )を意味する。^{[39] ：Lem.2.3}逆の含意はn =2のときは真だが、n >2のときは真ではない。

PROP*( n -1)から次の最大シェア近似が導かれ、したがってEF1からも導かれる: ^{[39] :Lem.2.7}

• 乗法近似：1/ n分数MMS（1/ nはタイト）^{[40] ：Prop.3.6}
• 順序近似: 1-of-(2 n -1) MMS (2 n -1 はタイトです)。同様に、すべての整数cに対して、 PROP* c は1-of-( c + n ) MMS を意味します。
• 価値関数がバイナリの場合の MMS。逆の意味も成り立ちます。

上記の意味は以下のように説明されます。

エージェントiの割り当ては、他のすべてのエージェントjについて、 jのバンドルから削除された任意の単一のアイテムに対してiが残りのアイテムを羨まないとき、羨望フリー(EF x ) と呼ばれます。EFx は EF1 よりも厳密に強いです。これは次の MMS 近似を意味します: ^{[40] : 命題 3.3-3.4}

• 2剤または3剤の2/3分割MMS（タイトです）
• 任意の数のエージェントに対する 4/7 分割 MMS (厳密かどうかは不明です。現在の上限は 8/13 です)。

2人のエージェントiとjに対して、エージェントi がiとjが受け取るアイテムに制限された2分の1の最大シェアを少なくとも受け取る場合、その割り当てはペアワイズ最大シェア公平（PMMS公平）と呼ばれます。PMMS割り当てが常に存在するかどうかは不明ですが、0.618近似は常に存在します。^[26]

エージェントのサイズkのサブグループごとに、サブグループの各メンバーが、このサブグループが受け取るアイテムに制限された1対kの最大シェアを受け取る場合、その割り当てはグループワイズ最大シェア公平（GMMS公平）と呼ばれます。^[41]

加法的な評価では、さまざまな公平性の概念が次のように関連しています。

• 嫉妬のなさはGMMSの公平性を意味する。^[41]
• GMMS公平性は、MMS公平性（サイズnのサブグループを取ることによって）とPMMS公平性（サイズ2のサブグループを取ることによって）を意味します。
• PMMS公平性は3つのエージェントに対して2/3-MMS公平性を意味し、一般的には4/7-MMS公平性を意味する。^[40]
• PMMS 公平性は EFX を意味し、EFX は EF1 を意味します。
• EF1は1/2-PMMSを意味し、EFXは2/3-PMMSを意味する。^{[40] ：命題3.7-3.8}したがって、1/2-PMMS割り当ては多項式時間で見つけることができます。
• MMS 公平性と PMMS 公平性は相互に意味を持ちません。

GMMS割り当ては、エージェントの評価が2値または同一の場合に必ず存在する。一般的な加法評価では、1/2-GMMS割り当てが存在し、多項式時間で見つけることができる。^[41]

エージェントが異なる権利を持つ場合（不平等な分配または非対称の権利とも呼ばれる）、MMS 公平性は、より高い権利を持つエージェントにより高い分配を保証するように適応される必要があります。さまざまな適応が提案されています。以下では、権利がベクトル によって与えられ、 がエージェントの権利を表すものと仮定します。 ${\displaystyle t=(t_{1},\ldots ,t_{n})}$${\displaystyle t_{i}}$${\displaystyle i}$

Farhadi、Ghodsi、Hajiaghayi、Lahaie、Pennock、Seddighin、および Seddigin ^{[42] は}、次のように定義される加重最大シェア (WMMS) を導入しています。

${\displaystyle \operatorname {WMMS} _{i}^{t}(C):=~~~\max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~{\frac {t_{i}}{t_{j}}}V(Z_{j})=~~~t_{i}\cdot \max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~{\frac {V(Z_{j})}{t_{j}}}}$

直感的には、最適な WMMS は、部分jの価値がエージェントjの権利に比例する分割によって達成されます。たとえば、すべての価値関数が合計であり、権利ベクトルがt =(1/6, 11/24, 9/24) であるとします。次に、分割 ({1,3},{5,6},{9}) によって、各部分の値が に等しいため最適になります。同じ分割によって、および になります。n 個の権利がすべて等しい場合、 になります。 ${\displaystyle \operatorname {WMMS} _{1}^{t}(\{1,3,5,6,9\})=4}$${\displaystyle i}$${\displaystyle 24t_{i}}$${\displaystyle \operatorname {WMMS} _{2}^{t}=11}$${\displaystyle \operatorname {WMMS} _{3}^{t}=9}$${\displaystyle \operatorname {WMMS} _{i}^{t}\equiv \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}}$

Cの割り当ては、各エージェント i の価値が少なくとも である場合、権利ベクトルtに対してWMMS 公平であると呼ばれます。すべてのn人のエージェントが同一の評価を持つ場合、定義により WMMS 公平な割り当てが常に存在します。ただし、評価が異なる場合、可能な限り最良の乗法近似は 1/ nです。上限は、2 n -1 個の商品とn人のエージェントを使用した次の例によって証明されます。ここで、ε>0 は非常に小さな定数です。 ${\displaystyle \operatorname {WMMS} _{i}^{t}(C)}$

すべてのエージェントには最適な WMMS パーティションがあります。「小型」エージェント (1、...、n -1) の場合、パーティションは ({1}、...、{ n -1}、{ n }) で、「大型」エージェント ( n ) の場合、パーティションは ({ n +1}、...、{2n -1 }、{1、...、n }) です。したがって、すべてのエージェントiについて(比較のため、小型エージェントの場合は 、大型エージェントの場合は であることに注意してください)。${\displaystyle \operatorname {WMMS} _{i}^{t}=t_{i}}$${\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=\epsilon =t_{i}}$${\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=[1-(n-1)\epsilon ]/n=t_{i}/n}$

WMMS の乗法近似では、すべてのエージェントが正の値を取得する必要があります。つまり、小さなエージェントはアイテム 1、...、nのうち少なくともn -1 個を取得するため、大きなエージェントには最大で 1 つのアイテムが残り、その値はほぼ 1 ではなく、 約 1/ nになります。

1/ n分数の WMMS 公平な割り当ては常に存在し、ラウンドロビンアイテム割り当てによって見つけることができます。各エージェントiが各財を最大で だけ評価するという制限されたケースでは、1/2 分数の WMMS 公平な割り当てが存在し、バッグフィリングに似たアルゴリズムによって見つけることができます。つまり、各エージェント i の評価に を掛け、各反復で、そのアイテムを最も高く評価する不満足なエージェント ( 未満の価値を持つエージェント) にアイテムを与えます。このアルゴリズムは、各エージェントiに少なくとも 、最大で を割り当てます。実際には、WMMS 公平な割り当てはほとんど常に存在します。^[42]${\displaystyle \operatorname {WMMS} _{i}^{t}}$${\displaystyle t_{i}/\operatorname {WMMS} _{i}^{t}}$${\displaystyle \operatorname {WMMS} _{i}^{t}/2}$${\displaystyle \operatorname {WMMS} _{i}^{t}/2}$${\displaystyle \operatorname {WMMS} _{i}^{t}}$

ババイオフ、ニサン、タルガム・コーエン^[43]は、異なる権利を持つエージェントへの順序MMS近似の自然な拡張を提示している。任意の2つの整数、集合C、価値関数Vに対して、次のように定義する。${\displaystyle l,d}$

${\displaystyle \operatorname {MMS} _{V}^{l{\text{-out-of-}}d}(C):=~~~\max _{P\in \operatorname {Partitions} (C,d)}~~~\min _{Z\in \operatorname {Unions} (P,l)}~~~V(Z)}$

ここで、最大値はCを互いに素な部分集合に分割したすべての部分に対して適用され、最小値はすべての部分の和集合に対して適用されます。たとえば、分割 ({1,6},{3,5},{9}) によって適用されます。ここで、順序最大シェア (OMMS)は次のように定義されます。${\displaystyle d}$${\displaystyle l}$${\displaystyle \operatorname {MMS} _{V}^{2{\text{-out-of-}}3}(\{1,3,5,6,9\})=15}$

${\displaystyle \operatorname {OMMS} _{i}^{t}(C):=~~~\max _{l,d:~l/d\leq t_{i}}\operatorname {MMS} _{i}^{l{\text{-out-of-}}d}(C)}$

例えば、エージェントiの権利が 2/3 以上の実数である場合、エージェント i は少なくともCの 2-out-of-3 MMS を受け取る権利があります。を満たすペアは無限にありますが、そのうち冗長でない（他のペアによって暗示されない）のは有限個だけであるため、OMMS を有限時間で計算することが可能です。^[44]割り当てZ ₁ ,..., Z _{n は}、各エージェント i の値が少なくとも である場合、権利ベクトル w に対して OMMS 公平であると呼ばれます。 ${\displaystyle l,d}$${\displaystyle l/d\leq t_{i}}$${\displaystyle \operatorname {OMMS} _{i}^{t}(C)}$

OMMSは値に応じてWMMSよりも高くなることも低くなることもあります。^[44]

• WMMS の方が高い例として、C = {40, 60}およびt = (0.4, 0.6)と仮定します。この場合、明らかに WMMS ₁ =40、WMMS ₂ =60 となるため、唯一の WMMS 公平な割り当ては 40 対 1、60 対 2 となります。ただし、OMMS ₁ =0 です。これは、満たす分数が 1/3、2/5、3/7 などであり、すべてのケースで、Cをサブセットに分割すると、少なくとも 1 つの空のサブセットが存在するためです。また、OMMS ₂ =40 です。これは、満たす分数が 1/2、2/4、3/5、4/7 などであり、すべての場合において、Cをサブセットに分割した場合、最も価値の低いサブセットに 60 が含まれないためです。したがって、OMMS 公平な割り当てでは、40 が 2 に、60 が 1 に割り当てられるか、1 に何も割り当てられない可能性がありますが、どちらも不公平に思えます。${\displaystyle l/d\leq 0.4}$${\displaystyle d}$${\displaystyle l}$${\displaystyle l/d\leq 0.6}$${\displaystyle d}$${\displaystyle l}$
• OMMS がより高い例として、C = {40, 60}およびt = (0.2, 0.2, 0.6)と仮定します。このとき、 Cの任意の 3 分割で少なくとも 1 つのバンドルが空であるため、すべてのiに対してWMMS _{i =0 となります。したがって、 WMMS 公平性基準は役に立ちません。同様に、 OMMS 1} =OMMS ₂ =0 です。ただし、ペアと分割 ({40},{60}) によりOMMS ₃ =40となるため、OMMS 公平性ではエージェント 3 に少なくとも 1 つのアイテムを与える必要があり、これはより公平であると思われます。${\displaystyle l/d=1/2}$

ババイオフ、エズラ、フェイジ^[45]は、公平性の第3の基準として、AnyPrice Share (APS)を導入しました。彼らはこれを2つの同等の方法で定義しています。そのうちの1つは明らかにマキシミンシェアの強化です。アイテムをd個の互いに素なバンドルに分割する代わりに、エージェントはバンドルの任意のコレクションを選択できます。バンドルは重複していてもかまいません。ただし、エージェントは各バンドルに重みを割り当て、重みの合計が少なくとも1になるようにする必要があります。また、各アイテムは、合計重みがエージェントの権利以下であるバンドルに属します。APSは、最も価値の低い正の重みのバンドルの値です。正式には、

${\displaystyle \operatorname {APS} _{V}^{t}(C):=~~~\max _{P\in \operatorname {AllowedBundleSets} (C,t_{i})}~~~\min _{Z\in P}~~~V(Z)}$

ここで最大値は、バンドルのすべてのセットにわたって、バンドルへの重みの割り当てに対して、すべてのバンドルの合計重みが少なくとも1であり、各アイテムの合計重みが最大でt _iであるようなものである。各エージェントに少なくともAPSの3/5を保証する多項式時間アルゴリズムがある。^[45]

APS は常に OMMS と同等かそれ以上の高さです。つまり、l/d ≤ t _iの最適なl個中d個の分割が与えられている場合、各部分がちょうど l個の結合に含まれるように、部分 1、...、 lの結合、部分 2、...、l +1 の結合などに 1/ d の重みを (巡回的に) 割り当てることができます。したがって、各アイテムは、合計重みが最大で l / d 、つまり最大で t i であるバンドルに属します。エージェントには、_{少なくとも}l個中d 個のMMS である、そのようなバンドルの中で最も価値が低いバンドルが保証されます。

場合によっては、APS が OMMS よりも大幅に高くなります。次に 2 つの例を示します。

• 異なる資格を持つ簡単な例: C = {2,1,1,1,0}、t _i = 2/5とします。OMMS は最大で 1 です ({1/3, 2/5} で l/d をチェックすれば十分です)。ただし、APS は 2 で、重みは 0.4*{2}、0.2*{1,1}、0.2*{1,1}、0.2*{1,1} です。重みの合計は 1 であることに注意してください。2 は重み 0.4 で 1 つのセットに出現しますが、1 はそれぞれ重み 0.2、0.2 で 2 つのセットに出現します。
• より複雑な例で、権利が等しい場合: C = {5, 5, 5, 7, 7, 7, 11, 17, 23, 23, 23, 31, 31, 31, 65}、t _i = 1/3とします。OMMS は 1-out-of-3 MMS に等しく、最大で 96 です。これは、3 つのパーティションをすべてチェックすることで確認できます。APS は 97 です。これは、各アイテムが正確に 2 つのバンドルに表示されるように、合計値が 97 である 5 つのアイテムのバンドルを 6 つ作成できるためです。次に、各バンドルに 1/6 の重みを割り当てることができます。
  • また、この例では、同一の評価と同等の権利を持つ 3 人のエージェントに対しても、APS 割り当てが存在しない可能性があることも示されています。これは、同一の評価と同等の権利を持つ OMMS や、同一の評価と任意の権利を持つ WMMS とは対照的です。

APS は WMMS よりも高くなることも低くなることもあります。例は OMMS と WMMS の場合と同じです。

• WMMS の方が高いです: C = {40, 60}かつt = (0.4, 0.6)。すると、WMMS ₁ =40、WMMS ₂ =60 になります。ただし、各アイテムの重みは最大で 0.4 である必要があるため、 APS _{1 =0 となり、空のバンドルの重みは少なくとも 0.2 にする必要があります。また、各アイテムの重みは最大で 0.6 である必要があるため、APS 2} =40 となり、{40} と空のバンドルの合計重みは少なくとも 0.4 にする必要があります。
• APS は高くなります: C = {40, 60}かつt = (0.2, 0.2, 0.6)。この場合、すべてのiに対してWMMS _i =0 となります。同様に、上記のように APS ₁ =APS ₂ =0 となります。ただし、重み 0.5*{40}、0.5*{60} などにより、 APS ₃ =40 となります。

セオドア・ヒル^[1]は、最大のアイテム値に依存するMMSのバージョンを提示した。

• ビンカバーリング問題とビンパッキング問題は、それぞれ分割不可能な財の割り当てと分割不可能な雑用の割り当ての特殊なケースとして見ることができる、よく研究された 2 つの最適化問題です。これらの問題に使用される多くの手法は、最大シェアアイテム割り当ての場合にも役立ちます。
• 平等なアイテム割り当て- よく似た名前「最大最小アイテム割り当て」と呼ばれますが、その定義と割り当ては最大最小シェア公平性とは大きく異なります。