AL手順

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

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

AL 手順では、対象者に関して次の前提が必要です。

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

人々がバンドルに対する好みの関係を報告できるとは想定されていません。バンドルは多数あり、それらすべてについて順位付けを報告するのは難しいかもしれません。

したがって、この手順は、アイテムのランキングと一致し、弱い加法性を持つすべての選好関係に対して、羨望のない割り当てを返す必要があります。言い換えれば、この手順は必然的に羨望のない割り当て（NEF）を返す必要があります。^{[3] : 303}

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

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

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

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

この手順は NEF 割り当てを返します。これは非常に単純ですが、多くのアイテムが競合パイルに破棄されるため、あまり効率的ではありません。AL 手順は少し複雑ですが、競合パイルが BT よりも大きくなることはなく、小さくなる可能性があります。

AL 手順は BT 手順と同様に機能しますが、アイテムを競合パイルに移動する前に、一方のパートナーにアイテムを割り当て、もう一方のパートナーに別のアイテムを補償しようとします。これが成功しなかった場合にのみ、アイテムは競合パイルに送られます。

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

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

BT 手順では、アリスに 1、ジョージに 2 が与えられます。これらは 2 人のお気に入りであり、異なるためです。次に、アリスとジョージの両方が 3 を選択したため、3 は破棄されます。次に、両方が 4 を選択したため、これも破棄されます。最終的な割り当ては、アリス←{1}、ジョージ←{2} です。これは NEF ですが、PE ではありません。

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

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

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

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