順序パレート効率

順序パレート効率とは、エージェントがアイテムに対してのみ順序効用を表し、バンドルに対しては表さない設定にパレート効率の概念を応用したものを指します。つまり、エージェントはアイテムを最良から最悪までランク付けしますが、アイテムのサブセットにはランク付けしません。特に、各アイテムに数値を与えません。このため、特定の配分がパレート効率的であるかどうかについて曖昧さが生じる可能性があります。例として、3つのアイテムと2人のエージェントを持つ経済を考えてみましょう。順位は次のようになります。

• アリス：x > y > z。
• ジョージ：x > z > y。

[アリス: x、ジョージ: y,z]という配分を考えてみましょう。この配分がパレート効率的かどうかは、エージェントの数値評価に依存します。例えば、次のようになります。

• アリスが{y,z}を{x}よりも好み、ジョージが{x}を{y,z}よりも好む可能性がある（例えば、アリスのx,y,zに対する評価が8,7,6で、ジョージの評価が7,1,2の場合、効用プロファイルは8,3となる）。この場合、アリスとジョージの両方が自分の財の組み合わせを交換した方が得になるため（効用プロファイルは13,7となる）、配分はパレート効率的ではない。
• 対照的に、アリスが{x}を{y,z}よりも好み、ジョージが{y,z}を{x}よりも好む場合もある（例えば、アリスの評価が12,4,2で、ジョージの評価が6,3,4の場合）。この場合、配分はパレート効率的である。他の配分では、アリスが依然としてxを受け取る場合、ジョージの効用は低くなる。アリスがxを受け取らない場合、アリスの効用は低くなる。さらに、項目が分割可能であっても（つまり、部分パレート効率的であっても）、配分はパレート効率的である。アリスがxをr量ジョージに譲る場合、ジョージはアリスの効用を同じレベルに保つために、 yを少なくとも3r量、またはzを6r量アリスに与えなければならない。しかし、その場合、ジョージの効用は6r - 9rまたは6r - 24rだけ変化し、これは負の値となる。

配分のパレート効率はバンドルの順位に依存するため、アイテムの順位のみが与えられた場合、配分の効率をどのように決定するかは、事前には明らかではない。

割り当て X = (X ₁ ,...,X _n )は、すべてのエージェントi がバンドルX _iをバンドル Y _iよりも弱く好み、かつ少なくとも 1 人のエージェントj がX jを Y _{jよりも厳密}に好む場合、別の割り当て Y _{= ( Y 1} ,...,Y _n ) をパレート優位とする。割り当て X は、他のどの割り当てもパレート優位としない場合にパレート効率的である。時として、割り当てが離散割り当てによって支配されないことを意味する離散パレート効率と、割り当てが分数割り当てによっても支配されないことを意味するより強い概念である分数パレート効率との区別がなされる。

上記の定義は、エージェントによるバンドル（アイテムの集合）のランキングに依存します。本設定では、エージェントはアイテムのランキングのみを報告します。バンドルのランキングは、シングルトンバンドルを、それに含まれるアイテムと同じ順序でランク付けする場合、アイテムのランキングと整合していると言われます。たとえば、アリスのランキングがw < x < y < zの場合、整合的なバンドルのランキングは {w} < {x} < {y} < {z] でなければなりません。多くの場合、許容されるバンドルのランキングの集合について追加の仮定が置かれ、これにより整合性にさらなる制約が課されます。仮定の例は次のとおりです。

• 単調性：バンドルにアイテムを追加すると、必ずバンドルが改善される。これは、すべてのアイテムが良いものであるという仮定に対応する。したがって、アリスのバンドルランキングは、例えば {y} < {y,x} となる必要がある。
• 応答性：アイテムをより良いアイテムに置き換えると、常にバンドルが改善されます。したがって、アリスのバンドルランキングは、例えば {w,x} < {w,y} < {x,y} < {x,z} となるはずです。これは一貫性よりも強いです。
• 加法性：エージェントは各項目に値を割り当て、各バンドルをその内容の合計として評価します。この仮定は応答性よりも強いものです。例えば、アリスが{x,y}<{z}とランク付けした場合、彼女は{w,x,y}<{w,z}とランク付けしなければなりません。
• 辞書式：エージェントは、アイテム x を含むバンドルを、x より低いランクのアイテムのみを含むバンドルよりも常に上位にランク付けします。上記の例では、アリスは {w,x,y} < {z} とランク付けする必要があります。

