日本ソフトウェア科学会第 32 回大会 (2015 年度) 講演論文集

二値効用下での戦略的操作不可能なケーキ分割メカニ
ズムの提案
伊原 尚正

鶴田 俊佑

東藤 大樹

櫻井 祐子

横尾 真

ケーキ分割問題とは，区間によって参加者の選好が異なる連続的な財を，公平に割り当てる方法を考える問題である．従来の研究では，参加者の効用関数に加法性を仮定していた．しかし，現実においては，参加者は加法的でない選好を持つことがある．そこで，本論文では非加法的な効用である二値効用のもとでケーキ分割問題を考える．初めに，二値効用下での非羨望性とパレート効率性の両立不可能性を示す．次に，戦略的操作不可能性とパレート効率性を満たす，2 つのメカニズムを提案する．また，パレート効率性を満たす割当を発見する問題は NP 困難であることを示す．そこで，参加者数に対して多項式時間で実行可能な近似アルゴリズムを提案する．また，戦略的操作不可能性と非羨望性を満たすメカニズムを提案する．最後に，提案メカニズムの性能を計算機実験によって評価する．

ケーキ分割問題において，非羨望性は望ましい性質

1 序論の中で，最も研究されている性質の 1 つである．あるメカニズムデザインはミクロ経済学とゲーム理論の

ケーキの割当が非羨望性を満たすならば，その割当の一分野であり，複数人の参加者間での意思決定のルー

もとでどの参加者も他の参加者の割当を羨ましく思

ルを議論する．これらのルールは，社会的な効率性

わない．例えば，参加者が 2 人しか存在しないとき，や，各参加者の効用に関する性質など，いくつかの性

cut-and-choose によって出力される割当は常に非羨質を満たしていることが望ましい．エージェント科学

望性を満たす．

の発展に伴い，メカニズムデザインの研究は人口知能

近年，人工知能やマルチエージェントシステムの研とマルチエージェントシステムの研究分野で盛んに行究者は，メカニズムデザインの一分野としてケーキ分

われている．

割問題を研究し，戦略的操作不可能なケーキ分割メカ

ケーキ分割問題は公平分割問題の一分野であり，通ニズムを研究している [3] [5] [8] [9]．ケーキ分割メカニ

常 [0, 1] の連続的な区間で表現される財を参加者にズムの中には，参加者が欲しがっている部分を割り当公平に分割する方法を考える問題である [6]．具体的てるため，参加者に自身の効用関数を尋ねるものがには，ミーティングルームの使用権，計算機資源のある．戦略的操作不可能なケーキ分割メカニズムは，

利用時間の分配，通信域の使用権などの分割財の分参加者がメカニズムに効用関数を申告するとき，真の配があげられる．cut-and-choose や moving-knife な効用関数を答えることが弱支配戦略となる．

ど，様々なケーキ分割アルゴリズムが提案されている [2] [4]．

様々な戦略的操作不可能性を満たすケーキ分割メ
カニズムが提案されているが，従来の研究では参加者の効用関数が加法的であることを仮定しており，参∗ Strategy-proof Cake Cutting Mechanisms for Binary

Utility
This is an unrefereed paper. Copyrights belong to
the Author(s).
Takamasa Ihara, Shunsuke Tsuruta, Taiki Todo, Yuko
Sakurai, Makoto Yokoo, 九州大学システム情報科学
府, ISEE, Kyushu University.

加者の効用関数が加法的でない場合については考慮されていない．そこで本論文では，ある区間の中からある長さ以上の連続的な割当を得られれば効用は1，得られなければ効用は 0 という二値効用を仮定したもとでのケーキ分割メカニズムについて考察する．

この二値効用は単純で現実に即しており，かつ非加法戦略的操作不可能性的である．二値効用の例として，以下の例を挙げる．
ミーティング室が必要より短い時間しか割り当てられ

非羨望性
パレート効率性ていないならば，ミーティングを開催することができ
RSD

SSD

EF-SSDF

ない．この例では，各参加者が必要としている量より短い区間しか割り当てられなかった場合，その参加者

RSDF

SSDF

