測＝…醐i朗‖川＝闘紺紬………剛………l…き≡ぎ＝‖…㈱裾制…刷帥瀾‖…晰珊漸……i緋＝酬酬Il酬帖制‖日脚隅酢…川‖‡榊！酬川…酢淵酬＝…帖削刷……l‖瞞榊酬＝…酢蛸㈲…川＝lii…⊆一描！e…川…

離散最適化とその応用

公

分割と会・平割

宍戸 栄徳，普通智州㈱附‖……川l…測‖…l川棚…＝……………棚I酬川……l服‖ll……榔柚制＝…ll輔！榊捕‖…削輔酬‖川…酬爛酬棚㈱醐輔…＝梱…き州……＝l帖粧甜…‖…‖酢柳川＝㈱酢制服仙＝…＝…l州あると仮定する．プレイヤ【によって〝わは異なるが，

1．はじめに共通の性質として以下のものを仮定する．

世界の資源は有限である．土地，石油などをめぐっ（1）空集合の測度は0である：〝わ（郎＝0．

て，様々な紛争か裸界各地に生じている．世界の捻人（2）♂一代数の任意の要素Aに対して，椚f（A〉≧0．

口が増え続ける今日，貴重な有限の資源をいかに公平（3）加算加法的である：椚f（∪畏．AJ）＝∑畏1押わ（AJ），に配分するかは重要な課題になっている．
しノ

2者間の公平分割は簡単である．1人が分けてもう（4）全体集合の測度は1である：〝わ（C）＝1．

1人が選ぶという単純な手続きによって，両者は互い

2．2 公平分割の対象物と情報に羨望（相手の取り分と交換したいと思う気持ち）を分割の対象とする物は，財（goods）あるいは負担持たず不満のない分割ができる．公平分割で3人以上（burdens，Chores）である．前者は各プレイヤ がよの場合に無羨望解を得る手続きについて論じたのは，り多く獲得することを求め，後者についてはプレイヤ

Gamow−Stern（1958，1999）が最初ではないかと思ー全体としては謹かか引き受けなければならないか，

われる．著者の1人はその訳本を中学生のときに読ん個人としてはなるペく少なく引き受けたい物である．

で公平分割問嬉の存在を知った．当時，3人以上の場

これまでの研究の大半は財の分割に関して述べている

合の無羨望分割に対する解法は未知であった．

が，特に混乱が生じない限り「財」をgoodsとbur−

しかし，60年代に入ってから，この分野の研究は

ヽ J

ただし，メ≠烏のときAノnA象票鋳である．

densの両方の意味を含める言葉として使う．

著しい発展を遂げてきた．3人だけではなく，任意人

また，それらが分割可能（divisible）であるか分割

穀の無羨望分割法もBrams−Taylor（1995）によっ

不可能（indivisible）であるかも解に大きく影響を与て開発された．その流れの一部は菅・茨木（1999）にえる．前者の例としてはケ【キが典型的であり，後者

紹介されている．近年，理論の面だけでなく，応用のの例としては1軒の家を何人かで借りて，各プレイヤ面も注目され，かなりの成果が得られている．本解説

何に1部屋ずつ適当に割り当て，部屋代をどのようには最新の発展状況に重点をおいて公平分割問題，公平

して公平に負担するかというHousemate問題が有名

割当問題を紹介する．

である．

分割可能財に対しては，各プレイヤーの財に対する2．公平分割の基本

評価は個人情報であるので，他人は知らないとする．

2．1公平分割同塵

一方，分割不可能財では各財に対するプレイヤ【の評公平分割問題（fairdivisionproblem）の枠組みを

価を相互に知っていると仮定する．

述べておく．分割に闘わる人をプレイヤ…と呼びその集合を〃禁（1，…，扉，対象物Cの分割をタ＝（月，・‥，

分割不可能財に対しては分割という言葉は不自然なので公平割当問題（fairallocationproblem）と呼ぶ．

島）とする．ここで，C＝∪た．汽で，g≠ノのとき

2．3 公平さの概念

