Loading article…
平等主義的ケーキカットとは、公平性の基準が平等主義ルールである一種の公平なケーキカットです。ケーキは、土地や時間などの連続的な資源を表し、その資源の一部に対する評価が異なる人々の間で分配されなければなりません。平等主義的ケーキカットの目標は、エージェントの最小値を最大化することです。この制約の下で、次に小さい値を最大化し、以下同様に繰り返します。最適化は効用ベクトルのレキシミン順序を用いて行われるため、レキシミンケーキカットとも呼ばれます。
割り当ての集合がコンパクト空間である場合、常にレキシミン最適割り当てが存在します。これは離散オブジェクトを割り当てる場合に常に当てはまり、有限個の連続した同質リソースを割り当てる場合に証明するのは簡単です。DubinsとSpanierは、連続した異質リソース（「ケーキ」）の場合、割り当ての集合がコンパクトであることを証明しました。[ 1 ]したがって、レキシミン最適ケーキ割り当ては常に存在します。このため、レキシミンケーキ割り当てルールは、Dubins–Spanierルールと呼ばれることもあります。[ 2 ]
エージェントの評価が正規化されていない場合（つまり、異なるエージェントが全体の価値に対して異なる値を割り当てる場合）、配分の絶対効用プロファイル（要素iはエージェントiの効用のみを表す）と相対効用プロファイル（要素iはエージェントiの効用をエージェントiの総価値で割った値）には差が生じます。絶対レキシミンルールは、絶対効用プロファイルがレキシミン最大となる配分を選択し、相対レキシミンルールは、相対効用プロファイルがレキシミン最大となる配分を選択します。
レキシミンルールのどちらのバリアントもパレート最適で、個体群単調です。ただし、他の特性が異なります。[ 3 ]
レキシミンルールのどちらのバリアントも、羨望のない配分ではない結果をもたらす可能性があります。たとえば、エージェントが5人いて、ケーキが3つの領域を持つ区分的に均質で、エージェントの評価が次のようになっているとします（欠損値はゼロです）。
すべてのエージェントはケーキ全体を15と評価しているので、絶対レキシミンと相対レキシミンは同等です。可能な最小値の最大値は5なので、レキシミン配分ではすべてのエージェントに少なくとも5を与える必要があります。これは、右側をエージェントC、D、Eに均等に分割し、中央をエージェントBに完全に与える必要があることを意味します。しかし、そうするとAはBを羨むことになります。[ 3 ]
DubinsとSpanier [ 1 ]は、すべての価値尺度が厳密に正である場合、すべての相対的レキシミン配分は羨望フリーであることを証明した。[ 4 ]：第4節
Weller [ 4 ] : Sec.4 では、相対的レキシミンではない、羨望のない効率的なケーキの割り当てを示しました。ケーキは [0,1] で、エージェントは 3 人おり、それぞれの価値尺度は、1/4、1/2、3/4 を中心とする三角形分布です。割り当て ([0,3/8],[3/8,5/8],[5/8,1]) の効用プロファイルは (3/8,7/16,7/16) です。これは羨望がなく、功利主義的に最適であるため、パレート効率的です。しかし、レキシミンにより優れた効用プロファイルを持つ別の割り当て ([0,5/16],[5/16,11/16],[11/16,1]) があります。
Dall'aglio [ 2 ]は、レキシミン最適リソース割り当てを計算するアルゴリズムを提示している。
Aumann、Dombb、Hassidim [ 5 ]は、すべてのe > 0 に対して、平等主義的福祉が最適値の少なくとも (1-e) である配分を計算するアルゴリズムを提示している。クエリ数。これはnに対して指数関数的ですが、精度桁数に対しては多項式的です。
一方、彼らは、P=NPでない限り、最適な平等主義的値をnの多項式時間で2倍より良く近似することは不可能であることを証明している。証明は3次元マッチング（3DM）からの還元による。m個のハイパーエッジを持つ3DMマッチングの各インスタンスに対して、 4m ≤ n ≤ 5mとなるn個のエージェントを持つケーキカットインスタンスを構築する。彼らは、3DMインスタンスが完全マッチングを許容する場合、少なくとも1/ mの平等主義的値を持つケーキの割り当てが存在することを証明している。そうでない場合、1/( 2m )より大きい平等主義的値を持つケーキの割り当ては存在しない。
