平等主義的ケーキカットは、公平性基準が平等主義ルールである、一種の公平なケーキカットです。ケーキは連続的な資源（土地や時間など）を表し、資源の各部分に対する評価が異なる人々の間で分配されます。平等主義的ケーキカットの目標は、エージェントの最小値を最大化し、それを条件として次に小さい値を最大化し、これを繰り返していくことです。最適化は効用ベクトルの レキシミン順序を用いて行われるため、レキシミンケーキカットとも呼ばれます。
平等主義的なケーキカットの概念は、デュビンスとスパニアーによって初めて提唱され、彼らはそれを「最適分割」と呼んだ。[1]
存在
レキシミン最適割り当ては、割り当て集合がコンパクト空間である場合には必ず存在する。これは離散的なオブジェクトを割り当てる場合には常に当てはまり、有限個の連続した均質なリソースを割り当てる場合には容易に証明できる。デュビンズとスパニアーは、連続した異質なリソース（「ケーキ」）に対して、割り当て集合がコンパクトであることを証明した。[1]したがって、レキシミン最適ケーキ割り当ては常に存在する。このため、レキシミンケーキ割り当て規則はデュビンズ・スパニアー規則と呼ばれることもある。[2]
変種
エージェントの評価が正規化されていない場合（つまり、異なるエージェントがケーキ全体に異なる価値を割り当てる場合）、割り当ての絶対効用プロファイル（要素iはエージェントiの効用そのもの）と相対効用プロファイル（要素iはエージェント i の効用をエージェントiの合計値で割ったもの）の間には差異が生じます。絶対レキシミンルールは、絶対効用プロファイルがレキシミン最大となる割り当てを選択し、相対レキシミンルールは、相対効用プロファイルがレキシミン最大となる割り当てを選択します。
プロパティ
レキシミンルールのどちらの変種もパレート最適かつ人口単調である。しかし、他の特性は異なる。[3]
嫉妬のなさとの関係
レキシミンルールのどちらの変種も、羨望フリーではない配分をもたらす可能性があります。例えば、5人のエージェントがいて、ケーキが3つの領域を持つ区分均質なものであり、エージェントの評価が以下の通りであるとします（欠損値は0です）。
| エージェント | 左 | 真ん中 | 右 |
|---|---|---|---|
| あ | 6 | 9 | |
| B | 5 | 10 | |
| C | 15 | ||
| D | 15 | ||
| E | 15 |
すべてのエージェントはケーキ全体の価値を15と評価するため、絶対的レキシミンと相対的レキシミンは等価です。最大の最小値は5であるため、レキシミンの割り当てはすべてのエージェントに少なくとも5を与える必要があります。つまり、右はエージェントC、D、Eで均等に分配され、中間はエージェントBに完全に分配される必要があります。しかし、AはBを羨ましがります。[3]
デュビンズとスパニアー[1]は、すべての価値尺度が厳密に正である場合、すべての相対的レキシミン割り当ては羨望の影響を受けないことを証明した。[4] ：第4節
Weller [4] : 第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]は、leximin最適資源配分を計算するアルゴリズムを提示している。
Aumann、Dombb、およびHassidim [5]は、すべてのe >0に対して、クエリを用いて、平等主義的福祉が最適値の少なくとも(1-e)となる割り当てを計算するアルゴリズムを提示している。これはnに対して指数関数的であるが、精度の桁数に対しては多項式的である。
一方、彼らは、P=NPでない限り、最適な平等主義的価値をnの多項式時間で2よりも良い因数に近似することは不可能であることを証明している。証明は、3次元マッチング（3DM）からの還元による。m個のハイパーエッジを持つ3DMマッチングのすべてのインスタンスに対して、彼らはn個のエージェントを持つケーキカットインスタンスを構築する。ここで、4 m ≤ n ≤ 5 mである。彼らは、3DMインスタンスが完全なマッチングを許容する場合、平等主義的価値が少なくとも1/ mであるケーキ割り当てが存在することを証明している。そうでない場合、平等主義的価値が1/(2 m )より大きいケーキ割り当ては存在しない。
参照
- 公平なケーキカット- 各エージェントに均等な効用を与える配分。多くの場合、平等主義的な配分は公平な配分と一致する。なぜなら、効用が異なる場合、効用が大きいエージェントからケーキを少し移動させることで、効用の小さいエージェントの効用を改善できるからである。
- 平等主義的等価性- 均質なリソース割り当ての文脈における同様の概念。
参考文献
- ^ abc Dubins, Lester Eli ; Spanier, Edwin Henry (1961). 「ケーキを公平に切る方法」アメリカ数学月刊誌. 68 (1): 1– 17. doi :10.2307/2311357. JSTOR 2311357.
- ^ ab Dall'Aglio, Marco (2001-05-01). 「公平な分割理論におけるデュビンス・スパニエ最適化問題」. Journal of Computational and Applied Mathematics . 130 ( 1–2 ): 17– 40. Bibcode :2001JCoAM.130...17D. doi : 10.1016/S0377-0427(99)00393-3 . ISSN 0377-0427.
- ^ ab シーガル・ハレヴィ、エレル;シクライ、バラーズ R. (2019-09-01)。 「ケーキカットにおける単調性と競争均衡」。経済理論。68 (2): 363–401 . arXiv : 1510.05229。土井：10.1007/s00199-018-1128-6。ISSN 1432-0479。S2CID 179618。
- ^ ab Weller, Dietrich (1985-01-01). 「測定可能な空間の公平な分割」 . Journal of Mathematical Economics . 14 (1): 5– 17. doi :10.1016/0304-4068(85)90023-0. ISSN 0304-4068.
- ^ Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013-05-06). 「社会的に効率的なケーキ分割の計算」. 2013年国際自律エージェント・マルチエージェントシステム会議議事録. AAMAS '13. サウスカロライナ州リッチランド: 国際自律エージェント・マルチエージェントシステム財団: 343–350 . ISBN 978-1-4503-1993-5。