の効用は 0 となる．
本論文では初めに，二値効用のもとではパレート

多項式時間で実行可能

効率性と非羨望性を同時に満たすケーキ分割メカニズムが存在しないことを示す．つまり，メカニズム

図1を考えるうえで，パレート効率性と非羨望性の少な
くとも一方を犠牲にしなければならない．そこで，

財 X の長さを len(X) =

研究成果

∑

I∈X len(I) で表す．

初めに非羨望性を諦め逐次的独裁メカニズム (Serial

また，各参加者の効用関数は二値効用とする. 二値

Dictatorship mechanism, SD) をベースとした，整列

効用において，参加者の効用がとりうる値は 0 か 1

逐次的独裁メカニズム (Sorted SD, SSD) と無作為逐である．

次的独裁メカニズム (Randomized SD, RSD) の 2 つ

定義 1 (二値効用関数) 参加者 i ∈ N は区間 ri =のメカニズムを提案する．これらのメカニズムは戦略[si , ei ] ⊆ [0, 1] において，長さ di ∈ (0, ei − si ] の財的操作不可能性とパレート効率性を満たす．次に，パを必要とする．ri を参加者 i の評価区間と呼ぶ.

レート効率的な割当を見つける問題は NP 困難である

区間 Xi が参加者 i に割り当てられているとき，そことを示す．そこで，参加者数に対する多項式時間での参加者の効用は以下のように定義される．
 1 ∃I s.t. I ⊆ X and len(I ∩ r ) ≥ d ,iii
Ui (Xi ) = 0 otherwise.

パレート効率的な割当に近い割当を出力する近似アルゴリズムを提案する．RSD を近似したアルゴリズム
を RSDF(RSD by Fixing the order of the allocation

pieces)，SSD を近似したアルゴリズムを SSDF(SSD
by fixing the order of the allocation pieces) と呼ぶ．
また，SSDF をもとに，パレート効率性を犠牲にして，非羨望性を満たすようにしたメカニズムを提案する．このメカニズムを EF-SSDF(Envy-Free SSDF)と呼ぶ．今回の研究成果は図 1 のように表される．

RSDF,SSDF,EF-SSDF は割当を参加者数に対する多項式時間で決定しているので，計算量的に効率のよいメカニズムといえる．最後に，提案メカニズムを計算機実験によって比較する．

この効用関数によって，ある参加者がミーティング
室を午後に 2 時間連続で使いたいような効用を表現できる．
定義より，任意の二値効用関数 Ui は非原子性を満たす．また，効用関数は正規化されていると仮定する．
非原子性: ∀x ∈ [0, 1] に対し，Ui ([x, x]) = 0,
正規性: Ui ([0, 1]) = 1.
非原子性より，参加者の効用を考えるうえでは，開区
間，半開区間は閉区間と同一に扱える．
すべての二値効用関数の集合を U とし，これは全参加者に共通とする．U = (Ui )i∈N を n 人の参加者の効用関数の組とし，U−i = (Uj )j∈N \{i} を n 人の2 準備

参加者から，参加者 i を除いた参加者の効用関数の組

2. 1 モデルとする．(Ui , U−i ) は，参加者 i の効用関数を Ui ，他

N = {1, 2, . . . , n} を参加者の集合とし，n = |N |を参加者数とする．分割する財を区間 [0, 1] で表現する．閉区間 I = [x, y] ⊆ [0, 1] の長さを len(I) = y − xで表す．また，I ∈ X を連続でない区間とするとき，の参加者の効用関数の組を U−i としたときの参加者
全員の効用関数の組である．

n 人の参加者に対するケーキの可能な割当を A，Ai を参加者 i に対する割当とする．任意の参加者

の 組 i, j(̸= i) ∈ N に 対 し Ai ∩ Aj = ∅ で あ り，∪i∈N Ai ⊆ [0, 1] を満たす (Ai )i∈N の集合を A とし，質である．

可能な割当と呼ぶ．AN を n 人の参加者に対する可戦略的操作不可能性を満たすとき，任意の i ∈ N ，任

能な割当の組とする．

