効率的でほぼ公平なアイテムの割り当て

異なる嗜好を持つ人々の間でオブジェクトを割り当てる場合、2つの主な目標はパレート効率性と公平性です。オブジェクトは不可分であるため、公平な割り当ては存在しない可能性があります。たとえば、1つの家と2人の人がいる場合、家の割り当てはすべて1人の人にとって不公平になります。そのため、最大シェア公平性(MMS) 、1つのアイテムまでの羨望のなさ(EF1)、1つのアイテムまでの比例性(PROP1)、 1つのアイテムまでの公平性(EQ1)など、いくつかの一般的な近似が研究されてきました。効率的な近似公平なアイテム割り当ての問題は、パレート効率的(PE)であり、これらの公平性の概念の1つを満たす割り当てを見つけることです。この問題は2016年に初めて提示され^[1]、それ以来かなりの注目を集めています。

Mで表されるオブジェクトの有限集合があります。n 個のエージェントが存在します。各エージェントi には、オブジェクトの各サブセットに値を割り当てる価値関数V _{i が}あります。目標は、Mをn個のサブセットX ₁、...、X _nに分割し、各サブセットX _{i を}エージェントiに与えて、割り当てがパレート効率的かつほぼ公平になるようにすることです。近似公平性にはさまざまな概念があります。

すべてのエージェントが自分のシェアの価値が他のエージェントの価値と少なくとも同じくらい高いと考えている場合、その 割り当ては羨望フリー(EF)と呼ばれます。2 人のエージェント i と j ごとに、j の束から最大で 1 つのアイテムが削除された場合、i は j を羨望しない場合、その割り当ては1 つのアイテムまで羨望フリー (EF1) と呼ばれます。正式には、

• ${\displaystyle \forall i,j:~~~\exists Y\subseteq X_{j}:~~~|Y|\leq 1,~~~V_{i}(X_{i})\geq V_{i}(X_{j}\setminus Y)}$

初期のアルゴリズムの中には、弱い形式の効率性を満たすほぼ公平な割り当てを見つけることができたものもありましたが、PE は満たしていませんでした。

• ラウンドロビン手順は、加法的効用を持つ完全なEF1割り当てを返します。envy -graph手順は、任意の単調な優先関係に対して完全なEF1割り当てを返します。^[2]どちらもenvy-cycleのない割り当てを返すことが保証されています。ただし、割り当てがパレート効率的であることは保証されていません。
• 近似CEEIメカニズムは、任意の優先関係に対して部分的なEF1割り当てを返します。割り当てられたオブジェクトに対してはPEですが、すべてのオブジェクトに対してはPEではありません（一部のオブジェクトは割り当てられずに残る可能性があるため）。^[3]

これにより、PE と EF1 の両方の割り当てを見つけるという問題が生じました。

Caragiannis、Kurokawa、Moulin、Procaccia、Shah、Wang ^[1]は、PE+EF1配分の存在を初めて証明した。彼らは、すべてのエージェントが正の加法効用を持つ場合、効用の積（ナッシュ福祉としても知られる）を最大化する配分はすべてEF1であることを証明した。最大化配分がPEであることは明らかなので、PE+EF1配分の存在が導かれる。

最大積割り当ては望ましい特性を持っているが、多項式時間で計算することはできない。最大積割り当てを見つけることはNP困難^[4]であり、APX困難でさえある^[5]。このため、近似係数を改善して最大積を近似しようとするさまざまな研究が行われた。

• ColeとGkatzelis ^[6]は2.89倍の近似値を提示した。
• Anari、Gharan、Saberi、Singh ^[7]はe因子近似値を提示した。
• Cole、Devanur、Gkatelis、Jain、Mai、Vazirani、Yazdanbod ^{[8] は}2 因子近似を提示しました。

ただし、これらの近似では EF1 が保証されるわけではありません。最近のアルゴリズムの中には、近似最大積と公平性の両方を保証するものもあります。

