公平さの代償

公平な分割の理論では、公平さの価格(POF) は、分割によって達成できる最大の経済的福祉と公平な分割によって達成される経済的福祉の比率です。POF は、公平性を保証するために社会が被る福祉の損失を定量的に測定するものです。

一般に、POF は次の式で定義されます。$${\displaystyle POF={\frac {\max _{D\in {\text{部門}}}{(\mathrm {welfare} (D))}}{\max _{D\in {\text{公平な部門}}}{(\mathrm {welfare} (D))}}}}$$

正確な価格は、私たちが関心を持つ分割の種類、公平性の種類、社会福祉の種類によって大きく異なります。

最もよく研​​究されているタイプの社会福祉は功利主義的社会福祉であり、すべてのエージェントの（正規化された）効用の合計として定義されます。もう 1 つのタイプは平等主義的社会福祉であり、エージェントあたりの最小の（正規化された）効用として定義されます。

この例では、比例性の功利主義的価格、つまり UPOP に焦点を当てます。

100 人のパートナー間で分割しなければならない異質な土地資産を考えてみましょう。その価値は全員 100 です (または価値が 100 に正規化されています)。まず、いくつかの極端なケースを見てみましょう。

• 最大の功利的福祉は 10000 です。この福祉は、各パートナーが土地の異なる部分を希望する非常にまれな場合にのみ達成可能です。
• 比例配分では、各パートナーは少なくとも 1 の価値を受け取るため、功利的福祉は少なくとも 100 になります。

上記の極端なケースでは、UPOP ≤ 10000/100 = 100 という単純な上限がすでに得られています。ただし、より厳しい上限を得ることもできます。

土地を 100 人のパートナーに効率的に分割し、功利主義的福祉をUと仮定します。これを比例分割に変換します。これを行うには、パートナーを現在の価値に応じてグループ化します。

• 現在の値が 10 以上のパートナーは幸運なパートナーと呼ばれます。
• 他のパートナーは不幸と呼ばれます。

2つのケースがあります:

• 幸運なパートナーが 10 人未満の場合は、現在の分割を破棄して、新しい比例分割を行います (たとえば、最後の減数プロトコルを使用)。比例分割では、すべてのパートナーが少なくとも 1 の値を受け取るため、合計値は少なくとも 100 になります。元の分割の値は (10*100+90*10)=1900 未満であるため、UPOP は最大で 19 になります。
• 幸運なパートナーが少なくとも 10 人いる場合は、最後の減数プロトコルの次のバリエーションを使用して比例分割を作成します。
  • 幸運なパートナーはそれぞれ自分の取り分を 0.1 ずつカットし、他の不運なパートナーに減らしてもらいます。その取り分は、幸運なパートナーか不運なパートナーの 1 人が受け取ります。
  • これは、最大 90 人の不運なパートナーのそれぞれがシェアを持つまで続きます。これで、最大 10 人の幸運なパートナーのそれぞれが、少なくとも以前の値の 0.1 を持ち、不運なパートナーのそれぞれが少なくとも以前の値を持つため、UPOP は最大 10 になります。

要約すると、パートナーの価値尺度に関係なく、UPOP は常に 20 未満になります。

UPOP は 1 まで低くなることがあります。たとえば、すべてのパートナーが同じ価値尺度を持っている場合、公平性に関係なく、どの部門でも功利主義的福祉は 100 になります。したがって、UPOP = 100/100 = 1 です。

しかし、私たちが関心があるのは最悪のケースの UPOP、つまり UPOP が大きい値測定の組み合わせです。次にその例を示します。

パートナーには次の 2 つの種類があると仮定します。

• 土地全体を均一に評価する90 人の均一なパートナー (つまり、土地の価値はそのサイズに比例します)。
• 10 人の集中パートナー。各パートナーは、土地の 0.1 をカバーする単一の地区のみを重視します。

次の 2 つのパーティションを検討してください。

• 公平な分割: 土地を均等に分割し、各パートナーに土地の 0.01 を与えます。集中パートナーはそれぞれ、希望する地区で 0.01 を受け取ります。この分割は公平です。均一な各パートナーの価値は 1 で、集中パートナーの価値は 10 なので、功利主義的福祉は 190 です。
• 効率的な分割: 土地全体を集中パートナーに分割し、各パートナーに希望する地区全体を与えます。実利的福祉は 100*10=1000 です。

この例では、UPOP は 1000/190 = 5.26 です。したがって、5.26 は最悪のケースの UPOP の下限です (「最悪のケース」は、値測定のすべての可能な組み合わせで採用されます)。

すべての結果を組み合わせると、最悪の場合の UPOP は 5 から 20 の間であることがわかります。

この例は、POF を制限するために使用される議論の典型です。下限を証明するには、1 つの例を説明するだけで十分ですが、上限を証明するには、アルゴリズムまたは別の高度な議論を提示する必要があります。

上記の数値例は、100 からn のパートナーに一般化することができ、最悪の場合の UPOP の境界は次のようになります。