汽∩月戸沌である．一般にCの部分集合A⊆Cに対公平さ（fairness）の概念は多数ある．近年の研究するプレイヤーfの評価を桝f（A）と表す．〝むはC

で主に使われているのが「無羨望」（envy−free）といの部分集合からなる♂一代数上のnon−atOmic測度でう基準である．Cの分割タ＝（月，…，鳥）が無羨望でししど はるのり，ぜん だおず
香川大学経済学部〒760−8523高松市幸町2−1
2003年3月号

あるとは，任意のf，ノ∈〃に対して〝わ（書）≧椚f（ろ）が成り立つことである．ここで，汽はプレイヤ輌iの取り分である．すなわち，各プレイヤ¶は自分の．取© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（43）203

得するものは一番良いと思っており，他のプレイヤ簡

簡単に実現できる．3人の場合については，1960年前の取り分と交換したいとは思わない．

後にアメリカNorthernIllinois大学のSclfridgeとイ

無羨望より緩い基準として，任意のi∈〃に対して
mL（書）≧1／nを満たす「比例」（proportional）分割がある．他人の取り分とは無関係に，自分の取り分が1／〝以上であればよいという考えである．その他の基準について，詳しくは曽・茨木（1999）を参照されたい．
公平さの筏念に対してプレイヤーが得た物の評価をギ．）スCambridge大学のConwayがそれぞれ独立に，

次の鞋散的手続きを提案した．

ステップ1．プレイヤ憮1がケーキを 二自分の測寝で均等に］3分割する．

ステップ2．プレイヤ閻2が［自分の測度椚2で3部分の中に最大になるものが二つ以上あると思えば］

すべてのプレイヤ…で等しくする平等性（equitabi−

パスする．［最大のものが一つだけあると思えば］3

1ity），全体の利益という観点からのPareto効率性な部分の中の［最大の］1部分のサイズを［2番目の大ども考えられている．また，乃人のプレイヤーがいる

きさと同じサイズまで］修正する．もしプレイヤ簡2

とき，1人の取り分をちょうど1／乃とするのが基本的

が1部分を削Ij取ったときは，切り乾された部分をな問題であるが，Shishido−Zeng（1999）などはそれ￡ とし，別に置いておく．

らを任意の比率（entitlement）に一般化して考えてステップ3．プレイヤ竹3，2，1はこの頓で￡以外の三つの中から［自分の測度で最大である］1部分

いる．

2．4 公平分割間竜を解くを選ぶ．ただし，ステップ2においてプレイヤ椚2が公平分割問題を解くとは，公平分割基準を満たす解修正した部分がある場合，それをプレイヤ竹3が選ばの存在を数学的に証明することと，その解を実現する

なかったら，プレイヤー2はそれを取らなければなら

分割手続きを示すことである．

ない．

分割手続きは分割の手頃を示すだけでなく，各プレ

ステップ4．プレイヤ冊2がステップ2でパスした

イヤmが各段階で決められた手続きをいかに実行する

場合はここで終わる．そうでなければ，プレイヤー2，かという戦略（推奨戦略）も明示しなければならない．

3の内，修正されなかった部分をもらった者を「分割手続きはある種のル…ルであり，どのような戦略を取省」と呼び，修正された部分をもらった者を「非分割

るかはプレイヤ¶が個人情報に基づいて決定する．各者」と呼ぶ．そして，分割者は￡を［F一分の測度でプレイヤ加が推奨戦略を忠実に実行する限り，満足で均等に］3部分に分ける．

きる配分が保証される．逆に，推奨戦略を忠実に実行

ステップ5．3人のプレイヤ閻は非分割者．プレイ

しなければ，他人に不利益を与えることはないが，自ヤ蘭1，分割者の傾で￡を分割した3部分の中から

分自身は不利益を被る可能性がある．この種の戦略は［自分の測度で最大の］1部分をそれぞれ選ぶ．

ゲmム理途では，慎重戦略（prudent strategy）と呼この離散的手続きを確解するため，2段階に分けてばれている．なお，以下で紹介するアルゴリズムの小考える．1段階臼（ステップ1−3）では，幡正のためにの［］で囲まれている部分は推奨戦略を示す．