意の U−i ∈ U n−1 ，任意の Ui ∈ U ，任意の Ui′ ∈ U

メカニズム f は f N : U n → AN で表される関数の集合とする．簡単のため，fN

定義 4 (戦略的操作不可能性 (SP)) メカニズム f がに対して，

Ui (fi ((Ui , U−i ))) ≥ Ui (fi ((Ui′ , U−i )))を f と表現する．与えられた効用関数の組 U に対して，メカニズム f によが成立する，

る出力を f (U ) と表す．また，出力 f (U ) の中で，参3 不可能性定理

加者 i に対する割当を fi (U ) と表す．

本章では，戦略的操作不可能性を考えなくても，二2. 2 ケーキ分割メカニズムに望ましい性質

値効用下ではパレート効率性と非羨望性を同時に満

ケーキ分割メカニズムに望ましい性質を定義する．

たすケーキ分割メカニズムが存在しないことを示す．

初めに，非羨望性 (Envy-Freeness, EF) を定義する．

定理 1

参加者 i が自身の割当を他の参加者 j の割当と交換し各参加者の効用関数が二値効用であるとき，パレーて効用が増加するならば，参加者 i は参加者 j に羨望

ト効率性と非羨望性を両立するケーキ分割メカニズを持つという．非羨望性は，公平性についての代表的

ムは存在しない．

な性質であり，全参加者は，他のどの参加者にも羨望

証明 1 背理法を用いて証明を行う．二値効用下でパを持たないことを保証する性質である．

レート効率性と非羨望性を同時に満たすメカニズム f

定義 2 (非羨望性 (EF)) ケーキ分割メカニズム fが存在すると仮定する．2 人の参加者 N = {1, 2} がが 非 羨 望 性 を 満 た す と き ，任 意 の U ∈ U ，任

存在し，任意の参加者 i ∈ N が ri = [0, 1], di = 1 で意 の Ui ∈ U と 任 意 の i, j (̸= i) ∈ N に 対 し ，

ある同じ効用関数を持っていると仮定する． 以下のUi (Ai ) ≥ Ui (Aj ) が成り立つ．

2 つの場合を考える．

n次に，パレート効率性 (Pareto Eﬃciency, PE) を

Case 1: 参加者 1 にケーキ全体を割り当て，参加者 2

定義する．この性質はメカニズムによる割当の効率性には何も割り当てない場合を考える．明らかに，参加を保証する性質であり，メカニズムデザインの文脈で者 2 の効用は 0 である．しかし，参加者 2 は，参加

広く議論される．パレート効率的なメカニズムによる者 1 と自身の割り当てを交換することで，自身の利出力に対して，その出力よりも少なくとも一人は効用

得を 0 から 1 にすることができる，よって，参加者 2が増加し，全員が効用が減少しない割当は存在しないは参加者 1 に羨望を持つ．一般性を失わずに，参加者ことを保証する性質である．

2 にケーキ全体を割り当てた場合，参加者 1 は参加者

定義 3 (パレート効率性 (PE)) N と U ∈ U

n

に対

′

2 に羨望を持つことが示せる．よって，非羨望性は満して，ある割当 A ∈ AN が別の割当 A ∈ AN をたされない．

パレート支配するとは，Ui (A′i ) ≥ Ui (Ai ) が任意のCase 2: Case1 で検討した割当以外の任意の割当をi ∈ N に対して成立し，ある j ∈ N に対して厳密に行う場合を考える．この時，参加者 1 と参加者 2 の効

大小関係が成立する場合である．ケーキ分割メカニズ

用はどちらも 0 である．もしメカニズムデザイナがム f がパレート効率性を満たすとき，任意の U ∈ Un

ケーキ全部を片方の参加者に割り当てたならば，もうに対して，A をパレート支配する割当 A ∈ AN は存1 人の参加者の効用を 0 から下げることなく，割り当在しない．

てられた参加者の効用を 0 から 1 に増加させること′最後に，戦略的操作不可能性 (Strategy Proofness,

SP) を定義する．これは真の効用関数をメカニズムに申告することが弱支配戦略であることを保証する性ができる．よって，パレート効率性は満たされない．
以上より二値効用のもとで，パレート効率性と非羨望性を満たすメカニズムは存在しない．

