AL手順

AL手続きは、2人の間で公平な物品割り当てを行う手続きです。この手続きは、物品のサブセットについて、羨望のない物品割り当てを見つけます。さらに、結果として得られる割り当ては、次の意味でパレート効率的です。つまり、一方にとってより良く、他方にとってより悪くない、羨望のない他の割り当ては存在しないということです。

AL手順は、ブラムス、キルガー、クラムラーによって初めて発表されました。^[1] その後、ハリス・アジズによって一般化され、行為者が無関心を表明するケースにも対応できるようになりました。^[2]

仮定

AL 手順では、人々に関して次の仮定が必要です。

各人がアイテムを最高から最低までランク付けできます (つまり、各人がアイテムに関する厳密な好みの関係を報告できます)。
各人はアイテムのバンドルに対する好みの関係を持ち、これはアイテムの順序付けの応答性の高いセット拡張と互換性があります。

要件

人々がバンドルに関する選好関係を報告できるとは想定されていません。バンドルは多数存在するため、それらすべてについて順位付けを報告することは困難かもしれません。

したがって、この手続きは、アイテムの順位付けと整合し、かつ弱加法性を満たすあらゆる選好関係において、羨望のない割り当てを返すべきである。言い換えれば、この手続きは必然的に羨望のない割り当て（NEF）を返すべきである。^[3]^{: 303}

二人がアリスとジョージだとします。ジョージのアイテムからアリスのアイテムへの注入fがあり、ジョージが受け取るアイテムxごとに、アリスがxよりもf ( x ) を好む場合、アリスにとっての割り当ては NEF です。対称性が満たされる場合、ジョージにとっての割り当ては NEF です。アイテムの割り当てが NEF の場合、両方のパートナーにとってNEFです。NEF の割り当てでは、アリスとジョージは同じ数のアイテムを受け取ることに注意してください。

空配分は明らかにNEFですが、非常に非効率的です。したがって、すべてのNEF配分の中で「最良」となる配分を探します。NEF配分は、ある人にとってより良く、かつ別の人にとってより悪くないNEF配分が他に存在しない場合、パレート効率的と呼ばれます。

BT手順

はじめに、次の簡単な除算手順を考えてみましょう。

すべてのアイテムをテーブルの上に置きます。
テーブルの上にアイテムがある間に、次の操作を実行します。
- パートナーに、テーブルにあるすべてのアイテムの中から好きなものを選んでもらいます。
- 選択が異なる場合は、各パートナーにお気に入りのアイテムを渡して続行します。
- 選択肢が同一の場合、選択されたアイテムを争奪パイルに送ります。そのアイテムは割り当てられません。

この手続きはNEF割り当てを返します。非常にシンプルですが、多くのアイテムが競合パイルに捨てられるため、あまり効率的ではありません。AL手続きは若干複雑ですが、競合パイルがBTよりも大きくなることはなく、小さくなる可能性もあることを保証します。

AL手順

AL手順はBT手順と似ていますが、アイテムを競合パイルに移動する前に、一方のパートナーにアイテムを割り当て、もう一方のパートナーに別のアイテムで補償しようとします。これが失敗した場合にのみ、アイテムは競合パイルに送られます。

たとえば、4 つのアイテム (1、2、3、4) があり、パートナーの好みが次のとおりであるとします。

アリス：1 > 2 > 3 > 4
ジョージ：2 > 3 > 4 > 1

BT手続きでは、アリスには1、ジョージには2が与えられます。これらはアリスとジョージのお気に入りであり、それぞれ異なるからです。その後、アリスとジョージはどちらも3を選択したため、3は捨てられます。さらに、アリスとジョージはどちらも4を選択したため、これも捨てられます。最終的な割り当ては、アリス←{1}、ジョージ←{2}です。これはNEFですが、PEではありません。

AL手続きも、まずアリスに1、ジョージに2を与えます。次に、アイテム3を捨てる代わりにアリスに与え、ジョージにアイテム4を補填します。最終的な割り当ては、アリス ← {1,3}、ジョージ ← {2,4}です。これはNEFとPEです。

どちらの手続きも操作可能であり、パートナーは誤った好みを報告することで利益を得ることができる。しかし、このような操作には相手の好みに関する知識が必要となるため、実際には困難である。

無関心を伴うAL手順

オリジナルの AL 手順は、アイテムのランキングが厳格であるという仮定に大きく依存しています。

^[2]は、この手順を一般的なランキングに一般化し、無差別な可能性も考慮しています。

参考文献

^ Brams SJ, Kilgour DM, Klamler C (2014年2月1日). 「2人による分割不可能な物の公平な分割：効率的で羨望のないアルゴリズム」(PDF) .アメリカ数学会報. 61 (2): 130. doi : 10.1090/noti1075 .
^ ab Aziz, Haris (2015). 「分割不可能なオブジェクトの公平な配分のためのAL法の一般化」.経済理論速報. 4 (2): 307– 324. arXiv : 1409.6765 . doi :10.1007/s40505-015-0089-1. S2CID 256407813.
^ Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432。

[bkk13-1] Brams SJ, Kilgour DM, Klamler C (2014年2月1日). 「2人による分割不可能な物の公平な分割：効率的で羨望のないアルゴリズム」(PDF) .アメリカ数学会報. 61 (2): 130. doi : 10.1090/noti1075 .

[h15-2] Aziz, Haris (2015). 「分割不可能なオブジェクトの公平な配分のためのAL法の一般化」.経済理論速報. 4 (2): 307– 324. arXiv : 1409.6765 . doi :10.1007/s40505-015-0089-1. S2CID 256407813.

[3] Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432。