羨望グラフ手順

羨望グラフ手順(羨望サイクル手順とも呼ばれる) は、公平なアイテム割り当ての手順です。家宝、お菓子、クラスの席など、いくつかの個別のアイテムを複数の人で分けたい場合に使用できます。

理想的には、割り当ては羨望のない(EF) ものにしたいものです。つまり、各エージェントに、他のすべてのエージェントのバンドルよりも好むバンドルを与えることです。ただし、アイテムは離散的であり、カットできないため、羨望のない割り当ては不可能な場合があります (たとえば、1 つのアイテムと 2 人のエージェントについて考えます)。羨望グラフ手順は、「次善の」オプション、つまり最大で 1 つの商品までの羨望のない状態(EF1) を実現することを目指しています。つまり、すべての人が他のすべての人に対して抱く羨望が、1 つのアイテムから得られる最大限界効用によって制限される割り当てを見つけます。言い換えると、2 人の人iとjごとに、そのアイテムが削除された場合にi がj を羨望しないアイテムが存在します。

この手順は、リプトンとマルカキス、モッセルとサベリ^[1]によって発表され、また^{[2]にも記載されています：300–301}

羨望グラフの手順では、各人がアイテムの束に対して基数効用関数を持っていると仮定します。この効用関数は単調である必要があります(セットの効用は、そのサブセットの効用と少なくとも同じ大きさである必要があります)。ただし、加法的である必要はありません。つまり、アイテムは独立した財であるとは想定されません。

エージェントは、実際に基数効用を報告する必要はありません。バンドルをランク付けする方法を知っていれば十分です。

1. 商品を任意に注文します。
2. 割り当てられていないアイテムがある場合:
   • 羨ましがられないエージェント、つまり他のエージェントが羨ましがらないエージェントが存在することを確認します。
   • 次のアイテムを羨ましがられていないエージェントに渡します。

ステップ 2 で、羨望の対象でないエージェントがいない場合は、羨望グラフに有向サイクルがあることを意味します。 有向グラフでは、各エージェントが羨望の対象であるすべてのエージェントを指します。サイクルは、バンドルの循環交換によって削除できます。すべてのサイクルが削除された後、羨望グラフには入ってくるエッジのないノードが存在する必要があります。このノードは羨望の対象でないエージェントを表します。

結果として生じる割り当ては必ずしも EF ではありませんが、1 つのアイテムを除いて羨望の的になりません。これは、最終割り当てだけでなく、中間の各割り当てにも当てはまります。アイテムは常に羨望の対象ではないエージェントに与えられるため、その割り当て後の他のすべてのエージェントの羨望の対象は最大で 1 つのアイテムになります。

m 個のアイテムがあるとします。アイテムの割り当てごとに、envy グラフに最大でn -1 個のエッジが追加されます。したがって、全体で最大で 個のエッジが追加されます。サイクル削除ごとに、少なくとも 2 個のエッジが削除されます。したがって、サイクル削除ステップを最大 回実行する必要があります。サイクルの検索は、 たとえば深さ優先探索を使用して、時間内に実行できます。全体として、実行時間は です。 ${\displaystyle (n-1)m}$${\displaystyle (n-1)m/2}$${\displaystyle O(n^{2})}$${\displaystyle O(n^{3}m)}$

これらの例では、優先順位は 1 から 3 までで、数字が大きいほど優先順位が高くなります。また、a、b、c は人であり、X、Y、Z はオブジェクトです。

1) 3 人の人と 3 つの物がある場合、割り当ての方法はどれも異なる結果になります。このケースは、3 人のそれぞれが同じ好みを持っている場合に発生します。物を割り当てる方法は 6 つあります。

最初は誰も何も持っていないため、全員が羨ましがられないエージェントであり、これはすべてのケースで同じです。同点の場合は、羨ましがられないエージェント間の同点を辞書式順序で解決します。

1. まず、X オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、Y オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト Z を c に渡します。これで、c は b と a に嫉妬し、b は a に嫉妬し、a は誰にも嫉妬しません。これで、嫉妬のサイクルがなくなり、渡すオブジェクトもなくなったので、手順は終了し、最終結果は a が X、b が Y、c が Z になります。
2. まず、X オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、Z オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、Y オブジェクトを c に渡します。これで、c は a に嫉妬し、b は a と c に嫉妬し、a は誰にも嫉妬しません。これで、嫉妬のサイクルがなくなり、渡すオブジェクトもなくなったので、手順は終了し、最終結果は a が X、b が Z、c が Y になります。
3. まず、Y オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、X オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト Z を c に渡します。これで、c は a と b に嫉妬し、a は b に嫉妬し、b は誰にも嫉妬しません。これで、嫉妬のサイクルがなくなり、渡すオブジェクトもなくなったので、手順は終了し、最終結果は a が Y、b が X、c が Z になります。
4. まず、Y オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、Z オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト X を c に渡します。これで、a は c に嫉妬し、b は a と c に嫉妬し、c は誰にも嫉妬しません。これで、嫉妬のサイクルがなくなり、渡すオブジェクトもなくなったので、手順は終了し、最終結果は a が Y、b が Z、c が X になります。
5. まず、Z オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、X オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト Y を c に渡します。これで、c は b に嫉妬し、a は b と c に嫉妬し、b は誰にも嫉妬しません。これで、嫉妬のサイクルがなくなり、渡すオブジェクトもなくなったので、手順は終了し、最終結果は a が Z、b が X、c が Y になります。
6. まず、Z オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、Y オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト X を c に渡します。これで、b は c に嫉妬し、a は b と c に嫉妬し、c は誰にも嫉妬しません。これで、嫉妬のサイクルがなくなり、渡すオブジェクトもなくなったので、手順は終了し、最終結果は a が Z、b が Y、c が X になります。

