(57)【要約】【課題】分割結果の取り分だけでなく、役割の割り当てについても公平に分割することが可能な３者間の公平分割装置、３者間の公平分割方法、及びプログラムを提供する。【解決手段】割当制御部が、分割対象の資源について３台の端末各々の評価尺度により３分割した各ポイントを当該３台の端末から取得し、当該各ポイントの相互関係により当該３台の端末の役割分担を決定した上で、当該３台の端末に対し資源の無羨望分割割り当てを行う。【選択図】図１
2011128860.tif 000002
【特許請求の範囲】
【請求項１】
区間［０、１］で表される資源を３台の端末間で公平に割り当てるための制御を行う割当制御部と、
それぞれ独自の所定の評価尺度を有し、上記割当制御部からの要求に応じて割り当てに必要な情報を当該割当制御部に送信する３台の端末と、
を備える３者間の公平分割装置であって、
上記割当制御部は、
上記３台の端末に対して、当該３台の端末がそれぞれの評価尺度により上記区間［０、１］を０から正方向を見て１／３に切ったポイントＬ１、Ｌ２、Ｌ３を送信するよう要求して、結果を各端末から受信し、
Ｌ１＝Ｌ２＝Ｌ３＝Ｌ123である場合、
上記３台の端末に対して、当該３台の端末がそれぞれの評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ１、Ｒ２、Ｒ３を送信するよう要求して、結果を各端末から受信し、
Ｒ１＝Ｒ２＝Ｒ３＝Ｒ123である場合には、区間［０、Ｌ123］、［Ｌ123、Ｒ123］、［Ｒ123、１］のそれぞれいずれかを上記３台の端末に割り当て、
Ｒ１＝Ｒ２＝Ｒ12≠Ｒ３である場合には、Ｒ12＜Ｒ３なら、Ｒ３を送信した端末ｐ３に区間［Ｒ12、１］を、残りの２台の端末ｐ１、ｐ２に区間［０、Ｌ123］、［Ｌ123、Ｒ12］のそれぞれいずれかを割り当て、Ｒ12＞Ｒ３なら、ｐ３に区間［Ｌ123、Ｒ12］を割り当て、残りの２台の端末ｐ１、ｐ２に区間［０、Ｌ123］、［Ｒ12、１］のそれぞれいずれかを割り当て、
Ｒ１＜Ｒ２＜Ｒ３である場合には、Ｒ２を送信した端末ｐ２による切り方で３分割し、Ｒ１を送信した端末ｐ１に区間［Ｌ123、Ｒ２］を、ｐ２には区間［０、Ｌ123］を、Ｒ３を送信した端末ｐ３に区間［Ｒ２、１］を割り当て、
Ｌ１＝Ｌ２＝Ｌ12≠Ｌ３である場合、
Ｌ１、Ｌ２を送信した２台の端末ｐ１、ｐ２に対して、ｐ１、ｐ２がそれぞれ各自の上記評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ１、Ｒ２を送信するよう要求して、結果を各端末から受信し、
Ｒ１＝Ｒ２＝Ｒ12である場合には、残りの端末ｐ３に対して、当該３分割された区間［０、Ｌ12］、［Ｌ12、Ｒ12］、［Ｒ12、１］のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ３から受信し、ｐ３にはｐ３が選択した区間を割り当て、ｐ１、ｐ２には残りの２つの区間のそれぞれいずれかを割り当て、
Ｒ１＜Ｒ２である場合には、まず、残りの端末ｐ３に対して、区間［０、Ｌ12］、［Ｌ12、Ｒ１］、［Ｒ２、１］のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ３から受信し、
ｐ３の評価尺度で評価値が最大となる区間が［０、Ｌ12］である場合には、ｐ１に［Ｌ12、Ｒ１］を、ｐ２に［Ｒ２、１］を、ｐ３に［０、Ｌ12］を割り当てた上、ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求して、結果をｐ３から受信し、ｐ１に対し、当該３分割された各区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、ｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当て、
ｐ３の評価尺度で評価値が最大となる区間が［Ｌ12、Ｒ１］である場合には、ｐ１に［０、Ｌ12］を、ｐ２に［Ｒ２、１］、ｐ３に［Ｌ12、Ｒ１］を割り当てた上、ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求して、結果をｐ３から受信し、ｐ２に対して、当該３分割した各区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、ｐ１に対して、残りの２区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、残った区間をｐ３に割り当て、
ｐ３の評価尺度で評価値が最大となる区間が［Ｒ２、１］である場合には、ｐ１に［Ｌ12、Ｒ１］を、ｐ２に［０、Ｌ12］、ｐ３に［Ｒ２、１］を割り当てた上、ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求して、結果をｐ３から受信し、ｐ１に対して、当該３分割した各区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、ｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当てる
３者間の公平分割装置。
【請求項２】
請求項１に記載の３者間の公平分割装置において、
上記割当制御部は更に、
Ｌ１＜Ｌ２＜Ｌ３である場合、
Ｌ３を送信した端末ｐ３に対して、ｐ３の評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ３を送信するよう要求して、結果をｐ３から受信し、
Ｌ２を送信した端末ｐ２に対して、区間［０、Ｌ３］、［Ｌ３、Ｒ３］、［Ｒ３、１］のうちｐ２の評価尺度による評価値が最大の区間が１つだけか、２つ以上あるかを送信するよう要求して、結果をｐ２から受信し、
ｐ２の評価尺度による評価値が最大の区間が２つ以上ある場合は、Ｌ１を送信した端末ｐ１に対して、区間［０、Ｌ３］、［Ｌ３、Ｒ３］、［Ｒ３、１］のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、ｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当て、
ｐ２の評価尺度による評価値が最大の区間αが１つの場合は、ｐ２に対して、ｐ２の評価尺度で評価値が２番目の区間と同じになるようにαの一部である区間ｘを切り取りこれを送信するよう要求して、区間ｘをｐ２から受信し、
ｐ１に対して、区間α−ｘとその他２つの区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、ｐ１に区間α−ｘを割り当てた場合にはｐ２に対して、その他２つの区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ２から受信し、ｐ２にこの区間を、残った区間をｐ３に割り当て、また、ｐ１に区間α−ｘを割り当てなかった場合にはｐ２に区間α−ｘを、残った区間をｐ３に割り当て、
区間α−ｘが割り当てられなかったｐ１又はｐ２いずれかの端末（以下、「Ｐ１」という。）に対して、区間ｘをＰ１の評価尺度で３分割した結果を送信するよう要求して、結果をＰ１から受信し、区間α−ｘが割り当てられたｐ１又はｐ２いずれかの端末（以下、「Ｐ２」という。）に対して、Ｐ１により３分割された各区間のうちＰ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をＰ２から受信し、Ｐ２にはこの区間を割り当て、ｐ３に対して、残りの２区間のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ３から受信し、ｐ３にはこの区間を割り当て、残った区間をＰ１に割り当てる
３者間の公平分割装置。
【請求項３】
区間［０、１］で表される資源を３台の端末間で公平に割り当てるための制御を行う割当制御部と、
それぞれ独自の所定の評価尺度を有し、上記割当制御部からの要求に応じて割り当てに必要な情報を当該割当制御部に送信する３台の端末と、
を用いて実行する３者間の公平分割方法であって、
上記割当制御部が、
上記３台の端末に対して、当該３台の端末がそれぞれの評価尺度により上記区間［０、１］を０から正方向を見て１／３に切ったポイントＬ１、Ｌ２、Ｌ３を送信するよう要求して、結果を各端末から受信する第１分割ステップと、
Ｌ１＝Ｌ２＝Ｌ３＝Ｌ123である場合に、
上記３台の端末に対して、当該３台の端末がそれぞれの評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ１、Ｒ２、Ｒ３を送信するよう要求して、結果を各端末から受信する第２分割ステップと、
Ｒ１＝Ｒ２＝Ｒ３＝Ｒ123である場合に、
区間［０、Ｌ123］、［Ｌ123、Ｒ123］、［Ｒ123、１］のそれぞれいずれかを上記３台の端末に割り当てる第１割当ステップと、
Ｒ１＝Ｒ２＝Ｒ12≠Ｒ３である場合に、
Ｒ12＜Ｒ３なら、Ｒ３を送信した端末ｐ３に区間［Ｒ12、１］を、残りの２台の端末ｐ１、ｐ２に区間［０、Ｌ123］、［Ｌ123、Ｒ12］のそれぞれいずれかを割り当て、Ｒ12＞Ｒ３なら、ｐ３に区間［Ｌ123、Ｒ12］を割り当て、残りの２台の端末ｐ１、ｐ２に区間［０、Ｌ123］、［Ｒ12、１］のそれぞれいずれかを割り当てる第２割当ステップと、
Ｒ１＜Ｒ２＜Ｒ３である場合にはＲ２を送信した端末ｐ２による切り方で３分割し、Ｒ１を送信した端末ｐ１に区間［Ｌ123、Ｒ２］を、ｐ２には区間［０、Ｌ123］を、Ｒ３を送信した端末ｐ３に区間［Ｒ２、１］を割り当てる第３割当ステップと、
Ｌ１＝Ｌ２＝Ｌ12≠Ｌ３である場合に、
Ｌ１、Ｌ２を送信した２台の端末ｐ１、ｐ２に対して、ｐ１、ｐ２がそれぞれ各自の上記評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ１、Ｒ２を送信するよう要求して、結果を各端末から受信する第３分割ステップと、
Ｒ１＝Ｒ２＝Ｒ12である場合に、
残りの端末ｐ３に対して、当該３分割された区間［０、Ｌ12］、［Ｌ12、Ｒ12］、［Ｒ12、１］のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ３から受信し、ｐ３にはｐ３が選択した区間を割り当て、ｐ１、ｐ２には残りの２つの区間のそれぞれいずれかを割り当てる第４割当ステップと、
Ｒ１＜Ｒ２である場合に、
残りの端末ｐ３に対して、区間［０、Ｌ12］、［Ｌ12、Ｒ１］、［Ｒ２、１］のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ３から受信する選択ステップと、
ｐ３の評価尺度で評価値が最大となる区間が［０、Ｌ12］である場合に、
ｐ１に［Ｌ12、Ｒ１］を、ｐ２に［Ｒ２、１］を、ｐ３に［０、Ｌ12］を割り当てる第５割当ステップと、
ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求して、結果をｐ３から受信し、ｐ１に対し、当該３分割された各区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、ｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当てる第６割当ステップと、
ｐ３の評価尺度で評価値が最大となる区間が［Ｌ12、Ｒ１］である場合に、
ｐ１に［０、Ｌ12］を、ｐ２に［Ｒ２、１］を、ｐ３に［Ｌ12、Ｒ１］を割り当てる第７割当ステップと、
ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求して、結果をｐ３から受信し、ｐ２に対して、当該３分割した各区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、ｐ１に対して、残りの２区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、残った区間をｐ３に割り当てる第８割当ステップと、
ｐ３の評価尺度で評価値が最大となる区間が［Ｒ２、１］である場合に、
ｐ１に［Ｌ12、Ｒ１］を、ｐ２に［０、Ｌ12］を、ｐ３に［Ｒ２、１］を割り当てる第９割当ステップと、
ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求して、結果をｐ３から受信し、ｐ１に対して、当該３分割した各区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、ｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当てる第１０割当ステップと、
を実行する３者間の公平分割方法。
【請求項４】
請求項３に記載の３者間の公平分割方法において、更に、
Ｌ１＜Ｌ２＜Ｌ３である場合に、
Ｌ３を送信した端末ｐ３に対して、ｐ３の評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ３を送信するよう要求して、結果をｐ３から受信する第４分割ステップと、
Ｌ２を送信した端末ｐ２に対して、区間［０、Ｌ３］、［Ｌ３、Ｒ３］、［Ｒ３、１］のうちｐ２の評価尺度による評価値が最大の区間が１つだけか、２つ以上あるかを送信するよう要求して、結果をｐ２から受信する評価ステップと、
ｐ２の評価尺度による評価値が最大の区間が２つ以上ある場合に、
Ｌ１を送信した端末ｐ１に対して、区間［０、Ｌ３］、［Ｌ３、Ｒ３］、［Ｒ３、１］のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、ｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当てる第１１割当ステップと、
ｐ２の評価尺度による評価値が最大の区間αが１つの場合に、
ｐ２に対して、ｐ２の評価尺度で評価値が２番目の区間と同じになるようにαの一部である区間ｘを切り取りこれを送信するよう要求して、区間ｘをｐ２から受信する切取ステップと、
ｐ１に対して、区間α−ｘとその他２つの区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、ｐ１に区間α−ｘを割り当てた場合にはｐ２に対して、その他２つの区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ２から受信し、ｐ２にこの区間を、残った区間をｐ３に割り当て、また、ｐ１に区間α−ｘを割り当てなかった場合にはｐ２に区間α−ｘを、残った区間をｐ３に割り当てる第１２割当ステップと、
区間α−ｘが割り当てられなかったｐ１又はｐ２いずれかの端末（以下、「Ｐ１」という。）に対して、区間ｘをＰ１の評価尺度で３分割した結果を送信するよう要求して、結果をＰ１から受信し、区間α−ｘが割り当てられたｐ１又はｐ２いずれかの端末（以下、「Ｐ２」という。）に対して、Ｐ１により３分割された各区間のうちＰ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をＰ２から受信し、Ｐ２にはこの区間を割り当て、ｐ３に対して、残りの２区間のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ３から受信し、ｐ３にはこの区間を割り当て、残った区間をＰ１に割り当てる第１３割当ステップと、
を実行する３者間の公平分割方法。
【請求項５】
請求項１又は２のいずれかに記載の３者間の公平分割装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経済社会における資源の３者間での公平分割に関し、特に、結果だけでなく役割分担も公平に割り当てるための３者間の公平分割装置、３者間の公平分割方法、及びそのプログラムに関する。
【背景技術】
【０００２】
ケーキの分割や領土の割り当てなど、(i)区間［０、１］間に存在し、その間の任意の箇所で分割可能な領域Ｘに対し、(ii)いかなる空でないＹ⊂Ｘに対しても各player iは０でない価値μｉ(Y)＞０を持ち、(iii)価値は足し算で計算される、すなわち重なりを持たない２つの領域Ｘ１とＸ２に対するplayer iの価値がμｉ(Ｘ１)、μｉ(Ｘ２)であるとき、μｉ(Ｘ１∪Ｘ２)＝μｉ(Ｘ１)＋μｉ(Ｘ２)が成立するＸを３者間（player 1〜3）で分割する分割方法について、以下のものが考えられている。
【０００３】
step 1：player 1が自分にとって価値が同じになるようにＸを３つの部分に分割する。
step 2：player 2は、player 1が分割した３つの部分を自分の価値尺度で価値の高いものから並べ、それぞれの価値をａ、ｂ、ｃとする。このとき、player 1にとってはａ＝ｂ＝ｃ、player 2にとってはａ≧ｂ≧ｃである。
【０００４】
step 3：もし、ａ、ｂ、ｃのうちでplayer 2にとって価値が最大のものが２つ以上あれば（ａ＝ｂ≧ｃのとき）、player 3、player 2の順に、残っている中から自分の価値が最大のものを選び、player 1は残りを得て、分割を終了する。
step 4：一方、ａ、ｂ、ｃのうちでplayer 2にとって価値が最大のものが１つのとき（ａ＞ｂ≧ｃのとき）は、player 2は自分にとって価値が最大であるａの一部を切り取って、価値が２番目に大きいｂと同じになるようにする。このとき、切り取った部分の価値をＬ、Ｌを切り取った後のａの価値をａ´とおく（つまり、player 2にとって、ａ´＝ｂ≧ｃ、ａ´＝ａ−Ｌ）。
【０００５】
step 5：ａ´、ｂ、ｃについて、player 3、player 2の順に、残っている中から自分の価値が最大のものを選び、player 1は残りを得る。ここで、player 3がａ´を選択しない場合には、player 2はａ´を選択する（つまり、player 2かplayer 3のいずれかがａ´を選択している）。
step 6：ａ´を選択したplayerをplayer B、そうでない方をplayer Aとし、player Aが自分にとって価値が同じになるようにＬを３つの部分に分割する。
step 7：player B、player 1の順に、分割されたＬの各部分のうち残っている中から自分にとって価値が最大となるものを選択し、player Aは残りを得て、分割を終了する。
【０００６】
以上の手法により、各player iが得た結果Ｘｉは無羨望、すなわちμｉ(Ｘｉ)≧μｉ(Ｘｊ)がすべてのｉ、ｊに対して成立し、自分の取り分を他のplayerの取り分と交換しようと思わない。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Jack Robertson, William Webb, "Cake-Cutting Algorithms: Be Fair If you Can", A K Peters Ltd, 1998, p.12-13
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし上記の手法では、player 1、2、3の役割は対称ではない。当該手法を実行しようとしているユーザのことをparty x、y、zと呼ぶとき、任意のparty xにとって、「party xがplayer 2、party yがplayer 3」という割り当てと、「party xがplayer 3、party yがplayer 2」という割り当てとを比べると後者が有利である。その理由を場合分けして説明する。
【０００９】
〔case 1〕party yがplayer 2のとき、party yが分割部分の一部を切り取らない場合
〔case 1-1〕party xがplayer 2で、party xが分割部分の一部を切り取る場合
party xは、step 4においてａの一部を切り取り、価値をａ´（＝ｂ）にする。そして、step 5の選択において、party xは価値がａ´である部分を得る。切り取った部分の価値Ｌはａ−ａ´であるが、party xにはこれが３つに分割されて与えられるため、party xはどのようにしても合計ａの価値を得ることができない。
これに対し、party yがplayer 2、party xがplayer 3のときには、party xはstep 3において１番目の選択権を有するため、ａの価値を得ることができる。
従って、このケースではplayer 3になる方が有利である。
【００１０】
〔case 1-2〕party xがplayer 2で、party xが分割部分の一部を切り取らない場合
party xはstep 3において２番目の選択権を有するため、ａ＝ｂ≧ｃであることから、ａの価値を得ることができる。
一方、party yがplayer 2、party xがplayer 3のときには、party xはstep 3において１番目の選択権を有するため、ａの価値を得ることができる。
従って、このケースではいずれのplayerになっても有利不利は無い。
【００１１】
〔case 2〕party yがplayer 2のとき、party yが分割部分から部分Ｍを切り取る場合
〔case 2-1〕party xがplayer 2の場合にもparty yと同じ分割部分から部分Ｍ´を切り取る場合（party xにとって価値が最大である分割部分とparty yにとって価値が最大である分割部分が同じである場合）
〔case 2-1-1〕party xの方が物理的に大きい部分を切り取る場合（Ｍ´＞Ｍの場合）
【００１２】
party xにとって価値が最大である分割部分の価値をａ、部分Ｍの価値をＬ、部分Ｍ´の価値をＬ´（＞Ｌ）とおく。
party xがplayer 2（party yがplayer 3）の場合、step 4においてＬより大きいＬ´が切り取られる。そのため、party yにとってはＬ´を切り取っていない分割部分の方が価値が高いことから、step 5においてparty yはそちらを選ぶ。従って、party xはａ−Ｌ´を得る。更に、step 6でparty yが３分割したＬ´について、step 7でparty xが１番目の選択権を有するため、少なくともＬ´／３を得る。従って、party xが得る価値の合計は「少なくともａ−２Ｌ´／３」である。
【００１３】
これに対し、party xがplayer 3（party yがplayer 2）の場合、step 4においてＬ´より小さいＬが切り取られる。そのため、party xにとってはＬ´を切り取った分割部分の方が価値が高いことから、step 5においてparty xはａ−Ｌを得る。更に、step 6でparty yが３分割したＬについて、step 7でparty xが１番目の選択権を有するため、少なくともＬ／３を得る。従って、party xが得る価値の合計は「少なくともａ−２Ｌ／３」である。
そしてＬ´＞Ｌなので、「少なくともこれだけはもらえる価値」を比較すると、このケースでもplayer 3になる方が有利である。
【００１４】
〔case 2-1-2〕party xの方が物理的に小さい部分を切り取る場合（Ｍ´＜Ｍの場合）
party xにとって価値が最大である分割部分の価値をａ、部分Ｍの価値をＬ、部分Ｍ´の価値をＬ´（＜Ｌ）とおく。このとき、party xにとってＬ´を切り取る前に２番目に価値の高い部分の価値はａ−Ｌ´である。
party xがplayer 2（party yがplayer 3）の場合、step 4においてＬより小さいＬ´が切り取られる。そのため、party yにとってはＬを切り取った分割部分の方が価値が高いことから、step 5においてparty yはそちらを選ぶ。従って、party xはａ−Ｌ´を得る。更に、step 6でparty xが３分割したＬ´について、step 7でＬ´／３を得る。従って、party xが得る価値の合計は、ａ−Ｌ´＋Ｌ´／３である。
【００１５】
これに対し、party xがplayer 3（party yがplayer 2）の場合、step 4においてＬ´より大きいＬが切り取られる。そのため、party xにとってはＬ´を切り取っていない分割部分の方が価値が高いことから、step 5においてparty xはａ−Ｌ´を得る。更に、step 6でparty xが３分割したＬについて、step 7でＬ／３を得る。従って、party xが得る価値の合計は、ａ−Ｌ´＋Ｌ／３である。
そして、Ｌ´＜Ｌなので、このケースでもplayer 3になる方が有利である。
【００１６】
〔case 2-1-3〕party xとparty yが同じ大きさの部分を切り取る場合（Ｍ´＝Ｍの場合）
party xにとって価値が最大である分割部分の価値をａ、部分Ｍの価値をＬ、部分Ｍ´の価値をＬ´（＝Ｌ）とおく。
party xがplayer 2（party yがplayer 3）の場合、step 4においてＬ´が切り取られ、step 5においてparty yはＬ´を切り取った残りを選び、party xはＬ´を切り取る前に２番目に価値の高い部分であるａ−Ｌ´を得る。更に、step 6でparty xが３分割したＬ´について、step 7でＬ´／３を得る。従って、party xが得る価値の合計は、ａ−Ｌ´＋Ｌ´／３である。
【００１７】
これに対し、party xがplayer 3（party yがplayer 2）の場合、step 4においてＬが切り取られ、step 5においてparty xはａ−Ｌを得る。更に、step 6でparty yが３分割したＬについて、step 7でparty xは１番目の選択権を有するため、少なくともＬ／３を得る。従って、party xが得る価値の合計は、「少なくとも」ａ−Ｌ＋Ｌ／３である。
そして、Ｌ´＝Ｌなので、このケースでもplayer 3になる方が有利である。
【００１８】
〔case 2-2〕party xがplayer 2の場合で、party yとは異なる分割部分から部分Ｍ´を切り取る場合（party xにとって価値が最大である分割部分とparty yにとって価値が最大である分割部分が異なる場合）
party yがplayer 2の時のparty yにとって価値が最大の分割部分のparty xによる価値をａ´、party xによる部分Ｍの価値をＬ、party xにとって価値が最大の分割部分のparty xによる価値をａ（＞ａ´）、party xによる部分Ｍ´の価値をＬ´とする。
party xがplayer 2の場合、party yはstep 5において、Ｌ´を取り除いた残りは自分にとって価値が最大の分割部分に係るものでないため選択しない。そのため、party xはａ−Ｌ´を得る。更に、step 6でparty yが３分割したＬ´について、step 7でparty xは１番目の選択権を有するが、最大でもＬ´未満である。従って、party xが得る価値の合計は、ａ未満である。
【００１９】
これに対し、party xがplayer 3の場合、自分にとって最大と思われる部分を全て得ることができる。すなわち、step 5においてａを、step 6においてＬ／３を得る。従って、party xが得る価値の合計は、ａ＋Ｌ／３である。
よって、この場合においてもplayer 3になる方が有利である。
【００２０】
〔case 2-3〕party xがplayer 2で、party xが分割部分の一部を切り取らない場合
party xにとって価値が最大の分割部分の価値をａ、部分Ｍの価値をＬとする。
party xがplayer 2の場合、価値ａの分割部分が少なくとも２つあるため、party xはａを得る。
一方、party yがplayer 2の場合、party xはstep 5においてaを、step 6においてＬ／３を得る。従って、party xが得る価値の合計は、ａ＋Ｌ／３である。
よって、この場合においてもplayer 3になる方が有利である。
【００２１】
以上のように、player 3となる方が「最低限得られる量」において、常に同じかよい結果を得る。
【００２２】
従って、実際に実行する場合には、３者のいずれがそれぞれplayer 1、2、3の役割を担うかを何らかの手段で決定する必要がある。役割の割り当てについて合意が行われた後にこの手法に従って分割を行えば、その分割結果の取り分について他のplayerと交換しようとは思わないが、そもそも役割によって上記のように有利不利が存在するためplayer間で役割交換の羨望が生じ、公平な結果の前提である役割の割り当てについての合意が取れない。それゆえ、この手法で公平な分割を行うことは実質的に不可能である。
【００２３】
本発明は、分割結果の取り分だけでなく、役割の割り当てについても公平に分割することが可能な３者間の公平分割装置、３者間の公平分割方法、及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２４】
本発明の３者間の公平分割装置は、割当制御部と３台の端末とを備える。
割当制御部は、区間［０、１］で表される資源を３台の端末間で公平に割り当てるための制御を行う。
３台の端末は、それぞれ独自の所定の評価尺度を有し、上記割当制御部からの要求に応じて割り当てに必要な情報を当該割当制御部に送信する。
【００２５】
そして、割当制御部は、
上記３台の端末に対して、当該３台の端末がそれぞれの評価尺度により上記区間［０、１］を０から正方向を見て１／３に切ったポイントＬ１、Ｌ２、Ｌ３を送信するよう要求して、結果を各端末から受信し、
Ｌ１＝Ｌ２＝Ｌ３＝Ｌ123である場合、
上記３台の端末に対して、当該３台の端末がそれぞれの評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ１、Ｒ２、Ｒ３を送信するよう要求して、結果を各端末から受信し、
Ｒ１＝Ｒ２＝Ｒ３＝Ｒ123である場合には、区間［０、Ｌ123］、［Ｌ123、Ｒ123］、［Ｒ123、１］のそれぞれいずれかを上記３台の端末に割り当て、
Ｒ１＝Ｒ２＝Ｒ12≠Ｒ３である場合には、Ｒ12＜Ｒ３なら、Ｒ３を送信した端末ｐ３に区間［Ｒ12、１］を、残りの２台の端末ｐ１、ｐ２に区間［０、Ｌ123］、［Ｌ123、Ｒ12］のそれぞれいずれかを割り当て、Ｒ12＞Ｒ３なら、ｐ３に区間［Ｌ123、Ｒ12］を割り当て、残りの２台の端末ｐ１、ｐ２に区間［０、Ｌ123］、［Ｒ12、１］のそれぞれいずれかを割り当て、
Ｒ１＜Ｒ２＜Ｒ３である場合には、Ｒ２を送信した端末ｐ２による切り方で３分割し、Ｒ１を送信した端末ｐ１に区間［Ｌ123、Ｒ２］を、ｐ２には区間［０、Ｌ123］を、Ｒ３を送信した端末ｐ３に区間［Ｒ２、１］を割り当て、
Ｌ１＝Ｌ２＝Ｌ12≠Ｌ３である場合、
Ｌ１、Ｌ２を送信した２台の端末ｐ１、ｐ２に対して、ｐ１、ｐ２がそれぞれ各自の上記評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ１、Ｒ２を送信するよう要求して、結果を各端末から受信し、
Ｒ１＝Ｒ２＝Ｒ12である場合には、残りの端末ｐ３に対して、当該３分割された区間［０、Ｌ12］、［Ｌ12、Ｒ12］、［Ｒ12、１］のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ３から受信し、ｐ３にはｐ３が選択した区間を割り当て、ｐ１、ｐ２には残りの２つの区間のそれぞれいずれかを割り当て、
Ｒ１＜Ｒ２である場合には、まず、残りの端末ｐ３に対して、区間［０、Ｌ12］、［Ｌ12、Ｒ１］、［Ｒ２、１］のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ３から受信し、
ｐ３の評価尺度で評価値が最大となる区間が［０、Ｌ12］である場合には、ｐ１に［Ｌ12、Ｒ１］を、ｐ２に［Ｒ２、１］を、ｐ３に［０、Ｌ12］を割り当てた上、ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求して、結果をｐ３から受信し、ｐ１に対し、当該３分割された各区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、ｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当て、
ｐ３の評価尺度で評価値が最大となる区間が［Ｌ12、Ｒ１］である場合には、ｐ１に［０、Ｌ12］を、ｐ２に［Ｒ２、１］、ｐ３に［Ｌ12、Ｒ１］を割り当てた上、ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求して、結果をｐ３から受信し、ｐ２に対して、当該３分割した各区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、ｐ１に対して、残りの２区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、残った区間をｐ３に割り当て、
ｐ３の評価尺度で評価値が最大となる区間が［Ｒ２、１］である場合には、ｐ１に［Ｌ12、Ｒ１］を、ｐ２に［０、Ｌ12］、ｐ３に［Ｒ２、１］を割り当てた上、ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求して、結果をｐ３から受信し、ｐ１に対して、当該３分割した各区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ１から受信し、ｐ１にはこの区間を割り当て、ｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をｐ２から受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当てる。
【発明の効果】
【００２６】
本発明の３者間の３者間の公平分割装置、３者間の公平分割方法、及びそのプログラムによれば、各者に各自の評価尺度に基づく評価結果を申告させ、各者の評価尺度のみにより公平に役割を決定するため、分割結果の取り分だけでなく役割の割り当てについても公平に分割することが可能となる。
【図面の簡単な説明】
【００２７】
【図１】３者間の公平分割装置１００の機能構成例を示すブロック図。
【図２】３者間の公平分割装置１００のＬ１＝Ｌ２＝Ｌ３、Ｌ１＝Ｌ２≠Ｌ３の場合の処理フロー例を示す図。
【図３】３者間の公平分割装置１００のＬ１＜Ｌ２＜Ｌ３の場合の処理フロー例を示す図。
【発明を実施するための形態】
【００２８】
図１に本発明の３者間の公平分割装置１００の機能構成例を示すブロック図を、図２にＬ１＝Ｌ２＝Ｌ３、Ｌ１＝Ｌ２≠Ｌ３の場合の処理フロー例を、図３にＬ１＜Ｌ２＜Ｌ３の場合の処理フロー例をそれぞれ示す。
【００２９】
本発明の３者間の公平分割装置１００は、区間［０、１］で表される資源を３台の端末間で公平に割り当てる装置であり、割当制御部１１０と３台の端末１２１、１２２，１２３とを備える。
【００３０】
割当制御部１１０は、区間［０、１］で表される資源を３台の端末間で公平に割り当てるため、各端末との間で情報の授受を行うなど以下で説明する処理をつかさどる。
【００３１】
３台の端末１２１、１２２、１２３は、それぞれ独自の所定の評価尺度を有し、割当制御部１１０からの要求に応じて割り当てに必要な情報を割当制御部１１０に送信する。なお、以下の説明では途中から各端末をｐ１、ｐ２、ｐ３と表現しているが、これは本発明においては、具体的な端末１２１、１２２、１２３のいずれかから応答されるＬ１、Ｌ２、Ｌ３間の大小関係及びＲ１、Ｒ２、Ｒ３間の大小関係に応じて、各端末の役割を加味した抽象的な端末ｐ１、ｐ２、ｐ３を割り当てるという形をとっているためである（すなわち、ｐ１とＬ１とＲ１との間、ｐ２とＬ２とＲ２との間、ｐ３とＬ３とＲ３との間にはそれぞれ対応関係があるが、それらと具体的な端末１２１、１２２、１２３との間には対応関係は無い）。
【００３２】
本発明の３者間の公平分割装置１００においては、割当制御部１１０と３台の端末１２１、１２２、１２３との間で、以下のように情報の送受を行うことで結果及び役割分担の双方について公平な分割を実現する。
【００３３】
まず、割当制御部１１０は、３台の端末１２１、１２２、１２３に対して、各端末がそれぞれの評価尺度により上記区間［０、１］を０から正方向を見て１／３に切ったポイントＬ１、Ｌ２、Ｌ３を送信するよう要求する。各端末はその要求に応じてＬ１、Ｌ２、Ｌ３を送信し、割当制御部１１０にてそれらを受信する（Ｓ１）。ここで、各端末から割当制御部に対し情報を送信するにあたっては、３者間での役割分担の公平性を担保するため、相互に情報が漏洩しないように構成することが望ましい。そこで例えば、各端末と割当制御部との間の通信を暗号化したり、コミットなどの暗号学的手法（参考文献１、２参照）を用いたりすることが考えられる。
〔参考文献１〕岡本龍明、山本博資、「現代暗号」、産業図書、1997、p.142-145
〔参考文献２〕Gilles Brassard, David Chaum, Claude Crepeau, "Minimum disclosure proofs knowledge", Journal of Computer and System Sciences, 1988, Volume 37, Issue 2, p.156-189
【００３４】
各端末からＬ１、Ｌ２、Ｌ３を受信した割当制御部１１０は、Ｌ１、Ｌ２、Ｌ３の大小関係に応じて、以下の処理を行う。
(1)Ｌ１＝Ｌ２＝Ｌ３＝Ｌ123である場合
この場合、割当制御部１１０は３台の端末１２１、１２２、１２３に対して、各端末がそれぞれの評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ１、Ｒ２、Ｒ３を送信するよう要求し、各端末はその要求に応じてＲ１、Ｒ２、Ｒ３を送信し、割当制御部１１０はそれらを受信する（Ｓ２）。各端末からＲ１、Ｒ２、Ｒ３を受信した割当制御部１１０は、Ｒ１、Ｒ２、Ｒ３の大小関係に応じて以下の処理を行う。
【００３５】
(i)Ｒ１＝Ｒ２＝Ｒ３＝Ｒ123である場合
割当制御部１１０は、区間［０、Ｌ123］、［Ｌ123、Ｒ123］、［Ｒ123、１］のそれぞれいずれかを上記３台の端末に割り当てる（Ｓ３）。
【００３６】
(ii)Ｒ１＝Ｒ２＝Ｒ12≠Ｒ３である場合
割当制御部１１０はＲ12＜Ｒ３なら、Ｒ３を送信した端末ｐ３に区間［Ｒ12、１］を、残りの２台の端末ｐ１、ｐ２に区間［０、Ｌ123］、［Ｌ123、Ｒ12］のそれぞれいずれかを割り当て、Ｒ12＞Ｒ３なら、ｐ３に区間［Ｌ123、Ｒ12］を割り当て、残りの２台の端末ｐ１、ｐ２に区間［０、Ｌ123］、［Ｒ12、１］のそれぞれいずれかを割り当てる（Ｓ４）。
【００３７】
(iii)Ｒ１＜Ｒ２＜Ｒ３である場合
割当制御部１１０は、Ｒ２を送信した端末ｐ２による切り方で３分割し、Ｒ１を送信した端末ｐ１に区間［Ｌ123、Ｒ２］を、ｐ２に区間［０、Ｌ123］を、Ｒ３を送信した端末ｐ３に区間［Ｒ２、１］を割り当てる（Ｓ５）。
(2)Ｌ１＝Ｌ２＝Ｌ12≠Ｌ３である場合
この場合、割当制御部１１０は、Ｌ１、Ｌ２を送信した２台の端末ｐ１、ｐ２に対して、ｐ１、ｐ２がそれぞれ各自の上記評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ１、Ｒ２を送信するよう要求して、各端末はその要求に応じてＲ１、Ｒ２を送信し、割当制御部１１０はそれらを受信する（Ｓ６）。各端末からＲ１、Ｒ２を受信した割当制御部１１０は、Ｒ１、Ｒ２の大小関係に応じて以下の処理を行う。
【００３８】
(i)Ｒ１＝Ｒ２＝Ｒ12である場合
割当制御部１１０は、残りの端末ｐ３に対して、当該３分割された区間［０、Ｌ12］、［Ｌ12、Ｒ12］、［Ｒ12、１］のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、ｐ３はその要求に応じて選択結果を送信し、割当制御部１１０はそれを受信する。そして、割当制御部１１０は、ｐ３にはｐ３が選択した区間を割り当て、ｐ１、ｐ２には残りの２つの区間のそれぞれいずれかを割り当てる（Ｓ７）。
【００３９】
(ii)Ｒ１＜Ｒ２である場合
割当制御部１１０はまず、残りの端末ｐ３に対して、区間［０、Ｌ12］、［Ｌ12、Ｒ１］、［Ｒ２、１］のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、ｐ３はその要求に応じて選択結果を送信し、割当制御部１１０はそれを受信する（Ｓ８）。この場合、いずれの区間の評価値が最大になるかにより、割当制御部１１０はそれぞれ以下の処理を行う。
【００４０】
(a)ｐ３の評価尺度で評価値が最大となる区間が［０、Ｌ12］である場合
割当制御部１１０は、ｐ１に［Ｌ12、Ｒ１］を、ｐ２に［Ｒ２、１］を、ｐ３に［０、Ｌ12］を割り当てた上（Ｓ９）、ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求し、ｐ３はその要求に応じて結果を送信し、割当制御部１１０はそれを受信する。続いて、割当制御部１１０はｐ１に対し、当該３分割された各区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、ｐ１はその要求に応じて選択結果を送信する。割当制御部１１０はそれを受信し、ｐ１にこの区間を割り当てる。続いて、割当制御部１１０はｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、ｐ２はその要求に応じて選択結果を送信する。割当制御部１１０はそれを受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当てる（Ｓ１０）。
【００４１】
(b)ｐ３の評価尺度で評価値が最大となる区間が［Ｌ12、Ｒ１］である場合
割当制御部１１０は、ｐ１に［０、Ｌ12］を、ｐ２に［Ｒ２、１］、ｐ３に［Ｌ12、Ｒ１］を割り当てた上（Ｓ１１）、ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求して、ｐ３はその要求に応じて結果を送信する。割当制御部１１０はそれを受信し、ｐ２に対して、当該３分割した各区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求する。ｐ２はその要求に応じて選択結果を送信し、割当制御部１１０はそれをｐ２から受信して、ｐ２にはこの区間を割り当てる。続いて、割当制御部１１０はｐ１に対して、残りの２区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、ｐ１はその要求に応じて選択結果を送信する。割当制御部１１０はそれを受信し、ｐ１にはこの区間を割り当て、残った区間をｐ３に割り当てる（Ｓ１２）。
【００４２】
(c)ｐ３の評価尺度で評価値が最大となる区間が［Ｒ２、１］である場合
割当制御部１１０は、ｐ１に［Ｌ12、Ｒ１］を、ｐ２に［０、Ｌ12］、ｐ３に［Ｒ２、１］を割り当てた上（Ｓ１３）、ｐ３に対して、区間［Ｒ１、Ｒ２］をｐ３の評価尺度で３分割した結果を送信するよう要求する。ｐ３はその要求に応じて結果を送信し、割当制御部１１０はそれを受信する。続いて、割当制御部１１０はｐ１に対して、当該３分割した各区間のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、ｐ１はその要求に応じて選択結果を送信する。割当制御部１１０はそれを受信し、ｐ１にはこの区間を割り当てる。続いて、割当制御部１１０はｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、ｐ２はその要求に応じて選択結果を送信する。割当制御部１１０は、それを受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当てる（Ｓ１４）。
(3)Ｌ１＜Ｌ２＜Ｌ３である場合
【００４３】
この場合、背景技術に示した３者無羨望分割のプロトコルにおいて、例えば、ｐ３をplayer 1、ｐ２をplayer 2、ｐ１をplayer 3にそれぞれあてはめて処理を行う。このあてはめは、この組み合わせが唯一ということではないが、組み合わせによってはplayerが正しく申告しないことが有利になるという問題点を持つ場合もあるため留意が必要である。以下、ｐ３をplayer 1、ｐ２をplayer 2、ｐ１をplayer 3にそれぞれあてはめた場合の処理を例示する。
【００４４】
割当制御部１１０は、Ｌ３を送信した端末ｐ３に対して、ｐ３の評価尺度により上記区間［０、１］を１から負方向を見て１／３に切ったポイントＲ３を送信するよう要求する。ｐ３はその要求に応じＲ３を送信し、割当制御部１１０はそれを受信する（Ｓ１５）。
【００４５】
続いて割当制御部１１０は、Ｌ２を送信した端末ｐ２に対して、区間［０、Ｌ３］、［Ｌ３、Ｒ３］、［Ｒ３、１］のうちｐ２の評価尺度による評価値が最大の区間が１つだけか、２つ以上あるかを送信するよう要求する。ｐ２はその要求に応じて評価結果を送信し、割当制御部１１０はその評価結果を受信する（Ｓ１６）。割当制御部１１０は、ｐ２による評価結果に応じ、次のように場合分けして処理を行う。
【００４６】
(i)ｐ２の評価尺度による評価値が最大の区間が２つ以上ある場合
割当制御部１１０は、Ｌ１を送信した端末ｐ１に対して、区間［０、Ｌ３］、［Ｌ３、Ｒ３］、［Ｒ３、１］のうちｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、ｐ１はその要求に応じて選択結果を送信する。割当制御部１１０はその選択結果を受信し、ｐ１にはこの区間を割り当てる。続いてｐ２に対して、残りの２区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、ｐ２はその要求に応じて選択結果を送信する。割当制御部１１０はその選択結果を受信し、ｐ２にはこの区間を割り当て、残った区間をｐ３に割り当てる（Ｓ１７）。
【００４７】
(ii)ｐ２の評価尺度による評価値が最大の区間αが１つの場合
割当制御部１１０はｐ２に対して、ｐ２の評価尺度で評価値が２番目の区間と同じになるようにαの一部である区間ｘを切り取りこれを送信するよう要求し、ｐ２はその要求に応じて区間ｘを送信し、割当制御部１１０はそれを受信する（Ｓ１８）。
【００４８】
続いて、割当制御部１１０はｐ１に対して、区間α−ｘとその他２つの区間のうち、ｐ１の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、ｐ１はその要求に応じて選択結果を送信する。割当制御部１１０はそれを受信し、ｐ１にはこの区間を割り当てる。ｐ１に区間α−ｘを割り当てた場合にはｐ２に対して、その他２つの区間のうちｐ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求する。ｐ２はその要求に応じて選択結果をｐ２から受信し、ｐ２にこの区間を、ｐ３に残った区間を割り当てる。一方、ｐ１に区間α−ｘを割り当てなかった場合にはｐ２に区間α−ｘを、ｐ３に残った区間を割り当てる（Ｓ１９）。
【００４９】
続いて、割当制御部１１０は、区間α−ｘが割り当てられなかったｐ１又はｐ２いずれかの端末（以下、「Ｐ１」という。）に対して、区間ｘをＰ１の評価尺度で３分割した結果を送信するよう要求し、Ｐ１はその要求に応じて結果を送信する。割当制御部１１０はそれを受信し、区間α−ｘが割り当てられたｐ１又はｐ２いずれかの端末（以下、「Ｐ２」という。）に対して、Ｐ１により３分割された各区間のうちＰ２の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求する。Ｐ２はその要求に応じて選択結果を送信し、割当制御部１１０はそれを受信し、Ｐ２にはこの区間を割り当てる。続いて、割当制御部１１０はｐ３に対して、残りの２区間のうちｐ３の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、ｐ３はその要求に応じて選択結果を送信する。割当制御部１１０はその選択結果を受信し、ｐ３にはこの区間を割り当て、残った区間をＰ１に割り当てる（Ｓ２０）。
【００５０】
以上のように、本発明の３者間の３者間の公平分割装置、３者間の公平分割方法、及びそのプログラムによれば、各者に各自の評価尺度に基づく評価結果を申告させ、各者の評価尺度のみにより公平に役割を決定するため、分割結果の取り分だけでなく役割の割り当てについても公平に分割することが可能となる。
【００５１】
なお、上記の実施例では割当制御部と各端末とによるサーバ−クライアント型の構成を示したが、割当制御部の機能を各端末に分散して各端末のみにより構成してもよい。この場合、各端末間の通信には参考文献１、２に示されるコミットなどの暗号学的手法により、例えば各playerが値を送る際に自分だけが復号化できる暗号化を行って送り、全員が受信したのち、復号化した結果を、その復号化の正しさの証明をつけた形で送ることで端末間での情報の漏洩を防止することが考えられる。
【００５２】
上記の３者間の公平分割装置をコンピュータによって実現する場合、割当制御部が担う処理機能はプログラムによって記述される。そしてパソコンや携帯端末上で、入力手段や各種記憶手段とＣＰＵとのデータのやりとりを通じてこのプログラムを実行することにより、ハードウェアとソフトウェアが協働し、上記処理機能がコンピュータ上で実現されて本発明の３者間の公平分割装置の作用効果を奏する。なおこの場合、処理機能の少なくとも一部をハードウェア的に実現することとしてもよい。また、上記の各種処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【図１】
2011128860.tif 000003
【図２】
2011128860.tif 000004
【図３】
2011128860.tif 000005