公平なケーキカット

公平な (EQ) ケーキカットは、公平性の基準が公平性である、一種の公平なケーキカット問題です。これは、すべてのパートナーの主観的価値が同じであるケーキの割り当てです。つまり、各パートナーは自分の取り分に等しく満足しています。数学的には、すべてのパートナーiとjについて次のようになります。

${\displaystyle V_{i}(X_{i})=V_{j}(X_{j})}$

どこ：

• ${\displaystyle X_{i}}$パートナーiに割り当てられたケーキです。
• ${\displaystyle V_{i}}$はパートナーiの価値尺度です。これは、ケーキの各ピースについて、そのピースからのパートナーiの効用を表す数値を返す実数値関数です。通常、これらの関数は、すべてのiについておよび となるように正規化されます。${\displaystyle V_{i}(\emptyset )=0}$${\displaystyle V_{i}(EntireCake)=1}$

他の公平性基準との例および比較については、 公平性に関するページを参照してください。

パートナーが 2 人いる場合、1 回のカットで EQ 分割が可能ですが、パートナーの評価を完全に把握している必要があります。^[1]ケーキが区間 [0,1] であると仮定します。各 について、および を計算し、同じグラフにプロットします。最初のグラフは 0 から 1 に増加し、2 番目のグラフは 1 から 0 に減少するため、交差点があることに注意してください。その点でケーキを切ると、公平な分割が得られます。この分割には、いくつかの追加のプロパティがあります。 ${\displaystyle x\in [0,1]}$${\displaystyle u_{1}([0,x])}$${\displaystyle u_{2}([x,1])}$

• 各パートナーが少なくとも 1/2 の値を受け取るため、これは EF です。
• パートナー1人あたりの値が1/2を超える可能性があるため、EXではありません。
• 単一のカットを使用するすべての部門の中で、パレート効率的（PE）です。ただし、2つ以上のカットを使用するより効率的な部門が存在する可能性があります。 ^[2]
• ケーキの方向がランダムに選択される場合（つまり、0が1になり、1が0になるように反転できる場合）、この手順は次の意味で弱い真実性も示します。誠実な確率測定を提出することによってのみ、パートナーは少なくともケーキの半分を受け取ることを保証できます。^[1]

同じ手順を家事の分担にも使用できます（負の効用）。

完全開示手順には、より弱い公平性とより強い誠実性を満たす変種^[3]がある。この手順では、まず各パートナーの中央値を求める。パートナー A の中央値が で、パートナー B の中央値が で、 であるとする。すると、A は を受け取り、B は を受け取る。ここで余剰 - がある。余剰は、パートナー間で均等に分割される。したがって、たとえば、A が余剰を 0.4 と評価し、B が余剰を 0.2 と評価する場合、A は からB の 2 倍の価値を受け取ることになる。したがって、このプロトコルは公平ではないが、それでも EF である。これは、次の意味で弱誠実である。リスク回避型のプレーヤーには、偽りの評価を報告すると価値が小さくなる可能性があるため、真の評価を報告するインセンティブがある。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle 0<a<b<1}$${\displaystyle [0,a]}$${\displaystyle [b,1]}$${\displaystyle [a,b]}$${\displaystyle [a,b]}$

オースティンのムービングナイフ手順では、 2 人のパートナーそれぞれに、主観的価値がちょうど1/2 のピースが与えられます。したがって、分割は EQ、EX、EF になります。2 回のカットが必要で、パートナーの 1 人に 2 つの切断されたピースが与えられます。

2回以上のカットが許される場合、EQだけでなくEFとPEも満たす分割が実現可能となる。著者の中には、このような分割を「完全」と呼ぶ人もいる。^[4]

PE-EF-EQ分割に必要な最小カット数はパートナーの評価によって異なります。ほとんどの実用的なケース（評価が区分線形であるすべてのケースを含む）では、必要なカット数は有限です。これらのケースでは、最適なカット数と正確な位置の両方を見つけることができます。アルゴリズムにはパートナーの評価に関する完全な知識が必要です。^[4]

上記の手順はすべて連続的です。2 番目の手順ではナイフが連続的に動き、その他の手順では 2 つの値測定値の連続的なプロットが必要です。したがって、これらの手順を有限数の個別のステップで実行することはできません。

この無限大の性質は、正確な結果を必要とする除算問題の特徴です。正確な除算#不可能性を参照してください。

ほぼ公平な分割とは、任意の に対して、パートナーの値の差が最大 である分割です。2 人のパートナーのほぼ公平な分割は、有限の時間と 1 回のカットで見つけることができます。^[5]${\displaystyle \epsilon }$${\displaystyle \epsilon >0}$

オースティンの手順は、 n 人のパートナーに拡張できます。各パートナーに、ちょうど の主観的価値を持つピースが与えられます。この分割は EQ ですが、必ずしも EX または EF または PE であるとは限りません (一部のパートナーは、他のパートナーに与えられるシェアを より大きく評価する可能性があるため)。 ${\displaystyle 1/n}$${\displaystyle 1/n}$

n -1個の可動ナイフを使用する別の手順があり、これを使用すると、エージェントの任意の順序に対して接続された公平な割り当てを見つけることができます。 ^{[6] ：Sec.6.2}

