アンダーカット手順
公正な物品割り当ての手順

アンダーカット手続きは、2人の間で公平な財の割り当てを行う手続きです。この手続きは、嫉妬のない完全な財の割り当てが存在する限り、それを証明可能に見つけ出します。この手続きは、Brams、Kilgour、Klamler [1]によって提案され、Aziz [2]によって簡略化・拡張されました。

仮定

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

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

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

本旨

アンダーカット手順は、分割可能な資源から分割不可能な資源への分割選択プロトコルの一般化と見ることができます。分割選択プロトコルでは、1人の人が資源を2つの等しい部分に分割する必要があります。しかし、資源に分割不可能な部分が含まれている場合、正確に等しい部分を切り取ることは不可能な場合があります。したがって、アンダーカット手順はほぼ等しい部分を切り取る場合に有効です。ある人のほぼ等しい部分を切り取るとは、アイテムの集合を2つの互いに素な部分集合 (X,Y) に分割することであり、次のようになります。

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

手順

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

  • ケース1：報告が異なっている場合、例えば、アリスにとってはほぼ均等カットとなる分割(X,Y)があるが、ジョージにとってはそうではない場合などです。この分割がジョージに提示されます。ジョージはこれを受け入れるか拒否するかを選択できます。
    • ジョージは、X よりも Y を好む場合、分割を受け入れます。その後、アリスは X を受け取り、ジョージは Y を受け取り、結果として生じる割り当ては羨望の影響を受けません。
    • ジョージは、XをYよりも好む場合、分割を拒否します。仮定により、(X,Y)はジョージにとってほぼ均等カットではありません。したがって、Xには、ジョージがを好むアイテムxが存在します。ジョージは を報告します。これは、ジョージがXをアンダーカットしていることを意味します。(X,Y)はアリスにとってほぼ均等カットであるため、アリスはを好みます。すると、ジョージは を受け取り、アリスは を受け取り、結果として生じる割り当ては羨望の影響を受けません。 X ∖ × {\displaystyle X\setminus x} はい ∪ × {\displaystyle Y\cup x} X ∖ × {\displaystyle X\setminus x} はい ∪ × {\displaystyle Y\cup x} X ∖ × {\displaystyle X\setminus x} X ∖ × {\displaystyle X\setminus x} はい ∪ × {\displaystyle Y\cup x}
  • ケース2：報告が同一、つまりアリスとジョージは全く同じほぼ等しいカットの集合を持っています。次に、手続きは彼らのほぼ等しいカットの1つが正確に等しいカットであるかどうかを尋ねます。厳密な単調性仮定によれば、(X,Y) が正確に等しいカットであるためには、(X,Y) と (Y,X) の両方がほぼ等しいカットである必要があります。したがって、ケース2では、アリスとジョージは同じ正確に等しいカットの集合を持っています。これには2つのサブケースがあります。
    • 簡単なケース：(X,Y) が全く等しい分割が存在する。この場合、どちらか一方（誰であっても）が X を受け取り、もう一方が Y を受け取り、その分割は嫉妬の影響を受けない。
    • 難しいケース：完全に等しいカットは存在しません。その場合、手続きは戻り、「羨望のない割り当ては存在しない」と報告します。

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

実行時の複雑さ

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

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

不平等な権利

アンダーカット手続きは、エージェント間の権利が不平等な場合にも適用できる。[2]各エージェントがアイテムの一部を受け取る権利を持ち、他方のエージェントが であるとする。この場合、（エージェント に対する）ほぼ均等なカットの定義は以下のように変更される。 私 {\displaystyle i} c 私 {\displaystyle c_{i}} − 私 {\displaystyle -i} 私 {\displaystyle i}

  • あなた 私 （ X ） ≥ c 私 c − 私 あなた 私 （ はい ） {\displaystyle u_{i}(X)\geq {c_{i} \over c_{-i}}u_{i}(Y)} 、 そして
  • Xの全てのxについて、 あなた 私 （ X ∖ × ） < c 私 c − 私 あなた 私 （ はい ∪ × ） {\displaystyle u_{i}(X\setminus x)<{c_{i} \over c_{-i}}u_{i}(Y\cup x)}

生成フェーズ

原著論文[1]では、アンダーカット手順の前に以下の生成段階が行われます。

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

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

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

アリス ジョージ
わ 9 1
× 8 4
y 7 3
z 6 2

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

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

参照

参考文献

  1. ^ ab Brams, Steven J.; Kilgour, D. Marc; Klamler, Christian (2011). 「アンダーカット手順：非分割物の羨望のない分割アルゴリズム」（PDF） . Social Choice and Welfare . 39 ( 2–3 ): 615. doi :10.1007/s00355-011-0599-1. S2CID 253844146. 2017年8月12日時点のオリジナルより アーカイブ（PDF） . 2019年12月11日閲覧。
  2. ^ abc Aziz, Haris (2015). 「アンダーカット手続きに関する注記」. Social Choice and Welfare . 45 (4): 723– 728. arXiv : 1312.6444 . doi :10.1007/s00355-015-0877-4. S2CID  253842795.
  • ブラント、フェリックス、コニツァー、ヴィンセント、エンドリス、ジェローム・ラング、アリエル・D・プロカッチャ（2016年）『計算社会選択ハンドブック』ケンブリッジ大学出版局、  306～ 307頁。ISBN 9781107060432。
「https://en.wikipedia.org/w/index.php?title=アンダーカット手順&oldid=1316089683」より取得