前提条件 ケーキC は、通常、有限の 1 次元セグメント、2 次元多角形、または多次元ユークリッド平面 R d
C 上に主観的価値関数 を持つn 人の人々がいます。各人i は、 C の部分集合を数値にマッピングする価値関数V i を持っています。すべての価値関数は、長さ、面積、または (一般に)ルベーグ測度 に関して絶対連続 であると仮定されます。[ 3 ] シグマ加法性 (全体の価値は部分の価値の合計に等しい) であると仮定されます。
Cは n 個の互いに素な部分集合に分割され、各人が互いに素な部分集合を受け取る。i 人に割り当てられた部分は、 X 私 {\displaystyle X_{i}} C = X 1 ∪ ⋯ ∪ X n {\displaystyle C=X_{1}\cup \cdots \cup X_{n}}
n人の人々は C に対して平等な権利を持っている。つまり、人々の権利について争いはなく、誰もが他の全員が公平な分け前を受け取る権利があることに同意している。唯一の問題は、各人が公平な分け前を受け取れるようにケーキをどのように分けるかということである。
以下の例では、以下のケーキを例として使用します。
このケーキはチョコレート味とバニラ味の2種類からできています。 アリスとジョージという二人の人物がいる。 アリスはチョコレートを9点、バニラを1点と評価している。 ジョージはチョコレートを6点、バニラを4点と評価している。
正義の要件
比例性 正義の最も古く、最も一般的な基準は比例性 （PR）です。比例的なケーキカット では、各人がケーキ全体の価値の少なくとも 1/ n に相当する価値を持つ一切れを受け取ります。例のケーキでは、比例的な分割は、バニラケーキすべてとチョコレートケーキの 4/9 をジョージ（価値 6.66）に、残りのチョコレートケーキの 5/9 をアリス（価値 5）に与えることで実現できます。記号で表すと次のようになります。
∀ 私 : V 私 （ X 私 ） ≥ 1 / n {\displaystyle \forall {i}:\ V_{i}(X_{i})\geq 1/n} 加算的な評価を行うn 人の場合、比例配分は必ず存在する。最も一般的なプロトコルは以下のとおりである。
ラストディミニッシャーは、 n個の ピースが連結していることを保証するプロトコルです（つまり、どの人も2つ以上の連結していないピースのセットを受け取ることはありません）。特に、ケーキが1次元の区間である場合、各人は区間を受け取ります。このプロトコルは離散的で、順番にプレイできます。必要なアクション数はO( n² ) です 。Dubins–Spanier移動ナイフ法は 、Last diminisher の連続時間バージョンです。[ 4 ] フィンクプロトコル（ 連続ペア または単独選択 とも呼ばれる）は、オンライン分割に使用できる離散プロトコルです。n − 1 人のパートナーに対する比例分割が与えられた場合、新しいパートナーが参加すると、プロトコルは既存の分割を変更して、新しいパートナーと既存のパートナーの両方が 1/ n の比率を維持するようにします。欠点は、各パートナーが多数の分離したピースを受け取ることです。 Even -Pazプロトコルは 、ケーキとエージェントのグループを再帰的に半分に分割することに基づいており、必要なアクション数はO( n log n )のみです。これは、比例分割において可能な限り最速の決定論的プロトコルであり、分割されたピースが確実に連結されることを保証できる比例分割において可能な限り最速のプロトコルです。 エドモンズ・プルース・プロトコルは、O( n ) 回のアクションしか必要としないランダム化プロトコルですが、部分的な比例配分（各パートナーは少なくとも 1/ an を受け取ります。ここでa はある定数です）しか保証せず、各パートナーに単一の連結したピースではなく、「パンくず」の集合を与える可能性があります。ベック領土分割議定書は、 係争地を複数の近隣諸国間で比例的に分割することができ、各国は自国が現在保有している領土に隣接し 、 かつ接続した領土を受け取ることになる。ウッドールの超比例分割プロトコルは、 少なくとも2人のパートナーが少なくとも1つのピースの価値について異なる意見を持っている場合、各パートナーに厳密に1/ n を超える分配額を与える分割結果を生み出す。詳細および参考文献については、「比例したケーキカット」を 参照してください。
比例原則は、人々の権利が平等でない状況にも一般化できる。例えば、異なる権利を持つ比例的なケーキカットでは、ケーキは株主に属し、一方が20％、もう一方が80％を保有する。これは、 加重比例 原則（WPR）につながる。
∀ 私 : V 私 （ X 私 ） ≥ w 私 {\displaystyle \forall i:V_{i}(X_{i})\geq w_{i}} ここで、w i
羨望の念がないこと もう一つの一般的な基準は、羨望のなさ （EF）です。羨望のないケーキカット では、各人が他のどのピースよりも少なくとも同等に価値のあるピースを受け取ります。記号で表すと次のようになります。
∀ 私 、 j : V 私 （ X 私 ） ≥ V 私 （ X j ） {\displaystyle \forall i,j:\ V_{i}(X_{i})\geq V_{i}(X_{j})} 場合によっては、比例性と羨望のなさの間には、以下の表にまとめたような含意関係が存在する。
分割選択 プロトコルは、常にEFとなる配分を見つけ出します。価値関数が加法性を持つ場合、この分割はPRにもなります。そうでない場合、比例性は保証されません。
n 人に対するEF分割は、評価が加法的でなくても、一貫した選好集合として表現できる限り存在する。EF分割は、要素が必ず連結されている場合と、要素が分離されていてもよい場合という、より容易なケースについて別々に研究されてきた。
接続された部品に関する主な結果は次のとおりです。
ストロムクイスト式ナイフ移動法は、 3人それぞれにナイフを渡し、あらかじめ決められた方法でケーキの上でナイフを連続的に動かすように指示することで、3人の間で嫉妬のない分け方を実現する。シモンズのプロトコルは、 n 人の人数に対する羨望のない分割の近似値を任意の精度で生成できます。価値関数が加法性を持つ場合、分割は比例的になります。そうでない場合、分割は羨望のない分割になりますが、必ずしも比例的になるとは限りません。このアルゴリズムは、公平な分割問題のいくつかを迅速かつ実用的に解決する方法を提供します。[ 5 ] [ 6 ] これらのアルゴリズムはどちらも無限です。1つ目は連続的であり、2つ目は収束に無限時間を要する可能性があります。実際、連結区間を3人以上の人に分割する際の、羨望のない分割方法は、いかなる有限な手順でも見つけることはできません。
互いに接続されていない可能性のある部品の場合、主な結果は以下のとおりです。
一般の場合の否定的な結果は、連結の場合よりもはるかに弱い。分かっているのは、羨望のない除算のためのすべてのアルゴリズムは、少なくともΩ( n² ) 回のクエリを使用する必要があるということだけだ。この結果と、既知の最良の手順の実行時間計算量の間には大きな隔たりがある。
詳細および参考文献については、「嫉妬のないケーキカット」を ご覧ください。
その他の基準 3つ目の、あまり一般的ではない基準は公平性 （EQ）です。公平な分配 では、各人がまったく同じ価値を得ます。ケーキの例では、各人にチョコレートとバニラを半分ずつ与えることで、各人が5の価値を得るように公平な分配を実現できます。記号で表すと次のようになります。
∀ 私 、 j : V 私 （ X 私 ） = V j （ X j ） {\displaystyle \forall i,j:\ V_{i}(X_{i})=V_{j}(X_{j})} 第4の基準は正確性である。各パートナー i の権利がw i 正確な分割 とは、以下の条件を満たす分割である。
∀ 私 、 j : V 私 （ X j ） = w j {\displaystyle \forall {i,j}:\ V_{i}(X_{j})=w_{j}} 重みがすべて等しい場合（1/ n の場合）、その割り算は完全割り算 と呼ばれ、次のようになります。
∀ 私 、 j : V 私 （ X j ） = 1 / n {\displaystyle \forall i,j:\ V_{i}(X_{j})=1/n}
確率的公平分割 従来の公平な分配方法では、通常、資源の一定割合を各参加者に決定論的な方法で割り当てます。一方、確率的な公平な分配では、貢献度、ニーズ、個人のスコアなど、参加者の属性に基づいて決定される確率に基づいて分配を行います。
一例として、統計力学 のボルツマン分布 を適用するボルツマン公平分配 法がある。[ 8 ]
p 私 = exp （ β s 私 ） ∑ j exp （ β s j ） {\displaystyle p_{i}={\frac {\exp(\beta s_{i})}{\sum _{j}\exp(\beta s_{j})}}} ここ、p 私 {\displaystyle p_{i}} 私 {\displaystyle i} s 私 s_i 私 {\displaystyle i} β {\displaystyle \beta } β = 0 {\displaystyle \beta =0} β {\displaystyle \beta }
この手法は、参加者のスコアによって与えられる制約の下でエントロピーを最大化することを目指し、厳密な平等と強力な実力主義 の間を補間できるような配分を生み出す。この確率的アプローチは、分割可能な資源や分割不可能な資源の分配など、さまざまな状況に適用でき、公平性や効率性に対する社会のさまざまな嗜好を反映するように調整できる。
ランダムな抽選や偶然による割り当てなど、その他の確率的な分割メカニズムも、特に分割不可能な物品を扱う場合や、決定論的な解決策の実施が困難な場合に用いられる。
幾何学的要件 場合によっては、パートナーに割り当てられるピースは、公平であることに加えて、いくつかの幾何学的制約を満たさなければならない。
最も一般的な制約は連結性 公平なパイの切り分けを 参照してください。 もう一つの制約は隣接性 です。この制約は、「ケーキ」が近隣諸国間で分割しなければならない係争地である場合に適用されます。この場合、各国に割り当てられる区画は、その国の現在の領土に隣接している必要があるかもしれません。この制約は、ヒルの土地分割問題 で扱われます。 土地の分割には、多くの場合、2次元の幾何学的制約があり、例えば、各区画は正方形であるか、（より一般的には）太い物体 でなければならない。[ 9 ]
手続き上の要件 最終的な分割結果に求められる特性に加えて、分割プロセス自体にも求められる特性があります。その特性の一つが真実性 （インセンティブ適合性 とも呼ばれる）であり、これには2つのレベルがあります。
もう一つの特性は対称性 です。手順における異なる役割間に違いがあってはなりません。この特性のいくつかのバリエーションが研究されています。
匿名性を確保 するには、エージェントを入れ替えて手順を再実行した場合、各エージェントが元の実行時と全く同じピースを受け取る必要があります。これは厳しい条件であり、現在、匿名手順が知られているのは2エージェントの場合のみです。対称性と は、エージェントを入れ替えて手順を再実行した場合、各エージェントが元の実行時と同じ値を受け取ることを意味します。これは匿名性よりも弱い条件です。現在、任意のエージェント数に対して対称かつ比例的な手順が知られており、O( n³ )回 の クエリが必要です。任意のエージェント数に対して対称かつ羨望のない手順も知られていますが、はるかに時間がかかります。既存の羨望のない手順をn !回実行する必要があります。アリストテレス 原理によれば、2つのエージェントが同一の価値尺度を持つ場合、両者は同じ価値を受け取る。これは対称性よりも弱い条件であり、羨望のない手続きであればどれでも満たされる。さらに、任意の数のエージェントに対してアリストテレス原理と比例関係を満たす手続きが知られており、必要なクエリ数はO( n³ ) である。詳細および参考文献については、「対称的な公平なケーキカット」を 参照してください。
手続き上の要件の3つ目の種類は単調性 です。分割手続きを、より小さい/大きいケーキとより小さい/大きいエージェントのセットで再適用した場合、すべてのエージェントの効用は同じ方向に変化する必要があります。詳細については、リソースの単調性を参照してください。
効率要件 正義に加えて、分割の経済効率性も考慮されるのが一般的である（効率的なケーキカット を参照）。効率性にはいくつかのレベルがある。
より弱い概念はパレート効率性 です。これは、ケーキ全体を一人に与えるだけで簡単に満たすことができます。課題は、公平性と両立させながらこれを満たすことです。効率的な嫉妬のない分配 を参照してください。 より強い概念は功利主義的最大化、つまり効用の合計を最大化することです（UM）。価値関数が加法的である場合、UM分割が存在します。直感的に、UM分割を作成するには、ケーキの各ピースを、それを最も高く評価する人に与える必要があります。例のケーキ では、UM分割ではチョコレート全体をアリスに、バニラ全体をジョージに与え、9 + 4 = 13の功利主義的価値を達成します。価値関数が区分的に一定である場合、つまりケーキを分割して各ピースの価値密度がすべての人にとって一定である場合、このプロセスは簡単に実行できます。価値関数が区分的に一定でない場合、UM配分の存在は古典的な測度論の定理から導かれます。功利主義的ケーキカットを 参照してください。
効率的で公平な分配 加法価値関数を持つn 人に対しては、必ず PEEF 分割が存在する。これはウェラーの定理で ある。[ 10 ]
ケーキが1次元区間 であり、各人が連結した区間を受け取る必要がある場合、次の一般的な結果が成り立ちます。価値関数が厳密に単調である場合（つまり、各人がそのすべての適切な部分集合よりも厳密に一片を好む場合）、すべてのEF分割はPEでもあります。[ 11 ] シモンズのプロトコルはPEEF分割を生成します。
ケーキが1次元の円 （つまり、2つの端点が位相的に同一である区間）であり、各人が連結した弧を受け取らなければならない場合、前述の結果は成り立ちません。EF分割は必ずしもPEではありません。さらに、PEEF分割が存在しない（非加法的）価値関数のペアが存在します。ただし、2人のエージェントがいて、そのうち少なくとも1人が加法的価値関数を持っている場合、PEEF分割が存在します。[ 12 ]
ケーキが一次元であっても、各人がそのケーキの断片的な部分を受け取る場合、EF分割は必ずしもPE分割とは限らない。この場合、PEEF分割を見つけるには、より複雑なアルゴリズムが必要となる。
価値関数が加法的かつ区分的に定数である場合、PEEF 分割を見つけるアルゴリズムが存在する。[ 13 ] リプシッツ連続で ある場合、それらは「好きなだけ」区分的に定数関数として近似できるため、そのアルゴリズムは「好きなだけ」PEEF 分割を近似する。[ 13 ]
EF 分割は必ずしも UM ではありません。[ 14 ] [ 15 ] [ 16 ]
計算モデル アルゴリズムの実行時間複雑性について考察するには、計算モデルが 必要となる。文献には、そのようなモデルがいくつか一般的に用いられている。
複数のケーキを分ける ケーキ切り分け問題には、複数のケーキがあり、各エージェントがそれぞれのケーキから一切れずつ取る必要があるという一般化がある。
Cloutier、Nyman、Su [ 18 ] は ルベール、ムニエ、カルボノー[ 19 ] Nyman、Su、Zerbib [ 20 ] は、 k 個の ケーキについて、 k ( n - 1) + 1 人のエージェントがいて、各ケーキがn 個の ピースにカットされている場合、EF 配分が常に存在することを証明しています ( n 人のエージェントの集合に対して配分は EF です)。 関連する2つの問題は次のとおりです。
多層ケーキカット[ 21 ] 公平な複数ケーキのカット[ 22 ]
参考文献 1 2 Steinhaus, Hugo (1949). 「公平な分配の問題」。Econometrica . 17 : 315– 9. doi : 10.2307 /1907319 . JSTOR 1907319 . ↑ アリエル・プロカシア、「ケーキカットアルゴリズム」。第13章、フェリックス・ブラント、ヴィンセント・コニツァー、ウル・エンドリス、ジェローム・ラング、アリエル・D・プロカシア（2016） 『 計算社会選択ハンドブック 』ケンブリッジ大学出版局。ISBN 9781107060432 。 ↑ Hill, TP; Morrison, KE (2010). "ケーキを丁寧に切る". The College Mathematics Journal . 41 (4): 281. CiteSeerX 10.1.1.185.656 . doi : 10.4169/074683410x510272 . S2CID 3813775 . ↑ Dubins, Lester Eli ; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly . 68 (1): 1– 17. doi : 10.2307/2311357 . JSTOR 2311357 . ↑ 「公平な分割計算機」 。 2010年2月28日に オリジナル からアーカイブ済み 。 2014年7月10日 に取得。 ↑ Ivars Peterson (2000年3月13日) 「ルームメイトのための公平な取引」 MathTrek 。 2012年9月20日の オリジナル からアーカイブ済み。 2014年 7月10日 取得 。 ↑ Aziz, Haris; Mackenzie, Simon (2017-08-27). "任意の数のエージェントのための離散的かつ有界な羨望のないケーキカットプロトコル". arXiv : 1604.03655 [ cs.DS ]. ↑ Park, J.-W., Kim, CU, Ghim, C., & Kim, BJ (2022). 分配的正義のためのボルツマンの公平な分割。Scientific Reports, 12, 15494. https://doi.org/10.1038/s41598-022-19792-3 ↑ エレル、シーガル・ハレヴィ。ニザン、シュムエル。ハシディズムの信奉者、アヴィナタン。オーマン、ヨナタン（2017）。 「正々堂々：二次元でのケーキカット」。 数理経済学ジャーナル 。 70 : 1–28.arXiv : 1409.4511 。 土井 ： 10.1016/j.jmateco.2017.01.007 。 S2CID 1278209 。 ↑ Weller, D. (1985). "測定可能な空間の公平な分割". Journal of Mathematical Economics . 14 : 5–17 . doi : 10.1016/0304-4068(85)90023-0 . ↑ Berliant, M.; Thomson, W.; Dunz, K. (1992). "異質商品の公正な分配について". Journal of Mathematical Economics . 21 (3): 201. doi : 10.1016/0304-4068(92)90001-n . ↑ Thomson, W. (2006). 「誕生日パーティーで子供が泣くのはなぜか？」。 経済 理論 。31 ( 3 ) : 501–521。doi : 10.1007 /s00199-006-0109-3。S2CID 154089829 。 1 2 Reijnierse, JH; Potters, JAM (1998). 「羨望のないパレート最適分割の発見について」. Mathematical Programming . 83 ( 1–3 ): 291–311 . doi : 10.1007/bf02680564 . S2CID 10219505 . ↑ カラギアンニス、I.カクラマニス、C.カネロプロス、P. Kyropoulou、M. (2011)。 「公平な分割の効率化」。 コンピューティング システムの理論 。 50 (4): 589. CiteSeerX 10.1.1.475.9976 。 土井 ： 10.1007/s00224-011-9359-y 。 S2CID 8755258 。 ↑ Aumann, Y.; Dombb, Y. (2010). "連結ピースによる公平な分割の効率性" . インターネットとネットワーク経済学 . コンピュータサイエンス講義ノート. 第6484巻. 26 ページ . CiteSeerX 10.1.1.391.9546 . doi : 10.1007/978-3-642-17572-5_3 . ISBN 978-3-642-17571-8 。↑ Cohler, Yuga Julian; Lai, John Kwang; Parkes, David C; Procaccia, Ariel (2011). Optimal Envy-Free Cake Cutting . AAAI. ↑ Balkanski, Eric; Brânzei, Simina; Kurokawa, David; Procaccia, Ariel (2014-06-21). "Simultaneous Cake Cutting" . Proceedings of the AAAI Conference on Artificial Intelligence . 28 (1). doi : 10.1609/aaai.v28i1.8802 . ISSN 2374-3468 . S2CID 1867115 . ↑ Cloutier, John; Nyman, Kathryn L.; Su, Francis Edward (2010-01-01). "2人プレイヤーの羨望のないマルチケーキ分割" . Mathematical Social Sciences . 59 (1): 26– 37. arXiv : 0909.0301 . doi : 10.1016/j.mathsocsci.2009.09.002 . ISSN 0165-4896 . S2CID 15381541 . ↑ Lebert, Nicolas; Meunier, Frédéric; Carbonneaux, Quentin (2013-11-01). "Envy-free two-player m-cake and three-player two-cake divisions" . Operations Research Letters . 41 (6): 607– 610. doi : 10.1016/j.orl.2013.07.010 . ISSN 0167-6377 . S2CID 7937916 . ↑ Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-09-15). "複数ピースによる公平な分割" . Discrete Applied Mathematics . 283 : 115– 122. arXiv : 1710.09477 . doi : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 . ↑ Hosseini, Hadi; Igarashi, Ayumi; Searns, Andrew (2020-04-28). "Fair Division of Time: Multi-layered Cake Cutting". arXiv : 2004.13397 [ cs.GT ]. ↑ Segal-Halevi, Erel (2021-03-11). "Fair multi-cake cutting" . Discrete Applied Mathematics . 291 : 15– 35. doi : 10.1016/j.dam.2020.10.011 . ISSN 0166-218X . S2CID 219792647 .
さらに読む 公平な分配に関する書籍リスト 公平な分配に関する研究論文一覧 