切り離された部分￡を除けば，無羨望の条件を満た

手続きには2種類のものがある．連続的手続きと離すようにケ冊キは分割されている．2段階目（ステッ

散的手続きである．連続的手続きはナイフ移動法

プ4，5）は，切り離された部分￡を処理する．1段（moving−knife procedure）とも呼ばれる．ケMキの折【‡に使われた方法をここで再び健闘することも可能

上でナイフを端から動力、していき．どのプレイヤ何もであるが．そうすると分割が無限に繰り返される可能任意の場所で「止まれ」と声をかけることができ，そ性がある．この子続きはそれを避けて，非分割者がいこでケーキを切断（したリマゎクを付けたり）する方

くらもらってもプレイヤ蘭1は文句を言わないという，法である．鮭散的手続きでは，移動しているナイフの変更できない優越性（irrevocable advantage）を使

停止位置をプレイヤ蘭に決めさせるような連続的な判って，一夜で解決しているところがポイントである．

断を求めず，切断位置などは鮭散的に決定される．

3．分割可能財に対する無喪望分割法

Brams−Taylor（1995）は分割可能な財に対して．
4人以上の場合の無羨望分割法を初めて与えた．その結果を受け，この分野の研究は大きく発展した．しか3．1藩数的手続き

し，その方法はアルゴリズムの形で書くと，20ステ

2人の場合には比例分割は無羨望分割と同値であり，ップ以上を必要とし非常に繁雑である．さらに，実際

卸（44）

ヽ−＿ノ

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレmションズ・リサ蘭チ

J J

に必要なカット数の上限を与えることもできない．たとえ4人の分割であっても，必要なカット敢はいくらした．たかだか5本のナイフを同時に敷かすという複点からは，まだ改良しなければならない点が残されて雑な換作を許せば，4人の場合に5回のカットだけでいる．

無羨望分割できることを示した．しかし，これらの方

3．2 ティフ移動法

法を5人以上に一般化することは困難であり未だに解

ナイフ移新法は鞋散的手続きより強力であることは決されていない．

次のAustin（1！は2）法から分かる．これは2入に

3．3 近似無喪望分割「正確分割」（exact division）を与える方法である．

薮密な無羨望分割法の開発には限界があるので，最1／2ずつになる．Austin法では2本のナイフA，Bを使用する．

近は：近似分割法の研究も行われている．
与えられたど＞0に対して，桝−（汽）≧桝 （昂）【∵∈がすべてのプレイヤ攣iとノに対して成り立つならば，

ステップ1．第3者がナイフAをケーキの左端から右端へ，どちらかのプレイヤーが［それぞれの測度

分割夕芸（汽，…，月！）はど−近似無羨望であるという．
Su（1999）はSpernerの補填を用いて汎用性の高でナイフAが1／2を経過したときに］「止まれ」の掃い近似分割手続きを提案している．Spernerの補題は示を出すまで移動する．

Brouwerの不動点定理の証明にも使われ 簡単だがステップ2．「止まれ」と指示したプレイヤ （扇殻性を失うことなく1とする）はナイフAを「止まれ」の位置から右へ，またナイフBをケ攣キの左端から右へ［両ナイフの間の量を測度刑．で翻って1／2に保ちながら］同時に動かす．プレイヤ【2は［ナイ

強力な考え方である．邦人の場合にも適用できるかこ
こでは簡単のため3人の場合について説明する．

基本的なアイデアは，正三角形の点とケーキの分割法に1対1の対応を付けることである．

図1は高さ1の正三角形ABCでケーキの分割を表

フん Bの間が測度椚2で測って1／2となるときに］す．三角形の点Dから辺BC，CA，ABへおろした「止まれ」の指示を出す．

垂線の長さをれ，あ，∬3とする．長さ1のケーキを

ステップ3．プレイヤー2から「止まれ」の指示があると，2本のナイフが止まった位置でそれぞれケゎ
キを切断し．両ナイフの間の部分と残りの（通常は左右の二つの）部分に分ける．

