合意の分裂

すべての${\displaystyle \varepsilon >0}$、アン${\displaystyle \varepsilon }$比率のほぼ正確な割り算${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$は、次のような部門です。

${\displaystyle |V_{i}(X_{j})-w_{j}|<\varepsilon }$

つまり、すべてのパートナーの間で、ピースjの価値はほぼ正確に${\displaystyle w_{j}}$差が以下${\displaystyle \varepsilon }$^{[ 1 ] : 127} いくつかの特殊なケースは次のとおりです。

• ${\displaystyle \varepsilon }$-コンセンサス 1/ k分割– 特殊なケース${\displaystyle w_{1}=\cdots =w_{n}=1/k}$。
• ${\displaystyle \varepsilon }$-コンセンサス半減期– 次のような特殊なケース${\displaystyle k=2}$そして${\displaystyle w_{1}=w_{2}=1/2}$。
• ${\displaystyle \varepsilon }$-完全除算– 特殊なケース${\displaystyle k=n}$そして${\displaystyle w_{1}=\cdots =w_{n}=1/n}$。

エージェントが区分的に一定の評価値を持つ場合、正確な分割の存在を証明するのは容易です。これは、ケーキをR 個の領域に分割でき、各領域の価値密度が均一であるとすべてのエージェントが同意することを意味します。たとえば、4 つの四分円それぞれに異なるトッピングが乗った円形のケーキを考えてみましょう。エージェントは各トッピングを異なる値で評価するかもしれませんが、同じトッピングの異なるピースを区別しません。各エージェントにとっての各ピースの価値は、各領域から得られる量のみに依存します。正確な分割は、次のようにして実現できます。

• 各領域をk個のサブ領域に分割し、サブ領域jにはちょうど${\displaystyle w_{j}}$地域の。
• 部分j を、すべてのR領域におけるj番目の部分領域の和集合とする。

必要なカットの数は${\displaystyle k\cdot R}$ここで、Rは領域の数である。このアルゴリズムは区分的線形評価に一般化できる。^{[ 4 ]}

エージェントが可算加法的な非原子測度を持つより一般的な設定では、正確な分割が存在する。これは、Dubins–Spanier凸性定理の系である（合意に基づく1/ k分割の存在は、以前にJerzy Neyman ^{[ 5 ]}によって指摘されている）。しかし、この定理は必要なカットの数については何も述べていない。

Woodall ^{[ 6 ]}は、区間ケーキの正確な分割を、区間の可算和集合として構成できることを示した。直感：上記で説明した区分的に均質なケーキの分割手順を考えてみよう。一般に、ケーキは区分的に均質ではない。しかし、値尺度は連続であるため、ケーキをより小さな領域に分割して、領域がますます均質になるようにすることができる。${\displaystyle R\to \infty }$このプロセスは合意による分割に収束する。しかし、極限における必要な切断の数は無限である。フレムリンは後に、このような分割を有限個の区間の和集合として構成できることを示した。

ケーキがn個の地区（部分区間）からなる区間であり、n個のパートナーそれぞれが1つの地区のみを重視すると仮定します。すると、ケーキをk個の部分集合に合意的に分割するには、${\displaystyle n\cdot (k-1)}$各地区は、その地区を重視するパートナーの目から見て等しいk個の部分に分割されなければならないため、分割数はkとなります。このことから、この正確な分割数で合意による分割が常に存在するのかという疑問が生じます。この問題は、主に一次元ケーキ（区間）に焦点を当てて、広範囲にわたって研究されてきました。

まず、合意形成による半減期のケースを考えてみましょう。${\displaystyle k=2}$そして、等しい重み。カット数の下限は ${\displaystyle n\cdot (k-1)=n}$実際、最大n回のカットで合意による半減が常に存在する。^{[ 7 ]}これはHobby–Rice 定理の直接的な系である。また、 Borsuk–Ulam 定理を使用して証明することもできる。^{[ 8 ]}

• 区間のすべての分割${\displaystyle n}$カットは長さのベクトルとして表現できます${\displaystyle n+1}$ここで、要素は部分区間の長さである。
• ベクトルの各要素は、正の値（ピース1に属する場合）または負の値（ピース2に属する場合）のいずれかになります。
• すべての分割の集合は球面と同相である${\displaystyle S^{n}}$。
• 関数を定義する${\displaystyle V:S^{n}\to \mathbb {R} ^{n}}$次のように：すべてのパーティションxに対して、${\displaystyle V(x)}$は、 i番目の要素が、パートナーiによるその分割におけるピース #1 の値から 1/2 を引いた値であるベクトルです。
• 関数Vは連続である。さらに、すべてのxに対して、${\displaystyle V(x)+V(-x)=0}$。
• したがって、ボルスク・ウラムの定理により、あるxが存在し、${\displaystyle V(x)=0}$その分割では、すべてのパートナーがピース1（およびピース2）をちょうど1/2と評価します。

エージェントの選好は尺度でモデル化されているが、証明では価値関数が部分集合上で正または加法的である必要はない。それらはボレルσ代数上で定義された任意の連続集合関数であってもよい。したがって、パートナーがケーキの部分集合に対して評価する値が加法的に分離可能である必要はない。^{[ 2 ]}

次に、合意に基づく 1/k 分割の場合を考えてみましょう。k > 1で重みが等しい場合です。Noga Alon は、1987 年のネックレス分割問題に関する論文で、次の結果を証明しました。${\displaystyle n}$間隔の異なる尺度、長さに関してすべて完全に連続。尺度によるネックレス全体の尺度${\displaystyle i}$、 は$\displaystyle k\cdot a_{i}}$すると、区間を分割することが可能になります。${\displaystyle k}$各部分（必ずしも隣接している必要はない）の測定値は、${\displaystyle i}$まさに${\displaystyle a_{i}}$最大${\displaystyle (k-1)n}$削減は必要であり、これは最適な措置だ。