2

ない．

4 戦略的操作不可能性とパレート効率性を満
たすケーキ分割メカニズム

次に，SSD が戦略的操作不可能性を満たすことを証明する．先に，参加者が評価区間の長さを操作して前章で，パレート効率性と非羨望性の両立不可能

も効用を増加させることはできないことを示す．二値について示した．そこで，初めに非羨望性を諦め，パ効用の定義より，d′i < di である d′i を得ても効用は 0

レート効率性を満たす戦略的操作不可能なケーキ分割であるので，このような虚偽申告をする誘因は存在しメカニズムを提案する．我々が提案するメカニズムはない．更に，参加者が d′i > di となる d′i を申告した

逐次的独裁メカニズムという，戦略的操作不可能性と場合，独裁者となる順番は後になる．これは，d′i を

パレート効率性を満たすメカニズムに基づく [1]．逐申告することで，真の申告をした場合に得られる可次的独裁メカニズム（SD）では，参加者に順序がつ能性があった割当を得るチャンスを失うことにつながけられ，まず可能な全ての割当の組から，1 番目に順るので，このような d′i を申告する誘因はない．次に，序付けられた参加者にとって最良の割当の組を選択す

参加者が評価区間 ri を操作しても効用を増加させる

る．次に，1 番目の参加者が選択した割当の組から，2ことはできないことを示す．メカニズムデザイナは，番目の参加者にとって最良の割当の組が選択される．

割り当てられる区間は変わったとしても，既に決定

これを繰り返し，割当を決定するメカニズムである．

された参加者の評価値を保証する範囲で，参加者 i のまず，整列逐次的独裁メカニズム (Sorted SD メカ

効用を最大化するように割当を決定する．つまり，もニズム, SSD) を提案する．

しも参加者 i が独裁者となった時点で，まだ効用が 1メカニズム 1 (SSD)となる割当が残っているなら，参加者 i はその割当を

1. 各参加者に，評価区間 [si , ei ] と必要な長さ diを申告させる．

受け取れることが保証される．よって，参加者が虚偽の申告を行っても，効用が 1 となるような割当を受

2. 参加者を di の昇順で並べ替える．同じ長さのけ取ることができない．よって，各参加者にとって，

di が必要な参加者が複数人存在した場合，その参評価区間 [si , ei ] と必要な長さ di を正直に申告する

加者間での順序は等確率でランダムに決定する．

ことが最良の戦略となる．

2

3. 最初の参加者から n 番目の参加者まで，順々に独裁者に指名する．指名された k 人目の参加者

以下で，SSD の動作例を示す．

は，既に指名された k − 1 人の効用を変えない制

例 1 6 人の参加者が存在し，選好は以下のとおりと約のもとで，その参加者によって最良の割当を

する．

得る．

参加者 1: [s1 , e1 ] = [0.25, 0.7], d1 = 0.4

定理 2 SSD は戦略的操作不可能性とパレート効率性

参加者 2: [s2 , e2 ] = [0.2, 0.4], d2 = 0.15

を満たす．

参加者 3: [s3 , e3 ] = [0, 1], d3 = 0.2

証明 2 初めに，SSD がパレート効率性を満たすこと

参加者 4: [s4 , e4 ] = [0.4, 0.85], d4 = 0.3を証明する．参加者 i が敗者となったとき，つまり，参加者 5: [s5 , e5 ] = [0.25, 0.45], d5 = 0.15

その参加者が割当を受け取れなかったとき，その参加

参加者 6: [s6 , e6 ] = [0.5, 1], d6 = 0.25

者の効用は 0 である．このとき，参加者 i が独裁者と初めに，参加者を di の昇順にソートする．この例

なった時点で，評価区間の中に必要な長さは残っていでは，参加者の順序は 2, 5, 3, 6, 4, 1 と決定される．

ない．もし，参加者 i の効用を 0 から 1 とするとき，参加者 2: [0.2, 0.35] を仮に割り当てる．