• Barman、Krishanmurthy、Vaish ^[9]は、擬似多項式時間でPE、(1+epsilon)-EF1、および最大積の1.45近似を保証するアルゴリズムを提示している（下記の価格上昇アルゴリズムを参照）。
• GargとMcGlaughlin ^[10]は、PE、PROP1、および最大積の2近似を強多項式時間で保証するアルゴリズムを提示している。
• Caragiannis、Gravin、Huang ^[11]は、いくつかの商品を破棄することで、EFX、PROP1、および最大積の2.9近似を保証するアルゴリズムを提示している（彼らはまた、2近似割り当ての存在を示している）。

最大積解法は、評価がバイナリ（各項目の値が 0 または 1）の場合に特に魅力的です。

• Amanatidis、Birmpas、Filos-Ratsikas、Hollender、Voudouris ^[12]は、バイナリ評価では最大積解はEF1だけでなくEFX（あらゆる財に対する羨望のなさ）でもあることを証明している。これは、各アイテムの値が2つの値のうちの1つを取ることができるときはいつでも成り立ち、必ずしも0または1である必要はない。一般的な加法評価では、最大積はEFXを意味するのではなく、その自然な一般化を意味する。
• Halpern、Procaccia、Psomas、Shah ^[13]は、バイナリ評価では辞書式タイブレークによる最大積ルールが多項式時間で計算でき、グループ戦略不可能であることを証明しています。

エージェントの効用が加法的でない場合、最大積解は必ずしもEF1​​ではない。しかし、エージェントの効用が少なくともサブモジュラーである場合、最大積解は、1項目を除く限界羨望の自由性（MEF1）と呼ばれるより弱い性質を満たす。これは、各エージェントiが自分のバンドルを（jから最良の項目を除いたバンドル）の限界効用と少なくとも同じだけ評価することを意味する。正式には： ^[14]

• ${\displaystyle \forall i,j:~~~\exists Y\subseteq X_{j}:~~~|Y|\leq 1,~~~V_{i}(X_{i})\geq V_{i}(X_{i}\cup (X_{j}\setminus Y))-V_{i}(X_{i})}$

より一般的な効用関数についても同様の近似値が見つかっています。

• Bei、Garg、Hoefer、Mehlhorn ^[15]と Anari、Mai、Gharan、Vazirani ^{[16] は}、各品目の複数のユニットがある市場を研究しており、評価は区分線形凹型で分離可能となっている。これは、異なる品目のバンドルの効用は、各品目の効用の合計である（これが「分離可能」の意味である）が、各品目の評価は限界効用が減少する（これが「区分線形凹型」の意味である）ことを意味する。彼らは最大積の 2 近似値を与えている。
• オルテガ^[17]は、二元評価のマルチユニット市場を研究している。彼は、平等主義ルールがローレンツ優位（レキシミン最適性よりも強い性質）であり、効用が一意であり、グループ戦略不可能であることを証明している。
• ガーグ、ホーファー、メルホーン^[18]は、サブモジュラー効用のサブクラスである予算加法評価を研究している。彼らは、入力サイズと1/ εにおける時間多項式の最大積の(2.404 + ε )近似値を与えている。
• Benabbou、Chakraborty、Igarashi、Zick ^{[19]は、 2値の限界利得（つまり、各アイテムが各バンドルの価値に0または1を追加する）を持つ}サブモジュラー効用を研究している。彼らは、そのような評価では、最大積とレキシミンの割り当ての両方がEF1であり、功利主義的福祉（効用の合計）を最大化することを証明している。
• ババイオフ、エズラ、フェイジ^[20]も、バイナリ（「二分法」）限界利得を持つサブモジュラー効用を研究している。彼らは、ローレンツ優位の配分、つまりEFXと最大積を出力する決定論的かつ真実のメカニズムを提示している。

