公平なケーキカット
公平な分割の種類

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

V 私 （ X 私 ） ＝ V j （ X j ） {\displaystyle V_{i}(X_{i})=V_{j}(X_{j})}

どこ：

  • X 私 {\displaystyle X_{i}} パートナーiに割り当てられたケーキです。
  • V 私 {\displaystyle V_{i}} はパートナーiの価値尺度です。これは実数値関数であり、ケーキの各ピースについて、そのピースからパートナーiが得る効用を表す数値を返します。通常、これらの関数は正規化され、すべてのiに対してとなります。 V 私 （ ∅ ） ＝ 0 {\displaystyle V_{i}(\emptyset )=0} V 私 （ E n t 私 r e C 1つの け e ） ＝ 1 {\displaystyle V_{i}(ケーキ全体)=1}

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

二人のパートナーにとって公平なケーキカットを見つける

ワンカット - 完全な暴露

パートナーが2人いる場合、1回のカットでEQ分割が可能ですが、パートナーの評価値を完全に把握している必要があります。[1]ケーキが区間[0,1]にあると仮定します。各 について、と を計算し、同じグラフ上にプロットします。最初のグラフは0から1に増加し、2番目のグラフは1から0に減少するため、交点があることに注意してください。その点でケーキを切ると、公平な分割になります。この分割には、さらにいくつかの特性があります。 × ∈ [ 0 、 1 ] {\displaystyle x\in [0,1]} あなた 1 （ [ 0 、 × ] ） {\displaystyle u_{1}([0,x])} あなた 2 （ [ × 、 1 ] ） {\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 である。これは次の意味で弱誠実である。リスク回避型のプレーヤーには、偽りの利益を報告するとより小さな利益しか残らない可能性があるため、真の利益を報告するインセンティブがある。 1つの {\displaystyle a} b {\displaystyle b} 0 < 1つの < b < 1 {\displaystyle 0<a<b<1} [ 0 、 1つの ] {\displaystyle [0,a]} [ b 、 1 ] {\displaystyle [b,1]} [ 1つの 、 b ] {\displaystyle [a,b]} [ 1つの 、 b ] {\displaystyle [a,b]}

2つのカット - 動くナイフ

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

多くのカット - 完全な暴露

2回以上のカットが許容される場合、EQだけでなくEFとPEも満たす分割が可能になります。一部の研究者は、このような分割を「完全」と呼んでいます。[4]

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

ランタイム

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

この無限大の性質は、正確な結果を求める割り算問題に特徴的な性質です。正確な割り算#不可能性を参照してください。

ワンカット - ほぼ公平な分割

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

3人以上のパートナーにとって公平な分割を見つける

可動ナイフ手術

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

n -1個の可動ナイフを使った別の手順があり、これを使うとエージェントの順序に関係なく連結された公平な割り当てを見つけることができます。 [6] ：Sec.6.2 

繋がったピース - 完全な啓示

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

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

比例分割（各パートナーに少なくとも を与える）が可能であることは既にわかっているため、最大の公平な値は少なくとも でなければならないことに注意してください。 1 / n {\displaystyle 1/n} 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 次元の円の形をしたケーキです (公平なパイ切り分けを参照)。

バーバネル、ブラムス、ストロムクイストは、円錐の等分割と等分割の両方が存在することを研究した。以下の存在結果は、具体的な分割アルゴリズムを示すことなく証明されている。[7]

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

分割可能な商品

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

クエリの複雑さ

ロバートソン・ウェッブクエリモデルでは、有限プロトコルを用いても公平なケーキの割り当ては2エージェントの場合であっても見つからない。[8]さらに、任意のε > 0に対して：

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

最大公平配分ルールの特性

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

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

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

要約表

名前 タイプ # パートナー # カット プロパティ
ジョーンズ[1] 完全啓示プロセス 2 1（最適） EQ、EF、1-PE
ブラムス・ジョーンズ・クラムラー法[3] 完全啓示プロセス n n −1（最適） EQ、( n −1)-PE
オースティン 移動ナイフプロセス 2 2 イコライザー、EF、EX
オースティン 移動ナイフプロセス n 多くの イコライザー
[6] : 6.2節  移動ナイフプロセス n n −1（最適） イコライザー、プロップ、WPE
バーバネル・ブラムス[4] 完全啓示プロセス 2 多くの EQ、EF、PE
チェヒラロヴァ＝ピラロヴァ[5] 離散近似プロシージャ 2 1（最適） ニアEQ

参照

  • 平等主義的ケーキカット- エージェントの最小効用を最大化する配分。多くの場合、平等主義的配分は公平な配分と一致する。なぜなら、効用が異なる場合、効用が大きいエージェントからケーキを少し移動させることで、小さい方の効用を改善できるからである。

参考文献

  1. ^ abc Jones, MA (2002). 「二人のための公平で羨望のない効率的なケーキカットと可分財へのその応用」.数学マガジン. 75 (4): 275– 283. doi :10.2307/3219163. JSTOR  3219163.
  2. ^ ab Steven J. Brams、Michael A. Jones、Christian Klamler (2013). 「N人称ケーキカット：完全な割り算は存在しないかもしれない」.アメリカ数学月刊誌. 120 :35. doi :10.4169/amer.math.monthly.120.01.035. S2CID  7929917.
  3. ^ abcd Steven J. Brams、Michael A. Jones、Christian Klamler (2007). 「ケーキを切るより良い方法 - 再考」(PDF) . AMSの通知.
  4. ^ abc Barbanel, Julius B.; Brams, Steven J. (2014). 「二人でケーキを切る：最適なカット回数」. The Mathematical Intelligencer . 36 (3): 23. CiteSeerX 10.1.1.361.366 . doi :10.1007/s00283-013-9442-0. S2CID  189867346. 
  5. ^ abc チェクラロヴァ、カタリーナ;ピラロヴァ、エヴァ (2012)。 「ほぼ公平な 2 人によるケーキカット アルゴリズム」。最適化。61 (11): 1321.土井:10.1080/02331934.2011.563306。S2CID  120300612。
  6. ^ abc シーガル・ハレヴィ、エレル; Sziklai、Balázs R. (2018-09-01)。 「接続されたケーキカットにおける資源の単調性と人口の単調性」。数学社会科学。95 : 19–30.arXiv : 1703.08928 。​​土井：10.1016/j.mathsocsci.2018.07.001。ISSN  0165-4896。S2CID  16282641。
  7. ^ Barbanel, JB; Brams, SJ; Stromquist, W. (2009). 「パイを切るのは簡単なことではない」. American Mathematical Monthly . 116 (6): 496. CiteSeerX 10.1.1.579.5005 . doi :10.4169/193009709X470407. 
  8. ^ ab Procaccia, Ariel D.; Wang, Junxing (2017-06-20). 「公平なケーキカットの下限値」. 2017 ACM Conference on Economics and Computation の議事録. EC '17. マサチューセッツ州ケンブリッジ、米国: Association for Computing Machinery. pp.  479– 495. doi :10.1145/3033274.3085107. ISBN 978-1-4503-4527-9. S2CID  9834718。
  9. ^ Brânzei, Simina; Nisan, Noam (2018-07-13). 「ケーキカットにおけるクエリの複雑性」. arXiv : 1705.02946 [cs.GT].
  10. ^ チェクラロヴァ、カタリーナ;ピラロバ、エヴァ (2012-11-01)。 「公平な分割の計算可能性について」。離散最適化。9 (4): 249–257。土井: 10.1016/j.disopt.2012.08.001。ISSN  1572-5286。{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
「https://en.wikipedia.org/w/index.php?title=Equitable_cake-cutting&oldid=1323047364」より取得