参加者 i の評価区間を割り当てられている勝者は割

参加者 5: 参加者 2 の効用が 1 となることを保証

当を失い，効用は 1 から 0 に減少する．結果として，した上では，参加者 5 の効用が 1 となる割当をどの参加者の効用も減少することなく，少なくとも 1

行うことができない．よって，参加者 5 には割人の参加者の効用を増加させるような割当は存在し当は行わない．

参加者 3: 参加者 2 の効用が 1 となることを保証

で可能な限りパレート効率的な割当に近い割当を求した上で，参加者 3 の効用が最大となる割り当て

める近似アルゴリズムの提案を行う．提案する割当アを考える．[0.2, 0.35] を参加者 2 に，[0.35, 0.55]

ルゴリズムは今までの独裁者の順番で決定された割を参加者 3 に割り当てる．

当の順序を変更しない．つまり，k 番目の参加者に割

参加者 6: 参加者 2,3 の効用が 1 となることを保証

当可能か判定する際，k − 1 人目までに割り当てられした上で，参加者 6 の効用が最大となる割り当て

た位置は変更してもよいが，k − 1 人までの参加者にを考える．[0.2, 0.35] を参加者 2 に，[0.35, 0.55]

割り当てた区間の位置関係を変化させない．

を参加者 3 に，[0.55, 0.8] を参加者 6 に割り当
てる．

このアルゴリズムを SSD に適用した近似アルゴリ
ズムを SSDF と呼ぶ．SSDF の動作は以下のように参加者 4: 参加者 2,3,6 の効用が 1 となることを保証した上で，参加者 4 の効用が最大となる割り当てを考える．参加者 2 に [0.2, 0.35] を，参加者 3 に [0, 0.2] を，参加者 6 に [0.7, 0.95] を，参加者 4 に [0.4, 0.7] を割り当てる．

なる．
メカニズム 2 (SSDF)

1. 各参加者に，評価区間 [si , ei ] と必要な長さ diを尋ねる．

2. 参加者を di の昇順で並べ替える．同じ長さの参加者 1: 参加者 2,3,4,6 の効用が 1 となること

di が必要な参加者が複数人存在した場合，その参を保証した上では，参加者 1 の効用が 1 となる

加者間での順序は等確率でランダムに決定する．

割当を行うことができない．よって，参加者 1 に

3. 最初の参加者から n 番目の参加者まで，順々には，割り当てを行わない．

独裁者に指名する．指名された k 人目の参加者
は，既に指名された k − 1 人の効用と，[0, 1] 区

結果として，勝者は参加者 2, 3, 4, 6 となる．

SSD では長さ di の昇順に参加者の順番を決定した

間の 0 地点から 1 地点に向けて，どの順序で割が，ランダムに参加者の順序を決定しても，SSD とり当てたかを変えない制約のもとで，その参加者

同様に戦略的操作不可能性とパレート効率性を同時によって最良の割当を得る．

に満たすことを保証する．このメカニズムを無作為

このメカニズムはパレート効率的ではないが，SSD

選択型独裁メカニズム (Randomized SD メカニズム,の戦略的操作不可能性を満たすのと同じ理由により，RSD) と呼ぶ．

戦略的操作不可能性を満たすといえる．また，RSD

次に，SSD，RSD の計算量について議論する．

にこのアルゴリズムを適用した近似アルゴリズムを

定理 3 SSD,RSD がパレート効率的な割当を発見する問題は NP 困難である．

RSDF と呼ぶ．
次に，この近似アルゴリズムの実行時間について議証明 3 k 人目の参加者が割当可能か判定する問題は，論する．

k − 1 人目までで勝者となった参加者と k 人目の参加

定理 4 提 案 し た 近 似 ア ル ゴ リ ズ ム の 実 行 時 間 は者の全員に割当可能か判定する問題と言い換えるこO(n3 ) である．

とができる．この割当問題は，最早開始時間と締切時

証明 4 1 人目から n 人目の参加者まで，割り当て可間が存在するスケジューリング問題と考えることがで能か判定する．前までに決定した参加者への割当の位