マーティンとウォルシュ^[21]は、「混合マナ」（正と負の両方の可能性がある加法評価）では、効用の積を最大化（またはマイナス効用の積を最小化）してもEF1が保証されないことを示しています。彼らはまた、効用が同一であってもEFX3の割り当てが存在しない可能性があることも証明しています。ただし、3次効用では、EFXとPOの割り当て、またはEFX3とPOの割り当てが常に存在し、効用が同一であれば、EFXとPOの割り当てが常に存在します。これらのケースでは、多項式時間アルゴリズムがあります。

Barman、Krishanmurthy、Vaish ^{[9]は、正の加法評価に対するPE+EF1割り当てを見つけるための}擬似多項式時間アルゴリズムを提示した。彼らは以下の結果を証明した。

• このアルゴリズムは、PE+EF1 割り当てを O(poly( m , n , v _max )) の時間で見つけます。ここで、m はオブジェクトの数、n はエージェントの数、v _{max は}アイテムの最大値です (すべての評価は整数です)。
• 同じアルゴリズムは、最大ナッシュ福祉の 1.45 近似値を提供します。
• このアルゴリズムは、EF1 かつ部分的パレート最適である割り当ての存在も証明します。

彼らのアルゴリズムは、フィッシャー市場における競争均衡の概念に基づいています。以下の概念を使用します。

• 近似 EF1 割り当て: 定数e > 0 が与えられた場合、割り当ては(1+ e )の乗法定数までの EF1 条件を満たす場合、e -EF1 になります。正式には:
  • ${\displaystyle \forall i,j:~~~\exists Y\subseteq X_{j}:~~~|Y|\leq 1,~~~(1+e)\cdot V_{i}(X_{i})\geq V_{i}(X_{j}\setminus Y)}$
• 価格ベクトル: 各アイテムに価格 (実数) を割り当てるベクトル。
• コストパフォーマンス比: エージェントiとオブジェクトoの場合、エージェントのアイテムの評価とアイテムの価格の比率です: v _ij / p _j。
• 最大効果対費用効果 (MBB) セット: エージェントiの場合、効果対費用効果比を最大化するオブジェクトのセットです (価格ベクトルpが与えられている場合)。
• MBB 割り当て: 各エージェントが自分の MBB セットからオブジェクトのみを受け取る割り当て。MBB 割り当てでは、各エージェントは自分の予算内で効用を最大化します (ただし、MBB 割り当ての方が条件が強い)。第一の福祉定理は、 MBB 割り当てが部分的パレート最適であることを意味します。
• 価格羨望のない (pEF) 割り当て: 2 人のエージェントi . jごとに、 X _iの価格( i の「所得」と呼ばれる) が価格X _jと少なくとも同じ大きさである割り当て X。これは、すべての所得が同一であることを意味します。さらに、 MBB と pEF の両方である割り当ては羨望のない割り当てです。これは、各エージェントが自分の所得を与えられた場合に効用を最大化し、他のすべてのエージェントの所得が同じであるためです。
• 1人を除いて価格羨望のない（pEF1）配分：2人のエージェントi.jごとに、価格p( Xi )が少なくとも 最も高価な品目を除いたXjの価格と同じである配分。これは所得が同一であることを意味するものではない。しかし、MBBかつpEF1である配分はEF1でもある。_[ ^{9] ：Lem.4.1}
• e -pEF1 割り当て、定数e > 0 の場合: 2 人のエージェントi . jごとに、積 (1+ e )·p( X _i ) が、最も高価なアイテムを除いたp( Xj )と少なくとも同じ大きさになる割り当て。e -pEF1 条件は、 eが大きいほど弱くなる。特に、pEF1 割り当ては、e > 0 の場合すべて e -pEF1 ですが、その逆は真ではありません。MBB かつe -pEF1である割り当てもe -EF1です。 ^{[9] : Lem.4.1}
• 最小支出者: 割り当てと価格ベクトルが与えられた場合、 p( X _i )が最小となるエージェントiです (同点の場合は、エージェントの事前指定された順序に基づいて決定されます)。割り当てがe -pEF1となるのは、 e -pEF1 条件が最小支出者 (エージェントi ) に対して満たされる場合のみであることに注意してください。
• エージェントiのMBB 階層(割り当てXと価格ベクトルpが与えられた場合): 次の方法で構築されたツリー構造。
  • エージェントi をルートに配置します (これをレベル 0 と呼びます)。
  • エージェントiに、その MBB セット内のすべてのオブジェクトを接続します (価格ベクトルpが与えられます)。
  • X内の各オブジェクトを所有するエージェントがツリー内にまだ存在しない場合は、そのオブジェクトに接続します（これをレベル 1 と呼びます）。
  • レベル 1 の各エージェントに、ツリー内にまだ存在する MBB セット内のすべてのオブジェクトを接続します。
  • 同様の方法で、エージェントとオブジェクトを交互に追加し続けます。各エージェントに、その MBB オブジェクトを追加し、各アイテムに、その所有エージェントを追加します。
