効率的なケーキカット

効率的なケーキの切り分けは、経済学とコンピュータ科学における問題です。これは、異なるトッピングのケーキや異なる覆いの土地など、分割可能であると仮定される異質な資源を扱います。つまり、その価値を損なうことなく、任意の小さな断片に切り分けることができます。この資源は、ケーキの異なる部分に対する好みが異なる複数のパートナー間で分割する必要があります。例えば、チョコレートのトッピングを好む人もいれば、チェリーを好む人も、できるだけ大きな一切れを望む人もいます。この分配は経済的に効率的でなければなりません。効率性に関するいくつかの概念が研究されています。

• 最も一般的な概念はパレート効率性です。これは、少なくとも1人の参加者にとってより良い配分は存在せず、かつ全員にとって少なくとも同等に良い配分は存在しないことを意味します。
• より弱い概念としては、無駄がないという考え方がある。ある配分が無駄がないというのは、どのエージェントも、自分にとって価値が0で、かつ他のエージェントにとって価値が0より大きいケーキを受け取らない場合である。

効率性は多くの場合、公平性との関連で研究され、その目的は効率性と公平性の両方の基準を満たす部門分けを見つけることである。

ケーキがあります${\displaystyle C}$通常は、有限の1次元セグメント、2次元多角形、または多次元ユークリッド平面の有限部分集合であると想定される。$\displaystyle \mathbb {R} ^{d}}$。

がある${\displaystyle n}$パートナー。各パートナー${\displaystyle i}$主観的価値関数を持つ${\displaystyle V_{i}}$サブセットをマッピングする${\displaystyle C}$数字へ。

${\displaystyle C}$分割する必要がある${\displaystyle n}$互いに素な部分集合であり、各人が互いに素な部分集合を受け取る。${\displaystyle i}$と呼ばれる${\displaystyle X_{i}}$、 となることによって${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n}}$。

以下の記述では、チョコレート、バニラ、レモン、砂糖の4つの部分からなるケーキと、アリスとジョージという2人のエージェントについて、それぞれの評価値を以下のように考えます。

割り当て${\displaystyle X}$あるエージェントにとって価値が0であるが、別のエージェントにとっては0より大きい価値を持つピースをそのエージェントに割り当てる場合、それは無駄であると呼ばれます。記号で表すと次のようになります。

${\displaystyle \exists {i,j}:\exists Z\subseteq X_{i}:V_{i}(Z)=0~~{\text{and}}~~V_{j}(Z)>0}$そして${\displaystyle \exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})}$。

それ以外の場合は、無駄のない配分（NW）と呼ばれます。ケーキの例では、ケーキ全体をアリスに与える配分はNWですが、ケーキ全体をジョージに与える配分は、レモンの部分が「無駄になる」ため無駄になります。他にも多くのNWな配分があり、例えば、チョコレートをジョージに、残りのケーキをアリスに与えるのはNWです。

割り当て${\displaystyle Y}$配分をパレート優位にする${\displaystyle X}$少なくとも一人が${\displaystyle Y}$より優れている${\displaystyle X}$誰も${\displaystyle Y}$より悪い${\displaystyle X}$記号で表すと：

${\displaystyle \forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})}$そして${\displaystyle \exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})}$

割り当て${\displaystyle X}$他のどの分割によってもパレート支配されない、つまり異議なく改善できない分割は、パレート最適(PO)と呼ばれます。ケーキの例では、ケーキ全体をアリスに与えるのは PO ですが、ケーキ全体をボブに与えるのは、レモンの部分をアリスに与える分割によってパレート支配されます。一般に (ピース間の接続要件がない場合)、すべての無駄な分割はパレート支配されるため、すべての PO 分割は NW です。ただし、その逆は真ではありません。たとえば、チョコレートをジョージに、残りのケーキをアリスに与える分割は NW ですが、PO ではありません。これは、ジョージにバニラとチョコレートの半分を与える分割によってパレート支配されます。これは、元の分割では (アリス、ジョージ) の効用が (3、6) であるのに対し、代替の分割では効用が (5.5、7) であるためです。

効率的な配分は常に存在する。例えば、功利主義的に最適なケーキの切り分けはすべてPOであり、したがってNWでもある。

しかし、そのような割り当てを見つけるのは難しい場合があります。区分的に均一な評価値を持つエージェントが2つしかない場合でも、有限個の「マーク」クエリと「評価」クエリを使用してNWケーキ割り当てを見つけることは不可能かもしれません。^{[ 1 ] : 9、Clm.3}これは、そのようなクエリを有限個実行した後、アルゴリズムは有限個の区間に関する情報しか得られず、区間内の無駄を防ぐことができないためです。エージェントへの区間の割り当てに関して、このエージェントはこの区間の一部を0と評価し、もう一方のエージェントは同じ部分を1と評価する可能性があります。したがって、POも有限プロトコルでは達成できません。^{[ 2 ] : 560、Thm.5}