ここで、 k = 2 で任意の重みの場合を考えてみましょう。ストロムクイストとウッドール^{[ 9 ] は}、各ピースが最大でn - 1 個の区間を含むようなパイ(円形のケーキ)の正確な分割が存在することを証明しました。したがって、最大で 2 n - 2 回のカットが必要です。ストロムクイスト-ウッドールの定理を参照してください。カットの数は、一般的な重みに対して本質的に最適です。この定理は、任意のk > 1 および任意の重みに対して、O( nk ) 回のカットを使用して正確な分割を得るために再帰的に適用できます。

ストーン・テューキーの定理は、 n次元空間にn個の測定可能な「オブジェクト」がある場合、それらすべてを（その測定、つまり体積に関して）単一の（n -1）次元超平面で半分に分割できると述べています。

言い換えれば、ケーキがスペースであるならば$\displaystyle \mathbb {R} ^{n}}$、パートナーの価値尺度は有限であり、どの時点でも消滅する。${\displaystyle n-1}$次元超平面が存在する場合、各パートナーに対して値がちょうど 1/2 となる半空間が存在する。したがって、単一のカットを用いた合意分割が存在する。

この定理の原文は、ケーキの次元数とパートナーの人数が等しい場合にのみ有効です。例えば、この定理を使って3次元のサンドイッチを4人以上のパートナーに分けることはできません。

しかし、そのような分割を可能にする一般化が存在する。それらは超平面ナイフではなく、より複雑な多項式曲面を使用する。^{[ 10 ]}

これらの多次元結果には離散的な適応も存在する。^{[ 11 ]}

有限個のクエリで正確な除算を計算することは不可能であり、エージェントがn = 2 個、ピースがk = 2 個しかない場合でも、重みは 1/2 に等しくなります。 ^{[ 1 ] : 103–104}これは、離散アルゴリズムを使用して達成できる最良の結果は、ほぼ正確な除算であることを意味します。

証明：プロトコルがステップkにあるとき、最大でk 個のピース​​の集合があります。正確な分割を行うには、プロトコルは正確な部分集合、つまり両方のパートナーが正確に 1/2 と評価するピースの部分集合を見つける必要があります。ここでは、すべてのkに対して、ステップkで正確な部分集合が存在しない状況があり、そのためプロトコルが無限に続く可能性があることを証明します。

最初は、両方のパートナーが1と評価するピースは1つしかないので、明らかに正確な部分集合は存在しません。1ステップ後には、最大で1人のパートナー（例えばアリス）がケーキを切る選択肢を持つことになります。アリスがケーキを2つのピースに切り分け、それが彼女にとって等しいピースだとしても、ジョージにとっては異なるピースになる可能性があるので、やはり正確な部分集合は存在しません。

