正直なケーキカット

正直なケーキカットとは、公平なケーキカットのためのアルゴリズムを研究するものであり、同時に正直なメカニズムでもある。つまり、参加者がケーキの各部分に対する真の評価を明らかにするよう促すものである。

ケーキを分ける際の古典的な分割方式は、必ずしも公平とは言えません。切る側が選ぶ側の好みを知っていれば、戦略的に行動することで1/2以上の分け前を得ることができるからです。例えば、切る側がケーキの大きさを重視し、選ぶ側がチョコレートの量を重視しているとします。この場合、切る側はチョコレートの量がほぼ同じになるようにケーキを2つに分け、小さい方のピースに少しだけチョコレートを多く入れることができます。すると、選ぶ側は小さい方のピースを選び、切る側は大きい方のピースを手に入れることができます。この大きいピースは、チョコレートの分け方によっては1/2以上の分け前になる可能性もあります。

公平なケーキの分け方を実現する、自明なランダム化真実メカニズムが存在する。それは、1人のエージェントを無作為に選び、その人にケーキ全体を与えるというものだ。このメカニズムは質問を一切しないため、自明に真実である。さらに、期待値においても公平である。各パートナーの期待値は正確に1/ nとなる。しかし、結果として得られる分配は公平ではない。課題は、事前だけでなく事後においても公平な真実メカニズムを開発することである。そのようなメカニズムはいくつか開発されている。

決定論的なメカニズムの場合、すべてのエージェントが区分的に一定の評価値を持っている場合でも、結果は概して否定的である。

黒川、ライ、プロカッチャは、ロバートソン・ウェッブ・クエリの数が限定されている決定論的、真実かつ羨望のないメカニズムは存在しないことを証明した。^{[ 5 ]}

アジズとイェは、以下の特性のいずれかを満たす決定論的な真実のメカニズムは存在しないことを証明している。^{[ 4 ]}

• 比例的かつパレート最適。
• 堅牢で比例的かつ無駄がない（「無駄がない」とは、それを望まないエージェントにはどの部分も割り当てられないことを意味し、パレート最適性よりも弱い）。

メノンとラーソンは、 ε-真実性の概念を導入しました。これは、どのエージェントも虚偽報告からεの割合を超える利益を得ないことを意味します。ここで、 εはエージェントの評価とは無関係な正の定数です。彼らは、決定論的メカニズムが以下の特性のいずれにも該当しないことを証明しました。^{[ 6 ]}

• ε-真実性、近似比例性、および非無駄性（近似定数が最大で1/ nの場合）。
• 真実であり、ほぼ比例し、連結している（近似定数は最大で 1/ n）。

彼らはEven–Pazプロトコルにわずかな修正を加え、nが偶数の 場合はε = 1 - 3/(2 n ) 、 nが奇数の 場合はε = 1 - 3/(2 n ) + 1/ n ²でε-真実であることを証明した。

Bei、Chen、Huzhang、Tao、Wuは、直接開示モデルであっても、以下の追加特性のいずれかを満たす決定論的、真実かつ羨望のないメカニズムは存在しないことを証明している。^{[ 7 ]}

• 連結された部品。
• 無駄がない。
• 位置を考慮しない配分 ― ケーキの一片の配分は、その一片に対するエージェントの評価のみに基づいて行われ、ケーキ全体における相対的な位置は考慮されない。

これらの不可能性の結果は、自由処分を前提とする場合と前提としない場合の両方で成り立つことに注意してください。

良い面としては、各エージェントがk回複製される複製経済では、真実を語ることがナッシュ均衡となる羨望のないメカニズムが存在する: ^{[ 7 ]}

• 接続要件がある場合、羨望のないメカニズムでは、kが無限大に近づくと真実を語る行為はナッシュ均衡に収束する。
• 接続性の要件がない場合、各均質な部分区間をすべてのエージェントに均等に割り当てるメカニズムでは、k ≥ 2 のときにすでに真実を語ることはナッシュ均衡になります。

Taoは、Bei、Chen、Huzhang、Tao、Wuによる以前の不可能性の結果を改善し、直接啓示モデルであっても、また以下のすべてが成り立つ場合でも、決定論的、真実かつ比例的なメカニズムは存在しないことを示した。^{[ 8 ]}

• エージェントは2人しかいません。
• エージェントは空腹である。各エージェントの評価は正の値である（つまり、0にはなり得ない）。
• この仕組みでは、ケーキの一部を割り当てずに残しておくことが許容される。

この不可能性の結果が3人以上のエージェントにも適用されるかどうかは未解決である。