Lノ

Barbanel−Brams（2001）はこの結果をさらに改善

でも大きくなるおそれがある．そのため，実用性の観

すなわち，両者の測度から見ると，分割結果は共にLノ

カット敦はたかだか11にできる．

3部分に分割し，左から顧に1，2，3と名付けそれぞれの部分の長さに座標れ，裁，J3を対応させる．
図2に示すように，三角形を小三角形に分割（単体
分割）し．すべての小三角形の3項点に一つずつプレステップ4．抽選により2人のプレイヤーにそれぞイヤ【P，Q，Rのラベルを付け，このラベルをそのれ1部分（中央の部分か左右を合わせた部分）を与え点の所有者とする．すべての頂点で，所有者にその点る．

の座標に対応するケ椚キ分割を行ったときに，何番のBrams−Taylor−Zwicker（1997）はAustin 法を4
人の無羨望分割問題に応用した．まず，プレイヤー1

部分を希望するかを開き，その番号を補助ラベルとして付ける．

と2がAustin法を3回使用して，ケMキを4部分に

長さ0のケーキは誰も希望しないと仮定すれば，点産確分割する．次に，プレイヤM3に1部分から￡Aの所有者は（誰であれ）部分1を希望する．Bのを削り取る【最大サイズを持つ部分が二つあることを所有者は2，Cの所有者は3を希望する．同様に，辺保養する］筏会を与える．後は，プレイヤ 4，3，2，
1の噸で1部分ずつを選ぶことで，￡以外の部分を無羨望で分割できる．ただし，プレイヤー3が削った部分をプレイヤ蟹4が選ばなかったら，プレイヤー3自身がそれを受け取らなければならない．最後に，プレイヤー1と2が，削られた部分をもらったプレイヤーに対して￡に関しての変更できない優越性を持つことに注意し，Selfridge−Conwayの方法と同じようにして，￡を無羨望に分割できる．その結果，分割の2003年3月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

陶1（45）215

プレイヤーは正直に申告しているとし，ゲーム理論のような戦略についての議論は行わない．したがって，
無羨望割当問題を解くのは無羨望性を満たす割当方法
二三を，それを実現する補償金額と併せて求めるアルゴリ
ズムを見つけることである．

二

ミ…F三三二≡三△… ▲Q（B）R P Q R（C）2 2 2 3 3

4．1Klijnのアルゴリズム

Aragones（1995）やKlijn（2000）は無羨望割当問
題をグラフ理論的なアプローチで解いている．

図2

プレイヤ憮と財の集合をそれぞれ，〟，Qとする．

ABの上の頂点では1か2を，辺BC上では2か3を，プレイヤ椚∫∈〃が財ノ∈￠を得たとき，貨幣によるそして辺CA上では3か1を希望する．三角形ABC

補償みを受け取るとし，評価を貨幣に関する準線形の内部の項点では，所有者の希望は1，2，3のどの吋の効用関数αu＝恥＋ちと仮定する．ここで，恥は能住もある．以上から，補助ラベルはSpernerのラ

プレイヤ慣fの財ノに対する効用である．

ベリングになる．Spernerの補填により，図2にある

無羨望割当の存在を保証するために．貨幣が十分に太線の小三角形のように3頂点に葡助ラベル1．2，3あると仮定する．無羨望割当問題はα 机〉≧αむ，∀i∈を持つものが奇数個（したがって少なくとも一つ）存〃，∀ノ∈￠となる〃→￠の1対1写像♂と補償金額Jjを求めることである．プレイヤーの放と財の敢が在する．

太線の小三角形が十分小さければ3頂点に対応する

同じnであるときに，AragonesとKlijnがnに関す分割法はほぼ同じである．一方，3頂点の績助ラベル

る多項式オ慣ダのアルゴリズムで無羨望割当問題を解が1，2，3となっているとき，3人がそれぞれ異なるいた．Aragonesは最適割当問題を解いて，Pareto

部分を希望することになり，近似無羨望分割が実現さ

