真実のケーキカット

真実のケーキカットとは、公正なケーキカットのためのアルゴリズムの研究であり、真実のメカニズムでもあります。つまり、参加者がケーキのさまざまな部分に対する本当の評価を明らかにするように動機付けます。

ケーキカットにおける古典的な「分割と選択」の手順は、真実ではありません。もしカットする人が選ぶ人の好みを知っていれば、戦略的に行動することで、半分よりもはるかに多くのものを手に入れることができるのです。例えば、カットする人がケーキの大きさで価値を評価し、選ぶ人がチョコレートの量で価値を評価するとします。すると、カットする人はほぼ同じ量のチョコレートでケーキを2つに切り分け、小さい方のケーキにはわずかに多くのチョコレートが入っています。すると、選ぶ人は小さい方のケーキを取り、カットする人は大きい方のケーキを獲得することになります。そのケーキの価値は、チョコレートの分配方法によっては、半分よりもはるかに高くなる可能性があります。

ランダム化メカニズム

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

正確な分割メカニズム

正確な分割（コンセンサス分割とも呼ばれる）とは、ケーキをn個のピース​​に分割し、各エージェントが各ピースの価値をちょうど1/ nと評価する分割である。このような分割の存在は、デュビンス・スパニエの凸性定理の系である。さらに、最大でカット回数が1回の分割が存在する。これは、ストロムキスト・ウッドールの定理とネックレス分割定理の系である。 ${\displaystyle n(n-1)^{2}}$

一般に、有限アルゴリズムでは正確な割り算を見つけることはできません。しかし、例えばすべてのエージェントが区分線形評価を持つ場合など、特殊なケースでは正確な割り算を見つけることが可能です。正確な割り算を見つけるための非真実アルゴリズム（またはオラクル）があると仮定します。これを用いて、期待値が真実であるランダム化メカニズムを構築できます。 ^{[1] [2]}このランダム化メカニズムは直接開示メカニズムであり、すべてのエージェントにそれぞれの価値尺度全体を明らかにするよう求めることから始まります。

1. エージェントに価値尺度を報告してもらいます。
2. 既存のアルゴリズム/オラクルを使用して正確な除算を生成します。
3. コンセンサス パーティションに対してランダムな順列を実行し、各パートナーにピースの 1 つを渡します。

ここで、各エージェントの期待値は、報告された価値関数に関わらず常に1/ nです。したがって、このメカニズムは真実です。つまり、嘘をつくことで利益を得るエージェントはいません。さらに、真実を語るパートナーは、確率1で正確に1/ nの価値が保証されます（期待値だけではありません）。したがって、パートナーは真の価値関数を明らかにするインセンティブを持ちます。

超比例機構

超比例分割とは、各主体が自身の価値尺度において1/ nよりも確実に大きい金額を受け取るケーキ分割である。このような分割が存在するのは、少なくとも2つの主体がケーキの少なくとも1切れに対して異なる評価を行う場合にのみ知られている。常に比例分割を返し、かつ超比例分割が存在する場合は常に超比例分割を返すような 決定論的メカニズムは、真実ではない。

モーセルとタムズは、期待値に忠実な超比例ランダム化メカニズムを提示している。 ^[1]

1. 特定の分布Dから分割を 1 つ選択します。
2. 各エージェントに自分の作品を評価してもらいます。
3. すべてのn評価が 1/ nより大きい場合は、割り当てを実装して終了します。
4. それ以外の場合は、正確な除算メカニズムを使用します。

ステップ1の分布Dは、エージェントの評価に関わらず、超比例配分が存在する場合、それが選択される確率が正となるように選択する必要があります。ステップ2では、各エージェントが真の価値を報告することが最適となります。低い値を報告しても、エージェントの価値が超比例配分から比例配分に低下する可能性があります（ステップ4）。高い値を報告しても、エージェントの価値が比例配分から1/ n未満に低下する可能性があります（ステップ3）。

クエリを使用して正確な除算を近似する

エージェントが評価を直接明らかにするのではなく、マークおよび評価クエリに答えることで間接的に価値を明らかにするとします (Robertson-Webb モデルの場合と同様)。