プラス面では、Tao は「比例的リスク回避的真実性」（PRAT）と呼ばれるより弱い概念を達成する 2 つのアルゴリズムを提示しています。これは、エージェントiにとって利益のある逸脱のいずれにおいても、 iが比例的な取り分よりも少ない値を受け取るような他のエージェントの評価が存在することを意味します。この特性は、「リスク回避的真実性」よりも強く、これは i にとって利益のある逸脱のいずれにおいても、i が真実の報告における自身の価値よりも少ない値を受け取るような他のエージェントの評価が存在することを意味します。彼は、PRAT かつ羨望のないアルゴリズムと、PRAT かつ比例的かつ連結なアルゴリズムを提示しています。^{[ 8 ] [ 9 ]}

すべてのエージェントが区分的に均一な評価値を持つと仮定します。これは、各エージェントにとって、ケーキのサブセットのうち、そのエージェントにとって望ましい部分が存在し、各部分に対するエージェントの価値は、その部分に含まれる望ましいケーキの量に等しいことを意味します。例えば、ケーキの一部が均一なチョコレート層で覆われている一方で、他の部分は覆われていないとします。各部分を、含まれるチョコレートの量のみで評価するエージェントは、区分的に均一な評価値を持つことになります。これは、区分的に定数の評価値の特殊なケースです。この特殊なケースに対応する、いくつかの真実性アルゴリズムが開発されています。

Chen、Lai、Parkes、およびProcacciaは、決定論的、比例的、羨望フリー、パレート最適、多項式時間である直接開示メカニズムを提示しています。 ^{[ 2 ]}これは任意の数のエージェントに対して機能します。以下は、2 つのエージェントに対する CLPP メカニズムの例です (ケーキは区間です)。

1. 各エージェントに、希望する勤務間隔を報告してもらう。
2. どのエージェントからも望まれない各部分区間は破棄される。
3. ちょうど1人のエージェントが希望する各サブインターバルは、そのエージェントに割り当てられる。
4. 両方のエージェントが希望するサブインターバルは、両方のエージェントが同じ合計長さを得るように割り当てられます。

さて、エージェントが実際には望んでいない区間を「欲しい」と答えた場合、ステップ3でより多くの役に立たないケーキを受け取り、ステップ4でより少ない役に立つケーキを受け取る可能性があります。逆に、実際には望んでいる区間を「欲しくない」と答えた場合、ステップ3でより少ない役に立つケーキを受け取り、ステップ4でより多くの役に立つケーキを受け取りますが、ステップ4で与えられる量は他のエージェントと共有されるため、結局、嘘をついたエージェントは損をすることになります。この仕組みは、任意の数のエージェントに一般化できます。

CLPPメカニズムは、自由廃棄の仮定、すなわち、どのエージェントも望まない部品を廃棄できるという仮定に基づいている。

注：AzizとYe ^{[ 4 ]は}、CLPPメカニズムを区分的に一定の評価に拡張する2つのメカニズム、制約付きケーキ食いアルゴリズムと市場均衡アルゴリズムを提示しました。しかし、これらの拡張はどちらも、評価が区分的に一様でない場合にはもはや真実ではありません。

MayaとNisanは、 CLPPメカニズムが次の意味でユニークであることを示している。^{[ 10 ]}区分的に一様な評価を持つ2人のエージェントの特殊なケースを考えてみよう。ケーキは[0,1]であり、アリスはあるa <1に対して部分区間[0, a ]だけを欲しがり、ボブはあるb <1に対して部分区間[1 − b ,1]だけを欲しがる。無駄のないメカニズム、つまり少なくとも1人のプレイヤーが欲しがる各ピースを、それを欲しがるプレイヤーに割り当てるメカニズムだけを考える。このようなメカニズムはそれぞれ、アリスにはあるc <1に対して部分集合[0, c ]を、ボブにはあるd <1に対して部分集合[1 − d ,1]を与える必要がある。このモデルでは：

• 無駄のない決定論的メカニズムは、[0,1] 内の何らかのパラメータtに対して、アリスに区間 [0, min( a , max(1 − b , t ))] を、ボブに区間 [1 − min( b ,max(1 − a ,1 − t )),1]を与える場合に限り、真実である。
• このようなメカニズムは、 t = 1/2 の場合に限り羨望フリーとなる。この場合、それは CLPP メカニズムと同等である。

また、エージェントが2人の場合であっても、真実を語るメカニズムは、最適な社会的厚生の0.93しか達成できないことも示されている。