効率的な初期解から始める．一方，KlijIlでは任意のれる．

割当から始められるので，ここではKlijnの方法を例

一触的には，負担問題にはケ【キ分割の方法を直接適用できないが，Su（1999）では双対単体を利用して，負担問題を解決した．

で紹介する．
プレイヤ蘭と財の集合を〃＝￠＝（1，・‥，6），効用行
列を近似無羨望分割の他の方法についてはZeng（1999）

1 0 7 6 0 0
4 4 0 0 0 1に詳しく紹介されているので参照されたい．

また，Austin法による2人の場合の正確分割を紹

0 11 7 0 0
U＝（恥）＝

介したが，多人数の場合の正確分割は未解決である．

1 0 6 6 1 4RobertsonTWebb（1998）は乾散的手続きで多人数近0 0 1 6 5 0

似正確分割を与えている．∈−近似正確分割とは，与111 0 0 5

ヽ 一′
ノ

えられた正数∈と比率α＝（仇，…，仇）に対して，とし，割当♂（J）＝fと鯖惰守＝（0，…，0）を初期解とす

暮勒（汽）−1ちl＜ど（f，ノ＝1，…，乃）を満たす分割タ＝（月，る．図3は初期解に関する羨望を表している．頂点の…，鳥）のことである．

番号は分割不可能財の番号を示し，頂点ノの横の数字

4．分割不可能財に対する公平割当同塵
いくつかの分割不可能財を無羨望割当することは通（♂￣1（ノ），エす−．−J，）は財ノの所有者と．その補借金額を示す．矢印f→ノは実線の場合（強辺），財Jの所有者が財ノの所有者に羨望を持っている（和一Ⅰ…∫＋JJ−1（り＜常，不可能である．Brams−Fishburn（2000）は財が〟♂−．…ノ＋ェJ−．（ノ））ことを示し，点線の場合（弱辺）は，無限に多いとき無羨望割当が可能となる確率が1にな

同じ満足度を待っている（〟J−1（r〉f十ヱ万一−（r）＝和一1（りノることを証明した．そのため，有限偶の分割不可能財＋∫J−1…）ことを示す．辺のないところは羨望がないを無羨望割当するために．貨幣のような分割可能財にことを示す．

よる葡篠をして無羨望性を満たす方法が考えられる．
無羨望割当問題ではプレイヤ蘭の評価開放は互いに知られていると仮定する．財に対する評価について，
撰（46）

J

強辺を含むサイクルは，サイクルに含まれる財を割当てられているプレイヤ竹の間でサイクルをなくすよ

うに財を交換する．この例では，図3にある，1→3→
オペレ椚ションズ・l巨啓一チ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（6，0）◎（1，0）

問題である．Haake−Raith−Su（2002）がKlijnのア（6，0）（5，0）◎

ルゴリズムよりもっと分かりやすい「補償手続き」をG）（2，0）

提案している．

プレイヤーiは部屋ノを割当てられればいくら払うかを恥で表明し，bidと呼ぶ．iがノを借りるときには部屋代qを支払うとし，iの評価は払が¶qとなる．部屋代の総額で家賃を支払わなければならないので，C≦∑畏1qが成立する．
解の効率性を高めるために，部屋の割当て方は各プ（6，，0．4）

母⁚（5，0）⑥，．

レイヤーに異なる部屋を割当てたときの部屋代の合計（4，2・6）◎が最大になるようにする．これは最適割当問題を解くことで実現できる．一般性を失うことなく，プレイヤ
ー」に部局＝が割当てられるとすると，
乃

◆■●
しノ

（4，−2ト喝（叩（3）感（1，−2．4）（1，−2）固6

図5几〟≡∑狛戸maX∑仇抑）
i＝1

2・6）

Ji＝1