ここで、ステップkに到達し、ピースがk個あると仮定します。一般性を失うことなく、各ピースは両方のパートナーにとってゼロ以外の価値を持つと仮定できます。これは、例えばアリスが0と評価するピースを切った場合、ジョージも同じピースを0と評価する可能性があるため、そのピースを捨てて他のピースで処理を続けることができるからです。

異なる部分集合の総数は 2 ^kであり、帰納法の仮定により、それらのどれも正確ではありません。ステップkで、プロトコルはアリスまたはジョージのいずれかに特定のピースを 2 つのピースに切るように依頼できます。一般性を失うことなく、切断者がジョージであり、彼がピース X を 2 つの部分ピース X1 と X2 に切断するとします。これで、部分集合の総数は 2 ^{k +1}になります。その半分は既に存在しており、仮定によりそれらは正確ではないため、プロトコルが正確な部分集合を見つける唯一の方法は、新しい部分集合を調べることです。各新しい部分集合は、ピース X が X1 または X2 のいずれかに置き換えられた古い部分集合で構成されます。ジョージは切断者であるため、これらの部分集合の 1 つを彼にとって正確な部分集合にするように切断できます (たとえば、ピース X を含む特定の部分集合の値が 3/4 であった場合、ジョージは X1 の値が 1/4 になるように X を切断し、新しい部分集合の値がちょうど 1/2 になるようにすることができます)。しかし、ジョージはアリスの評価を知らないため、切り分ける際にそれを考慮に入れることができません。したがって、ピースX1とX2がアリスにとって持つ可能性のある値は、数えきれないほど無限に存在します。新しい部分集合の数は有限であるため、アリスにとって1/2という値を持つ新しい部分集合が存在しないケースは無限に存在し、したがって、新しい部分集合はどれも正確ではありません。

2人のエージェントは、オースティンの移動ナイフ法を用いて合意による分割を達成することができる。

最も単純なケースは、重みが 1/2 の場合、つまり両者が合意したケーキの価値の半分に相当するピースを切り取る場合です。これは次のように行われます。一方のエージェントがケーキの上で 2 本のナイフを左から右に動かし、ナイフ間の値を常に正確に 1/2 に保ちます。中間値の定理により、ある時点でナイフ間のピースのもう一方のパートナーに対する値も正確に 1/2 になることが証明できます。その時点でもう一方のエージェントが「ストップ！」と叫び、ピースが切り取られます。

同じプロトコルを使用して、両方のエージェントがその価値が正確に等しいことに同意するピースを切り出すことができます。${\displaystyle 1/n}$このような断片を複数組み合わせることで、有理数である任意の比率で合意による分割を達成することが可能です。ただし、これには多数の分割が必要となる場合があります。

合意に基づく分割を実現するより良い方法は、ケーキの両端を特定し、それを円のように扱うことです。つまり、右側のナイフが右側に到達したら、すぐに左側に移動し、ナイフ間のピースは、右側のナイフの右側のピースと左側のナイフの左側のピースの和集合になります。このようにして、あらゆるケーキに対して合意に基づく分割を見つけることができます。${\displaystyle p\in [0,1]}$一方のエージェントはケーキの周りをナイフを周期的に動かし、ナイフ間の値を常にちょうどpに保ちます。ある時点で、ナイフ間のピースのもう一方のパートナーに対する値もちょうどpになることが証明できます。^{[ 12 ]}その時点でもう一方のエージェントは「停止！」と叫び、ピースがカットされます。これには 2 回カットするだけで済みます。

上記の手順を繰り返し適用することで、 n = 2 のパートナーと任意のk > 1 のサブセット間で合意による分割を達成できます。カットの回数は${\displaystyle 2(k-1)}$。

2015年現在、この移動ナイフ法をn > 2エージェントに一般化することは知られていない。^{[ 13 ]}

任意の特定の${\displaystyle \varepsilon >0}$各パートナーに、すべてのパートナーが自分の価値の差が以下であると信じるようなピースを与えることができます。${\displaystyle \varepsilon }$すなわち、すべてのiとすべてのjについて: ^{[ 1 ] : 127}

${\displaystyle |V_{i}(X_{j})-w_{j}|<\varepsilon }$

ほぼ正確な分割手順は、粉砕と梱包の2つのステップから構成されます。

