Title
二並行マッチング再構成の安定マッチング到達不能状況
の検証
Author(s)
金城, 秀樹; 名嘉村, 盛和; 翁長, 健治
Citation
沖縄大学マルチメディア教育研究センター紀要 = The
Bulletin of Multimedia Education and Research Center,
University of Okinawa(3): 35-44
Issue Date
2003-03-31
URL
http://hdl.handle.net/20.500.12001/6371
二並行マ ッチ ング再構成の安定 マ ッチング到達不能状況の検証
金城秀樹 I
,名嘉村盛和 I
I
,翁長健治 I
I
I
I沖縄大学マルチメデ ィア教育研究センタT
I
I琉球大学工学部情報工学科
I
I
Iデ ィジタル社会総合研究所
私達の生活する社会は､様々な構成要素が 自律的に判断 を行い振舞 う ｢自律分散 システム｣ として機能 している｡ この ことか ら､自律分散 システムへ適用 した分散安定マ ッチ ング問題 は､実社会 における様 々な組合せ事象 に適 用可能 な組合せ作成手法である｡ 分散安定マ ッチ ング間琴 における私達の研究は､安定結婚問題の自律分散環境への適用 に始 ま り､参加 メンバー の自律的な判断 により､現在の安定マ ッチ ングか ら異 なる安定マ ッチ ングへ組合せの構成 を変化することが可能 であるマ ッチ ング再構成 と呼ばれる安定マ ッチ ングの遷移手法の提案 を行 った｡ しか しなが ら､提案 されたマ ッ チ ング再構成は､一度 に実行 されるのは唯一人の メンバーによるマ ッチ ング再構成である との仮定 を設けていた ことか ら､複数のメンバーが並行的 にマ ッチ ング再構成 を実行する複数マ ッチ ング再構成の提案 を行 ったが､実 行可能 なアルゴリズムの提案 には至 っていないかった｡ 本論文では､複数マ ッチ ング再構成の実行が可能 なアルゴリズムを提案す るにあた り､先 に提案 した単一マ ッチ ング再構成アルゴリズムを用いて､複数マ ッチ ング再構成の基礎 となる二並行マ ッチ ング再構成 を実行 した場合 に､安定マ ッチ ングへ導 くことがで きないケースの検証 を行 い､二並行マ ッチ ング再構成 を実現するための課題 を提示す る｡Ver
i
f
ic
at
i
onoft
heSi
t
uat
i
oni
nwhi
c
hTwoConcur
r
entMat
c
hi
ng
Rec
ons
t
r
uc
t
i
onCannotLeadt
oAnot
herSt
abl
eMat
c
hi
ng
Hi
de
kiKI
N
J
Ol
,Mor
i
k
a
z
uNAKAMURA
H,
Ke
n
j
iONAGA
I
H
I
Mul
t
i
me
di
aEduc
a
t
i
ona
ndRe
s
e
a
r
c
hCe
nt
e
r
,
Oki
na
waUni
ve
r
s
i
t
y
I
I
De
pa
r
t
me
nto
fl
nf
b
r
ma
t
i
onEngl
●
ne
e
r
l
●
ng
,
Uni
ve
r
s
i
t
yoft
heRyukyus
t
H
Re
s
e
a
r
c
hI
ns
t
i
t
ut
ef
o
rDi
gi
t
a
lSoc
i
e
t
y
Societyinwhichwearelivingcanbecalledanautonomousdistributedsystem becauseofsocialsystem is workingbyautonomousbehaviorofitselements.Thatmeansdistributedstablematchingproblem callbe appliedtosocialsystems.
Ⅰnourpreviousworks
,
ithasbeenproposedthatstablemana●geproblem wasappliedtoautonomousdis -tributedenvironment,
andintroducedautonomousmechanism forexchangl●ngPartners,
Calledmatchingre -construction.However,
wewillbeconcernedinourstudywithquestionofhow twoormorememberscan initiatematchingreconstructionprocessesatsameperiods.ThepurposeofthispaperistoverifyofthesituationinwhichtwoconcurrentmatchingreconstructiollCannot leadtoanotherstablematchingandshowtheproblemswhichshouldbesolvedf♭rexecutionortwoconcurrent matchingreconstruction.
5-１まえがき
安定結婚問題は、、ＧａｌｅとLShapleyによる、“CollegeAdmissionsandtheStabilityofMarriage[1]，，の
中で発表きれた組合せ問題である。得られるマッチングの安定性や分散環境におけるノードの組み合わせに適し ていることから、安定結婚問題は実社会の広い範囲に適用可能であり、また、数学的な興味もあることから、多くの研究者に高い関心を持たれている[2]・本論文では、以後一般的な意味を持たせるため、安定結婚問題を安
定マッチング問題と呼ぶ。本研究では、注目を集めている研究分野の１つである、複数の自律移動ロボットによる協調作業[3,4,5]では、
自律分散システムを構成する自律移動ロボット等のノード同士の組み合わせが必要となることから、自律分散環 境におけるマッチングゲームを考え、安定マッチング問題における参加メンバーを分散システムにおける構成要素と捉え、分散環境に適用した分散安定マッチング問題を定義した[6,7]・
分散安定マッチング問題においては、Gale-Shapley基本アルゴリズム｛1]を基にした分散Gale-Shapleyアルゴ
リズム[7]により、安定マッチングを得ることが可能であることを示したが､提案アルゴリズムては、Gale-Shapley
基本アルゴリズム同様、複数存在する安定マッチングの中で特定のマッチングしか得ることができない。この問題を解決する為、本研究ではマッチング再構成[7]を提案したが、任意のメンバーによりマッチング再構成が実行
された場合、そのマッチング再構成が終了する迄、他のメンバーはマッチング再構成を実行することができない という、同時には単一のメンバーのみがマッチング再構成を実行できるという条件を設けていた。この条件のも とでは、マッチングゲームへの参加メンバーが増え、それに伴いマッチング再構成の希望者が増加すると、マッ チング再構成を希望しても、実際に再構成を行える迄の待ち時間が長くなるという問題が存在する。 本研究では、マッチング再構成をより柔軟に実行できる環境として、任意のメンバーによってマッチング再構 成が実行され、そのマッチング再構成の終了を待たずに、他のメンバーによりマッチング再構成を実行できる、つまり、複数のメンバーによる並行的なマッチング再構成の提案を行った[8]・複数のメンバーによって同時に行
われるマッチング再構成においては、各々の起動者によって起動されたマッチング再構成が互いに影響しあうこ とから、そのパートナー交換は単一起動者によるマッチング再構成に比べ複雑である。複数マッチング再構成が成功する必要十分条件の証明を行うには、先に提案した分散Gale-Shapleyアルゴリズムによって並行的にマッ
チング再構成を実行した場合の問題点を検証することが必要となる。 本論文では、２節で本研究の基礎となる安定マッチング問題を紹介し、３節では、我々のこれまでの研究で行っ た、安定マッチング問題を分散環境へ適用した分散安定マッチング問題の定義及び分散安定マッチング問題を解 くアルゴリズムを示す。また、単一メンバーによる安定マッチングの再構成手法について述べる。４節では、複 数安定マッチング再構成の定義およびその検証に利用するメッセージの流れを定義したパートナー交換フローの 定義を示す。本論文において中心となる５節では、複数の再構成プロセスによる並行的なマッチング再構成が、 どのような場合に安定マッチングへ導くことができない力､の検証を行う。最後に、６節で本論文のまとめを行う。２安定マッチング問題
本節では、以下の議論に必要な分散安定マッチング問題の基礎となっている安定マッチング問題について説明 を行う。 安定マッチング問題では、要素数、の２つの集合、男'性グループ、、女性グループｗが与えられる。 {ｍｎｍ２,…川冗}， O {'U,,uﾉ2,…川､｝ ｍｗ このとき、男性グループに属するメンバーを男`性メンバーと呼び、女性グループに属するメンバーを女性メンバーと呼ぶ。また、任意のグループに属するメンバーｐを考えるとき、ｐと同じグループに属するメンバーをｐ
の同性メンバー、異なるグループに属するメンバーをｐの異性メンバーと呼ぶ。 －３６－男'性グループ及び女性グループに属する各メンバーは、異性のグループに含まれる全てのメンバーを厳密に順
位付けしたリスト(PreferenceList:以後ＰL）を持っている。このとき、任意のメンバーｐと、ｐの異性メンバー
である９，７について、ＰのＰＬにおいて９がγより上位にランクされるとき、Ｐはγより９を好むと言い、次
のように表現する。PLp(9)＜PLp(γ）
マッチングＭとは、男女のペア（ｒＭｊ),ｍＥｎＭ)ｅｗの集合
Ｍ＝｛(ｍ,Ｕ)ｌｍＥｍ,ＬｕＥｗ}，|Ｍ|＝、
で、各メンバーはＭ中にたかだか１回しか出現しない。このとき、安定マッチングを次の様に定義する。定義１［11マッチングＭに含まれる２つのペア(ｍＭＵｄ),(mj,tUj）において
ｎｚｉは１０.よりｕﾉﾉを好む、且つ
ＬＵｊはｍｊよりｍｊを好む
が成立するとき、これらは不安定なペアという。マッチングＭ内の、任意の２つのペアが不安定でないとき、 「Ｍは安定なマッチングである」という。□ 安定マッチング問題において、与えられた問題例（男性グループ､女性グループ及びそれぞれに属するメンバーのＰＬ）には少なくとも一つの安定マッチングが存在する[2]。一般に、与えられた問題例には複数の安定マッチン
グが存在し、最も多い場合、その問題例における集合の要素数の指数オーダー存在することが知られている[2]。
、ＧａｌｅとLShapleyの提案したGale-Shapley基本アルゴリズム[1]によって、与えられた問題例における安
定マッチングを求めることが可能である。３分散安定マッチング問題
本節では、安定マッチング問題を分散システムへ適用した分散安定マッチング問題について述べる。3.1分散Gale-Shapleyアルゴリズム
安定結婚問題を分散システムへ適用する前に、本論文で想定する分散システムを次の様に定義する。 1．任意の分散要素間で相互に通信できる非同期システムとする。 ２．分散要素内の全ての命令は有限時間内で終了するものとする。 ３．通信遅延は有限である。安定マッチング問題における各メンバーを、上記のような分散システムにおける分散要素（ノード）と捉える
ことにより、分散システムへ安定マッチング問題を適用する。本論文で定義する分散安定マッチング問題とは、上記のような分散システムにおいて、有限回のメッセージ通
信と有限時間の計算で、次に示す初期状態から最終状態へ導くアルゴリズムを求める問題をいう。
［初期状態］各メンバーは男性グループと女性グループの２グループのいづれかに所属していて、他の全て
のメンバーの識別子（ID）と所属しているグループを知っている。また、各プロセスは、自己のＰＬのみ持っ ている。 －３７－［最終状態］各メンバーは、自分のパートナーを知っている。この時、分散システム全体として各メンバーの
組み合わせは安定なマッチングとなっている。分散安定マッチング問題を解く分散アルゴリズムとして、Gale-Shapley基本アルゴリズムを基にした分散Gale-Shapleyアルゴリズムを提案した［7]・この分散アルゴリズムにおいては、メンバー間で次のメッセージの送受
信を行う。 Propose:送信者の受信者に対するパートナー要請を意味する。 Accept：送信者が受信者のパートナー要請を受諾したことを意味する。 Reject：送信者が受信者のパートナー要請を断わったことを意味する。 Proposed送信者がパートナー要請きれたことを受信者に対し伝える。また、提案アルゴリズムにおいては、メッセージは次のコマンドにより送受信される。
Send(ハMes)：メッセージＭｅｓをｐへ送る。 Receive(p,Mes):ｐからのメッセージＭｅｓを受け取る。図１に、分散Gale-Shapleyアルゴリズムを示す。
分散Gale-Shapleyアルゴリズムは、もととなるGale-Shapley基本アルゴリズムと同様の性質をもっている。
つまり、男性メンバーがProposeを行い、女`性メンバーがそれを受けるとき、得られる安定マッチングは、男性
優先安定マッチングとなる。3.2マッチング再構成
分散Gale-Shapleyアルゴリズムで得られる安定マッチングは、男`性優先解もしくは女性優先解という、一方
のグループのメンバーにとって最良で、もう一方のグループのメンバーにとって最悪となる`性質をもっている。
その様な安定マッチングでは、パートナーに対し不満を持ち、より良いパートナーを望むメンバーが存在するこ
とが考えられる。本節では、安定マッチングから異なる安定マッチングヘ導くマッチングの再構成手法について
述べる。先ず、マッチング再構成の手法を定義する。定義２任意の安定マッチングＭにおいて、メンバーｔｕが、現在のパートナーに対しRejectメッセージを送
信し、各メンバーが分散Gale-Shapleyアルゴリズムに基づいた行動をとるとき、Ｍとは異なる安定マッチング
ヘ導かれる。この手法をマッチング再構成と呼ぶ。このときのパートナー交換の実行過程を再構成プロセスと呼
び、mrpXl/と表現する。また、COをmrpXlrの起動者という。□
メンバーｕ）が、安定マッチングＭにおけるパートナーに対し自律的にRejectメッセージを送信したとき、再
構成プロセスが起動されたという。再構成プロセスによるパートナー交換の結果、起動者ｕ）が新たなパートナー
を得た場合、起動前とは異なる安定マッチングへ導かれている。このとき再構成プロセスは成功したという。一
方、ＰＬの最下位の異性メンバーからRejectメッセージを受信し、これ以上Proposeメッセージを送信する相
手がいないメンバーが現れた場合、起動者は新たなパートナーを得ることができず、この場合、起動前とは異な
る安定マッチングへ導けなかったことになり、再構成プロセスは失敗したという［7]。
定義３マッチング再構成において、「一つの再構成プロセスによるパートナー交換が実行中であれば、異なる再
構成プロセスを起動できない」と仮定するとき、このマッチング再構成を単一マッチング再構成と呼ぶ。
定理１[7]単一マッチング再構成は、起動者が最良のパートナー（起動者が男性であれば男性優先安定マッチン
グにおけるパートナー）以外に対し起動した場合、異なる安定マッチングへ導く。□
－３８－1 procedure l\IIan is
2 begin
3 loop
4 w:= the i-th member of PL; 5 Send(w, Propose);
6 Receive(w, Mes);
7 case Mes is
8 when Reject: i=i+1;
9 when Accept: break the loop; 10 end case;
11 end loop;
12 partner:= w;
13 end.
14
15 procedure WOMAN is'
16 begin 17
m:=
null; 18 loop 19 Receive(p, Mes); 20 case Mes is 21 when Propose: 22 if m := null then 23 m := p;24 Send(every wonlan who participates,Proposed);
25 else if preferpto m then
26 Send(m, Reject); 27 m := p; 28 else 29 Send(p, Reject); 30 end if; 31 when Proposed:
32 if received Proposed from every woman then
33 Send(m, Accept); break the loop;
34 end if; 35 end case; 36 end loop; 37 partner:= m; 38 end. ~ 1: 7t~ Gale-Shapley 7 }v'::ll) :A'b,