き，このスケジューリング問題は NP 困難であること

置関係を入れ替えないので，k 人目が割り当て可能かが示されている [7]．よって，パレート効率的な割当判定する場合，判定中の独裁者ををどこに挿入する

2

か，高々n 通り判定を行う．1 つの順序で割当可能かを求める問題は NP 困難である．

を判定するのにかかる時間は O(n) である．よって，

5 近似アルゴリズム

近似アルゴリズムに実行時間は O(n3 ) である．

2

前章で述べたように，パレート効率的な割当を決定する問題は NP 困難である．そこで，現実的な時間内

6 戦略的操作不可能性と非羨望性を満たす

ケーキ分割メカニズム
本章では SSDF を基にして，パレート効率性を諦ていないかのどちらかであるので，どの敗者も勝者に羨望を持つことはない．

2

めるかわりに非羨望性を満たすケーキ分割メカニズ

例 2 この例では，例 1 と同じ問題設定での EF-SSDF

ムを提案する．SSDF では，参加者は必要な長さ diの動作例を示す．

の昇順で順序をつける．しかし，同じ長さが必要な参EF-SSDF で は ，参 加 者 2 と 5 の 必 要 な 長 さ は加者の組が存在した場合，それらの参加者は等確率で

d2 = d5 = 0.15 であり，6 人の参加者の中で最も短い

順序付けられる．つまり，SSDF で割当を行うと，結ので，最初のグループ g1 に所属する．この 2 人につ果は参加者の順序がどうなるかで決まり，敗者は勝者

いて，以下の 2 種類の順序を考える:2 → 5 と 5 → 2.

に羨望を持ちうる．このような不満を避けるために，

参加者 2 が先に順序つけられたとき，参加者 2 だけ必要な長さ di でグループ分けする．同じ長さが必要に割り当てができるので，参加者 2 が勝者の候補にな参加者は，同じグループに属する．

なる．これに対して，参加者 5 が先に順序つけられメカニズム 3 (Envy-Free SSDF, EF-SSDF)

たとき，参加者 5 だけに割り当てができるので，参

1. 各参加者に評価区間 [si , ei ] と必要な長さ di を尋ねる．

2. 他の参加者の評価区間と競合せずに，効用が 1となる区間を受け取れる参加者にその区間を割り当てる．

3. 参加者を，必要な長さ di が同じ参加者ごとにグループ分けする．

4. グループを di の昇順で順序付けする． k 番目のグループを gk とする．

5. 最初のグループ，つまり k = 1 から，gk に含まれる全参加者の全順序で割り当てを試み，それ加者 5 が勝者の候補になる．2 パターンで違う参加者の組が勝者の候補となったので，メカニズムは停止す
る．結果として，誰にも割り当ては行われない．

7 計算機実験
提案した近似メカニズムが効率よく財を参加者に割り当てることを示すため，提案メカニズムによる割り当て人数を計算機実験で評価する．本実験は，Intel(R) Core(TM) i7-3960X CPU processors with
32.0GB RAM および，Windows 7 Professional にて行った．

ぞれの順序での勝者候補を求める．もしも全て必要な長さ di が何種類あるかを div で表す．例の順序で，同じ参加者集合が勝者となるならば，

えば，div = 1 であるならば，全参加者の必要な長次のグループ gk+1 も同様に判定を行うそうでなさ di は単一である．di は [0.10−0.01(div −1), 0.10+

ければ，gk の誰にも割り当てを行わず，メカニ

0.01(div − 1)] から一様ランダムに選ばれる．si と ei

ズムを終了する．それぞれの順番で割り当てを決は，それぞれ [0, 1 − di ]，[si + di , 1] から一様ランダ

定する際，提案した近似アルゴリズムを用いる．

ムに選ばれる．参加者人数は 15 人とし，div は 3 か定理 5 EF-SSDF は戦略的操作不可能性と非羨望性を満たす．

ら 9 の間とする．
図 2 は各メカニズムでの勝者数の平均値を示して証明 5 SSD と同様の議論により，EF-SSDF が戦略いる．参加者数 n = 15 のとき，最適な割り当てを的操作不可能性を満たしていることは示すことがで行った場合の割り当て人数（Optimal）と，SSD によきる．以下では，EF-SSDF が非羨望性を満たすこと