Brams、Edelman、Fishburn ^{[ 1 ] : 9 は}、エージェントのアイテムランキングと一致するすべてのバンドルランキングに対してパレート効率的である場合、その割り当てをパレート保証と呼んでいます (すべての単調かつ応答的なバンドルランキングを許容します)。例:

• エージェントの評価が正であると仮定すると、すべてのアイテムを単一のエージェントに与えるすべての配分はパレート最適性を保証する。
• アリスの順位が x>y で、ジョージの順位が y>x である場合、割り当て [アリス:x、ジョージ:y] はパレート最適性を保証する。
• アリスの順位が x>y>z で、ジョージの順位が x>z>y であり、割り当てが離散的である必要がある場合、割り当て [アリス: x,y; ジョージ: z] はパレート最適性を保証する。^{[ 1 ] : 5}
• 上記の順位付けでは、配分[アリス: x、ジョージ: y,z]はパレート最適性を確保していません。序論で説明したように、例えばアリスのx,y,zに対する評価が8,7,6で、ジョージの評価が7,1,2の場合、パレート効率的ではありません。なお、これらの評価はどちらもエージェントの順位付けと一致しています。

Bouveret、Endriss、Lang ^{[ 2 ] : 3 は}同等の定義を使用しています。彼らは、エージェントのアイテムランキングと一致するバンドルランキングが存在し、そのランキングで X が Y をパレート支配する場合、割り当て X は割り当て Y をパレート支配する可能性があると述べています。割り当ては、他の割り当てがパレート支配する可能性がない場合、必然的にパレート効率的 (NecPE)と呼ばれます。

この2つの定義は論理的に同等である。

• 「Xはパレート最適性を保証する」とは、「すべての整合性のあるバンドルランキングにおいて、他のすべての割り当てYに対して、YはXをパレート最適に支配しない」と同等である。
• 「XはNecPEである」は、「他のすべての割り当てYについて、すべての整合性のあるバンドルランキングについて、YはXをパレート優位にしない」と同等である。「すべての」という量化子の順序を入れ替えても、論理的な意味は変わらない。

NecPE条件は、加法的なバンドルランキングをすべて許容する場合でも、差分が逓減する加法的な評価に基づくランキングのみを許容する場合でも、同じままである。^{[ 3 ]：第8節}

Brams、Edelman、Fishburn ^{[ 1 ] : 9 は}、エージェントのアイテムランキングと一致するいくつかのバンドルランキングに対してパレート効率的である場合、その割り当てをパレート可能と呼ぶ。明らかに、パレートを保証するすべての割り当てはパレート可能である。さらに、次のとおりである。

• アリスの順位が x>y>z で、ジョージの順位が x>z>y の場合、割り当て [アリス: x、ジョージ: y,z] はパレート可能となります。序論で説明したように、例えばアリスの x,y,z に対する評価が 12,4,2 で、ジョージの評価が 6,3,4 の場合、この割り当てはパレート効率的となります。なお、これらの評価はどちらもエージェントの順位と一致しています。
• アリスの順位が x>y で、ジョージの順位が y>x の場合、割り当て [Alice:y, George:x] はパレート可能ではありません。なぜなら、常に割り当て [Alice:x, George:y] によってパレート支配されるからです。

Bouveret、Endriss、Lang ^{[ 2 ]： 3は}異なる定義を使用しています。彼らは、エージェントのアイテムランキングと一致するすべてのバンドルランキングで、XがYをパレート優位にする場合、割り当てXは割り当てYを必然的にパレート優位にすると述べている。他の割り当てが必ずしもパレート優位にならない場合、割り当ては潜在的にパレート効率的（PosPE）と呼ばれる。

この2つの定義は論理的に同等ではない。

• 「Xはパレート最適である」とは、「他のすべての配分Yに対して、YがXを支配しないような、一貫性のあるバンドルランキングが存在する」と同値である。他のすべての配分Yに対して、同じバンドルランキングでなければならない。
• 「XはPosPEである」とは、「他のすべての割り当てYに対して、YがXを支配しないような一貫したバンドルランキングが存在する」と同値である。他のすべての割り当てYに対して、異なるバンドルランキングが存在する可能性がある。