ジョーンズの完全な開示手続きは、次のようにパートナーにも適用できる。 ^[3]${\displaystyle n}$

• パートナーの可能な順序ごとに、変数の方程式のセットを作成します。変数はカットポイントであり、方程式は隣接するパートナーの公平性を決定します。たとえば、パートナーが 3 人いて順序が A:B:C の場合、2 つの変数は(A と B の間のカットポイント) と で、2 つの方程式はとです。これらの方程式には、すべてのパートナーが同じ値を持つ解が少なくとも 1 つあります。${\displaystyle n!}$${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle x_{AB}}$${\displaystyle x_{BC}}$${\displaystyle V_{A}(0,x_{AB})=V_{B}(x_{AB},x_{BC})}$${\displaystyle V_{B}(x_{AB},x_{BC})=V_{C}(x_{BC},1)}$
• すべての順序付けの中で、すべてのパートナーの（等しい）値が最大となる順序付けを選択します。${\displaystyle n!}$

比例分割（各パートナーに少なくとも を与える）が可能である ことは既にわかっているので、最大の公平な値は少なくとも でなければならないことに注意してください。${\displaystyle 1/n}$${\displaystyle 1/n}$

パートナーの価値尺度が互いに絶対的に連続している場合（つまり、同じサポートがある場合）、パートナーの価値を増やそうとすると、他のパートナーの価値が下がることになります。つまり、接続されたピースを提供するソリューションの中で、ソリューションは PE です。

Brams、Jones、Klamler は、EQ、PE、EF による分割を研究しています (彼らはこのような分割を「完全」と呼んでいます)。

彼らはまず、連結されたピースを取得しなければならない3つのパートナーに対して、EQ+EFの分割が存在しない可能性があることを証明しました。^[3]彼らは、1次元ケーキ上の3つの特定の価値尺度を記述することによってこれを行います。このケーキでは、2つのカットによるすべてのEQ割り当てがEFではありません。

そして、3人以上のパートナーがいる場合、ピースが分離していてもPE+EF+EQの分割は存在しない可能性があることを証明しました。^[2]彼らは、1次元ケーキ上の3つの特定の価値尺度を記述することでこれを行い、次の特性を備えています。

• 2 カットの場合、すべての EQ 割り当ては EF でも PE でもありません (ただし、EF と 2-PE、または EQ と 2-PE の割り当てはあります)。
• 3 回のカットでは、すべての EQ 割り当てが PE ではありません (ただし、EQ + EF 割り当てはあります)。
• 4 回のカットでは、すべての EQ 割り当てが EF になるわけではありません (ただし、EQ+PE 割り当てはあります)。

パイは、1 次元の円の形をしたケーキです (フェアなパイカットを参照)。

バルバネル、ブラムス、ストロムクイストは、EQとEFの両方であるパイの分割の存在を研究しています。次の存在結果は、特定の分割アルゴリズムを提供することなく証明されています。^[7]

• 2 人のパートナーの場合、常に嫉妬のない公平なパイの分割が存在します。パートナーの価値尺度が互いに対して絶対的に連続している場合 (つまり、一方のパートナーにとって正の価値を持つすべてのピースは、もう一方のパートナーにとっても正の価値を持つ場合)、嫉妬のない公平で非支配的な分割が存在します。
• 3 人以上のパートナーがいる場合、嫉妬がなく公平な割り当てを見つけるのは不可能かもしれません。しかし、公平で支配されない分割は常に存在します。

調整された勝者手順は、 2人のパートナー間で分割可能な一連の商品の公平で嫉妬のない効率的な分割を計算します。

ロバートソン・ウェッブクエリモデルでは、2エージェントの場合でも有限プロトコルを使用して公平なケーキの割り当てを見つけることはできません。 ^[8]さらに、任意のε>0に対して:

• 連結ε公平ケーキカットには少なくともΩ(log ε ⁻¹ )回のクエリが必要である。^[9] 2エージェントの場合、O(log ε ⁻¹ )プロトコルが存在する。^[5] 3エージェント以上の場合、最もよく知られているプロトコルではO( n (log n + log ε ⁻¹ ))回のクエリが必要である。^[10]
• たとえ接続性がなくても、ε公平なケーキカットには少なくともΩ(log ε ⁻¹ / log log ε ⁻¹ )回のクエリが必要である。^[8]

最大公平分割ルールは、すべての公平なケーキの割り当ての中から、エージェントの共通価値が最大となるものを選択するルールです。このルールには 2 つのバリエーションがあります。

• 絶対公平ルールは、絶対値（正規化されていない値）を均等化します。
• 相対的公平ルールは、相対的な（正規化された）値を均等化します。

常に最大公平な割り当て（絶対的および相対的）が関連して存在し、一般化されたムービングナイフ手順を使用して見つけることができます。

• 絶対的公平ルールは弱いパレート最適かつ資源単調ですが、比例的ではありません。
• 相対的公平ルールは弱いパレート最適かつ比例的であるが、資源単調ではない。^[6]

• 平等主義的ケーキカット- エージェントの最小の効用を最大化する割り当て。効用が異なる場合、効用の大きいエージェントからケーキを移動することで、小さい効用を改善できるため、平等主義的割り当ては公平な割り当てと一致することがよくあります。