クラム化ステップ：目標は、各パートナーが各クラムに十分小さな値を割り当てるように、ケーキを小さな断片（「クラム」）に切ることです。これは次のように行われます。k をある定数とします。パートナー #1 に、1/ kと評価するk 個のピース​​にケーキを切るように頼みます。パートナー #2 に、各ピースの値が最大で 1/k になるように、必要に応じてピースをトリミングするように頼みます（最大でk -1 回のカットを使用） 。これらの新しいピースは、もちろんパートナー #1 にとって依然として最大で 1/k の価値を持ちます。パートナー #3、#4、...、# nで続けます。最終的に、 n個のパートナー全員が、結果として得られる各クラムを最大で 1/ kと評価します。

パッキングステップ：ここでの目標は、パンくずをn個のサブセットに分割し、各サブセットjの値の合計がwjに_近くなるようにすることです。以下は、重みが1/2の場合の2人のパートナー（アリスとジョージ）に対するパッキングステップの直感的な説明です。^{[ 1 ]： 68-71}

1. 空のボウルを用意してください。
2. ボウルにパンくずを1つ入れます。
3. ボウルの中のパンくずの量がどちらかのパートナーの半分を超えた場合は、そのパートナーにボウルを渡し、残りのパンくずをもう一方のパートナーに渡す。
4. それ以外の場合（ボウル内の値が両方のパートナーにとって 1/2 未満の場合）、ボウル内の値がアリスにとっての値よりジョージにとっての値が大きい場合は、ジョージにとっての値がアリスにとっての値より大きいパンくずを見つけます（すべてのパンくずの値の合計はアリスとジョージの両方にとって 1 なので、そのようなパンくずは必ず存在します）。このパンくずをボウルに加え、ステップ 2 に戻ります。

帰納法によって、アリスとジョージのボウルの評価の差は常に最大でも 1/ kであることを証明できる。したがって、どちらかのパートナーがボウルを受け取ると、両者にとってのボウルの価値は 1/2-1/ kから 1/2+1/ kの間になる。

形式的には、各ピースは値のベクトルとして表すことができ、各ピースはパートナーごとに1つずつあります。各ベクトルの長さは制限されており、つまり、各ベクトルvに対して次のようになります。${\displaystyle ||v||\leq {\sqrt {n}}/k}$私たちの目標は、各パートナーjに対して、すべての要素がw _jに近いベクトルを作成することです。これを行うには、ベクトルを部分集合に分割し、各部分集合j内のベクトルの合計が、すべての要素がw _jであるベクトルに十分近くなるようにする必要があります。これは、V. Bergström の定理^{[ 14 ] [ 1 ] : 126–128のおかげで可能です。}

クラム・アンド・パック手順は、ロバートソン・ウェッブ・プロトコルのサブルーチンです。このプロトコルは、ほぼ正確で、かつケーキカットに不利にならない分割を生成します。

クラムアンドパック手順の別の説明は、BramsとTaylorによって提供されている。^{[ 15 ]}

ε近似コンセンサス半減は、ボルスク・ウラム定理の離散版であるタッカーの補題に基づくアルゴリズムによって計算できます。^{[ 2 ]}このアルゴリズムの適応により、この問題は複雑性クラスPPAに属することが示されます。^{[ 16 ]}これは、任意の有界かつ非原子的な評価に対しても成り立ちます。ただし、このアルゴリズムの実行時間は、問題のパラメータに対して指数関数的になる可能性があります。実際、コンセンサス半減は、いくつかの点で計算が困難です。

まず、ε がnの逆指数関数であると仮定します(つまり、1/ εはnの指数関数です)。すると、ε近似コンセンサス半減を見つけることはPPA 困難です。困難性は、次の追加条件でも成り立ちます。^{[ 16 ]}

• エージェントは区分的に定数となる評価値を持つ。問題への入力には、各エージェントについて、その区分的に定数となる評価値の端点と値が含まれる。また、すべての数値（近似精度εを含む）はバイナリで表現される。
• 区分的に定数な評価における要素の数はnの多項式である（値自体はnの指数関数となる可能性がある）。
• 近似係数εはnの逆多項式であってもよい。^{[ 17 ]}
• エージェントの評価は、2 つのブロックのみで区分的に一様です (ただし、エージェントが単一のブロックで区分的に一様の評価を持つ場合、 nカットの場合はパラメータ化された多項式時間で、任意の定数dの場合は 2 n - dカットの場合は多項式時間で問題を解くことができます) 。^{[ 18 ]}
• エージェントの数は定数であり、少なくとも3つである（ただし、2つのエージェントでも多項式時間で解くことができる）。^{[ 19 ]}