る割り当て人数はほぼ同じということができる．divを示す．EF-SSDF では，グループ間でどの順序で割を変化させても，RSD,SSD,RSDF,SSDF での割り当

り当てを行っても，結果が同じ場合のみ実際に割り当て可能人数はほとんど変わらないが，EF-SSDF ではてを行う．よって，グループ内の参加者間で互いに羨

div を増加させると割り当て可能人数も大きく増加す

望を持つことは無い．さらに，勝者の得た区間は敗者

る．これは，div が増加し，同じ長さの di が必要なの必要な長さより短いか，敗者の必要な区間と競合し参加者が減ったことで，メカニズムが途中で終了する
可能性が減ったことが原因だと考えられる．また，最Num. of winners

メカニズムについて議論することもあげられる [10]．
10

謝辞 本研究は科研費（科研費番号 24220003,15H027

851,15K12101）の助成を受けました．ここに深く感謝します．

6
Optimal
RSD
SSD
RSDF
SSDF
EF-SDFA

42

参 考 文 献

0
3

4

5

6

7

8

9

div

図2

平均勝者数

初に di の長さでソートした場合，ソートしなかった
場合に比べて性能が向上していることがわかる．

8 結論
本論文では，二値効用下における戦略的操作不可
能性を満たすケーキ分割メカニズムについて議論した．初めに，パレート効率性と非羨望性の両立不可能性を示した．そこで，まず非羨望性を諦め，逐次的独裁メカニズムに基づいた戦略的操作不可能とパレート効率性を満たすメカニズムを提案した．次に，パレート効率的な割当に近い割当を効率的に発見する近似アルゴリズムを提案した．また，パレート効率性を諦め，非羨望性を満たすメカニズムを提案した．
今後の課題としては，より複雑な効用関数のもとで研究を行うことが挙げられる．具体的には，評価区間の中である長さの連続的な割当を得られれば嬉しいが，さらに長い割当を得られると更に嬉しいといった効用があげられる．また，戦略的操作不可能性より強い性質である，架空名義操作不可能性を満たすケーキ分割[ 1 ] Abdulkadiroğlu, A., Sönmez, T.: Random serial
dictatorship and the core from random endowments
in house allocation problems. Econometrica 66(3),689–701 (1998)[ 2 ] Austin, A.: Sharing a cake. The Mathematical
Gazette pp. 212–215 (1982)[ 3 ] Aziz, H., Ye, C.: New cake cutting algorithms:
a random assignment approach to cake cutting.
The Computing Research Repository abs/1307.2908(2013)[ 4 ] Brams, S.J., Taylor, A.D.: An envy-free cakedivision protocol. American Mathematical Monthly
pp. 9–18 (1995)[ 5 ] Chen, Y., Lai, J.K., Parkes, D.C., Procaccia,
A.D.: Truth, justice, and cake cutting. Games andEconomic Behavior 77(1), 284–297 (2013)[ 6 ] Gamow, G., Stern, M.: Puzzle-math. Macmillan(1958)[ 7 ] Garey, M.R., Johnson, D.S.: Two-processor
scheduling with start-times and deadlines. SIAM
Journal on Computing 6(3), 416–426 (1977)[ 8 ] Maya, A., Nisan, N.: Incentive compatible twoplayer cake cutting. In: Proceedings of the 8th International Conference on Internet and Network Economics. pp. 170–183. WINE’12 (2012)[ 9 ] Mossel, E., Tamuz, O.: Truthful fair division. In:
Algorithmic Game Theory, pp. 288–299. Springer(2010)[10] Tsuruta, S., Oka, M., Todo, T., Sakurai, Y.,
Yokoo, M.: Fairness and false-name manipulations
in randomized cake cutting. In: Proceedings ofthe 2015 International Conference on Autonomous
Agents and Multiagent Systems. pp. 909–917. International Foundation for Autonomous Agents andMultiagent Systems (2015)