3者間の公平分割装置、3者間の公平分割方法、及びそのプログラム
【課題】分割結果の取り分だけでなく、役割の割り当てについても公平に分割することが可能な3者間の公平分割装置、3者間の公平分割方法、及びプログラムを提供する。
【解決手段】割当制御部が、分割対象の資源について3台の端末各々の評価尺度により3分割した各ポイントを当該3台の端末から取得し、当該各ポイントの相互関係により当該3台の端末の役割分担を決定した上で、当該3台の端末に対し資源の無羨望分割割り当てを行う。
【解決手段】割当制御部が、分割対象の資源について3台の端末各々の評価尺度により3分割した各ポイントを当該3台の端末から取得し、当該各ポイントの相互関係により当該3台の端末の役割分担を決定した上で、当該3台の端末に対し資源の無羨望分割割り当てを行う。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、経済社会における資源の3者間での公平分割に関し、特に、結果だけでなく役割分担も公平に割り当てるための3者間の公平分割装置、3者間の公平分割方法、及びそのプログラムに関する。
【背景技術】
【0002】
ケーキの分割や領土の割り当てなど、(i)区間[0、1]間に存在し、その間の任意の箇所で分割可能な領域Xに対し、(ii)いかなる空でないY⊂Xに対しても各player iは0でない価値μi(Y)>0を持ち、(iii)価値は足し算で計算される、すなわち重なりを持たない2つの領域X1とX2に対するplayer iの価値がμi(X1)、μi(X2)であるとき、μi(X1∪X2)=μi(X1)+μi(X2)が成立するXを3者間(player 1〜3)で分割する分割方法について、以下のものが考えられている。
【0003】
step 1:player 1が自分にとって価値が同じになるようにXを3つの部分に分割する。
step 2:player 2は、player 1が分割した3つの部分を自分の価値尺度で価値の高いものから並べ、それぞれの価値をa、b、cとする。このとき、player 1にとってはa=b=c、player 2にとってはa≧b≧cである。
【0004】
step 3:もし、a、b、cのうちでplayer 2にとって価値が最大のものが2つ以上あれば(a=b≧cのとき)、player 3、player 2の順に、残っている中から自分の価値が最大のものを選び、player 1は残りを得て、分割を終了する。
step 4:一方、a、b、cのうちでplayer 2にとって価値が最大のものが1つのとき(a>b≧cのとき)は、player 2は自分にとって価値が最大であるaの一部を切り取って、価値が2番目に大きいbと同じになるようにする。このとき、切り取った部分の価値をL、Lを切り取った後のaの価値をa´とおく(つまり、player 2にとって、a´=b≧c、a´=a−L)。
【0005】
step 5:a´、b、cについて、player 3、player 2の順に、残っている中から自分の価値が最大のものを選び、player 1は残りを得る。ここで、player 3がa´を選択しない場合には、player 2はa´を選択する(つまり、player 2かplayer 3のいずれかがa´を選択している)。
step 6:a´を選択したplayerをplayer B、そうでない方をplayer Aとし、player Aが自分にとって価値が同じになるようにLを3つの部分に分割する。
step 7:player B、player 1の順に、分割されたLの各部分のうち残っている中から自分にとって価値が最大となるものを選択し、player Aは残りを得て、分割を終了する。
【0006】
以上の手法により、各player iが得た結果Xiは無羨望、すなわちμi(Xi)≧μi(Xj)がすべてのi、jに対して成立し、自分の取り分を他のplayerの取り分と交換しようと思わない。
【先行技術文献】
【非特許文献】
【0007】
【非特許文献1】Jack Robertson, William Webb, "Cake-Cutting Algorithms: Be Fair If you Can", A K Peters Ltd, 1998, p.12-13
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかし上記の手法では、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」という割り当てとを比べると後者が有利である。その理由を場合分けして説明する。
【0009】
〔case 1〕party yがplayer 2のとき、party yが分割部分の一部を切り取らない場合
〔case 1-1〕party xがplayer 2で、party xが分割部分の一部を切り取る場合
party xは、step 4においてaの一部を切り取り、価値をa´(=b)にする。そして、step 5の選択において、party xは価値がa´である部分を得る。切り取った部分の価値Lはa−a´であるが、party xにはこれが3つに分割されて与えられるため、party xはどのようにしても合計aの価値を得ることができない。
これに対し、party yがplayer 2、party xがplayer 3のときには、party xはstep 3において1番目の選択権を有するため、aの価値を得ることができる。
従って、このケースではplayer 3になる方が有利である。
【0010】
〔case 1-2〕party xがplayer 2で、party xが分割部分の一部を切り取らない場合
party xはstep 3において2番目の選択権を有するため、a=b≧cであることから、aの価値を得ることができる。
一方、party yがplayer 2、party xがplayer 3のときには、party xはstep 3において1番目の選択権を有するため、aの価値を得ることができる。
従って、このケースではいずれのplayerになっても有利不利は無い。
【0011】
〔case 2〕party yがplayer 2のとき、party yが分割部分から部分Mを切り取る場合
〔case 2-1〕party xがplayer 2の場合にもparty yと同じ分割部分から部分M´を切り取る場合(party xにとって価値が最大である分割部分とparty yにとって価値が最大である分割部分が同じである場合)
〔case 2-1-1〕party xの方が物理的に大きい部分を切り取る場合(M´>Mの場合)
【0012】
party xにとって価値が最大である分割部分の価値をa、部分Mの価値をL、部分M´の価値をL´(>L)とおく。
party xがplayer 2(party yがplayer 3)の場合、step 4においてLより大きいL´が切り取られる。そのため、party yにとってはL´を切り取っていない分割部分の方が価値が高いことから、step 5においてparty yはそちらを選ぶ。従って、party xはa−L´を得る。更に、step 6でparty yが3分割したL´について、step 7でparty xが1番目の選択権を有するため、少なくともL´/3を得る。従って、party xが得る価値の合計は「少なくともa−2L´/3」である。
【0013】
これに対し、party xがplayer 3(party yがplayer 2)の場合、step 4においてL´より小さいLが切り取られる。そのため、party xにとってはL´を切り取った分割部分の方が価値が高いことから、step 5においてparty xはa−Lを得る。更に、step 6でparty yが3分割したLについて、step 7でparty xが1番目の選択権を有するため、少なくともL/3を得る。従って、party xが得る価値の合計は「少なくともa−2L/3」である。
そしてL´>Lなので、「少なくともこれだけはもらえる価値」を比較すると、このケースでもplayer 3になる方が有利である。
【0014】
〔case 2-1-2〕party xの方が物理的に小さい部分を切り取る場合(M´<Mの場合)
party xにとって価値が最大である分割部分の価値をa、部分Mの価値をL、部分M´の価値をL´(<L)とおく。このとき、party xにとってL´を切り取る前に2番目に価値の高い部分の価値はa−L´である。
party xがplayer 2(party yがplayer 3)の場合、step 4においてLより小さいL´が切り取られる。そのため、party yにとってはLを切り取った分割部分の方が価値が高いことから、step 5においてparty yはそちらを選ぶ。従って、party xはa−L´を得る。更に、step 6でparty xが3分割したL´について、step 7でL´/3を得る。従って、party xが得る価値の合計は、a−L´+L´/3である。
【0015】
これに対し、party xがplayer 3(party yがplayer 2)の場合、step 4においてL´より大きいLが切り取られる。そのため、party xにとってはL´を切り取っていない分割部分の方が価値が高いことから、step 5においてparty xはa−L´を得る。更に、step 6でparty xが3分割したLについて、step 7でL/3を得る。従って、party xが得る価値の合計は、a−L´+L/3である。
そして、L´<Lなので、このケースでもplayer 3になる方が有利である。
【0016】
〔case 2-1-3〕party xとparty yが同じ大きさの部分を切り取る場合(M´=Mの場合)
party xにとって価値が最大である分割部分の価値をa、部分Mの価値をL、部分M´の価値をL´(=L)とおく。
party xがplayer 2(party yがplayer 3)の場合、step 4においてL´が切り取られ、step 5においてparty yはL´を切り取った残りを選び、party xはL´を切り取る前に2番目に価値の高い部分であるa−L´を得る。更に、step 6でparty xが3分割したL´について、step 7でL´/3を得る。従って、party xが得る価値の合計は、a−L´+L´/3である。
【0017】
これに対し、party xがplayer 3(party yがplayer 2)の場合、step 4においてLが切り取られ、step 5においてparty xはa−Lを得る。更に、step 6でparty yが3分割したLについて、step 7でparty xは1番目の選択権を有するため、少なくともL/3を得る。従って、party xが得る価値の合計は、「少なくとも」a−L+L/3である。
そして、L´=Lなので、このケースでもplayer 3になる方が有利である。
【0018】
〔case 2-2〕party xがplayer 2の場合で、party yとは異なる分割部分から部分M´を切り取る場合(party xにとって価値が最大である分割部分とparty yにとって価値が最大である分割部分が異なる場合)
party yがplayer 2の時のparty yにとって価値が最大の分割部分のparty xによる価値をa´、party xによる部分Mの価値をL、party xにとって価値が最大の分割部分のparty xによる価値をa(>a´)、party xによる部分M´の価値をL´とする。
party xがplayer 2の場合、party yはstep 5において、L´を取り除いた残りは自分にとって価値が最大の分割部分に係るものでないため選択しない。そのため、party xはa−L´を得る。更に、step 6でparty yが3分割したL´について、step 7でparty xは1番目の選択権を有するが、最大でもL´未満である。従って、party xが得る価値の合計は、a未満である。
【0019】
これに対し、party xがplayer 3の場合、自分にとって最大と思われる部分を全て得ることができる。すなわち、step 5においてaを、step 6においてL/3を得る。従って、party xが得る価値の合計は、a+L/3である。
よって、この場合においてもplayer 3になる方が有利である。
【0020】
〔case 2-3〕party xがplayer 2で、party xが分割部分の一部を切り取らない場合
party xにとって価値が最大の分割部分の価値をa、部分Mの価値をLとする。
party xがplayer 2の場合、価値aの分割部分が少なくとも2つあるため、party xはaを得る。
一方、party yがplayer 2の場合、party xはstep 5においてaを、step 6においてL/3を得る。従って、party xが得る価値の合計は、a+L/3である。
よって、この場合においてもplayer 3になる方が有利である。
【0021】
以上のように、player 3となる方が「最低限得られる量」において、常に同じかよい結果を得る。
【0022】
従って、実際に実行する場合には、3者のいずれがそれぞれplayer 1、2、3の役割を担うかを何らかの手段で決定する必要がある。役割の割り当てについて合意が行われた後にこの手法に従って分割を行えば、その分割結果の取り分について他のplayerと交換しようとは思わないが、そもそも役割によって上記のように有利不利が存在するためplayer間で役割交換の羨望が生じ、公平な結果の前提である役割の割り当てについての合意が取れない。それゆえ、この手法で公平な分割を行うことは実質的に不可能である。
【0023】
本発明は、分割結果の取り分だけでなく、役割の割り当てについても公平に分割することが可能な3者間の公平分割装置、3者間の公平分割方法、及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【0024】
本発明の3者間の公平分割装置は、割当制御部と3台の端末とを備える。
割当制御部は、区間[0、1]で表される資源を3台の端末間で公平に割り当てるための制御を行う。
3台の端末は、それぞれ独自の所定の評価尺度を有し、上記割当制御部からの要求に応じて割り当てに必要な情報を当該割当制御部に送信する。
【0025】
そして、割当制御部は、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を0から正方向を見て1/3に切ったポイントL1、L2、L3を送信するよう要求して、結果を各端末から受信し、
L1=L2=L3=L123である場合、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2、R3を送信するよう要求して、結果を各端末から受信し、
R1=R2=R3=R123である場合には、区間[0、L123]、[L123、R123]、[R123、1]のそれぞれいずれかを上記3台の端末に割り当て、
R1=R2=R12≠R3である場合には、R12<R3なら、R3を送信した端末p3に区間[R12、1]を、残りの2台の端末p1、p2に区間[0、L123]、[L123、R12]のそれぞれいずれかを割り当て、R12>R3なら、p3に区間[L123、R12]を割り当て、残りの2台の端末p1、p2に区間[0、L123]、[R12、1]のそれぞれいずれかを割り当て、
R1<R2<R3である場合には、R2を送信した端末p2による切り方で3分割し、R1を送信した端末p1に区間[L123、R2]を、p2には区間[0、L123]を、R3を送信した端末p3に区間[R2、1]を割り当て、
L1=L2=L12≠L3である場合、
L1、L2を送信した2台の端末p1、p2に対して、p1、p2がそれぞれ各自の上記評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2を送信するよう要求して、結果を各端末から受信し、
R1=R2=R12である場合には、残りの端末p3に対して、当該3分割された区間[0、L12]、[L12、R12]、[R12、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、p3にはp3が選択した区間を割り当て、p1、p2には残りの2つの区間のそれぞれいずれかを割り当て、
R1<R2である場合には、まず、残りの端末p3に対して、区間[0、L12]、[L12、R1]、[R2、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、
p3の評価尺度で評価値が最大となる区間が[0、L12]である場合には、p1に[L12、R1]を、p2に[R2、1]を、p3に[0、L12]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対し、当該3分割された各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当て、
p3の評価尺度で評価値が最大となる区間が[L12、R1]である場合には、p1に[0、L12]を、p2に[R2、1]、p3に[L12、R1]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p2に対して、当該3分割した各区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、p1に対して、残りの2区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、残った区間をp3に割り当て、
p3の評価尺度で評価値が最大となる区間が[R2、1]である場合には、p1に[L12、R1]を、p2に[0、L12]、p3に[R2、1]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対して、当該3分割した各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる。
【発明の効果】
【0026】
本発明の3者間の3者間の公平分割装置、3者間の公平分割方法、及びそのプログラムによれば、各者に各自の評価尺度に基づく評価結果を申告させ、各者の評価尺度のみにより公平に役割を決定するため、分割結果の取り分だけでなく役割の割り当てについても公平に分割することが可能となる。
【図面の簡単な説明】
【0027】
【図1】3者間の公平分割装置100の機能構成例を示すブロック図。
【図2】3者間の公平分割装置100のL1=L2=L3、L1=L2≠L3の場合の処理フロー例を示す図。
【図3】3者間の公平分割装置100のL1<L2<L3の場合の処理フロー例を示す図。
【発明を実施するための形態】
【0028】
図1に本発明の3者間の公平分割装置100の機能構成例を示すブロック図を、図2にL1=L2=L3、L1=L2≠L3の場合の処理フロー例を、図3にL1<L2<L3の場合の処理フロー例をそれぞれ示す。
【0029】
本発明の3者間の公平分割装置100は、区間[0、1]で表される資源を3台の端末間で公平に割り当てる装置であり、割当制御部110と3台の端末121、122,123とを備える。
【0030】
割当制御部110は、区間[0、1]で表される資源を3台の端末間で公平に割り当てるため、各端末との間で情報の授受を行うなど以下で説明する処理をつかさどる。
【0031】
3台の端末121、122、123は、それぞれ独自の所定の評価尺度を有し、割当制御部110からの要求に応じて割り当てに必要な情報を割当制御部110に送信する。なお、以下の説明では途中から各端末をp1、p2、p3と表現しているが、これは本発明においては、具体的な端末121、122、123のいずれかから応答されるL1、L2、L3間の大小関係及びR1、R2、R3間の大小関係に応じて、各端末の役割を加味した抽象的な端末p1、p2、p3を割り当てるという形をとっているためである(すなわち、p1とL1とR1との間、p2とL2とR2との間、p3とL3とR3との間にはそれぞれ対応関係があるが、それらと具体的な端末121、122、123との間には対応関係は無い)。
【0032】
本発明の3者間の公平分割装置100においては、割当制御部110と3台の端末121、122、123との間で、以下のように情報の送受を行うことで結果及び役割分担の双方について公平な分割を実現する。
【0033】
まず、割当制御部110は、3台の端末121、122、123に対して、各端末がそれぞれの評価尺度により上記区間[0、1]を0から正方向を見て1/3に切ったポイントL1、L2、L3を送信するよう要求する。各端末はその要求に応じてL1、L2、L3を送信し、割当制御部110にてそれらを受信する(S1)。ここで、各端末から割当制御部に対し情報を送信するにあたっては、3者間での役割分担の公平性を担保するため、相互に情報が漏洩しないように構成することが望ましい。そこで例えば、各端末と割当制御部との間の通信を暗号化したり、コミットなどの暗号学的手法(参考文献1、2参照)を用いたりすることが考えられる。
〔参考文献1〕岡本龍明、山本博資、「現代暗号」、産業図書、1997、p.142-145
〔参考文献2〕Gilles Brassard, David Chaum, Claude Crepeau, "Minimum disclosure proofs knowledge", Journal of Computer and System Sciences, 1988, Volume 37, Issue 2, p.156-189
【0034】
各端末からL1、L2、L3を受信した割当制御部110は、L1、L2、L3の大小関係に応じて、以下の処理を行う。
(1)L1=L2=L3=L123である場合
この場合、割当制御部110は3台の端末121、122、123に対して、各端末がそれぞれの評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2、R3を送信するよう要求し、各端末はその要求に応じてR1、R2、R3を送信し、割当制御部110はそれらを受信する(S2)。各端末からR1、R2、R3を受信した割当制御部110は、R1、R2、R3の大小関係に応じて以下の処理を行う。
【0035】
(i)R1=R2=R3=R123である場合
割当制御部110は、区間[0、L123]、[L123、R123]、[R123、1]のそれぞれいずれかを上記3台の端末に割り当てる(S3)。
【0036】
(ii)R1=R2=R12≠R3である場合
割当制御部110はR12<R3なら、R3を送信した端末p3に区間[R12、1]を、残りの2台の端末p1、p2に区間[0、L123]、[L123、R12]のそれぞれいずれかを割り当て、R12>R3なら、p3に区間[L123、R12]を割り当て、残りの2台の端末p1、p2に区間[0、L123]、[R12、1]のそれぞれいずれかを割り当てる(S4)。
【0037】
(iii)R1<R2<R3である場合
割当制御部110は、R2を送信した端末p2による切り方で3分割し、R1を送信した端末p1に区間[L123、R2]を、p2に区間[0、L123]を、R3を送信した端末p3に区間[R2、1]を割り当てる(S5)。
(2)L1=L2=L12≠L3である場合
この場合、割当制御部110は、L1、L2を送信した2台の端末p1、p2に対して、p1、p2がそれぞれ各自の上記評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2を送信するよう要求して、各端末はその要求に応じてR1、R2を送信し、割当制御部110はそれらを受信する(S6)。各端末からR1、R2を受信した割当制御部110は、R1、R2の大小関係に応じて以下の処理を行う。
【0038】
(i)R1=R2=R12である場合
割当制御部110は、残りの端末p3に対して、当該3分割された区間[0、L12]、[L12、R12]、[R12、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、p3はその要求に応じて選択結果を送信し、割当制御部110はそれを受信する。そして、割当制御部110は、p3にはp3が選択した区間を割り当て、p1、p2には残りの2つの区間のそれぞれいずれかを割り当てる(S7)。
【0039】
(ii)R1<R2である場合
割当制御部110はまず、残りの端末p3に対して、区間[0、L12]、[L12、R1]、[R2、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、p3はその要求に応じて選択結果を送信し、割当制御部110はそれを受信する(S8)。この場合、いずれの区間の評価値が最大になるかにより、割当制御部110はそれぞれ以下の処理を行う。
【0040】
(a)p3の評価尺度で評価値が最大となる区間が[0、L12]である場合
割当制御部110は、p1に[L12、R1]を、p2に[R2、1]を、p3に[0、L12]を割り当てた上(S9)、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求し、p3はその要求に応じて結果を送信し、割当制御部110はそれを受信する。続いて、割当制御部110はp1に対し、当該3分割された各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p1はその要求に応じて選択結果を送信する。割当制御部110はそれを受信し、p1にこの区間を割り当てる。続いて、割当制御部110はp2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、p2はその要求に応じて選択結果を送信する。割当制御部110はそれを受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる(S10)。
【0041】
(b)p3の評価尺度で評価値が最大となる区間が[L12、R1]である場合
割当制御部110は、p1に[0、L12]を、p2に[R2、1]、p3に[L12、R1]を割り当てた上(S11)、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、p3はその要求に応じて結果を送信する。割当制御部110はそれを受信し、p2に対して、当該3分割した各区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求する。p2はその要求に応じて選択結果を送信し、割当制御部110はそれをp2から受信して、p2にはこの区間を割り当てる。続いて、割当制御部110はp1に対して、残りの2区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p1はその要求に応じて選択結果を送信する。割当制御部110はそれを受信し、p1にはこの区間を割り当て、残った区間をp3に割り当てる(S12)。
【0042】
(c)p3の評価尺度で評価値が最大となる区間が[R2、1]である場合
割当制御部110は、p1に[L12、R1]を、p2に[0、L12]、p3に[R2、1]を割り当てた上(S13)、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求する。p3はその要求に応じて結果を送信し、割当制御部110はそれを受信する。続いて、割当制御部110はp1に対して、当該3分割した各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p1はその要求に応じて選択結果を送信する。割当制御部110はそれを受信し、p1にはこの区間を割り当てる。続いて、割当制御部110はp2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p2はその要求に応じて選択結果を送信する。割当制御部110は、それを受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる(S14)。
(3)L1<L2<L3である場合
【0043】
この場合、背景技術に示した3者無羨望分割のプロトコルにおいて、例えば、p3をplayer 1、p2をplayer 2、p1をplayer 3にそれぞれあてはめて処理を行う。このあてはめは、この組み合わせが唯一ということではないが、組み合わせによってはplayerが正しく申告しないことが有利になるという問題点を持つ場合もあるため留意が必要である。以下、p3をplayer 1、p2をplayer 2、p1をplayer 3にそれぞれあてはめた場合の処理を例示する。
【0044】
割当制御部110は、L3を送信した端末p3に対して、p3の評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR3を送信するよう要求する。p3はその要求に応じR3を送信し、割当制御部110はそれを受信する(S15)。
【0045】
続いて割当制御部110は、L2を送信した端末p2に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp2の評価尺度による評価値が最大の区間が1つだけか、2つ以上あるかを送信するよう要求する。p2はその要求に応じて評価結果を送信し、割当制御部110はその評価結果を受信する(S16)。割当制御部110は、p2による評価結果に応じ、次のように場合分けして処理を行う。
【0046】
(i)p2の評価尺度による評価値が最大の区間が2つ以上ある場合
割当制御部110は、L1を送信した端末p1に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p1はその要求に応じて選択結果を送信する。割当制御部110はその選択結果を受信し、p1にはこの区間を割り当てる。続いてp2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、p2はその要求に応じて選択結果を送信する。割当制御部110はその選択結果を受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる(S17)。
【0047】
(ii)p2の評価尺度による評価値が最大の区間αが1つの場合
割当制御部110はp2に対して、p2の評価尺度で評価値が2番目の区間と同じになるようにαの一部である区間xを切り取りこれを送信するよう要求し、p2はその要求に応じて区間xを送信し、割当制御部110はそれを受信する(S18)。
【0048】
続いて、割当制御部110はp1に対して、区間α−xとその他2つの区間のうち、p1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p1はその要求に応じて選択結果を送信する。割当制御部110はそれを受信し、p1にはこの区間を割り当てる。p1に区間α−xを割り当てた場合にはp2に対して、その他2つの区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求する。p2はその要求に応じて選択結果をp2から受信し、p2にこの区間を、p3に残った区間を割り当てる。一方、p1に区間α−xを割り当てなかった場合にはp2に区間α−xを、p3に残った区間を割り当てる(S19)。
【0049】
続いて、割当制御部110は、区間α−xが割り当てられなかったp1又はp2いずれかの端末(以下、「P1」という。)に対して、区間xをP1の評価尺度で3分割した結果を送信するよう要求し、P1はその要求に応じて結果を送信する。割当制御部110はそれを受信し、区間α−xが割り当てられたp1又はp2いずれかの端末(以下、「P2」という。)に対して、P1により3分割された各区間のうちP2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求する。P2はその要求に応じて選択結果を送信し、割当制御部110はそれを受信し、P2にはこの区間を割り当てる。続いて、割当制御部110はp3に対して、残りの2区間のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p3はその要求に応じて選択結果を送信する。割当制御部110はその選択結果を受信し、p3にはこの区間を割り当て、残った区間をP1に割り当てる(S20)。
【0050】
以上のように、本発明の3者間の3者間の公平分割装置、3者間の公平分割方法、及びそのプログラムによれば、各者に各自の評価尺度に基づく評価結果を申告させ、各者の評価尺度のみにより公平に役割を決定するため、分割結果の取り分だけでなく役割の割り当てについても公平に分割することが可能となる。
【0051】
なお、上記の実施例では割当制御部と各端末とによるサーバ−クライアント型の構成を示したが、割当制御部の機能を各端末に分散して各端末のみにより構成してもよい。この場合、各端末間の通信には参考文献1、2に示されるコミットなどの暗号学的手法により、例えば各playerが値を送る際に自分だけが復号化できる暗号化を行って送り、全員が受信したのち、復号化した結果を、その復号化の正しさの証明をつけた形で送ることで端末間での情報の漏洩を防止することが考えられる。
【0052】
上記の3者間の公平分割装置をコンピュータによって実現する場合、割当制御部が担う処理機能はプログラムによって記述される。そしてパソコンや携帯端末上で、入力手段や各種記憶手段とCPUとのデータのやりとりを通じてこのプログラムを実行することにより、ハードウェアとソフトウェアが協働し、上記処理機能がコンピュータ上で実現されて本発明の3者間の公平分割装置の作用効果を奏する。なおこの場合、処理機能の少なくとも一部をハードウェア的に実現することとしてもよい。また、上記の各種処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【技術分野】
【0001】
本発明は、経済社会における資源の3者間での公平分割に関し、特に、結果だけでなく役割分担も公平に割り当てるための3者間の公平分割装置、3者間の公平分割方法、及びそのプログラムに関する。
【背景技術】
【0002】
ケーキの分割や領土の割り当てなど、(i)区間[0、1]間に存在し、その間の任意の箇所で分割可能な領域Xに対し、(ii)いかなる空でないY⊂Xに対しても各player iは0でない価値μi(Y)>0を持ち、(iii)価値は足し算で計算される、すなわち重なりを持たない2つの領域X1とX2に対するplayer iの価値がμi(X1)、μi(X2)であるとき、μi(X1∪X2)=μi(X1)+μi(X2)が成立するXを3者間(player 1〜3)で分割する分割方法について、以下のものが考えられている。
【0003】
step 1:player 1が自分にとって価値が同じになるようにXを3つの部分に分割する。
step 2:player 2は、player 1が分割した3つの部分を自分の価値尺度で価値の高いものから並べ、それぞれの価値をa、b、cとする。このとき、player 1にとってはa=b=c、player 2にとってはa≧b≧cである。
【0004】
step 3:もし、a、b、cのうちでplayer 2にとって価値が最大のものが2つ以上あれば(a=b≧cのとき)、player 3、player 2の順に、残っている中から自分の価値が最大のものを選び、player 1は残りを得て、分割を終了する。
step 4:一方、a、b、cのうちでplayer 2にとって価値が最大のものが1つのとき(a>b≧cのとき)は、player 2は自分にとって価値が最大であるaの一部を切り取って、価値が2番目に大きいbと同じになるようにする。このとき、切り取った部分の価値をL、Lを切り取った後のaの価値をa´とおく(つまり、player 2にとって、a´=b≧c、a´=a−L)。
【0005】
step 5:a´、b、cについて、player 3、player 2の順に、残っている中から自分の価値が最大のものを選び、player 1は残りを得る。ここで、player 3がa´を選択しない場合には、player 2はa´を選択する(つまり、player 2かplayer 3のいずれかがa´を選択している)。
step 6:a´を選択したplayerをplayer B、そうでない方をplayer Aとし、player Aが自分にとって価値が同じになるようにLを3つの部分に分割する。
step 7:player B、player 1の順に、分割されたLの各部分のうち残っている中から自分にとって価値が最大となるものを選択し、player Aは残りを得て、分割を終了する。
【0006】
以上の手法により、各player iが得た結果Xiは無羨望、すなわちμi(Xi)≧μi(Xj)がすべてのi、jに対して成立し、自分の取り分を他のplayerの取り分と交換しようと思わない。
【先行技術文献】
【非特許文献】
【0007】
【非特許文献1】Jack Robertson, William Webb, "Cake-Cutting Algorithms: Be Fair If you Can", A K Peters Ltd, 1998, p.12-13
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかし上記の手法では、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」という割り当てとを比べると後者が有利である。その理由を場合分けして説明する。
【0009】
〔case 1〕party yがplayer 2のとき、party yが分割部分の一部を切り取らない場合
〔case 1-1〕party xがplayer 2で、party xが分割部分の一部を切り取る場合
party xは、step 4においてaの一部を切り取り、価値をa´(=b)にする。そして、step 5の選択において、party xは価値がa´である部分を得る。切り取った部分の価値Lはa−a´であるが、party xにはこれが3つに分割されて与えられるため、party xはどのようにしても合計aの価値を得ることができない。
これに対し、party yがplayer 2、party xがplayer 3のときには、party xはstep 3において1番目の選択権を有するため、aの価値を得ることができる。
従って、このケースではplayer 3になる方が有利である。
【0010】
〔case 1-2〕party xがplayer 2で、party xが分割部分の一部を切り取らない場合
party xはstep 3において2番目の選択権を有するため、a=b≧cであることから、aの価値を得ることができる。
一方、party yがplayer 2、party xがplayer 3のときには、party xはstep 3において1番目の選択権を有するため、aの価値を得ることができる。
従って、このケースではいずれのplayerになっても有利不利は無い。
【0011】
〔case 2〕party yがplayer 2のとき、party yが分割部分から部分Mを切り取る場合
〔case 2-1〕party xがplayer 2の場合にもparty yと同じ分割部分から部分M´を切り取る場合(party xにとって価値が最大である分割部分とparty yにとって価値が最大である分割部分が同じである場合)
〔case 2-1-1〕party xの方が物理的に大きい部分を切り取る場合(M´>Mの場合)
【0012】
party xにとって価値が最大である分割部分の価値をa、部分Mの価値をL、部分M´の価値をL´(>L)とおく。
party xがplayer 2(party yがplayer 3)の場合、step 4においてLより大きいL´が切り取られる。そのため、party yにとってはL´を切り取っていない分割部分の方が価値が高いことから、step 5においてparty yはそちらを選ぶ。従って、party xはa−L´を得る。更に、step 6でparty yが3分割したL´について、step 7でparty xが1番目の選択権を有するため、少なくともL´/3を得る。従って、party xが得る価値の合計は「少なくともa−2L´/3」である。
【0013】
これに対し、party xがplayer 3(party yがplayer 2)の場合、step 4においてL´より小さいLが切り取られる。そのため、party xにとってはL´を切り取った分割部分の方が価値が高いことから、step 5においてparty xはa−Lを得る。更に、step 6でparty yが3分割したLについて、step 7でparty xが1番目の選択権を有するため、少なくともL/3を得る。従って、party xが得る価値の合計は「少なくともa−2L/3」である。
そしてL´>Lなので、「少なくともこれだけはもらえる価値」を比較すると、このケースでもplayer 3になる方が有利である。
【0014】
〔case 2-1-2〕party xの方が物理的に小さい部分を切り取る場合(M´<Mの場合)
party xにとって価値が最大である分割部分の価値をa、部分Mの価値をL、部分M´の価値をL´(<L)とおく。このとき、party xにとってL´を切り取る前に2番目に価値の高い部分の価値はa−L´である。
party xがplayer 2(party yがplayer 3)の場合、step 4においてLより小さいL´が切り取られる。そのため、party yにとってはLを切り取った分割部分の方が価値が高いことから、step 5においてparty yはそちらを選ぶ。従って、party xはa−L´を得る。更に、step 6でparty xが3分割したL´について、step 7でL´/3を得る。従って、party xが得る価値の合計は、a−L´+L´/3である。
【0015】
これに対し、party xがplayer 3(party yがplayer 2)の場合、step 4においてL´より大きいLが切り取られる。そのため、party xにとってはL´を切り取っていない分割部分の方が価値が高いことから、step 5においてparty xはa−L´を得る。更に、step 6でparty xが3分割したLについて、step 7でL/3を得る。従って、party xが得る価値の合計は、a−L´+L/3である。
そして、L´<Lなので、このケースでもplayer 3になる方が有利である。
【0016】
〔case 2-1-3〕party xとparty yが同じ大きさの部分を切り取る場合(M´=Mの場合)
party xにとって価値が最大である分割部分の価値をa、部分Mの価値をL、部分M´の価値をL´(=L)とおく。
party xがplayer 2(party yがplayer 3)の場合、step 4においてL´が切り取られ、step 5においてparty yはL´を切り取った残りを選び、party xはL´を切り取る前に2番目に価値の高い部分であるa−L´を得る。更に、step 6でparty xが3分割したL´について、step 7でL´/3を得る。従って、party xが得る価値の合計は、a−L´+L´/3である。
【0017】
これに対し、party xがplayer 3(party yがplayer 2)の場合、step 4においてLが切り取られ、step 5においてparty xはa−Lを得る。更に、step 6でparty yが3分割したLについて、step 7でparty xは1番目の選択権を有するため、少なくともL/3を得る。従って、party xが得る価値の合計は、「少なくとも」a−L+L/3である。
そして、L´=Lなので、このケースでもplayer 3になる方が有利である。
【0018】
〔case 2-2〕party xがplayer 2の場合で、party yとは異なる分割部分から部分M´を切り取る場合(party xにとって価値が最大である分割部分とparty yにとって価値が最大である分割部分が異なる場合)
party yがplayer 2の時のparty yにとって価値が最大の分割部分のparty xによる価値をa´、party xによる部分Mの価値をL、party xにとって価値が最大の分割部分のparty xによる価値をa(>a´)、party xによる部分M´の価値をL´とする。
party xがplayer 2の場合、party yはstep 5において、L´を取り除いた残りは自分にとって価値が最大の分割部分に係るものでないため選択しない。そのため、party xはa−L´を得る。更に、step 6でparty yが3分割したL´について、step 7でparty xは1番目の選択権を有するが、最大でもL´未満である。従って、party xが得る価値の合計は、a未満である。
【0019】
これに対し、party xがplayer 3の場合、自分にとって最大と思われる部分を全て得ることができる。すなわち、step 5においてaを、step 6においてL/3を得る。従って、party xが得る価値の合計は、a+L/3である。
よって、この場合においてもplayer 3になる方が有利である。
【0020】
〔case 2-3〕party xがplayer 2で、party xが分割部分の一部を切り取らない場合
party xにとって価値が最大の分割部分の価値をa、部分Mの価値をLとする。
party xがplayer 2の場合、価値aの分割部分が少なくとも2つあるため、party xはaを得る。
一方、party yがplayer 2の場合、party xはstep 5においてaを、step 6においてL/3を得る。従って、party xが得る価値の合計は、a+L/3である。
よって、この場合においてもplayer 3になる方が有利である。
【0021】
以上のように、player 3となる方が「最低限得られる量」において、常に同じかよい結果を得る。
【0022】
従って、実際に実行する場合には、3者のいずれがそれぞれplayer 1、2、3の役割を担うかを何らかの手段で決定する必要がある。役割の割り当てについて合意が行われた後にこの手法に従って分割を行えば、その分割結果の取り分について他のplayerと交換しようとは思わないが、そもそも役割によって上記のように有利不利が存在するためplayer間で役割交換の羨望が生じ、公平な結果の前提である役割の割り当てについての合意が取れない。それゆえ、この手法で公平な分割を行うことは実質的に不可能である。
【0023】
本発明は、分割結果の取り分だけでなく、役割の割り当てについても公平に分割することが可能な3者間の公平分割装置、3者間の公平分割方法、及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【0024】
本発明の3者間の公平分割装置は、割当制御部と3台の端末とを備える。
割当制御部は、区間[0、1]で表される資源を3台の端末間で公平に割り当てるための制御を行う。
3台の端末は、それぞれ独自の所定の評価尺度を有し、上記割当制御部からの要求に応じて割り当てに必要な情報を当該割当制御部に送信する。
【0025】
そして、割当制御部は、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を0から正方向を見て1/3に切ったポイントL1、L2、L3を送信するよう要求して、結果を各端末から受信し、
L1=L2=L3=L123である場合、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2、R3を送信するよう要求して、結果を各端末から受信し、
R1=R2=R3=R123である場合には、区間[0、L123]、[L123、R123]、[R123、1]のそれぞれいずれかを上記3台の端末に割り当て、
R1=R2=R12≠R3である場合には、R12<R3なら、R3を送信した端末p3に区間[R12、1]を、残りの2台の端末p1、p2に区間[0、L123]、[L123、R12]のそれぞれいずれかを割り当て、R12>R3なら、p3に区間[L123、R12]を割り当て、残りの2台の端末p1、p2に区間[0、L123]、[R12、1]のそれぞれいずれかを割り当て、
R1<R2<R3である場合には、R2を送信した端末p2による切り方で3分割し、R1を送信した端末p1に区間[L123、R2]を、p2には区間[0、L123]を、R3を送信した端末p3に区間[R2、1]を割り当て、
L1=L2=L12≠L3である場合、
L1、L2を送信した2台の端末p1、p2に対して、p1、p2がそれぞれ各自の上記評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2を送信するよう要求して、結果を各端末から受信し、
R1=R2=R12である場合には、残りの端末p3に対して、当該3分割された区間[0、L12]、[L12、R12]、[R12、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、p3にはp3が選択した区間を割り当て、p1、p2には残りの2つの区間のそれぞれいずれかを割り当て、
R1<R2である場合には、まず、残りの端末p3に対して、区間[0、L12]、[L12、R1]、[R2、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、
p3の評価尺度で評価値が最大となる区間が[0、L12]である場合には、p1に[L12、R1]を、p2に[R2、1]を、p3に[0、L12]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対し、当該3分割された各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当て、
p3の評価尺度で評価値が最大となる区間が[L12、R1]である場合には、p1に[0、L12]を、p2に[R2、1]、p3に[L12、R1]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p2に対して、当該3分割した各区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、p1に対して、残りの2区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、残った区間をp3に割り当て、
p3の評価尺度で評価値が最大となる区間が[R2、1]である場合には、p1に[L12、R1]を、p2に[0、L12]、p3に[R2、1]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対して、当該3分割した各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる。
【発明の効果】
【0026】
本発明の3者間の3者間の公平分割装置、3者間の公平分割方法、及びそのプログラムによれば、各者に各自の評価尺度に基づく評価結果を申告させ、各者の評価尺度のみにより公平に役割を決定するため、分割結果の取り分だけでなく役割の割り当てについても公平に分割することが可能となる。
【図面の簡単な説明】
【0027】
【図1】3者間の公平分割装置100の機能構成例を示すブロック図。
【図2】3者間の公平分割装置100のL1=L2=L3、L1=L2≠L3の場合の処理フロー例を示す図。
【図3】3者間の公平分割装置100のL1<L2<L3の場合の処理フロー例を示す図。
【発明を実施するための形態】
【0028】
図1に本発明の3者間の公平分割装置100の機能構成例を示すブロック図を、図2にL1=L2=L3、L1=L2≠L3の場合の処理フロー例を、図3にL1<L2<L3の場合の処理フロー例をそれぞれ示す。
【0029】
本発明の3者間の公平分割装置100は、区間[0、1]で表される資源を3台の端末間で公平に割り当てる装置であり、割当制御部110と3台の端末121、122,123とを備える。
【0030】
割当制御部110は、区間[0、1]で表される資源を3台の端末間で公平に割り当てるため、各端末との間で情報の授受を行うなど以下で説明する処理をつかさどる。
【0031】
3台の端末121、122、123は、それぞれ独自の所定の評価尺度を有し、割当制御部110からの要求に応じて割り当てに必要な情報を割当制御部110に送信する。なお、以下の説明では途中から各端末をp1、p2、p3と表現しているが、これは本発明においては、具体的な端末121、122、123のいずれかから応答されるL1、L2、L3間の大小関係及びR1、R2、R3間の大小関係に応じて、各端末の役割を加味した抽象的な端末p1、p2、p3を割り当てるという形をとっているためである(すなわち、p1とL1とR1との間、p2とL2とR2との間、p3とL3とR3との間にはそれぞれ対応関係があるが、それらと具体的な端末121、122、123との間には対応関係は無い)。
【0032】
本発明の3者間の公平分割装置100においては、割当制御部110と3台の端末121、122、123との間で、以下のように情報の送受を行うことで結果及び役割分担の双方について公平な分割を実現する。
【0033】
まず、割当制御部110は、3台の端末121、122、123に対して、各端末がそれぞれの評価尺度により上記区間[0、1]を0から正方向を見て1/3に切ったポイントL1、L2、L3を送信するよう要求する。各端末はその要求に応じてL1、L2、L3を送信し、割当制御部110にてそれらを受信する(S1)。ここで、各端末から割当制御部に対し情報を送信するにあたっては、3者間での役割分担の公平性を担保するため、相互に情報が漏洩しないように構成することが望ましい。そこで例えば、各端末と割当制御部との間の通信を暗号化したり、コミットなどの暗号学的手法(参考文献1、2参照)を用いたりすることが考えられる。
〔参考文献1〕岡本龍明、山本博資、「現代暗号」、産業図書、1997、p.142-145
〔参考文献2〕Gilles Brassard, David Chaum, Claude Crepeau, "Minimum disclosure proofs knowledge", Journal of Computer and System Sciences, 1988, Volume 37, Issue 2, p.156-189
【0034】
各端末からL1、L2、L3を受信した割当制御部110は、L1、L2、L3の大小関係に応じて、以下の処理を行う。
(1)L1=L2=L3=L123である場合
この場合、割当制御部110は3台の端末121、122、123に対して、各端末がそれぞれの評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2、R3を送信するよう要求し、各端末はその要求に応じてR1、R2、R3を送信し、割当制御部110はそれらを受信する(S2)。各端末からR1、R2、R3を受信した割当制御部110は、R1、R2、R3の大小関係に応じて以下の処理を行う。
【0035】
(i)R1=R2=R3=R123である場合
割当制御部110は、区間[0、L123]、[L123、R123]、[R123、1]のそれぞれいずれかを上記3台の端末に割り当てる(S3)。
【0036】
(ii)R1=R2=R12≠R3である場合
割当制御部110はR12<R3なら、R3を送信した端末p3に区間[R12、1]を、残りの2台の端末p1、p2に区間[0、L123]、[L123、R12]のそれぞれいずれかを割り当て、R12>R3なら、p3に区間[L123、R12]を割り当て、残りの2台の端末p1、p2に区間[0、L123]、[R12、1]のそれぞれいずれかを割り当てる(S4)。
【0037】
(iii)R1<R2<R3である場合
割当制御部110は、R2を送信した端末p2による切り方で3分割し、R1を送信した端末p1に区間[L123、R2]を、p2に区間[0、L123]を、R3を送信した端末p3に区間[R2、1]を割り当てる(S5)。
(2)L1=L2=L12≠L3である場合
この場合、割当制御部110は、L1、L2を送信した2台の端末p1、p2に対して、p1、p2がそれぞれ各自の上記評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2を送信するよう要求して、各端末はその要求に応じてR1、R2を送信し、割当制御部110はそれらを受信する(S6)。各端末からR1、R2を受信した割当制御部110は、R1、R2の大小関係に応じて以下の処理を行う。
【0038】
(i)R1=R2=R12である場合
割当制御部110は、残りの端末p3に対して、当該3分割された区間[0、L12]、[L12、R12]、[R12、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、p3はその要求に応じて選択結果を送信し、割当制御部110はそれを受信する。そして、割当制御部110は、p3にはp3が選択した区間を割り当て、p1、p2には残りの2つの区間のそれぞれいずれかを割り当てる(S7)。
【0039】
(ii)R1<R2である場合
割当制御部110はまず、残りの端末p3に対して、区間[0、L12]、[L12、R1]、[R2、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、p3はその要求に応じて選択結果を送信し、割当制御部110はそれを受信する(S8)。この場合、いずれの区間の評価値が最大になるかにより、割当制御部110はそれぞれ以下の処理を行う。
【0040】
(a)p3の評価尺度で評価値が最大となる区間が[0、L12]である場合
割当制御部110は、p1に[L12、R1]を、p2に[R2、1]を、p3に[0、L12]を割り当てた上(S9)、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求し、p3はその要求に応じて結果を送信し、割当制御部110はそれを受信する。続いて、割当制御部110はp1に対し、当該3分割された各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p1はその要求に応じて選択結果を送信する。割当制御部110はそれを受信し、p1にこの区間を割り当てる。続いて、割当制御部110はp2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、p2はその要求に応じて選択結果を送信する。割当制御部110はそれを受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる(S10)。
【0041】
(b)p3の評価尺度で評価値が最大となる区間が[L12、R1]である場合
割当制御部110は、p1に[0、L12]を、p2に[R2、1]、p3に[L12、R1]を割り当てた上(S11)、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、p3はその要求に応じて結果を送信する。割当制御部110はそれを受信し、p2に対して、当該3分割した各区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求する。p2はその要求に応じて選択結果を送信し、割当制御部110はそれをp2から受信して、p2にはこの区間を割り当てる。続いて、割当制御部110はp1に対して、残りの2区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p1はその要求に応じて選択結果を送信する。割当制御部110はそれを受信し、p1にはこの区間を割り当て、残った区間をp3に割り当てる(S12)。
【0042】
(c)p3の評価尺度で評価値が最大となる区間が[R2、1]である場合
割当制御部110は、p1に[L12、R1]を、p2に[0、L12]、p3に[R2、1]を割り当てた上(S13)、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求する。p3はその要求に応じて結果を送信し、割当制御部110はそれを受信する。続いて、割当制御部110はp1に対して、当該3分割した各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p1はその要求に応じて選択結果を送信する。割当制御部110はそれを受信し、p1にはこの区間を割り当てる。続いて、割当制御部110はp2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p2はその要求に応じて選択結果を送信する。割当制御部110は、それを受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる(S14)。
(3)L1<L2<L3である場合
【0043】
この場合、背景技術に示した3者無羨望分割のプロトコルにおいて、例えば、p3をplayer 1、p2をplayer 2、p1をplayer 3にそれぞれあてはめて処理を行う。このあてはめは、この組み合わせが唯一ということではないが、組み合わせによってはplayerが正しく申告しないことが有利になるという問題点を持つ場合もあるため留意が必要である。以下、p3をplayer 1、p2をplayer 2、p1をplayer 3にそれぞれあてはめた場合の処理を例示する。
【0044】
割当制御部110は、L3を送信した端末p3に対して、p3の評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR3を送信するよう要求する。p3はその要求に応じR3を送信し、割当制御部110はそれを受信する(S15)。
【0045】
続いて割当制御部110は、L2を送信した端末p2に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp2の評価尺度による評価値が最大の区間が1つだけか、2つ以上あるかを送信するよう要求する。p2はその要求に応じて評価結果を送信し、割当制御部110はその評価結果を受信する(S16)。割当制御部110は、p2による評価結果に応じ、次のように場合分けして処理を行う。
【0046】
(i)p2の評価尺度による評価値が最大の区間が2つ以上ある場合
割当制御部110は、L1を送信した端末p1に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p1はその要求に応じて選択結果を送信する。割当制御部110はその選択結果を受信し、p1にはこの区間を割り当てる。続いてp2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、p2はその要求に応じて選択結果を送信する。割当制御部110はその選択結果を受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる(S17)。
【0047】
(ii)p2の評価尺度による評価値が最大の区間αが1つの場合
割当制御部110はp2に対して、p2の評価尺度で評価値が2番目の区間と同じになるようにαの一部である区間xを切り取りこれを送信するよう要求し、p2はその要求に応じて区間xを送信し、割当制御部110はそれを受信する(S18)。
【0048】
続いて、割当制御部110はp1に対して、区間α−xとその他2つの区間のうち、p1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p1はその要求に応じて選択結果を送信する。割当制御部110はそれを受信し、p1にはこの区間を割り当てる。p1に区間α−xを割り当てた場合にはp2に対して、その他2つの区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求する。p2はその要求に応じて選択結果をp2から受信し、p2にこの区間を、p3に残った区間を割り当てる。一方、p1に区間α−xを割り当てなかった場合にはp2に区間α−xを、p3に残った区間を割り当てる(S19)。
【0049】
続いて、割当制御部110は、区間α−xが割り当てられなかったp1又はp2いずれかの端末(以下、「P1」という。)に対して、区間xをP1の評価尺度で3分割した結果を送信するよう要求し、P1はその要求に応じて結果を送信する。割当制御部110はそれを受信し、区間α−xが割り当てられたp1又はp2いずれかの端末(以下、「P2」という。)に対して、P1により3分割された各区間のうちP2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求する。P2はその要求に応じて選択結果を送信し、割当制御部110はそれを受信し、P2にはこの区間を割り当てる。続いて、割当制御部110はp3に対して、残りの2区間のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求し、p3はその要求に応じて選択結果を送信する。割当制御部110はその選択結果を受信し、p3にはこの区間を割り当て、残った区間をP1に割り当てる(S20)。
【0050】
以上のように、本発明の3者間の3者間の公平分割装置、3者間の公平分割方法、及びそのプログラムによれば、各者に各自の評価尺度に基づく評価結果を申告させ、各者の評価尺度のみにより公平に役割を決定するため、分割結果の取り分だけでなく役割の割り当てについても公平に分割することが可能となる。
【0051】
なお、上記の実施例では割当制御部と各端末とによるサーバ−クライアント型の構成を示したが、割当制御部の機能を各端末に分散して各端末のみにより構成してもよい。この場合、各端末間の通信には参考文献1、2に示されるコミットなどの暗号学的手法により、例えば各playerが値を送る際に自分だけが復号化できる暗号化を行って送り、全員が受信したのち、復号化した結果を、その復号化の正しさの証明をつけた形で送ることで端末間での情報の漏洩を防止することが考えられる。
【0052】
上記の3者間の公平分割装置をコンピュータによって実現する場合、割当制御部が担う処理機能はプログラムによって記述される。そしてパソコンや携帯端末上で、入力手段や各種記憶手段とCPUとのデータのやりとりを通じてこのプログラムを実行することにより、ハードウェアとソフトウェアが協働し、上記処理機能がコンピュータ上で実現されて本発明の3者間の公平分割装置の作用効果を奏する。なおこの場合、処理機能の少なくとも一部をハードウェア的に実現することとしてもよい。また、上記の各種処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【特許請求の範囲】
【請求項1】
区間[0、1]で表される資源を3台の端末間で公平に割り当てるための制御を行う割当制御部と、
それぞれ独自の所定の評価尺度を有し、上記割当制御部からの要求に応じて割り当てに必要な情報を当該割当制御部に送信する3台の端末と、
を備える3者間の公平分割装置であって、
上記割当制御部は、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を0から正方向を見て1/3に切ったポイントL1、L2、L3を送信するよう要求して、結果を各端末から受信し、
L1=L2=L3=L123である場合、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2、R3を送信するよう要求して、結果を各端末から受信し、
R1=R2=R3=R123である場合には、区間[0、L123]、[L123、R123]、[R123、1]のそれぞれいずれかを上記3台の端末に割り当て、
R1=R2=R12≠R3である場合には、R12<R3なら、R3を送信した端末p3に区間[R12、1]を、残りの2台の端末p1、p2に区間[0、L123]、[L123、R12]のそれぞれいずれかを割り当て、R12>R3なら、p3に区間[L123、R12]を割り当て、残りの2台の端末p1、p2に区間[0、L123]、[R12、1]のそれぞれいずれかを割り当て、
R1<R2<R3である場合には、R2を送信した端末p2による切り方で3分割し、R1を送信した端末p1に区間[L123、R2]を、p2には区間[0、L123]を、R3を送信した端末p3に区間[R2、1]を割り当て、
L1=L2=L12≠L3である場合、
L1、L2を送信した2台の端末p1、p2に対して、p1、p2がそれぞれ各自の上記評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2を送信するよう要求して、結果を各端末から受信し、
R1=R2=R12である場合には、残りの端末p3に対して、当該3分割された区間[0、L12]、[L12、R12]、[R12、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、p3にはp3が選択した区間を割り当て、p1、p2には残りの2つの区間のそれぞれいずれかを割り当て、
R1<R2である場合には、まず、残りの端末p3に対して、区間[0、L12]、[L12、R1]、[R2、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、
p3の評価尺度で評価値が最大となる区間が[0、L12]である場合には、p1に[L12、R1]を、p2に[R2、1]を、p3に[0、L12]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対し、当該3分割された各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当て、
p3の評価尺度で評価値が最大となる区間が[L12、R1]である場合には、p1に[0、L12]を、p2に[R2、1]、p3に[L12、R1]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p2に対して、当該3分割した各区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、p1に対して、残りの2区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、残った区間をp3に割り当て、
p3の評価尺度で評価値が最大となる区間が[R2、1]である場合には、p1に[L12、R1]を、p2に[0、L12]、p3に[R2、1]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対して、当該3分割した各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる
3者間の公平分割装置。
【請求項2】
請求項1に記載の3者間の公平分割装置において、
上記割当制御部は更に、
L1<L2<L3である場合、
L3を送信した端末p3に対して、p3の評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR3を送信するよう要求して、結果をp3から受信し、
L2を送信した端末p2に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp2の評価尺度による評価値が最大の区間が1つだけか、2つ以上あるかを送信するよう要求して、結果をp2から受信し、
p2の評価尺度による評価値が最大の区間が2つ以上ある場合は、L1を送信した端末p1に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当て、
p2の評価尺度による評価値が最大の区間αが1つの場合は、p2に対して、p2の評価尺度で評価値が2番目の区間と同じになるようにαの一部である区間xを切り取りこれを送信するよう要求して、区間xをp2から受信し、
p1に対して、区間α−xとその他2つの区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p1に区間α−xを割り当てた場合にはp2に対して、その他2つの区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にこの区間を、残った区間をp3に割り当て、また、p1に区間α−xを割り当てなかった場合にはp2に区間α−xを、残った区間をp3に割り当て、
区間α−xが割り当てられなかったp1又はp2いずれかの端末(以下、「P1」という。)に対して、区間xをP1の評価尺度で3分割した結果を送信するよう要求して、結果をP1から受信し、区間α−xが割り当てられたp1又はp2いずれかの端末(以下、「P2」という。)に対して、P1により3分割された各区間のうちP2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をP2から受信し、P2にはこの区間を割り当て、p3に対して、残りの2区間のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、p3にはこの区間を割り当て、残った区間をP1に割り当てる
3者間の公平分割装置。
【請求項3】
区間[0、1]で表される資源を3台の端末間で公平に割り当てるための制御を行う割当制御部と、
それぞれ独自の所定の評価尺度を有し、上記割当制御部からの要求に応じて割り当てに必要な情報を当該割当制御部に送信する3台の端末と、
を用いて実行する3者間の公平分割方法であって、
上記割当制御部が、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を0から正方向を見て1/3に切ったポイントL1、L2、L3を送信するよう要求して、結果を各端末から受信する第1分割ステップと、
L1=L2=L3=L123である場合に、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2、R3を送信するよう要求して、結果を各端末から受信する第2分割ステップと、
R1=R2=R3=R123である場合に、
区間[0、L123]、[L123、R123]、[R123、1]のそれぞれいずれかを上記3台の端末に割り当てる第1割当ステップと、
R1=R2=R12≠R3である場合に、
R12<R3なら、R3を送信した端末p3に区間[R12、1]を、残りの2台の端末p1、p2に区間[0、L123]、[L123、R12]のそれぞれいずれかを割り当て、R12>R3なら、p3に区間[L123、R12]を割り当て、残りの2台の端末p1、p2に区間[0、L123]、[R12、1]のそれぞれいずれかを割り当てる第2割当ステップと、
R1<R2<R3である場合にはR2を送信した端末p2による切り方で3分割し、R1を送信した端末p1に区間[L123、R2]を、p2には区間[0、L123]を、R3を送信した端末p3に区間[R2、1]を割り当てる第3割当ステップと、
L1=L2=L12≠L3である場合に、
L1、L2を送信した2台の端末p1、p2に対して、p1、p2がそれぞれ各自の上記評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2を送信するよう要求して、結果を各端末から受信する第3分割ステップと、
R1=R2=R12である場合に、
残りの端末p3に対して、当該3分割された区間[0、L12]、[L12、R12]、[R12、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、p3にはp3が選択した区間を割り当て、p1、p2には残りの2つの区間のそれぞれいずれかを割り当てる第4割当ステップと、
R1<R2である場合に、
残りの端末p3に対して、区間[0、L12]、[L12、R1]、[R2、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信する選択ステップと、
p3の評価尺度で評価値が最大となる区間が[0、L12]である場合に、
p1に[L12、R1]を、p2に[R2、1]を、p3に[0、L12]を割り当てる第5割当ステップと、
p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対し、当該3分割された各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる第6割当ステップと、
p3の評価尺度で評価値が最大となる区間が[L12、R1]である場合に、
p1に[0、L12]を、p2に[R2、1]を、p3に[L12、R1]を割り当てる第7割当ステップと、
p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p2に対して、当該3分割した各区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、p1に対して、残りの2区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、残った区間をp3に割り当てる第8割当ステップと、
p3の評価尺度で評価値が最大となる区間が[R2、1]である場合に、
p1に[L12、R1]を、p2に[0、L12]を、p3に[R2、1]を割り当てる第9割当ステップと、
p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対して、当該3分割した各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる第10割当ステップと、
を実行する3者間の公平分割方法。
【請求項4】
請求項3に記載の3者間の公平分割方法において、更に、
L1<L2<L3である場合に、
L3を送信した端末p3に対して、p3の評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR3を送信するよう要求して、結果をp3から受信する第4分割ステップと、
L2を送信した端末p2に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp2の評価尺度による評価値が最大の区間が1つだけか、2つ以上あるかを送信するよう要求して、結果をp2から受信する評価ステップと、
p2の評価尺度による評価値が最大の区間が2つ以上ある場合に、
L1を送信した端末p1に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる第11割当ステップと、
p2の評価尺度による評価値が最大の区間αが1つの場合に、
p2に対して、p2の評価尺度で評価値が2番目の区間と同じになるようにαの一部である区間xを切り取りこれを送信するよう要求して、区間xをp2から受信する切取ステップと、
p1に対して、区間α−xとその他2つの区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p1に区間α−xを割り当てた場合にはp2に対して、その他2つの区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にこの区間を、残った区間をp3に割り当て、また、p1に区間α−xを割り当てなかった場合にはp2に区間α−xを、残った区間をp3に割り当てる第12割当ステップと、
区間α−xが割り当てられなかったp1又はp2いずれかの端末(以下、「P1」という。)に対して、区間xをP1の評価尺度で3分割した結果を送信するよう要求して、結果をP1から受信し、区間α−xが割り当てられたp1又はp2いずれかの端末(以下、「P2」という。)に対して、P1により3分割された各区間のうちP2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をP2から受信し、P2にはこの区間を割り当て、p3に対して、残りの2区間のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、p3にはこの区間を割り当て、残った区間をP1に割り当てる第13割当ステップと、
を実行する3者間の公平分割方法。
【請求項5】
請求項1又は2のいずれかに記載の3者間の公平分割装置としてコンピュータを機能させるためのプログラム。
【請求項1】
区間[0、1]で表される資源を3台の端末間で公平に割り当てるための制御を行う割当制御部と、
それぞれ独自の所定の評価尺度を有し、上記割当制御部からの要求に応じて割り当てに必要な情報を当該割当制御部に送信する3台の端末と、
を備える3者間の公平分割装置であって、
上記割当制御部は、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を0から正方向を見て1/3に切ったポイントL1、L2、L3を送信するよう要求して、結果を各端末から受信し、
L1=L2=L3=L123である場合、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2、R3を送信するよう要求して、結果を各端末から受信し、
R1=R2=R3=R123である場合には、区間[0、L123]、[L123、R123]、[R123、1]のそれぞれいずれかを上記3台の端末に割り当て、
R1=R2=R12≠R3である場合には、R12<R3なら、R3を送信した端末p3に区間[R12、1]を、残りの2台の端末p1、p2に区間[0、L123]、[L123、R12]のそれぞれいずれかを割り当て、R12>R3なら、p3に区間[L123、R12]を割り当て、残りの2台の端末p1、p2に区間[0、L123]、[R12、1]のそれぞれいずれかを割り当て、
R1<R2<R3である場合には、R2を送信した端末p2による切り方で3分割し、R1を送信した端末p1に区間[L123、R2]を、p2には区間[0、L123]を、R3を送信した端末p3に区間[R2、1]を割り当て、
L1=L2=L12≠L3である場合、
L1、L2を送信した2台の端末p1、p2に対して、p1、p2がそれぞれ各自の上記評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2を送信するよう要求して、結果を各端末から受信し、
R1=R2=R12である場合には、残りの端末p3に対して、当該3分割された区間[0、L12]、[L12、R12]、[R12、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、p3にはp3が選択した区間を割り当て、p1、p2には残りの2つの区間のそれぞれいずれかを割り当て、
R1<R2である場合には、まず、残りの端末p3に対して、区間[0、L12]、[L12、R1]、[R2、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、
p3の評価尺度で評価値が最大となる区間が[0、L12]である場合には、p1に[L12、R1]を、p2に[R2、1]を、p3に[0、L12]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対し、当該3分割された各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当て、
p3の評価尺度で評価値が最大となる区間が[L12、R1]である場合には、p1に[0、L12]を、p2に[R2、1]、p3に[L12、R1]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p2に対して、当該3分割した各区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、p1に対して、残りの2区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、残った区間をp3に割り当て、
p3の評価尺度で評価値が最大となる区間が[R2、1]である場合には、p1に[L12、R1]を、p2に[0、L12]、p3に[R2、1]を割り当てた上、p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対して、当該3分割した各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる
3者間の公平分割装置。
【請求項2】
請求項1に記載の3者間の公平分割装置において、
上記割当制御部は更に、
L1<L2<L3である場合、
L3を送信した端末p3に対して、p3の評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR3を送信するよう要求して、結果をp3から受信し、
L2を送信した端末p2に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp2の評価尺度による評価値が最大の区間が1つだけか、2つ以上あるかを送信するよう要求して、結果をp2から受信し、
p2の評価尺度による評価値が最大の区間が2つ以上ある場合は、L1を送信した端末p1に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当て、
p2の評価尺度による評価値が最大の区間αが1つの場合は、p2に対して、p2の評価尺度で評価値が2番目の区間と同じになるようにαの一部である区間xを切り取りこれを送信するよう要求して、区間xをp2から受信し、
p1に対して、区間α−xとその他2つの区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p1に区間α−xを割り当てた場合にはp2に対して、その他2つの区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にこの区間を、残った区間をp3に割り当て、また、p1に区間α−xを割り当てなかった場合にはp2に区間α−xを、残った区間をp3に割り当て、
区間α−xが割り当てられなかったp1又はp2いずれかの端末(以下、「P1」という。)に対して、区間xをP1の評価尺度で3分割した結果を送信するよう要求して、結果をP1から受信し、区間α−xが割り当てられたp1又はp2いずれかの端末(以下、「P2」という。)に対して、P1により3分割された各区間のうちP2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をP2から受信し、P2にはこの区間を割り当て、p3に対して、残りの2区間のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、p3にはこの区間を割り当て、残った区間をP1に割り当てる
3者間の公平分割装置。
【請求項3】
区間[0、1]で表される資源を3台の端末間で公平に割り当てるための制御を行う割当制御部と、
それぞれ独自の所定の評価尺度を有し、上記割当制御部からの要求に応じて割り当てに必要な情報を当該割当制御部に送信する3台の端末と、
を用いて実行する3者間の公平分割方法であって、
上記割当制御部が、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を0から正方向を見て1/3に切ったポイントL1、L2、L3を送信するよう要求して、結果を各端末から受信する第1分割ステップと、
L1=L2=L3=L123である場合に、
上記3台の端末に対して、当該3台の端末がそれぞれの評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2、R3を送信するよう要求して、結果を各端末から受信する第2分割ステップと、
R1=R2=R3=R123である場合に、
区間[0、L123]、[L123、R123]、[R123、1]のそれぞれいずれかを上記3台の端末に割り当てる第1割当ステップと、
R1=R2=R12≠R3である場合に、
R12<R3なら、R3を送信した端末p3に区間[R12、1]を、残りの2台の端末p1、p2に区間[0、L123]、[L123、R12]のそれぞれいずれかを割り当て、R12>R3なら、p3に区間[L123、R12]を割り当て、残りの2台の端末p1、p2に区間[0、L123]、[R12、1]のそれぞれいずれかを割り当てる第2割当ステップと、
R1<R2<R3である場合にはR2を送信した端末p2による切り方で3分割し、R1を送信した端末p1に区間[L123、R2]を、p2には区間[0、L123]を、R3を送信した端末p3に区間[R2、1]を割り当てる第3割当ステップと、
L1=L2=L12≠L3である場合に、
L1、L2を送信した2台の端末p1、p2に対して、p1、p2がそれぞれ各自の上記評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR1、R2を送信するよう要求して、結果を各端末から受信する第3分割ステップと、
R1=R2=R12である場合に、
残りの端末p3に対して、当該3分割された区間[0、L12]、[L12、R12]、[R12、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、p3にはp3が選択した区間を割り当て、p1、p2には残りの2つの区間のそれぞれいずれかを割り当てる第4割当ステップと、
R1<R2である場合に、
残りの端末p3に対して、区間[0、L12]、[L12、R1]、[R2、1]のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信する選択ステップと、
p3の評価尺度で評価値が最大となる区間が[0、L12]である場合に、
p1に[L12、R1]を、p2に[R2、1]を、p3に[0、L12]を割り当てる第5割当ステップと、
p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対し、当該3分割された各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる第6割当ステップと、
p3の評価尺度で評価値が最大となる区間が[L12、R1]である場合に、
p1に[0、L12]を、p2に[R2、1]を、p3に[L12、R1]を割り当てる第7割当ステップと、
p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p2に対して、当該3分割した各区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、p1に対して、残りの2区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、残った区間をp3に割り当てる第8割当ステップと、
p3の評価尺度で評価値が最大となる区間が[R2、1]である場合に、
p1に[L12、R1]を、p2に[0、L12]を、p3に[R2、1]を割り当てる第9割当ステップと、
p3に対して、区間[R1、R2]をp3の評価尺度で3分割した結果を送信するよう要求して、結果をp3から受信し、p1に対して、当該3分割した各区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる第10割当ステップと、
を実行する3者間の公平分割方法。
【請求項4】
請求項3に記載の3者間の公平分割方法において、更に、
L1<L2<L3である場合に、
L3を送信した端末p3に対して、p3の評価尺度により上記区間[0、1]を1から負方向を見て1/3に切ったポイントR3を送信するよう要求して、結果をp3から受信する第4分割ステップと、
L2を送信した端末p2に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp2の評価尺度による評価値が最大の区間が1つだけか、2つ以上あるかを送信するよう要求して、結果をp2から受信する評価ステップと、
p2の評価尺度による評価値が最大の区間が2つ以上ある場合に、
L1を送信した端末p1に対して、区間[0、L3]、[L3、R3]、[R3、1]のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p2に対して、残りの2区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にはこの区間を割り当て、残った区間をp3に割り当てる第11割当ステップと、
p2の評価尺度による評価値が最大の区間αが1つの場合に、
p2に対して、p2の評価尺度で評価値が2番目の区間と同じになるようにαの一部である区間xを切り取りこれを送信するよう要求して、区間xをp2から受信する切取ステップと、
p1に対して、区間α−xとその他2つの区間のうちp1の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp1から受信し、p1にはこの区間を割り当て、p1に区間α−xを割り当てた場合にはp2に対して、その他2つの区間のうちp2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp2から受信し、p2にこの区間を、残った区間をp3に割り当て、また、p1に区間α−xを割り当てなかった場合にはp2に区間α−xを、残った区間をp3に割り当てる第12割当ステップと、
区間α−xが割り当てられなかったp1又はp2いずれかの端末(以下、「P1」という。)に対して、区間xをP1の評価尺度で3分割した結果を送信するよう要求して、結果をP1から受信し、区間α−xが割り当てられたp1又はp2いずれかの端末(以下、「P2」という。)に対して、P1により3分割された各区間のうちP2の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をP2から受信し、P2にはこの区間を割り当て、p3に対して、残りの2区間のうちp3の評価尺度で評価値が最大となる区間を選択して結果を送信するよう要求して、結果をp3から受信し、p3にはこの区間を割り当て、残った区間をP1に割り当てる第13割当ステップと、
を実行する3者間の公平分割方法。
【請求項5】
請求項1又は2のいずれかに記載の3者間の公平分割装置としてコンピュータを機能させるためのプログラム。
【図1】
【図2】
【図3】
【図2】
【図3】
【公開番号】特開2011−128860(P2011−128860A)
【公開日】平成23年6月30日(2011.6.30)
【国際特許分類】
【出願番号】特願2009−286394(P2009−286394)
【出願日】平成21年12月17日(2009.12.17)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【公開日】平成23年6月30日(2011.6.30)
【国際特許分類】
【出願日】平成21年12月17日(2009.12.17)
【出願人】(000004226)日本電信電話株式会社 (13,992)
[ Back to top ]