次に、εが定数（nに依存しない）であると仮定します。すると、ε近似コンセンサス半減問題を見つけることはPPAD困難であり、これは理論的にはPPA困難よりも弱い問題です。証明は、ε近似一般化回路問題からの還元によって行われます。困難性は、以下の条件下でも成り立ちます。

• 評価額は区分的に一定である。
• 定数個の追加カットを使用することが許可されています（つまり、定数dに対してn + dカットを使用してnエージェントの合意半減を探索します）。^{[ 20 ]}
• εが定数の場合、 ε近似コンセンサス半減がPPA困難（PPAD困難よりも強い）であるかどうかは未解決である。^{[ 16 ]}
• また、 εが定数であっても、 n -1回のカットでε近似コンセンサス半減が存在するかどうかを判定することはNP困難である。証明は3SATからの還元による。^{[ 20 ]}

εが定数の場合、2種類の近似を多項式時間で計算できます。これらのアルゴリズムは、一般的な加法評価（必ずしも区分的に定数である必要はありません）に対して機能します。評価は、すべてのn個の評価の合計に対するマーククエリを含む、Robertson–Webbクエリモデルのクエリを使用してアクセスされます。^{[ 3 ]}次の近似が得られます。

• 各エージェントが各部分を少なくとも 1/ 2nと評価するような分割を見つけるには、${\displaystyle n}$カット。
• 各エージェントが各部分を 1/2 ± εと評価するような分割を見つけるには、${\displaystyle O((n\log {n})/(\varepsilon ^{2}))}$オンラインアルゴリズムのカット、または${\displaystyle n\cdot \lceil 2+\log _{2}(1/\epsilon )\rceil }$オフラインアルゴリズムにおけるカット。
  • 任意の定数dに対するn + dカットの PPAD 困難性と 2 n +O(log( ε))の多項式時間アルゴリズムの間にはギャップがあることに注意してください。
• εが定数またはnの逆多項式である場合、ε近似コンセンサス分割は計算上ネックレス分割問題と等価であり、それぞれを多項式時間で他方に還元できる（これはネックレス分割がPPAD困難であることを意味する）。^{[ 16 ]}
• 正確な解を見つけることに興味がある場合、コンセンサス半減ははるかに困難です。n カットの解を見つけることはFIXP困難であり、 n -1 カットの解が存在するかどうかを判定することは ETR 完全です。^{[ 21 ]}
• エージェントの評価が代数回路で表現される場合、ε近似合意半減法は、Borsuk-Ulam探索問題の厳密解の近似を計算することと多項式時間で同等です。これは、 Borsuk-Ulam定理によって存在が保​​証されている問題の解を含むFIXPのスーパークラスである複雑性クラスBUに対して完全であることを意味します。^{[ 22 ]}

分割する資源がケーキではなく分割可能な資源の集合である場合、問題はより簡単になります。^{[ 23 ]}

• 加法効用を持つエージェントの場合、最大n 回のカットで合意の半分を計算する多項式時間アルゴリズムと、最大 ( k - 1) n 回のカットで合意のk分割を計算する多項式時間アルゴリズムが存在する。
• 与えられたインスタンスに対して最適なカット数で合意半減を計算することはNP困難である。さらに、 OPTをインスタンスに対する最適なカット数とした場合、最大でOPT+ n -1回のカットで合意半減を計算することもNP困難である。
• エージェントの効用が確率分布から抽出される場合、合意による半減にはほぼ確実にn回のカットが必要となる。
• 非加法的な単調効用を持つエージェントの場合、合意の半減は依然としてPPAD困難ですが、エージェントの数が固定されている場合は多項式時間アルゴリズムが存在します。

計算の観点からは、正確な除算の計算についてはあまり知られていない。${\displaystyle (k-1)n}$削減${\displaystyle k\geq 3}$問題は必ずしもより難しいとは限らないことに注意してください。${\displaystyle k\geq 2}$なぜなら、より多くのカットを使用できるからです。現在わかっていることは以下のとおりです。

• 問題は、任意のkに対してPPA- kにある。^{[ 24 ]}
• 1/ εがnの指数関数である場合、 k =3の場合、この問題はPPA困難である。^{[ 18 ]}