ブランゼイとミルターセン^[3]は、正確な除算メカニズムを「離散化」し、クエリモデルで実行できることを示しています。これにより、任意の に対して、最大 回のクエリを要求し、期待値が真実であり、すべてのエージェントの評価に基づいて、各エージェントに から までの価値を割り当てる、ランダム化されたクエリベースのプロトコルが得られます。 ${\displaystyle \epsilon >0}$ ${\displaystyle O(n^{2}/\epsilon )}$ ${\displaystyle 1/n-\epsilon }$ ${\displaystyle 1/n+\epsilon }$

一方、彼らは、あらゆる決定論的かつ真実性の高いクエリベースのプロトコルにおいて、すべてのエージェントがケーキのすべての部分を正に評価する場合、少なくとも1人のエージェントが空の部分を手に入れることを証明しました。これは、エージェントが2人だけの場合、少なくとも1人のエージェントが「独裁者」となり、ケーキ全体を手に入れることを意味します。明らかに、このようなメカニズムは嫉妬から逃れることはできません。

区分定数評価のためのランダム化メカニズム

すべてのエージェントが区分的に一定の評価値を持つと仮定する。これは、各エージェントにとってケーキが有限個の部分集合に分割され、各部分集合におけるエージェントの価値密度が一定であることを意味する。この場合、AzizとYeはより経済的に効率的なランダム化アルゴリズムを提示する。制約付き直列独裁制は期待値が真実で、ロバストな比例関係にあり、全会一致と呼ばれる性質を満たす。つまり、各エージェントが最も好むケーキの1/ nの長さが他のエージェントと互いに素である場合、各エージェントは最も好むケーキの1/ nの長さを得る。これは、正確な分割に基づくメカニズムでは満たされない、弱い効率性である。エージェントが2人だけの場合、このアルゴリズムは多項式時間かつロバストな羨望フリーである。^[4]

決定論的メカニズム：区分定数評価

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

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

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

• 比例およびパレート最適;
• ロバスト比例かつ無駄がない (「無駄がない」とは、欲しくないエージェントにはピースが割り当てられないことを意味します。パレート最適性よりも弱いです)。

メノンとラーソンはε-真実性の概念を導入した。これは、いかなるエージェントも誤報告によってεの割合以上の利益を得られないことを意味する。ここでεはエージェントの評価とは無関係な正の定数である。彼らは、いかなる決定論的メカニズムも以下のいずれかの性質を満たさないことを証明した。^[6]

• ε -真実、近似的に比例し、無駄がない（近似定数が最大1/ nの場合）。
• 真実であり、近似的に比例し、連結されています（近似定数は最大で 1/ n）。

彼らはEven-Pazプロトコルに小さな修正を加え、nが偶数の ときはε =1-3/(2n )、nが奇数のときはε =1-3/(2n ) +1/ n2で ε真であることを証明^した。

ベイ、チェン、フージャン、タオ、ウーは、直接啓示モデルにおいてさえ、以下のいずれかの追加特性を満たす決定論的、真実かつ嫉妬のないメカニズムは存在しないことを証明している。^[7]

• 接続されたピース。
• 無駄がない;
• 位置を考慮せず - ケーキの一部の割り当ては、ケーキ上の相対的な位置ではなく、エージェントのその部分の評価のみに基づきます。

これらの不可能性の結果は、自由な処分の有無にかかわらず当てはまることに注意してください。

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

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

タオは、ベイ、チェン、フージャン、タオ、ウーによる以前の不可能性の結果を改良し、直接啓示モデルにおいてさえ、また以下のすべてが成り立つ場合であっても、決定論的、真実かつ比例的なメカニズムは存在しないことを示している。^[8]

• エージェントは 2 つだけです。
• エージェントは飢えています: 各エージェントの評価は正です (つまり、0 にはなれません)。
• このメカニズムでは、ケーキの一部を割り当てずに残しておくことができます。

この不可能性の結果が 3 つ以上のエージェントにまで及ぶかどうかは不明です。

肯定的な側面として、タオは「比例的リスク回避的誠実性」（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つのメカニズム、すなわち制約付きケーキ食いアルゴリズムと市場均衡アルゴリズムを提示した。しかし、これらの拡張はいずれも、評価が区分均一でない場合、もはや真実ではない。

