調整された勝者手続き

調整済み勝者 (AW) は、嫉妬のないアイテム割り当てアルゴリズムです。2 つの当事者といくつかの個別の商品を指定すると、2 つの当事者間の商品の分割が次のように返されます。

1. 嫉妬がない: 各当事者は、自分の財産の取り分が相手方の取り分と同等かそれ以上であると信じています。
2. 公平: 両者のシェアから得られる「相対的な幸福度」は等しい。
3. パレート最適: 一方の当事者にとってより良い配分は存在せず、他方の当事者にとっても少なくとも同じくらい良い配分は存在しない。
4. 当事者間で最大 1 つの商品を分割します。

これは、4つの特性すべてを同時に満たすことができる唯一の手順です。^[1]しかし、それにもかかわらず、このアルゴリズムが実際に紛争解決に使用されたという報告はありません。

この手順はスティーブン・ブラムスとアラン・D・テイラーによって考案され、公平な分割に関する著書^{[2] : 65–94}に掲載され、後に独立した本として出版されました。^{[3] : 69–88}調整勝利法は以前米国で特許を取得していましたが、2016年に失効しました^。[4]

各当事者には商品のリストと、分配する均等な固定ポイントが与えられます。次に、各商品に価値を割り当て、（封印された）入札リストを仲裁者に提出します。仲裁者は各商品を最高入札者に割り当てます。

一方の当事者の商品の合計価値が他方の当事者の商品よりも大きい場合、アルゴリズムは比率に基づいて価値の高い当事者の商品を昇順で並べ、それらの商品を合計価値の高い当事者から合計価値の低い当事者に移し、両者の評価がほぼ等しくなるまで続けます（それ以上商品を移動すると、合計価値の低い当事者の合計価値が他方の当事者よりも高くなります）。次に、次の商品は、両者の価値が同じになるように当事者間で分割されます。^{[3] : 71–74}$${\displaystyle {\frac {\text{value for higher-combined-value party}}{\text{value for lower-combined-value party}}},}$$

たとえば、2 つの当事者が 4 つの商品に対して次の評価を行っているとします。

• アリス：86、75、30、9
• ボブ：19、81、60、40

まず、アリスが商品1を受け取り、ボブが商品2、3、4を受け取るように商品が分割されます。この時点で、アリスの商品の合計評価額は86で、ボブの商品は81 + 60 + 40 = 181です。したがって、ボブの商品は比率に基づいて順序付けられ、 ${\displaystyle {\frac {\text{Bob's valuations}}{\text{Alice's valuations}}}}$

• [良い 2 = ]、[良い 3 = ]、[良い 4 = ]。${\displaystyle {\frac {81}{75}}}$${\displaystyle {\frac {60}{30}}}$${\displaystyle {\frac {40}{9}}}$

ボブからアリスに商品 2 を移動すると、アリスの評価額がボブの評価額 (161 対 100) よりも高くなるため、商品は移動されません。代わりに、商品 2 はアリスとボブの間で分割されます。アリスは商品の を受け取り (約 60.9%)、ボブはを受け取ります (約 39.1%)。これで、それぞれの評価額は と になり、等しくなります。 ${\displaystyle {\frac {95}{156}}}$${\displaystyle {\frac {61}{156}}}$${\displaystyle 86+{\frac {95}{156}}(75)=131.673...}$${\displaystyle 60+40+{\frac {61}{156}}(81)=131.673...}$

現実の紛争の解決に調整勝者が使用された例はない。しかし、いくつかの研究では、アルゴリズムが使用された場合に特定の紛争がどのようになったかをシミュレートしている。

• キャンプ・デービッド合意。その評価関数はイスラエルとエジプトにとっての各問題の相対的な重要性に基づいてモデル化されており、理論的な結果は実際の合意と類似していた。^[5]
• イスラエル・パレスチナ紛争については、^[6]
• スプラトリー諸島紛争については、^[7]
• パナマ運河条約
• 1980年のジョリス対ジョリス離婚事件。^{[2] : 95～114}

AWは誠実なメカニズムではありません。当事者は、より大きな分け前を得るために、相手をスパイし、その報告を改ざんすることで利益を得ることができます。^[2]しかし、調整された勝者は常に近似ナッシュ均衡を持ち、情報に基づいたタイブレークでは、純粋なナッシュ均衡も持ちます。^[1]

特許取得済みのアルゴリズムでは、当事者が加法的効用関数を持っていると想定しています。つまり、商品の価値は個々の商品の価値の合計に等しいということです。たとえば、限界効用が減少する商品の複数のインスタンスは処理できません。

このアルゴリズムは2つの当事者のみを対象に設計されており、3つ以上の当事者がいる場合、嫉妬がなく、公平で、パレート最適な割り当てが同時に実現できない可能性があります。これは、JHReijnierse ^{[2] : 82–83}によって構築された、 3つの当事者とその評価を含む次の例で示されます。

• アリス：40、50、10
• ボブ：30、40、30
• カール：30、30、40

パレート最適かつ公平な割り当ては、財 1 をアリスに、財 2 をボブに、財 3 をカールに与える割り当てだけです。ただし、アリスはボブを羨むため、この割り当ては羨望の的になりません。

これら 3 つの特性のうち 2 つを同時に満たすことができます。

• 各当事者に各財を等量与えることによって、嫉妬のない公平な分配が実現できるだろう。
• 嫉妬のないパレート最適な割り当ては、パレート効率的な嫉妬のない分割またはウェラーの定理によって見つけることができます。
• 公平かつパレート最適な配分は線形計画法によって見つけることができる。^{[8] [9]}

さらに、パレート最適/嫉妬フリー、またはパレート最適/公平でありながら、2つ以上の当事者間で共有する必要があるオブジェクトの数を最小化する割り当てを見つけることが可能です。これは通常、調整された勝者の手順を3つ以上の当事者に一般化すると考えられています。^[10]

調整された勝者は、アイテムに対して肯定的な評価を持つエージェント向けに設計されています。ただし、混合（肯定的および否定的）評価を持つ当事者にも一般化できます。^[11]

Brams -Taylor 手順は同じ著者によって設計されましたが、それは嫉妬のないケーキカットの手順です。調整勝利の同質財よりも分割が難しい異質リソース (「ケーキ」) を扱います。^{[どのように? ]}したがって、BT は嫉妬のなさのみを保証し、他の属性は保証しません。

公平な分割実験に関する記事では、AW と関連手順を比較するいくつかの実験室実験について説明します。

• 調整された勝者を説明するウェブサイト