厳密な正値性（各エージェントがケーキの各点を厳密に0より大きい値と評価する）を仮定すると、問題は簡単になる。すべての配分は自明にNWであり、ケーキ全体を単一のエージェントに与えるすべての配分は自明にPOである（他のすべての配分はこのエージェントに厳密に低い効用を与えるため）。

クエリではなく直接開示を用いるアルゴリズムであれば、この問題は容易に解決できます。直接開示アルゴリズムでは、各エージェントが自身の評価関数全体をアルゴリズムに開示します。これは、例えば区分的に定数な評価を用いる場合に可能です。直接開示を用いると、（各要素を最も高く評価するエージェントに与えることで）功利主義的に最適な配分を容易に見つけることができ、そのような配分はPOかつNWでもあります。

多くの場合、効率的であるだけでなく、さまざまな公平性の概念に従って公平な配分を見つけることが求められる。存在は依然として次のとおりである。

• 比例性も兼ね備えたPO配分は必ず存在する。例えば、比例性を満たす値の合計を最大化する配分は必ず存在し（比例配分の集合はコンパクトであるため）、かつ、比例性はパレート改善によって維持されるため、POである。
• さらに、羨望のないPO配分は常に存在する。これは、羨望のない状態がパレート改善によって維持されないため、上記の議論から直接導かれるものではない。しかし、ウェラーの定理として明示的に証明されている。

計算モデルによっては、厳密にプラスの評価であっても、そのような配分を見つけるのは難しい場合がある。

• クエリモデルでは、各エージェントにケーキの正の割合を与える有限アルゴリズムは、厳密に正の評価値を持つエージェントが2人しかいない場合でも、PO（Personal Outcome：最適最適化）にはなり得ません。これは、有限アルゴリズムは常に有限個の区間の値を知っているため、区間内の非効率性を回避できないからです。つまり、区間の割り当て方法に関わらず、アルゴリズムが検出できないような、部分区間の有利な交換が存在する可能性があるのです。
• 直接開示モデル（区分的に一定の評価）では、市場均衡アルゴリズム^{[ 3 ]}は、任意の数のエージェントに対して、多項式時間でPOと羨望のない（したがって比例的な）配分を生成します。

多くの場合、効率性と公平性に加えて、ピースには幾何学的な制約があります。たとえば、ケーキが区間である場合、各エージェントは連続した区間であるピースを必要とする場合があります。この追加要件により、次のようになります。

• 比例配分も含むPO配分は必ず存在する。これは、すべての比例的な連続配分の集合が依然としてコンパクトであり、パレート改善によって比例性が維持されるためである。
• 区分的に定数的な評価値を持つエージェントが少なくとも3人いる場合、羨望のないPO配分は存在しない可能性がある。 ^{[ 4 ]：例5.1}

計算論的な観点から：

• 一般的な評価では、価値密度が厳密に正である場合、分割して選択することは2 人のエージェントにとって PO かつ比例的です。一般性を無視して、アリスが切り分け、ジョージが最も左のピースを選び、アリスが最も右のピースを得るとします。ジョージが左のピースを得てアリスが右のピースを得るような代替配分は、パレート改善にはなり得ません。なぜなら、（厳密な正性の仮定により）切り分け位置が左に移動するとジョージが不利になり、右に移動するとアリスが不利になるからです。ジョージが右のピースを得てアリスが左のピースを得るような代替配分も、パレート改善にはなり得ません。なぜなら、そのような配分では、少なくともどちらか一方が総価値の 1/2 未満しか得られないのに対し、元の配分では両方とも少なくとも 1/2 以上を得るからです。
• 区分的に一定の評価では、市場均衡アルゴリズムは必ずしも連結した部分を生成するとは限らないため、機能しません。しかし、^{[ 5 ] : 317、定理5}に類似したアルゴリズムを使用して、任意の数のエージェントの効用の合計を最大化する比例配分を見つけることができます。${\displaystyle O(m^{n})}$線形計画問題（mは部品の数）。

厳密に正の評価値を持つ3人以上のエージェントに対して、有限個のクエリを使用して（クエリモデルの場合）、または多項式アルゴリズムを使用して（直接開示モデルの場合）、連結比例PO配分を見つけることができるかどうかは、現時点では不明である。

• 実用的なケーキカット
• 公平なケーキカット
• 公平さの代償