2) 3 人の人と 3 つの物がある場合、あらゆる割り当ては同じ結果になります。このケースは、3 人のそれぞれがまったく異なる好みを持っている場合に発生します。なぜなら、各人が何を望んでも、それぞれが別のものを好むからです。

オブジェクトを割り当てる方法は 6 つあります。

最初は誰も何も持っていないため、全員が羨ましがられないエージェントであり、これはすべてのケースで同じです。同点の場合は、羨ましがられないエージェント間の同点を辞書式順序で解決します。

1. まず、X オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、Y オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト Z を c に渡します。これで、a、b、c は誰に対しても嫉妬しなくなり、羨望のサイクルがなくなり、渡すオブジェクトもなくなったため、手順は終了し、最終結果は a が X、b が Y、c が Z を取得します。
2. まず、X オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、Z オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。次に、最後のオブジェクト Y を c に渡します。これで、c は b に嫉妬し、b は c に嫉妬し、a は誰にも嫉妬しません。b と c の間には羨望のサイクルがあるため、オブジェクトを交換し、b は Y を、c は Z を取得します。そして、羨望のサイクルがなくなり、配布するオブジェクトがなくなったため、手順は終了し、最終結果は a が X、b が Y、c が Z を取得します。
3. まず、Y オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、X オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト Z を c に渡します。これで、b は a に嫉妬し、a は b に嫉妬し、c は誰にも嫉妬しません。b と c の間には羨望のサイクルがあるため、オブジェクトを交換し、a は X を取得し、b は Y を取得します。そして、羨望のサイクルがなくなり、配布するオブジェクトがなくなったため、手順は終了し、最終結果は a が X を取得し、b が Y を取得し、c が Z を取得します。
4. まず、Y オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、Z オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。次に、最後のオブジェクト X を c に渡します。これで、b は a に嫉妬し、a は c に嫉妬し、c は b に嫉妬します。a、b、c の間には羨望のサイクルがあるため、嫉妬の方向とは逆にオブジェクトが回転し、a は X、b は Y、c は Z を取得します。これで羨望のサイクルがなくなり、配布するオブジェクトがなくなったため、手順は終了し、最終結果は a が X、b が Y、c が Z を取得します。
5. まず、Z オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。そこで、X オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。そこで、最後のオブジェクト Y を c に渡します。これで、b は a と c に嫉妬し、a は b と c に嫉妬し、c は b と a に嫉妬します。a、b、c の間には羨望のサイクルがあるため、嫉妬の方向とは逆にオブジェクトが回転し、a は X を、b は Y を、c は Z を取得します。そして、羨望のサイクルがなくなり、配布するオブジェクトがなくなったため、手順は終了し、最終結果は a が X、b が Y、c が Z を取得します。
6. まず、Z オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、Y オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト X を c に渡します。これで、c は a に嫉妬し、a は c に嫉妬し、b は誰にも嫉妬しません。a と c の間には羨望のサイクルがあるため、オブジェクトを交換し、a は X を取得し、c は Z を取得します。そして、羨望のサイクルがなくなり、配布するオブジェクトがなくなったため、手順は終了し、最終結果は a が X、b が Y、c が Z を取得します。

3) 3 人の人物と 3 つのオブジェクトの場合、最初の例と 2 番目の例以外の状況では、1 ～ 6 個の結果が返されます。そのため、この結果が発生するには、少なくとも 2 人が 1 つのオブジェクトに対して同じ好みを持っているか、最大で 2 人が同じオブジェクトに対して異なる好みを持っている必要があります。

オブジェクトを割り当てる方法は 6 つあります。

最初は誰も何も持っていないため、全員が羨ましがられないエージェントであり、これはすべてのケースで同じです。同点の場合は、羨ましがられないエージェント間の同点を辞書式順序で解決します。