が成立している．したがって，プレイヤけどが部屋fを借りて，支払う部屋代はcゴ＝恥となる．
もし，鋸＝〟 −Cf＜恥＝恥¶qであれば，プレイ
ヤー」は部屋ノを割当てられているプレイヤーノに羨望を持つ．この羨望をプレイヤーに適当な補償を与え2のサイクルがなくなり，図4となる．
サイクルはないが強辺があれば，補償を行い強辺の数を減らす．この例では，図4にある，財1と財2の所有者に2の補償を，財3と財4の所有者に【2の補償をすれば，強辺5→4が消滅する．
これらの手続きを状況に応じて有限回線り返し連用
すれば，図6のように強辺かなくなり無羨望割当を実を割当てられたときの評価はα▲f＝〟たf惰Cぎ十訪，∀鳥∈〃と修正される．羨望がなくなった状態では，5＝〟冊C−∑怨．d ≧0の余剰が出る．余剰Sを新たな羨望が生じないようにプレイヤー間で分配すれば無羨望割

4人のHousemate問題を考える．家賃C＝100と結局，評価行列（恥）＝（恥十み）は
4．6 3．6 0 −0．4

6．6 6．6 【2．4 【2．4 0 0．6
3．6 3．6 1

3，6
【0．4

2．6 2．6 鴨1．4

3．6

3．6 3．6 −1．4 ¶2．4の下線はこの割当方法での効用（部屋代）を示す．
斤1月2Jも 点44・60となる．ここで，数字の下線は得られた割当の組合せ且を示し，各行の最大値になっているので，この割当と部屋代 50 40 25

靖債の組は無羨望である．

初期評価行列（恥）＝（恥【q）は

月 角 番 月もよかったか，得られた解はPareto効率的である．
ヰ．2 日ouse汀鳩te同竃節4．1で考えた問題を もっと具体化して．
Housemate問題を考えよう．n部屋からなる1軒の家を邦人で借り，入居する乃人が割り当てられる部
屋の良さに応じて家賃Cをどのように負担するかが2003年3月号

35

Klijnの方法では初期解はPareto効率的でなくて

50

10 20

40m40

3．6 2，6はプレイヤーiを，凡は部屋ノを表す．また，数字

20

3，6

し，各プレイヤーのbidは次の行列に示している．」R

50︻．602．6 3．6 −1．4 4．6 0
5一〇

Lノ∫に対し葡借オーを与えると，プレイヤ【々が部屋f

当が得られる．「補償手続き」を例で説明する．

現できる．
3．6 2．6

ることによって，段階的になくす．仮に，プレイヤー月

0 冊20 −15 −10

鳥

10

月

｛50

且

補償金額 0© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

0 ¶10 ¶20
000 ［5 〔15
0

5
0

0

0

（47）21丁となる．各行の評価値を対角成分と比較することによは0になる．他のすべての部屋の部屋代を少なくともり，プレイヤー2がプレイヤー1に対して，またプレbidの値にして，プレイヤ¶の余剰を0に抑えないとイヤー3がプレイヤ価4に対して羨望を持っているこ

4の部屋に割り当てられた者の羨望をなくすことはでとが分かる．

きない．このとき，部屋代の和は108で100を超えてこの羨望をなくすため，鳥と鳥の列の要素にそれぞれ品＝10とゐ＝5を加え，プレイヤー2に10，プ

レイヤー3に5の補儒を与える．
評価行列（恥）＝（恥−q＋め）は

fち

5．その他の問題
これまでに触れなかったが，最近注目を集めている二つの話題について紹介する．

月 島 月 旦月

しまい，余剰の8を無羨望に分けられない．

0 −10 −10 −10

5．1超無法窒分割

10 10 【5 −20

超無羨望分割（superenVy−freedivisi（）n）とは．

月−50 10

且

0

5

5

5 ¶10

補償金額 0 10

椚f（翔＞‡＞研一（ろ），∀′，ノ∈〃，葎ノ0
50を満たす分割（月，‥・，鳥）のことである．この基準はとなる．今度はプレイヤー3と4がプレイヤー2に羨無羨望であることに加えて，他人が各自の測度で1／搾望を持っている．昂と月の列の要素にそれぞれ5を以上を取得することを許さない厳しい基準である．

加えることにより，晶＝10，d＝5となi），評価行列