マヤとニサンは、 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は、 CLPPと同じ特性（真実、決定論的、比例的、嫉妬なし、パレート最適、多項式時間で実行）を持ちながら、ケーキ全体が割り当てられることを保証する、区分的に均一な評価を持つ2つのエージェントのためのメカニズムを提示している：^[13]

1. アリスの[0, x ]での希望の長さがボブの[ x ,1]での希望の長さと等しくなるように、[0,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 メカニズムと同じ報酬を生み出します。

真実のメカニズムと不可能性の結果をまとめる

名前	タイプ	決定論的？	#エージェント( n )	評価[15]	家事？[16]	実行時間	全部？[17]	PO? [18]	EF? [19]	匿名？[20]	コネ？[21]	正位？[22]	無駄がない？[23]
正確な除算[1] [2]	直接	いいえ	多くの	一般的な	はい	無制限[24]	はい	いいえ	はい	はい	いいえ	?	?
超比例[1]	直接	いいえ	多くの	一般的な	はい	無制限	はい	いいえ	いいえ	はい	いいえ	?	?
離散的厳密除算[3]	クエリ	いいえ	多くの	一般的な	はい	${\displaystyle O(n^{2}/\epsilon )}$	はい	いいえ	${\displaystyle \epsilon }$ -EF	はい	いいえ	?	?
制約された連続独裁政権[4]	直接	いいえ	多くの	PWC	?	?	いいえ	全会一致	プロップ。	?	いいえ	?	?
CLPP [2]	直接	はい	多くの	PWU	いいえ	多項式	いいえ	はい	はい	はい	いいえ	?	はい
BHS 1、2	直接	はい	2	PWU	はい	多項式	はい	はい	はい	いいえ	いいえ	いいえ	はい
BHS 3、4	直接	はい	多くの	PWU1	はい	多項式	はい	はい	はい（ケーキの場合）	?	?	?	はい
拡張[12]	直接	はい	多くの	PWU1+注文	?	多項式	?	?	はい	?	はい	?	?
拡張+のロック解除	直接	はい	多くの	PWU1	?	多項式	?	?	はい	?	2 n -2 カット	?	?
不可能な組み合わせ:
[BM] [3]	クエリ	はい	2歳以上	どれでも
[BHS] [13]	直接	はい	2歳以上	PWU			はい		はい	はい
[BHS]	直接	はい	2歳以上	PWU			はい		はい		はい
[BHS]	直接	はい	2歳以上	PWU			はい		はい			はい
[T] [8]	直接	はい	2歳以上	PWC					はい（提案の場合でも）
[BCHTW] [7]	直接	はい	2歳以上	PWC			はい		はい		はい
[BCHTW]	直接	はい	2歳以上	PWC			はい		はい			はい
[BCHTW]	直接	はい	2歳以上	PWC			はい		はい				はい
[BCHTW]	一連	はい	2歳以上	PWC			はい		はい

参照

• 戦略的フェア分割
• 真実の資源配分

参考文献

1. Mossel, Elchanan; Tamuz, Omer (2010). 「真実かつ公正な分割」. Kontogiannis, Spyros C.; Koutsoupias, Elias; Spirakis, Paul G. (編).アルゴリズムゲーム理論 – 第3回国際シンポジウム, SAGT 2010, アテネ, ギリシャ, 2010年10月18日～20日. Proceedings . Lecture Notes in Computer Science. Vol. 6386. Springer. pp.  288– 299. arXiv : 1003.5480 . Bibcode :2010LNCS.6386..288M. doi :10.1007/978-3-642-16170-4_25. ISBN 9783642161704. S2CID  11732339。
2. Chen, Yiling ; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013-01-01). 「真実、正義、そしてケーキカット」（PDF） . Games and Economic Behavior . 77 (1): 284– 297. doi :10.1016/j.geb.2012.10.009. ISSN  0899-8256. S2CID  2096977.
3. Brânzei, Simina; Miltersen, Peter Bro (2015-06-22). 「ケーキカットにおける独裁定理」第24回国際人工知能合同会議.
4. Aziz, Haris; Ye, Chun (2014). 「区分定数および区分一様評価のためのケーキカットアルゴリズム」 Liu, Tie-Yan, Qi, Qi, Ye, Yinyu (編). Web and Internet Economics – 10th International Conference, WINE 2014, Beijing, China, December 14–17, 2014. Proceedings . Lecture Notes in Computer Science. Vol. 8877. Springer. pp.  1– 14. arXiv : 1307.2908 . doi :10.1007/978-3-319-13129-0_1. ISBN 978-3-319-13128-3。
5. 黒川, デイビッド; ライ, ジョン・K.; プロカッチャ, アリエル・D. (2013-06-30). 「パーティーが終わる前にケーキを切る方法」.第27回AAAI人工知能会議. 27 : 555–561 . doi : 10.1609/aaai.v27i1.8629 . S2CID  12638556.
6. Menon, Vijay; Larson, Kate (2017-05-17). 「決定論的、戦略証明可能、そして公平なケーキカット」arXiv : 1705.06306 [cs.GT].
7. Bei, Xiaohui; Chen, Ning; Huzhang, Guangda; Tao, Biaoshuai; Wu, Jiajun (2017). 「ケーキカット：嫉妬と真実」第26回国際人工知能合同会議議事録. IJCAI'17. AAAI Press: 3625– 3631. ISBN 9780999241103。
8. Tao, Biaoshuai (2022-07-13). 「真実かつ公正なケーキカットメカニズムの存在について」.第23回ACM経済・計算会議論文集. pp.  404– 434. arXiv : 2104.07387 . doi :10.1145/3490486.3538321. ISBN 9781450391504. S2CID  233241229。
9. Bu, Xiaolin; Song, Jiaxin; Tao, Biaoshuai (2023-06-01). 「真実かつ公正なケーキカットメカニズムの存在について」.人工知能. 319 103904. arXiv : 2104.07387 . doi :10.1016/j.artint.2023.103904. ISSN  0004-3702.
10. Maya, Avishay; Nisan, Noam (2012). 「インセンティブ両立型2人用ケーキカット」 Goldberg, Paul W. (編).インターネットとネットワーク経済学 – 第8回国際ワークショップ, WINE 2012, リバプール, イギリス, 2012年12月10～12日. Proceedings . Lecture Notes in Computer Science. Vol. 7695. Springer. pp.  170– 183. arXiv : 1210.0155 . doi :10.1007/978-3-642-35311−6_13 (2025年9月7日現在非アクティブ). ISBN 9783642353116. S2CID  1927798。
11. Li, Minming; Zhang, Jialin; Zhang, Qiang (2015-06-22). 「外部性を考慮した真実のケーキカットメカニズム：他人を気にさせすぎないように！」第24回国際人工知能合同会議.
12. アリジャニ、レザ;ファルハディ、マジッド。ゴドシ、モハマド。セディギン、マスード。タジク語、アフマド S. (2017-02-10)。 「最小限のカット数で羨望のないメカニズム」。第 31 回 AAAI 人工知能会議。３１．土井：10.1609/aaai.v31i1.10584。S2CID  789550。
13. Bei, Xiaohui; Huzhang, Guangda; Suksompong, Warut (2020). 「自由処分のない真実かつ公正な分割」. Social Choice and Welfare . 55 (3): 523– 545. arXiv : 1804.06923 . doi :10.1007/s00355-020-01256-0. PMC 7497335. PMID 33005068  . 
14. Ianovski, Egor (2012-03-01). 「ケーキ切断機構」. arXiv : 1203.0100 [cs.GT].
15. PWC = 区分的に一定、PWU = 区分的に均一、PWU1 = 単一の希望間隔を持つ区分的に均一。
16. アルゴリズムが負の効用（雑用）を持つケーキも処理できるかどうか。
17. ケーキ全体を分割して廃棄しないかどうか。
18. 結果として得られる割り当てが常にパレート最適であるかどうか。
19. 結果として得られる割り当てが常に羨望の影響を受けないかどうか。
20. メカニズムが匿名であるかどうか。
21. 結果のピースが常に接続されているかどうか。
22. 機構が位置を意識するかどうか。
23. アルゴリズムが無駄のないことを保証するかどうか。
24. 実行時間は、正確な割り算の計算によって支配されます。一般的には無制限ですが、特殊な場合には多項式になることがあります。