1. まず、X オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、Y オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト Z を c に渡します。これで、a は誰にも嫉妬せず、b は a と c に嫉妬し、c は誰にも嫉妬しません。これで、嫉妬のサイクルがなくなり、渡すオブジェクトもなくなったので、手順は終了し、最終結果は a が X、b が Y、c が Z になります。
2. まず、X オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、Z オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、Y オブジェクトを c に渡します。これで、a は誰にも嫉妬せず、b は a に嫉妬し、c は b に嫉妬します。これで、嫉妬のサイクルがなくなり、渡すオブジェクトもなくなったので、手順は終了し、最終結果は a が X、b が Z、c が Y になります。
3. まず、Y オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、X オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト Z を c に渡します。これで、b と c は誰にも嫉妬せず、a は b に嫉妬します。これで、嫉妬のサイクルがなくなり、渡すオブジェクトもなくなったので、手順は終了し、最終結果は a が Y、b が X、c が Z になります。
4. まず、Y オブジェクトを a に渡します。その後、b と c は両方とも羨ましがられないエージェントになります。そこで次に、Z オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。そこで次に、最後のオブジェクト X を c に渡します。これで、a は c に嫉妬し、b は c に嫉妬し、c は a と b に嫉妬します。したがって、a と c の間と、b と c の間の 2 つの羨望サイクルが存在します。タイブレーカーは辞書式順序によるため、手順では最初に a と c の羨望サイクルを実行し、次に a と c が入れ替わります。次に、a は誰にも嫉妬せず、b は a に嫉妬し、c は b に嫉妬します。これで羨望サイクルがなくなり、配布するオブジェクトがなくなったため、手順は終了し、最終結果は a が X を取得し、b が Z を取得し、c が Y を取得します。
5. まず、Z オブジェクトを a に渡します。その後、b と c はどちらも羨ましがられないエージェントになります。次に、X オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。最後に、最後のオブジェクト Y を c に渡します。これで、a は b と c に嫉妬し、b は誰にも嫉妬せず、c は a に嫉妬します。a と c の間には羨望のサイクルがあるため、オブジェクトを交換し、a は Y を、c は Z を取得します。羨望のサイクルがなくなり、配布するオブジェクトがなくなったため、手順は終了し、最終結果は a が Y、b が X、c が Z を取得します。
6. まず、Z オブジェクトを a に渡します。その後、b と c は両方とも羨ましがられないエージェントになります。そこで次に、Y オブジェクトを b に渡します。その後、c は羨ましがられないエージェントになります。そこで次に、最後のオブジェクト X を c に渡します。これで、b は a と c に嫉妬し、a は b と c に嫉妬し、c は b と a に嫉妬します。a、b、c の間には羨望のサイクルがあるため、嫉妬の方向とは逆にオブジェクトを回転させます。ただし、a、b、c の間には 2 つの羨望のサイクルがあるため、2 つのオプションが考えられます。タイブレーカーは辞書式順序であるため、a は c から X を取得し、b は a から Z を取得し、c は b から Y を取得するため、結果は a が X を取得し、b が Z を取得し、c が Y を取得します。そして、羨望のサイクルがなく、配布するオブジェクトがなくなったため、手順は終了し、最終結果は a が X を取得し、b が Z を取得し、c が Y を取得します。

羨望グラフアルゴリズムは、アイテムが商品の場合（各アイテムの限界効用がすべてのエージェントにとって正である）、EF1 を保証します。しかし、商品と家事の両方がある場合、EF1 は保証されません。一般化羨望グラフと呼ばれる適応は、商品と家事が混在していても EF1 を保証します。これは、評価が二重単調である場合に機能します。つまり、各エージェントはアイテムを 2 つのサブセットに分割できます。1 つのサブセットには商品（限界効用が常に正であるアイテム）が含まれ、もう 1 つのサブセットには家事（限界効用が常に負であるアイテム）が含まれます。^[3]

エージェントにカーディナリティ制約がある場合（つまり、アイテムの各カテゴリに対して、各エージェントがこのカテゴリから取得できるアイテムの数に上限がある場合）、羨望グラフアルゴリズムは失敗する可能性があります。ただし、これをラウンドロビンプロトコルと組み合わせると、EF1であり、カーディナリティ制約を満たす割り当てを見つけるアルゴリズムが得られます。^[4]

エージェントが割り当て評価（別名OXS評価）を持つ場合、羨望グラフアルゴリズムの拡張である「アルゴリズムH」があり、羨望されていないエージェントへの次の割り当ては、エージェントアイテムの効用が最大化されるように選択されます。このアルゴリズムの特性に対する正式な証明はありませんが、現実的なデータではうまく機能します。^[5]

• 羨望のないアイテム割り当て
• 貪欲な数値分割- すべてのエージェントが同一の評価を持つ場合の羨望グラフ アルゴリズムの特殊なケースと見なすことができます。
• 需要減少手順とアンダーカット手順- バンドルの順序付けに基づく 2 つの追加手順。