Barbanel（1996）は，超無蒸望分割か存在するためはの必要十分条件は，評価関数（桝 1結〃が線形独立であ
月

fち

鳥

省

0 −10 −115

角

10 10 0 −15

ることを証明した．

貝

その後，Robertson−Webb（1998）は超無羨望分割−5を実現する分割法を与えた．乃人の評価関数が線形独立である条件として，ケMキの一部Aの分割〟＝−50 10 10 10

鳥

0

鳥

鯖借金額

5 ¶5

5

0 10 10

5（Al，・‥，A〝‡があり，行列y＝（〝わ（Aノ））が正則であるとする．さらに，一般性を失うことなく，A＝Cと仮定してもよい．行列yは（各行の要素が非負で，となる．
これですべてのプレイヤ…の羨望がなくなった．各

その和が1になる）確率行列なので，逆行列y￣1のプレイヤーへの補償金額の総額は10十10＋5＝25であ

各行和は1になる．このとき，行列斤＝（rむ）…y￣1Ⅳる．当初に捻頼〟＝145だけのbidをしていたので，
余剰はぎ＝145【100−25＝20となる．これを各人にも確率行列になるような十分小さい正数∂が存在す
る．ただし，Ⅳ＝（れ，む）で，1＋∂， 〃

均等に分けて5ずつ払い戻せば，各プレイヤ蘭の最終

靖借金額はd＝（5，15，15，10）で，最終的な支払い金額

1

はぐ−d＝（45，25，10，20）である．

∂〝 柁−1，

この例のように無羨望割当が可能であったのは，負J＝ノのとき．

J（！u′‥‥‥g≠ノのとき．

Eは不等式0＜∈＜∂／乃2を満たすものとする．ど−近似の部屋代を許しているからである．部屋代を非負の値

正確分割法を使えば，Aノに対して比率（り1，…，「函）に限ると〃≧4のとき，無羨望割当は不可能な場合がでの近似分割（昆．，…，昆乃）ができる．その結果，プある．Brams−Kilgour（2001）の例を考えよう．

レイヤー鳥に鳥…βi▲∪‥・∪β鵬を与えれば超無羨望

尺1．斤2。丹ユ」打 合計分割になる．

月 36 34 30 0 100
昂 31 36 33 0 100

5．2 勝者調整法
Brams−Taylor（1999）は勝者詞整法（adjusted

fも 34 30 36 0 100

winner）で平等性も考慮した公平分割の方法を提毒f1 32 33 35 0 100

している．

部屋4については誰も正の部屋代をbidしていない．

いくつかの対象物を2人に割当てるとき，各プレイ

しかし．負の部屋代は許されないので部屋4の部屋代

ヤ【がそれぞれの財に合計が100点となるように配点

オペレ椚ションズ・リサ冊チ2㈲（48）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

I I

し，各財に対してより高い点数を付けた者が勝者としpreferences：enVy−freeness，Pareto−Optimality，andてその財を一時的に受け取る．一時的な財の割当に基印uity ，艮〉C由JC如如㍑那＝穐的叩17，247−267（2000）．
［6コBrams，S．J．andKilgour，D．M．：

づいて各プレイヤ【の総得点を計算する．同点であれ

Divisionば終了する．そうでなければ，より獲得点数の高いプ

CompetitiveFair，JbuTmlq／fわLititd肋no珊凱109，418−443（2001）．

レイヤ【から低いプレイヤーに財を平等性を満たすよ［7］Brams，SJ．andTaylor，A．D．：

うに，両者の得点が等しくなるまで譲渡する．この際，Division Protocol

2人の評価の比率が低いものから噸に譲ることにして，

AnEnvy−FreeCake，AmeYican MathematicalMonth玩

102，9−18（1995）．

効率性がなるべく損なわれないようにする．

［8］Brams，S．）．and Taylor，A．D∴

勝者調整法は効率性，無羨性に平等性を併せて満たFair Division：

FromCake−CuttingtoDisputeResolution

す優れた方法であり，Bramsらはアメリカでパテン，Cambrid−

geUniversityPress（1996）．