Li、Zhang、Zhangは、外部性（つまり、一部のエージェントが他のエージェントに与えられた価値から何らかの利益を得る）が存在する場合でも、外部性が十分に小さい限り、CLPPメカニズムがうまく機能することを示した。一方、外部性（正または負）が大きい場合、真実で無駄がなく、位置に依存しないメカニズムは存在しない。^{[ 11 ]}

Alijani、Farhadi、Ghodsi、Seddighin、Tajik は、区分的に均一な評価の特殊なケースに対するいくつかのメカニズムを提示しています。^{[ 12 ]}

• この拡張プロセスは、各エージェントが単一の希望区間を持ち、さらにエージェントの希望区間が順序付け特性を満たすような区分的に均一な評価を扱います。これは多項式時間で実行でき、真実性があり、羨望がなく、連結した区間を保証します。
• ロック解除を伴う拡張プロセスは、各エージェントが単一の希望区間を持つものの、順序付けの要件がない区分的に均一な評価を扱います。このプロセスは多項式時間で、真実性があり、羨望がなく、必ずしも連結である必要はありませんが、最大で 2 n − 2 回のカットを行います。

Bei、Huzhang、Suksompongは、区分的に均一な評価を持つ2人のエージェントのためのメカニズムを提示しており、これはCLPPと同じ特性（真実性、決定論性、比例性、羨望フリー、パレート最適、多項式時間で実行）を持ちながら、ケーキ全体が割り当てられることを保証します。^{[ 13 ]}

1. [0,1] の中で、アリスが望む長さ [0, x ] とボブが望む長さ [ x ,1]が等しくなるような最小のx を見つけます。
2. アリスには、アリスが値付けした区間 [0, x ] と、ボブが値付けしなかった区間 [ x ,1]をそれぞれ与え、残りをボブに与えます。

BHSメカニズムは、ケーキカットと家事分担（エージェントの評価がマイナスの場合）の両方に有効です。ただし、BHSにはいくつかの自然な望ましい特性が満たされていないことに注意してください。

• これは連結したピースを保証するものではありません。たとえば、アリスが[0,1]を望み、ボブが[0,0.5]を望む場合、x =0.25では、アリスは[0,0.25]と[0.5,1]を取得し、ボブは[0.25,0.5]を取得します。
• これは匿名ではありません（対称的な公平なケーキカットを参照）：アリスが[0,1]を望み、ボブが[0,0.5]を望む場合、アリスは希望する長さ0.75を取得し、ボブは0.25を取得しますが、評価が入れ替わると（アリスは[0,0.5]を望み、ボブは[0,1]を望む）、x =0.5となり、両方のエージェントが希望する長さ0.5を取得します。
• 位置に依存しないわけではありません。アリスが[0,0.5]を望み、ボブが[0,1]を望む場合、両方のエージェントは0.5の値を取得しますが、アリスの希望する区間が[0.5,1]に移動すると、x =0.75となり、アリスは0.25、ボブは0.75を取得します。

これは特定のメカニズムの問題ではなく、たとえ区分的に均一な評価を持つ2人のエージェントであっても、ケーキ全体を分配し、これら3つの特性のいずれかを保証する、真実で羨望のないメカニズムを持つことは証明不可能である。^{[ 13 ]}

BHSメカニズムは任意の数のエージェントに拡張されましたが、各エージェントが[0, x _i ]の形式の単一の区間のみを望む区分的に一様な評価の特殊なケースに限られます。

イアノフスキー^{[ 14 ]}は、すべてのエージェントが区分的に均一な評価を持っている場合でも、真実のメカニズムでは功利主義的に最適なケーキカットを達成できないことを証明しています。さらに、真実のメカニズムでは、他のどのメカニズムよりも少なくとも功利主義的な厚生が大きい配分を達成することはできません。しかし、無駄のない単純な真実のメカニズム（Lex Orderと表記）があります。エージェント1に好きなピースをすべて与え、次にエージェント2に好きなピースのうちまだエージェント1に与えられていないピースをすべて与え、以下同様に行います。このメカニズムの変種として、長さゲームがあります。これは、エージェントを希望する間隔の合計の長さで改名し、最短の間隔を持つエージェントを1、次に短い間隔を持つエージェントを2、以下同様にします。ただし、これは真実のメカニズムではありません。

• すべての主体が正直であれば、功利主義的に最適な資源配分が実現する。
• エージェントが戦略的である場合、そのすべての良好なナッシュ均衡はパレート効率的かつ羨望がなく、CLPPメカニズムと同じ利得をもたらします。

• 戦略的な公正な区分
• 真実に基づいた資源配分