アンダーカット手順

アンダーカット手順は、2人の間で公平なアイテム割り当てを行う手順です。この手順は、嫉妬のないアイテム割り当てが存在する場合はいつでも、それを証明できます。この手順は、Brams、Kilgour、Klamler ^[1]によって提案され、Aziz ^[2]によって簡略化および拡張されました。

アンダーカット手順では、人々に関して次の弱い仮定のみが必要です。

• 各人は、アイテムのサブセットに対して弱い好み関係を持っています。
• それぞれの選好関係は厳密に単調です。つまり、あらゆる集合と項目に対して、人は厳密にを好みます。${\displaystyle X}$${\displaystyle y\notin X}$${\displaystyle X\cup y}$${\displaystyle X}$

エージェントが応答的な好みを持っているとは想定されていません。

アンダーカット手順は、分割可能なリソースから分割不可能なリソースへの分割選択プロトコルの一般化と見ることができます。分割選択プロトコルでは、1 人の人間がリソースを 2 つの等しい部分にカットする必要があります。ただし、リソースに分割不可能な部分が含まれている場合は、正確に等しいカットを行うことができない可能性があります。したがって、アンダーカット手順は、ほぼ等しいカットで機能します。人のほぼ等しいカットとは、アイテムのセットを 2 つの互いに素なサブセット (X、Y) に分割することです。

• その人は弱々しく X を Y より好みます。
• いずれか 1 つのアイテムが X から Y に移動された場合、その人は X よりも Y を厳密に好みます (つまり、X 内のすべての x について、その人はを好みます)。${\displaystyle Y\cup x}$${\displaystyle X\setminus x}$

各人がほぼ均等にカットしたものをすべて報告します。2 つのケースがあります。

• ケース 1 : レポートが異なります。たとえば、アリスにとってはほぼ均等カットであるが、ジョージにとってはそうではないパーティション (X,Y) があります。次に、このパーティションがジョージに提示されます。ジョージはそれを受け入れるか拒否するかを選択できます。
  • ジョージは、X よりも Y を好む場合は分割を受け入れます。その後、アリスは X を受け取り、ジョージは Y を受け取り、結果として生じる割り当ては嫉妬のないものになります。
  • ジョージは、Y より X を好む場合、分割を拒否します。仮定により、(X,Y) はジョージにとってほぼ等しいカットではありません。したがって、ジョージがを好む X のアイテム x が存在します。ジョージは を報告します。ジョージが X を下回ると言います。(X,Y) はアリスにとってほぼ等しいカットであるため、アリスはを好みます。すると、ジョージは受け取り、アリスは受け取り、結果として生じる割り当ては嫉妬フリーになります。${\displaystyle X\setminus x}$${\displaystyle Y\cup x}$${\displaystyle X\setminus x}$${\displaystyle Y\cup x}$${\displaystyle X\setminus x}$${\displaystyle X\setminus x}$${\displaystyle Y\cup x}$
• ケース 2 : レポートは同一です。つまり、アリスとジョージは、ほぼ等しいカットのセットがまったく同じです。次に、手順は、ほぼ等しいカットの 1 つが正確​​に等しいカットであるかどうかを尋ねます。厳密な単調性仮定により、(X,Y) が正確に等しいカットであるのは、(X,Y) と (Y,X) の両方がほぼ等しいカットである場合のみです。したがって、ケース 2 では、アリスとジョージは、正確に等しいカットのセットが同じです。2 つのサブケースがあります。
  • 簡単なケース: 完全に等しいカット (X,Y) が存在します。その場合、1 人 (誰であっても) が X を受け取り、もう 1 人が Y を受け取り、分割は嫉妬なしで行われます。
  • 難しいケース: 完全に等しいカットはありません。その場合、手順は戻り、「envy-free 割り当ては存在しません」と報告します。