トを取得している．しかし，3人以上の場合にはこれ［9］Brams，S．）．and Taylor，A．D．：

The Win−Winらの3条件を同時には満たさない例の存在が知られてSolution：Guaranteeing Fair Shares to Everybody ，おり，一般化は困簸である．

W．W．Norton（NewYork）（1999）（日本語訳：プラムス，テイラォ（宍戸栄徳監修，宍戸律子訳：「公平分割の6．おわりに法則」，TBSブリタニカ（2000））．

ヽ J［10］Brams，S．）．，Taylor，A．D．andZwickerW．S．

大学院の学生であった頃，研究室の学生仲間と予備

movlng−knife solution to the four−perSOn enVy−free

校の試験の採点をアルバイトとしてやっていた．6間Cakedivisionproblem

壇を6人で1題ずつ採点するのであるが，難しい問填

，Proceedings qf theAmericcn〟混血糊血血扉5抜滋身125，547−554（1997）．

では白紙の答案も多く採点は簡単であるが，やさしい［11］Gamow，G．and Stern，M．： Puzzle−Math ，New

問題は多くの受験僅がそれなりの解答を書いているの

York：Viking（1958）（日本語訳：ガモフ，スタhン（由で採点に手間取ってしまう．このように，問題によっ良統吉訳：「敦は魔術師」，白揚社（1958，1999））．

て採点時間が異なるので，謝礼金の分配金領を問題ご［12］Haake，C．−J．，Raith，M．G．andSu，F．E．： Bidfor envy−freeness：A proceduralapproach to n−とに決めるのに苦労した．d宝金額の謝礼金をどのように分けるかは難しい問題であった．

player fair−division problems

もし当時，無羨望の概念が広く知られ，House．

，SbchzZ Cゐoite and勒的柁，19，723−749（2002）．

［13］Klijn，F．： Analgorithmforenvy−freea1location

mate問題が解決されていれば，納得のできる公平割

in aneconomywithindivisibleobjects and money

当はすぐに見つけられたであろう．

，

艮）C由JCあ♂加β乃dIl々的柁，17，20ト215（2000）．
拳考文献［1］Aragones，E．：
斡Iution
Lノ［14］Robertson，J．and Webb，W．： Cake−Cutting Al−●AderivationofthemoneyrawIsian，ふ｝CねJC払加J槻JW郷加，12，267−276［2］Austin，A．K∴ Sharing a cake ，肋fhemalict21

algorithmsforfairandstronglyfairdivision，GYOゆ

肋由わ乃α乃d職卵ぬJね乃，8，125−137（1999）．

血gfね66，212−215（1982）．
independenceofmeasures，Natic，MA：A K

Peters（1998）．

［15］Shishido，H．and Zeng，D．−Z．： Mark−Choose−Cut（1995）．

［3］Barbanel，J．B．：

gorithms：Be FairIf You Can

SuperenvyLfreecakedivisionand［16］Su，F．E．：，）？urna［d肋themalictl（

FairDivision

RentalHarmony：Sperner，sLemmain，Americt2n肋ihimlitd Month玩106，930−942（1999）．

A符α如怨β乃dA抑fわ那，197，54−60（1996）．

［4］Barbanel，）．B．and Brams，S．J．： Cake Divisi。n ［17］Zeng，D．−Z．： Approximateenvy−freeprocedureswith MinimalCuts：Envy−Free Procedures for 3（F．Patrone，Ⅰ．Garcia−JuradoandS．Tijseds．），（おmePersons．4Person＄，andBeyond

伽c庇g：α融鵬祓加り知椚4妙肋＝施剛 259−271，，Dikcussion♪卸erRR＃：2001−07，C．V．StarrCenterforAppliedEconomics，

Kluwer Academic Press（2000）．

［18］皆道智，茨木俊秀＝「公平分割とその手頃」，応用数理，

NewYork University（2001）．
［5］Brams，S．）．andFishburn，P．C．：

9，12−27（1999）．
Fairdivisi。n。f

indivisibleitems between two peoplewithidentical

2003年3月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（49）20g