√n / 2 ≤ UPOP ≤ 2√n -1

UPOP = Θ( √n )

2人のパートナーの場合、より詳細な計算では、8-4*√3 ≅ 1.07という上限が得られます。^[1]

ケーキ全体を分割する場合、嫉妬のない分割は常に比例します。したがって、最悪の場合の UPOP の下限 (√ n /2) はここでも適用されます。一方、上限としてはn -1/2の弱い上限しかありません。^[1]したがって:

√n /2≤UPOV≤n- 1 / 2

Ω(√ n ) ≤ UPOV ≤ O( n )

2人のパートナーの場合、より詳細な計算では、8-4*√3 ≅ 1.07という上限が得られます。^[1]

${\displaystyle {(n+1)^{2} \over 4n}\leq UPOQ\leq n}$

${\displaystyle UPOQ=\Theta (n)}$

2人のパートナーの場合、より詳細な計算では、9/8 = 1.125という上限が得られます。^[1]

分割不可能なアイテムの場合、比例性、嫉妬のなさ、公平性を満たす割り当てが常に存在するわけではありません（簡単な例として、2人のパートナーが1つの貴重なアイテムを分割しようとしていると想像してください）。公平なアイテムの割り当ても参照してください。したがって、公平性の計算では、関連する公平性の概念を満たす割り当てがない場合が考慮されません。結果の簡単な要約：^[1]

UPOP = n - 1 + 1/ n ; 2人の場合: 3/2。

(3 n +7)/9-O(1/ n ) ≤ UPOV ≤ n -1/2; 2人の場合: 3/2

UPOQ=Infinity; 2人の場合: 2

「ケーキ」が望ましくない場合（例えば芝刈り）のケーキカットの問題については、次の結果が得られます。^[1]

( n +1)^2/4 n ≤ UPOP ≤ n ; 2人の場合: 9/8

(n+1)^2/4n ≤ UPOV ≤ 無限大; 2人の場合: 9/8

UPOQ= n です

UPOP = n

UPOV = 無限

UPOQ = 無限大

公平なケーキカットの問題には、ピースが連結されている必要があるバリエーションがあります。このバリエーションでは、POF 式の分子と分母の両方が小さくなります (最大値はより小さな集合で取得されるため)。そのため、POF が連結されていない場合よりも小さくなるか大きくなるかは、事前には明らかではありません。

功利主義的福祉については次のような結果が得られた: ^[2]

UPOP = Θ( √n )

UPOV = Θ( √n )

n -1+1/ n ≤ EPOQ ≤ n

EPOQ = Θ( n )

比例分割では、各パートナーの価値は合計の少なくとも 1/ nです。特に、最も恵まれないエージェントの価値 (分割の平等主義的福祉と呼ばれる) は少なくとも 1/ nです。これは、平等主義的最適分割では平等主義的福祉が少なくとも 1/ nであり、平等主義的最適分割は常に比例的であることを意味します。したがって、平等主義的比例価格 (EPOP) は 1 です。

1 倍

同様の考慮事項が平等主義的公平性価格 (EPOQ) にも当てはまります。

EPOQ = 1

嫉妬から解放されることの平等主義的な代償ははるかに大きい：^[2]

EPOV = n /2

これは興味深い結果です。嫉妬のなさという基準を主張すると、社会的格差が拡大し、最も不幸な市民に害を及ぼすことを意味します。比例性の基準は、それほど有害ではありません。

公平性による福祉の損失を計算する代わりに、福祉の最適化による公平性の損失を計算することができます。次の結果が得られます。^[2]

平等主義の比例価格 = 1

平等主義の嫉妬の代償 = n -1

功利主義の比例価格 = 無限大

平等主義の嫉妬の代償 = 無限

ケーキカットと同様に、分割不可能なアイテムの割り当てには、アイテムが一列に並び、割り当てられた各ピースが一列にブロックを形成するバリエーションがあります。結果の簡単な要約：^[3]

UPOP = n - 1 + 1/ n

UPOV = Θ( √n )

UPOQ = 無限大; 2人の場合: 3/2

1 倍

EPOV = n /2

EPOQ = 無限大; 2人の場合: 1

結果の簡単な要約: ^[4]

n /2 ≤ UPOP ≤ n

UPOV = 無限

UPOQ = n

1 倍

EPOV = 無限大

EPOQ = 1

公平性の価格は、石油や木材などの均質で分割可能な資源の割り当てをめぐる競争においても研究されてきた。既知の結果は次の通りである。^{[5] [6]}

UPOV = UPOP = Θ( √n )

これは、平等な所得からの競争均衡のルールにより、羨望のない配分が得られ、その効用価格は O(√n) となるためです。

公平性の価格は、公平な部分集合和問題の文脈で研究されてきました。

正当な代表の代償は、承認投票の場で正当な代表を求めることによって生じる平均満足度の損失である。^[7]

• 経済効率
• 無秩序の代償