2 種類の近似は、 Robertson-Webb クエリの多項式数を使用して計算できます。^{[ 3 ]}

• 各エージェントが各部分を少なくとも 1/ knと評価するような分割を見つけるには、${\displaystyle (k-1)n}$オンラインアルゴリズムにおけるカット。
  • 1/ knを改善できるかどうかは未解決である。特に、各エージェントが各部分を少なくとも 1/ c ( k ) と評価するような効率的な (オンラインまたはオフライン) アルゴリズムが存在するかどうかは未解決である。ここで、c(k) はkの何らかの関数( nに依存しない) であり、${\displaystyle (k-1)n}$カット。
• 各エージェントが各部分を 1/ k ± εと評価するような分割を見つけるには、${\displaystyle O({\frac {kn\log {(kn)}}{\varepsilon ^{2}}})}$オンラインアルゴリズムのカット、または${\displaystyle n\cdot (k-1)\cdot \lceil 2+\log _{2}(3k/\epsilon )\rceil }$カット。^{[ 3 ]：第6節}
  • カット数を改善できるかどうかは未解決である。オンラインアルゴリズムの場合、 k = 2のときのカット数の下限は次のようになる。${\displaystyle O({\frac {n}{\varepsilon ^{2}}})}$つまり、対数的なギャップが存在する。

In the problem of cake-cutting among families,^[25] there are n agents grouped into k families; the goal is to partition a cake into k pieces and allocate one piece per family. A natural fairness criterion in this setting is unanimous proportionality, which means that all members in all families value their family's share at least 1/k (for other criteria and related problems, see fair division among groups). The problem is equivalent to exact division in the following sense:

• 任意のnとkに対して、k個のファミリーにグループ化されたn ( k -1)+1 個のエージェント間での全員一致比例分割の解は、 k個のピース​​（および等しい重み）を持つn個のエージェント間での正確な分割の解を意味します。具体的には、全員一致比例分割には少なくともn -1 回の分割が必要であり、近似的な全員一致比例分割を見つけることは PPA 困難であることを意味します。
• 任意のnとkに対して、 n 個のエージェントとk 個のピース​​間の正確な分割の解は、 k個のファミリーにグループ化された n+1 個のエージェント間の全会一致比例分割の解を意味します。特に、正確な全会一致比例分割は ( n -1)( k -1) 回のカットで実行でき、近似的な全会一致比例分割を見つけることは PPA に含まれることを意味します。カットの数はk = 2 ファミリーの場合はタイトですが、k > 2 の場合はタイトではありません。^{[ 25 ]}

合意形成のためのアルゴリズムは、パートナーが報告する価値尺度に依存します。パートナーがアルゴリズムの仕組みを知っている場合、自分の重み以上のものを得るために、価値尺度について嘘をつくインセンティブを持つ可能性があります。これを防ぐために、真実性を確保するためのメカニズムを使用する必要があります。^{[ 4 ] [ 26 ]}

最も単純な真実の分配方法は、重みによって決まる確率でパートナーを一人ランダムに選び、その人にケーキ全体を与えるというものです。この方法は質問を一切しないため、自明に真実です。さらに、期待値においては合意です。各パートナーの期待値はまさにその重みであり、これはあらゆる価値尺度において真です。しかし、結果として得られる分配は、もちろん合意に基づく分配ではありません。

合意による分割を見つけるための既存のアルゴリズム（またはオラクル）があれば、すべての重みが 1/ nの場合にも機能する、より真実性の高いメカニズムを構築することができる。

1. 各パートナーに、自身の価値評価指標を報告してもらう。
2. パートナーから報告された価値関数に従って、n個のピース​​すべてが正確に1/ nとなるようなパーティションを生成するために、既存のアルゴリズム/オラクルを使用します。
3. 合意された分割に対してランダムな順列を行い、各パートナーにその分割された断片の1つずつを割り当てる。

ここでは、報告された価値関数に関わらず、各パートナーの期待値は依然として 1/ nであるため、このメカニズムは依然として正直である。つまり、どのパートナーも嘘をついて利益を得ることはできない。さらに、正直なパートナーは、確率 1 で正確に 1/ nの値が得られることが保証される（期待値だけでなく）。したがって、パートナーは自身の真の価値関数を明らかにするインセンティブを持つ。