• 違反者(割り当てXと価格ベクトルpが与えられた場合):最も支出の少ない人iに対して pEF1 条件に違反するエージェントh 。したがって、最も高価な品目が取り除かれた場合でも、 X _hの価格はp ( X _i )よりも高くなります。同様に、e違反者は、最も支出の少ない人に対してe -pEF1 条件に違反するエージェントです。
• パス違反者(割り当てXと価格ベクトルp 、および MBB 階層が与えられた場合):最小支出者iの MBB 階層に現れ、iに関して pEF1 条件を部分的に違反するエージェントh。より詳しくは、 MBB 階層のエッジに沿って、最小支出者iからオブジェクトoへのパスがあり、オブジェクトoからエージェントhへのエッジがあるとします(つまり、X _hにoが含まれます)。 p ( X _h \ { o }) > p ( X _i ) の場合、h はパス違反者です。すべての違反者はパス違反者ですが、その逆は当てはまらないことに注意してください。同様に、 p ( X _h \ { o }) > (1+ e )· p ( X _i ) の場合、hはeパス違反者です。

パラメータeが与えられると、アルゴリズムは fPO かつ 3 e -pEF1 となる割り当てを見つけることを目指します。アルゴリズムはいくつかのフェーズで進行します。

フェーズ1: 初期のMBB割り当て+価格(X, p)を構築します。

• これを行う 1 つの方法は、各オブジェクトo を、それを最も高く評価するエージェントiに渡し(同点の場合は任意に決定)、 oの価格をv _i,oに設定することです。これにより、各エージェントのバンドル内のすべてのオブジェクトの費用対効果は正確に 1 になり、他のバンドル内のすべてのオブジェクトの費用対効果は最大でも 1 になることが保証されます。したがって、割り当ては MBB であり、したがって fPO でもあります。
• 割り当てが 3 e -pEF1 の場合はそれを返します。それ以外の場合はフェーズ 2 に進みます。

フェーズ2: MBB階層内の価格羨望を排除する:

• 現在の( X、p )に基づいて、最も支出が少ない人のMBB階層を構築します。
• L = 1,2,... の場合:
  • ツリーの レベルLの各エージェントhについて:
    • h がパス i → ... → h' → o → hに沿ったeパス違反者である場合、オブジェクトo をエージェントhからエージェントh'に転送します(割り当ては MBB のままであることに注意してください)。フェーズ 2 を再開します。
• eパス違反者 がいなくなったら:
  • 割り当てが 3 e -pEF1 の場合はそれを返します。それ以外の場合はフェーズ 3 に進みます。

フェーズ 3: 価格を上げる。次の 3 つのうちのいずれかが発生するまで、MBB 階層内のすべてのオブジェクトの価格を同じ乗数で上げます。