手順の正しさを証明するには、ハードケースでは、羨望のない割り当てが存在しないことを証明するだけで十分です。確かに、羨望のない割り当て (X,Y) が存在すると仮定します。ハードケースであるため、(X,Y) は厳密に等しいカットではありません。そのため、1 人の人物 (たとえば、ジョージ) は Y を X より厳密に好みますが、もう 1 人の人物 (アリス) は X を Y より弱く好みます。(X,Y) がアリスにとってほぼ等しいカットでない場合は、いくつかのアイテムを X から Y に移動し、アリスにとってほぼ等しいカットであるパー​​ティション (X',Y') を取得します。アリスは依然として X' を Y' より弱く好みます。単調性仮定により、ジョージは依然として Y' を X' より厳密に好みます。これは、(X',Y') がジョージにとってほぼ等しいカットではないことを意味します。しかし、ハードケースでは、両方のエージェントが同じほぼ等しいカットのセットを持ちます。これは矛盾です。

最悪の場合、エージェントはすべての可能なバンドルを評価する必要があるため、実行時間はアイテムの数に応じて指数関数的に増加する可能性があります。

これは驚くことではありません。なぜなら、アンダーカット手順は分割問題を解決するために使用できるからです。つまり、両方のエージェントが同一かつ加法的な評価を持っていると仮定し、アンダーカット手順を実行します。羨望のない割り当てが見つかった場合、この割り当ては均等分割を表します。分割問題は NP 完全であるため、多項式時間アルゴリズムでは解決できない可能性があります。

アンダーカット手続きは、エージェントが不平等な権利を持っている場合にも機能します。^[2]各エージェントがアイテムの一部に対する権利を持ち、 が他のエージェントであるとします。その場合、ほぼ均等なカットの定義（エージェントの場合）は次のように変更する必要があります。 ${\displaystyle i}$${\displaystyle c_{i}}$${\displaystyle -i}$${\displaystyle i}$

• ${\displaystyle u_{i}(X)\geq {c_{i} \over c_{-i}}u_{i}(Y)}$、 そして
• X内の全てのxに対して、${\displaystyle u_{i}(X\setminus x)<{c_{i} \over c_{-i}}u_{i}(Y\cup x)}$

オリジナルの出版物^[1]では、アンダーカット手順の前に次の生成段階が行われます。

• テーブルの上にアイテムがある間:
  • 各自が自分のベストアイテムを報告します。
    • 報告が異なった場合、各人が自分のベストアイテムを受け取ります。
    • 報告が同一である場合、最も優れた項目が争点となる山に置かれます。

上記のアンダーカット手順は、争われているパイルに対してのみ実行されます。

このフェーズでは、分割手順がより効率的になる可能性があります。争われている山は元のアイテムのセットよりも小さい可能性があるため、ほぼ均等にカットする計算と報告が容易になる可能性があります。

しかし、生成段階にはいくつかの欠点がある。^[2]

1. この手順では、羨望のない割り当てを見逃す可能性があります。たとえば、4 つのアイテムがあり、それらの評価が隣の表のとおりであるとします。アリスに {w,z} を、ジョージに {x,y} を与える割り当ては羨望がありません。実際、これはベア アンダーカット手順で見つけることができます。なぜなら、パーティション ({w,z}, {x,y}) はアリスにとってはほぼ等しいカットですが、ジョージにとってはそうではなく、ジョージはこのパーティションを受け入れるからです。しかし、生成フェーズでは、最初にアリスは w を取得し、ジョージは x を取得し、他のアイテム {y,z} は競合パイルに入れられ、競合パイルの羨望のない割り当ては存在しないため、手順は失敗します。
2. 人々は、他にどのような品物を受け取ることになるか知らずに、「最良の品物」を選択する必要があります。これは、品物が独立した財であるという仮定に基づいています。あるいは、応答性の仮定に基づいています。つまり、バンドル内の品物がより良い品物に置き換えられた場合、結果として得られるバンドルはより良いものになります (これは、弱加法的嗜好と密接に関連しています)。
3. エージェントの主張が不平等な場合には機能しません。
4. これは、戦略的な操作の影響を受けやすい順次割り当てに依存しています。

• 需要減少手順と羨望グラフ手順- バンドルの順序付けに基づく 2 つの追加手順。

• Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). 計算的社会的選択ハンドブック。ケンブリッジ大学出版局。pp. 306–307。ISBN 9781107060432。（無料オンライン版）