Xがパレート可能であれば、それはPosPEであるが、もう一方の含意は（論理的に）真ではない。

パレート最適条件は、加法的なバンドルランキングをすべて許容する場合でも、差分が逓減する加法的な評価に基づくランキングのみを許容する場合でも、同じままである。^{[ 3 ]：第8節}

ボゴモルナイアとムーラン^{[ 4 ]： 302-303}は、公平なランダム割り当ての設定（バンドルランキングが加算的で、割り当てが分数であり、各エージェントに与えられる分数の合計が最大で1である必要がある）に対する効率性の概念を提示している。これは確率的優位性の概念に基づいている。

各エージェントiについて、バンドルX _{i が} バンドルY _iを弱確率的に支配(wsd)するのは、すべてのアイテム z について、 X _i内のzより優れたアイテムの総割合がY _i内の割合以上である場合(割り当てが離散的である場合、X _i sd Y _{i は、すべてのアイテム z について、} X _i内のzより優れたアイテムの数がY _i内の割合以上であることを意味します)。sd 関係にはいくつかの同等の定義があります。応答セット拡張を参照してください。特に、X _i sd Y _{i は}、アイテムのランキングと一致するすべてのバンドルのランキングについて、X _{iが Y i}より少なくとも同等である場合に限ります。^{[ 5 ]} バンドルX _{i が}バンドルY _iを厳密に確率的に支配(ssd)するのは、X _i wsd Y _iかつ X _i ≠ Y _{iの場合です。同等に、少なくとも 1 つのアイテム z について、「Y i}内の割合以上」が「Y _i内の割合より厳密に大きい」になります。^{[ 1 ]}では、ssd関係は「X _i >> Y _i」と書かれている。

割り当て X = (X ₁ ,...,X _n )は、すべてのエージェントiについてX i wsd Y _iかつY≠X (同等に、少なくとも 1 つのエージェント i についてX _i ssd Y _{i ) である場合、別の割り当て Y = ( Y 1 , ...} ,Y _{n ) を確率的に支配します。} ^{[ 1 ]}では、割り当て間の確率的支配関係は「X >> Y」とも書かれています。これは、必要なパレート支配と同等です。

割り当ては、それを確率的に支配する割り当てがない場合、 sd-効率的^{[ 6 ]}（順序効率またはO-効率的とも呼ばれる）^{[ 4 ]}と呼ばれます。これはPosPEに似ていますが、バンドルのランキングは加法効用関数に基づいている必要があり、割り当ては分数である可能性があることを強調しています。

チョーは、辞書式優位性に基づいて、公平なランダム割り当ての設定に関する他の2つの効率性の概念を提示している。

割り当て X = (X ₁ ,...,X _n )が、別の割り当て Y = (Y ₁ ,...,Y _{n )}を下方辞書式 (dl) に支配するとは、すべてのエージェント i に対して、 X _{i がY i を}弱く dl 支配し、かつ少なくとも 1 つのエージェントjに対して、X _{j がY j}を厳密に dl 支配する場合をいう。割り当てがdl 効率的であるとは、それを dl 支配する他の割り当てが存在しない場合をいう。

同様に、上方辞書式（ul）支配の概念に基づくと、他の割り当てがそれをul支配しない場合、その割り当てはul効率的であると呼ばれます。

一般的に、sd優位はdl優位とul優位を意味する。したがって、dl効率とul効率はsd効率を意味する。

• Aziz、Gaspers、Mackenzie、Walsh ^{[ 10 ] は}、順序的公平性の概念に関連する計算上の問題を研究しています。セクション 7 では、sd-Pareto-efficiency を簡単に研究しています。
• Dogan、Dogan、Yildiz ^{[ 11 ] は}、割り当て間の異なる支配関係を研究しています。割り当て X が割り当て Y を支配するのは、アイテムのランキングと一致するより大きなバンドルランキングのセットに対してパレート効率的である場合です。
• AbdulkadiroğluとSönmez ^{[ 12 ]}は、sd効率と事後パレート効率の関係（ランダム割り当ての文脈において）を調査している。彼らは割り当ての集合に対する支配の新しい概念を導入し、くじがsd効率的であるのは、くじのサポートの各部分集合が非支配である場合に限ることを示している。