1. 最も支出が少ない人のアイデンティティが変わります。これは、階層外のエージェント (アイテムの価格が上昇しない) が、最も支出が少ない人になった場合に発生する可能性があります。この場合、フェーズ 2 から再開します。
2. MBB 階層に新しいオブジェクトが追加されます。これは、階層内のオブジェクトの価格が係数rだけ増加すると、階層内のオブジェクトの BB 比率がrだけ減少するのに対し、階層外のオブジェクトの BB 比率は同じままであるため発生する可能性があります。したがって、rが十分に大きい場合、外部のオブジェクトが何らかの階層エージェントの MBB になります。この場合も、フェーズ 2 から再開します。
3. 現在の割り当てX は3 e -pEF1 になります。これは、階層内のオブジェクトの価格が上昇すると、最も支出が少ないエージェントの収入が増加しますが、階層外のエージェントの収入は一定のままであるため発生する可能性があります。したがって、rが十分に大きい場合、最も支出が少ないエージェントに関して 3 e -pEF1 条件が満たされる可能性があります。この場合、割り当てXと新しい価格p を返します。

まず、上記のアルゴリズムが、すべての値が (1+ e ) の累乗であり、ある固定されたe >0であるインスタンスに対して実行されると仮定します。

• 最初の課題は、アルゴリズムが終了することを証明することです。すべての評価が (1+ e ) の累乗である場合、アルゴリズムは時間O (poly(m, n, 1/ e , ln( V _max )) で終了することが証明できます。ここで、V _maxはエージェントに対するオブジェクトの最大値です。^{[22] : 23–29}
• 初期割り当ては MBB 割り当てであり、すべての操作はこの条件を維持します。したがって、返される割り当ては MBB であり、fPO でもあります。
• 終了条件により、アルゴリズムが終了するたびに返される割り当ては 3 e -pEF1 なので、これも 3 e -EF1 になります。

ここで、一般的な評価を持つインスタンスがあると仮定します。上記のアルゴリズムを丸められたインスタンスで実行します。この場合、各評価は最も近い (1+ e ) の累乗に切り上げられます。各エージェントiとオブジェクトoについて、丸められた値V _i '( o ) はV _i ( o ) と (1+ e ) V _i ( o )の間に制限されることに注意してください。

• 前の段落により、丸められたインスタンスに関して、結果として得られる割り当ては fPO と 3 e -EF1 になります。
• 十分に小さいe （特に1/ 6m3Vmax4未満^）に対して、丸められたインスタンスのfPOである割り当ては、元のインスタンスのPOである。_[ ^{22 ]} ：^29–34
• 丸められたインスタンスの3 e -EF1 保証と丸めの境界を組み合わせると、返される割り当てが次の近似 EF1 条件を満たすことがわかります。
  • ${\displaystyle \forall i,j:~~~\exists C\subseteq X_{j}:~~~|C|\leq 1,~~~(1+e)\cdot (1+3e)\cdot V_{i}(X_{i})\geq V_{i}(X_{j}\setminus C)}$
• e が十分に小さい場合、積 (1+ e )(1+3 e ) は最大で (1+7 e ) になります。したがって、丸められたインスタンスの3 e -EF1である割り当ては、元のインスタンスの 7 e -EF1 になります。
• 元の評価は整数なので、e が十分に小さい場合、7 e -EF1 の割り当ても EF1 になります。
• したがって、結果として得られる割り当ては、元のインスタンスの PO+EF1 になります。

アジズ、カラギアニス、五十嵐、ウォルシュ^{[23] ：第4節では} EF1の条件を混合評価（オブジェクトは正と負の両方の効用^{を持つことができる）に拡張した。彼らは}調整勝者手順の一般化を提示し、2人のエージェントのPO+EF1割り当てを時間O( m2 )で見つけた。

オブジェクトの割り当てが比例的(PROP)であるとは、すべてのエージェントが自分の取り分をすべてのアイテムの価値の少なくとも 1/ nと評価する場合です。すべてのエージェントiについて、最大で 1 つのアイテムがiのバンドルに追加された場合、i がそのバンドルを合計の少なくとも 1/ nと評価する場合、1 つのアイテムまで比例的(PROP1)であると呼ばれます。正式には、すべてのi (ここでMはすべての商品の集合) について次のようになります。

• ${\displaystyle \exists Y\subseteq M\setminus X_{i}:~~~|Y|\leq 1,~~~V_{i}(X_{i}\cup Y)\geq V_{i}(M)/n}$。

PROP1条件は、公正な公的意思決定の文脈で コニツァー、フリーマン、シャー^{[24]によって導入されました。彼らは、この場合、PE+PROP1の割り当てが常に存在することを証明しました。}

すべての EF1 割り当ては PROP1 であるため、不可分項目割り当てにも PE+PROP1 割り当てが存在します。問題は、そのような割り当てが PE+EF1 のアルゴリズムよりも高速なアルゴリズムで検出できるかどうかです。

バーマンとクリシュナムルシー^[25]は、財（正の効用を持つ物体） に対するPE+PROP1割り当てを見つける強力な多項式時間アルゴリズムを提示した。

ブランゼイとサンドミルスキー^[26]はPROP1の条件を家事（負の効用を持つもの）に拡張した。正式には、すべてのiに対して：

• ${\displaystyle \exists Y\subseteq X_{i}:~~~|Y|\leq 1,~~~V_{i}(X_{i}\setminus Y)\geq V_{i}(M)/n}$。

彼らは、PE+PROP1 の雑用の割り当てを見つけるアルゴリズムを発表しました。このアルゴリズムは、オブジェクトの数またはエージェントの数 (あるいはその両方) が固定されている場合、強力に多項式時間です。

Aziz、Caragiannis、Igarashi、Walsh ^[23]は、PROP1 の条件を混合評価(オブジェクトは正の効用と負の効用の両方を持つことができる) に拡張しました。この設定では、各エージェントiについて、i のバンドルから負のアイテムを 1 つ削除するか、i のバンドルに正のアイテムを 1 つ追加すると、i の効​​用が合計の少なくとも 1/ nになる場合、割り当ては PROP1 と呼ばれます。彼らの一般化調整勝者アルゴリズムは、2 つのエージェントに対して PE+EF1 割り当てを見つけます。このような割り当ても PROP1 です。

アジズ、ムーラン、サンドミルスキー^[27]は、エージェントやオブジェクトの数が固定されていない場合でも、エージェントが異なる権利を持っている場合でも、一般的な混合評価を使用して、部分PE（PEよりも強い）およびPROP1である割り当てを見つけるための強力な多項式時間アルゴリズムを提示しました。

オブジェクトの割り当ては、すべてのエージェントの主観的価値が同じである場合に公平である（EQ）と呼ばれます。この概念を研究する動機は、人間の被験者が公平な割り当てを羨望のない割り当てよりも好むことを示す実験に由来しています。[ 28 ] 2人のエージェントiとjごとに、jの束から最大で1つのアイテムが削除された場合、iの主観的価値が少なくともjの主観的価値である場合、割り当ては1アイテムまで公平である（EQ1）と^呼ばれます。正式には、すべてのi、jについて、

• ${\displaystyle \exists Y\subseteq X_{j}:~~~|Y|\leq 1,~~~V_{i}(X_{i})\geq V_{j}(X_{j}\setminus Y)}$。

より強い概念は、任意の項目まで公平である (EQx)です。2 人のエージェント i と j ごとに、j のバンドルから任意の 1 つの項目が削除された場合、 i の主観的価値は少なくとも j の価値になります。

• ${\displaystyle \forall y\in X_{j}:~~~V_{i}(X_{i})\geq V_{j}(X_{j}\setminus \{y\})}$。

EQx 割り当ては、Gourves、Monnot、Tlilane によって最初に研究されましたが、彼らは「嫉妬に近い」という別の用語を使用しました。^{[29] : 3}彼らは、割り当てられたすべての財の和集合が与えられたマトロイドの基底であるという追加の要件があっても、部分的な EQx 割り当てが常に存在することを証明しました。彼らは、羨望グラフ手順に似たアルゴリズムを使用しました。Suksompong ^[30]は、すべての割り当てが直線の連続したサブセットでなければならないという追加の要件があっても、EQ1 割り当てが存在することを証明しました。

フリーマン、シドカー、ヴァイシュ、シア^[31]は次のようなより強力な結果を証明した。

• すべての評価が厳密に正の場合、PE+EQx 割り当てが常に存在し、PE+EQ1 割り当てを見つける擬似多項式時間アルゴリズムが存在します。
• 一部の評価がゼロになる可能性がある場合、PE+EQ1 の割り当ても存在しない可能性があり、PE+EQ/EQ1/EQx が存在するかどうかを判断することは非常に NP 困難です。
• PE+EQ1+EF1 割り当ては存在しない可能性があります。これが存在するかどうかを判断することは一般にNP 困難ですが、バイナリ (0 または 1) 評価では多項式時間で解決できます。

Bredereck、Kaczmarcyk、Knop、Niedermeier ^[32]は、エージェント数が少なく（nが小さい）、アイテムタイプ数が少ない（mが小さい）設定を研究しており、アイテムタイプあたりの効用は（ Vによって）上限が定められているが、各タイプのアイテムは多数存在できる。この設定について、彼らは次のメタ定理（定理2）を証明している。効率基準Eと公平性基準Fが与えられ、が  固定されている場合、EとFが次の特性を満たす限り、E効率的かつF公平な割り当てが存在するかどうかを多項式時間で決定することができる。 ${\displaystyle n+u_{\max }+m}$

• 公平性: F-公平な割り当てが存在するかどうかという問題は、固定次元の整数線形計画によってモデル化できます。
• 効率: ある割り当てが別の割り当てより E 優位になるかどうかという問題は、双対ツリーの深さと最大係数の絶対値が何らかの関数によって上限が定められている整数計画によってモデル化できます。${\displaystyle f(n,u_{\max })}$

次に、次のようないくつかの一般的な公平性と効率性の基準がこれらの特性を満たしていることを証明します。

• 公平性の概念: 嫉妬のなさ、EF1、EFx、グラフ EF (エージェントが固定グラフ上の近隣のみを嫉妬する場合)、平等主義、最大シェア、平均グループ嫉妬のなさ (エージェントの各グループが、そのシェアをメンバーの効用の算術平均として評価する場合)。
• 効率の概念: パレート効率、グラフ パレート効率 (パレート優位は固定グラフ上の隣接ノード間の交換のみを考慮)、およびグループ パレート効率。割り当てX がk グループ パレート効率的 (GPE _k )であるとは、サイズkのすべてのグループに対して少なくとも同等 (効用の算術平均で)で、サイズkの少なくとも 1 つのグループに対して厳密に優れている割り当てYが存在しないことを意味します。GPE ₁はパレート効率と同等であることに注意してください。GPE _{n は}、サイズnの グランド グループGに対して、算術平均効用がすべてのエージェントの効用の合計と同等であるため、効用最大割り当てと同等です。すべてのkに対して、 GPE _k+1は GPE _{k を}意味します。

彼らのアルゴリズムの実行時間は入力サイズ（ビット単位）の多項式であり、ここでdは結果のILPの変数の数であり、これはである。^{[32] ：sub.4.3}${\displaystyle d^{2.5d}}$${\displaystyle d=m(n+1)+m(n+1)\cdot (4\cdot (4n\cdot V+1)^{n})^{m(n+1)}}$

彼らは後にこれらの問題のいくつかに対してより実用的なアルゴリズムを開発した。^[33]

• 部分パレート効率#公平な fPO 割り当てを見つける

• 効率的な嫉妬のない分割- 分割可能なリソースの場合。正確な公平性が実現できるため、近似値は必要ありません。
• 羨望のないアイテム割り当て- PE の要件なし。
• レンタルハーモニー- 各エージェントが 1 つのアイテムを取得する必要があるという追加の制限があります。