Title
自律分散システムにおける安定マッチング問題
Author(s)
金城, 秀樹
Citation
沖縄大学マルチメディア教育研究センター紀要 = The
Bulletin of Multimedia Education and Research Center,
University of Okinawa(1): 23-35
Issue Date
2001-03-31
URL
http://hdl.handle.net/20.500.12001/6321
自律分散 システムにお ける安定マ ッチ ング問題
金城秀樹 琉球大学 工学部 情報工学科 計算機 の普及や通信技術の進歩､システムに対す る柔軟性のニーズの高ま り等､様 々な社会的要因 か ら自律分散 システム-注 目が集 まっている｡ 従来の集 中型 システムに対 し優れてい る点 として一般的に柔軟性や拡張性､耐故障性 が挙げ られ る が､これ らの高度な機能 を実現す るためには分散化 されたもの同士の協調が不可欠である｡効率的 な協調 を実現す るためには状況判断が､重要 となるが､自律分散 システムには､自分 (各分散要素) を取 り巻 く状況か らだけでは全体の動 きを把握できにくい とい う本質的な問題 が存在す る｡ 本論文で議論す る､自律分散 システムにおける安定マ ッチング問題 は､自律分散 システムの一形態 であるイ ンターネ ッ ト等で注 目を集 めている電子商取引等 にお ける商品 と購入者 の組合せ等-の 適用が期待できる問題である｡ 本論文では､自律分散 システムにおける安定マ ッチング問題 において､各分散要素の局所的な状況 把握 によ り､全体 として安定なマ ッチ ングを求める手法の提案 を行い､提案手法について検討 を行 う｡St
a
bl
eMa
t
c
hi
ngPr
o
bl
e
mi
nAut
o
no
mo
usDi
s
t
r
i
but
e
dSy
s
t
e
ms
HidekiKinjoDept.ofhfom ationEng.,UniversityoftheRyukyus
Autonomousdistributedsystemsarefocusedbecauseofspreadofcomputers,progressofinfom ation technology,increaseofimportancetoflexibility,andsoon.Generallyspeaking,autonomousdistributed systemsaregreaterthan centralizedsystemsastoflexibility,extensibleandrobustness,.However,itis necessaryforrealizationoftheseadvancedfunctionthatcooperationofdistributedelements.Circumstantial judgmentsareimportantforrealizationofefficientcooperation,butthereexistsaproblemthateachelement cannotgraspthewholesituationinthedistributedenvironment.
Inthispaper,Iconsiderthestablematchingprobleminautonomousdistributedsystems.Thisproblemcan be appliedtomatchingforcustomersandmerchandiseofelectriccommerceintheIntemet.Ishow the distributedGale-Shapleyalgorithmandmatchingreconstucrtionalgorithm,andconsiderproposedalgorithms.
3-１はじめに
顧客のニーズの多様化、システムに対する拡張性・耐故障性のニーズの高まりから、システム全体を集中管理
する従来の集中管理型システムに代わり、柔軟性に豊んだ新しいシステムとして自律分散システムヘの期待が高 まっている［1]・自律分散システムとは、システム全体を統合する管理機構をもたず、システムを構成する各要素（個・サブシステム）が自律的に行動しながら、協調・競合的に相互作用しあい、全体として任務を達成する
(秩序を形成または維持する）システムである[2]。しかしながら、自律分散システムにおいても、各サブシステ
ム間の組合せの数だけ統合の仕方があることから、各サブシステムを単純に協調させるだけでシステム全体がう まく働くようにすることは困難である。一方、インターネットの普及に伴い、ネットワーク上で品物を売買する電子商取引へ注目が集まっている。電
子商取引の一つであり、広く利用きれているネットオークションでは、購入者はネットワーク上に無数に存在す
る商品（販売者）から、また販売者は複数の購入希望者から適切な相手を選ぶという基本的な問題が存在する。
本論文では、組合せ問題の一つで、数学的興味のみならず、様々な分野への幅広い応用が可能であることから注目を集めている「安定結婚問題」を自律分散システムへ適用することにより、上記の問題を解決する自律分散
システムにおける組合せを求める一手法である分散安定マッチング手法［31を紹介する。
本論文の構成として、２節で、分散安定マッチング問題の基礎となる安定結婚問題について説明する。３節で
は、自律分散システムにおける安定結婚問題の定義、及び自律分散システムにおける安定結婚問題を解く協調ア
ルゴリズムの紹介、検討を行う。４章では、任意の安定マッチングから異なる安定マッチングへ導く手法の紹介、
検討を行う。２安定結婚問題
本節では、本論文で紹介する分散安定マッチング問題の基礎となっている安定結婚問題について説明を行う。安定結婚問題は、DavidＧａｌｅとLloydShapleyによって発表された論文、“CollegeAdmissionsandtheStability
ofMarriageI4]，'の中で公表された組合せ問題である。 安定結婚問題では、同じサイズ、の２つの集合、男性グループ、、女性グループｗが与えられる。 {ｍ1,ｍ2,…,ｍ､)， {z0,,tU2,…,uﾉｎ｝ ｍｗこのとき、男性グループに属するメンバーを男性メンバーと呼び、女性グループに属するメンバーを女`性メン
バーと呼ぶ。また、任意のグループに属するメンバーｐを考えるとき、ｐと同じグループに属するメンバーをｐ
の同性メンバー、異なるグループに属するメンバーをｐの異`性メンバーと呼ぶ。任意のメンバーｐは、異性メンバーの中から無作為に選んだ２メンバー９，７に対し、ｐはγよりｑを好む、
もしくはｐは９よりγを好むという関係のいずれかが常に成り立つ。男性グループ及び女性グループに属する
各メンバーは、上記の関係を基に、異なるグループに含まれる全てのメンバーを順位付けしたリスト（Preference
List:以後ＰL)を持っている。このとき、任意のメンバーｐと、ｐの異性メンバーである９，ｒについて、ｐがγ
よりｑを好むという関係が成り立つとき、ｐのＰＬにおいて９はγより上位にランクされると言い、次のよう
に表現する。 PLp(9)＜、p(γ） マッチングＭとは、男女のペア(nMu)'ｍＥｍｌｍＥｗの集合 Ｍ＝{(７Ｍﾉ)|ｍｅｒＭ）ＥＷ}，|Ｍ|＝、で、各メンバーはＭ中にたかだか１回しか出現しない｡このとき、安定マッチングを次の様に定義する[4]。
－２４－定義１Ｍに含まれる２つのペア(ｍＭＵｉ)、（mj,ｕｊｊ）において
PLmルゴ）＜PLmi(TUj)，且つ ＰＬｍｊ(ｍｊ）＜PLtUj(ｍｊ）が成立するとき、これらは不安定なペアという。マッチングＭ内の、任意の２つのペアが不安定でないとき、
「Ｍは安定なマッチングである」という。安定結婚問題のインスタンス（男性グループ、女性グループおよびそれぞれに属する各メンバーのＰＬ）には
少なくとも一つの安定マッチングが存在するに]。一般に、安定結婚問題のインスタンスには複数の安定マッチ
ングが存在し、最も多い場合、そのインスタンスにおける集合の要素数の指数乗個存在することが知られてい
る１５]。ＤＧａｌｅとLShapleyの提案したGale-Shapley基本アルゴリズム[4]によって、任意のインスタンスにおけ
る安定マッチングを求めることが可能である。 しかし、このアルゴリズムによって得られる安定マッチングでは、各男性メンバーは全ての安定マッチングの中で最も好ましい女性メンバーをパートナーとし、一方各女性メンバーは、全ての安定マッチングの中で最も好
ましくない男`性メンバーをパートナーとする。男性メンバーにとっては最良であるが女性メンバーにとっては最
悪となる極端な性質をもつこの安定マッチングを、男性優先安定マッチングと呼ぶ。また、Gale-Shapley基本ア
ルゴリズムにおいて男性と女性の役割を入れ換えることにより、女'性メンバーにとって最良で、男性メンバーに とって最悪な組み合わせとなる、女`性優先安定マッチングを得ることができる。 定義２[4,5]安定マッチングＭ、Ｍ'において、全ての男性メンバーが、Ｍ'におけるパートナーよりＭにお けるパートナーを好むか、Ｍ及び川において同一のパートナーであるとき、ＭはＭ'の男`性優位安定マッチ ングであるといい、ＭべＭと表現する。Ｍは、安定結婚問題のインスタンスにおける、すぺての安定マッチングの集合を表す。集合Ｍは半順序集
合になることが知られている［5]。このとき、安定マッチング間の半順序関係が男性側に立った優位関係に基づ いたものであれば、その関係を(Ｍ,≦）と表現する。また、半順序関係が女性側に立った優位関係に基づいたも のであれば、その関係を(川上）と表現する。定理１[5]安定結婚問題のインスタンスにおいて、男性優位の半順序集合である（Ｍ,≦）は、Ｍ八ＭとＭ
ｖＭ'で表現されるＭと川の交わりと結びが定義された分配束である。このとき、Ｍ八Ｍ'(ＭｖＭ')は、
すべての男性がＭとＭ'でのパートナーの好ましい（好ましくない）方とペアとなる安定マッチングである。
このとき、ハッセ図の極大元は男,性優先解を、極小元は女性優先解を意味し、それぞれＭ０，Ｍｚと表現する。
例１インスタンスを図１に示す。図１における各メンバーのＰＬにおいては、左端に表される異性メンバーが 最も好ましく、右にいくに従い好ましくなくなるものとする。例えば、ｍ，にとって最も好ましい異`性メンバー は、ｕ）５，次にｕﾉ８…となり最も好ましくないのが、山である。 図１におけるインスタンスより得られる安定マッチングのハツセ図を図２に示す。図２において、ノードは 図１より得られる安定マッチングである。各ノードにおける要素は、上段が男性メンバーを、下段が女性メン バーを表しており、上下段の対がそのノード（安定マッチング）におけるペアとなる。このとき、各ノードにお ける要素において、／の左側がメンバーＩＤを右側がそのノード（安定マッチング）におけるパートナーのラン クを表している。Ｍｂを例に取って説明すると、ｍｌは、７とペアとなっており、各々のＰＬにおけるランクは PLm,(TU7)＝３，ＰＬｍ７(､21)＝６である。また、ノード（安定マッチング）間の矢印は、矢尻に位置する安定マッ チングは矢先の安定マッチングに比べ男性優位であることを意味する。 －２５－川ノ５８７１３６２４ 脚２５３４８１６７２ 川３１６８５２４７３ 川乎５２４８６３７１ m５３７５１８４６２ 川６８７１２４５６３ m７６８５２１７４３ 脚８７６３１４５８２ ｗＩ７８２１５６４３ ｗ２８７２５６３４１ ｗ３７３４６１５８２ ｗィＳ３１７４２６８ ｗ５６７５４３２１８ ｗ６５２８３４７６１ ｗ７４７５３２１８６ Ｗ８４３７６８Ｚ５１ 図１：安定結婚問題におけるインスタンス 、i／ｍｊのパートナーのランク ｗｊ／ｗｉのパートナーのランク １/３２ﾉｮｮﾉ３４/２５m６/３７Ｂ８/２ 〃０ ７/６４ﾉ６Ｗ２２/７３ﾉ６１/OS/2６/３ １３２ﾉ５３/３４ﾉｮﾖﾉ１６/４７ＤＢ/２ Ｍノ ７/６１ﾉ３８/２４ﾉﾖｮﾉ６２/５５，６ﾉ３ l/３２ﾉﾖｮﾉ６４/４５/１６ﾉ４７/３８厄
:｢;≦鵲lＭ
I/３刀６３/３４/３５/１６ﾉ４７ﾉ３８/４/１６ﾉ４７ﾉ３８/４ － 妃ツＳ５ｎ１/２此};鶚:：
1/５２ﾉ５３/３４/３５/２６/４Ｗ３８/２",|鶚霊：
1/３２ﾉ５３/３４ﾉ３５ﾉ１６/６７/４８ﾉ２ Ｍ２ 7/６１Ｂ４/２８/１３/６２/ｓ５ｎ６/３ 7ﾉ６６/２８/２４ﾉｺﾞ３/６コ５５ﾉ２１/２ ? 3/５１/３８/２４ﾉ５７Ｂ２/５５/２６/３ ﾌﾉ６１/３８ﾉ２４/５］６５/１２/２６'３ Ｍ６ Ｍ78 1/５２ﾉ５３/６ ３/Ｓ１Ｂ４ｎ 〃 Ｍ, ＭＩＯ、 1石２/５３/３ ３ﾉ５１/３８/２ Ｍ８ JＯ Ｍ〃 】Ｂ２/６３/６４/４５/１６/４７ﾉ３８/４１６/４７Ｂ８Ｎ － ６２灯５，１厄 1/５２ﾉ５３/６４/４５ﾉ２６/４７/３８ﾉ２;二::ｉＩＩ害:;：
lﾉ３２/５３/６４/４５/１６/６７/４８，|｢:吾|芸:|}鶚二}
1ﾉ３２/６３ﾉ３４/３５/１６ﾉ６７/４８/４6ﾉ６７/４８/４ ￣ 5/１２/２１/２ 1ﾉ５２ﾉ５３ﾉ３４Ｂ５ﾉ２６/６７/４８/２::筈美:|隙
1/５２/６３/３４/３５/２６/４７/３８Ｎ 7/６６ﾉ２４/２Ｍ３/６２灯５/２１/２ 3/５１/３４/２８/１７/３２/５５/２６/３ 7ﾉ６１/３４/２８/１３/６５/１２ﾉZ６Ｂ 7ﾉ６６/２８/２４/５３/６５/１２/２１厄 3ﾉ５１/３８/２４/５７ﾉ３５/１２，６/３ 3/５６/２８/２４/５７/３２ﾉ５５，１/２ Ｖ５２ﾉ６３ﾉ６４/４５/２６/４７/３８ﾉ４;::篁筈:|""|鶚二|：
1/３２ﾉ６３ﾉ６４/４５m６/６７/４８/４:鵲筈lM"|崇｣;三:：
〃５２ﾉ５３/６４/４５/２６/６７/４８ﾉ２M,|鶚呈：
1ﾉ５２/６３/３４/３５/２６/６７/４別４:箸:Ｊ１:|M`|;焉二|芸
1/３２ﾉ６３/３４/３５/１６/６７石８ﾉ８ Ｍ〃 ﾉイ 3ﾉ５６'２４/２８ﾉ１７/３２石５/２１/２ 7/６６/２４/２８八３/６５/１２ﾉ２１/２ 3/５１/３４/２８/１７/３５/１２/２６/３ 3/５６/２８/２４/Ｓ７Ｂ５ｍ２/２１/２ 7/６６/２８/２４/５３/(isﾉｌｌｍ２/Ｉ 1/５コ６３/６４/４５/２６/６７/４８/４/２６′６７/４８脚 ￣ /３５/１２/２１/２M噸'１;器:器
1/３２/６３ﾉ６４ﾉ４５/１６ﾉ６７/５８/８5/１６ﾉ６７/５８/８ ３ﾉ６５/１１/１２/１M,|;鶚|芸
1/５２/６３ﾉ３４/３５/２６/６７ﾉ５８/８ Ｍﾉｱ3/５６/２４/２８/ｌ７Ｂ５/１２/２１/２ 7/６６ﾉ２４/２８/１３ﾉ６５/１１/１２/］ 3ﾉ５６/Ｚ８ｎ４/５７/３５ﾉ１１/１２/１ ６４/４５６/６７８/８ Ｍｚ ６/２４/２Ｍ７３５/１１/ｌ〃 図２:安定マッチングによるハッセ図 －２６－定義３[５１安定マッチングＭにおける任意の男性メンバーｍにおいて、ｓＭ(、)は、Ｍにおけるパートナー よりｍの方が好ましい女性メンバーの中で、ｍのＰＬにおいて最も上位にランクされる女`性メンバーｕ）のこ とを示し、neztM(、)は、女性メンバー８Ｍ(、)のＭにおけるパートナーを示す。 Ｍが安定マッチングであることから、ｍのＰＬにおいてｓＭ(、)がＭにおけるｍのパートナーより上位に ランクされることは無い。 定義４β＝(ｍｏ,ujo)(ｍ,,uﾉ,)…(ｍｒ－１,uﾉr-,）はマッチングＭにおけるペアの順序リストであり、すべてのｉ (0三ｊ三γ－１)において、(`+,)modγがｍｊのneztM(ｍ`)であるとき、βはＭのローテーションであるとい い、βにペア(ｍ`,山)が存在するとき、ｍｊ（又は、ｕ）`）はローテーションβに存在するという。 安定マッチングＭとＭのローテーションβにおいて、βに存在しないすべての男`性がＭでのパートナー とそのままペアとなり、βに存在する各男性ｍ`がⅦ）(j+')modγ＝sjw(川）とペアとなる安定マッチングをＭ〃 と表現する[5]。 補題１[5叩がＭのローテーションであるとき、ＭはＭ/βの優位安定マッチングである。 安定マッチングの束構造においてβがＭのローテーションであるとき、βは、ＭからＭ〃への有向枝のラ ベルで表される。本論文では、安定マッチングＭからローテーションβにより安定マッチングＭ〃を求める ことを、「βにより、ＭからＭ〃を導く」もしくは、「ＭからＭルヘ遷移する」という。また、βは、安 定マッチングＭだけのローテーションであるとは限らない｡ 例えば、図２において、β1＝(ｍ３，TU8)(ｍ４，ｕｊ４）は、Ｍ１のローテーションであるが、Ｍ３のローテーショ ンでもある。 安定結婚問題のインスタンスにおいて、全てのローテーションが対応するノードの集合で構成されるアサイク リックグラフをローテーションダイグラフＧ(Ｍ）という[5]。 定義５ローテーションβにペア（７Ｍ))が存在するとき、β'が、とｕ）がペアとなるマッチングへ導くロー テーションであるならば、ｃ(Ｍ）でβ'からβへの有向枝が存在する。このとき、β'はβのtzﾉpelの先行ロー テーションであるという。 定義６βが、ｍをｕｊ以下の女性とペアとなるマッチングへ導くローテーションであり、β'≠βでβ'が、ＴＵ を、以上の男性とペアとなるマッチングへ導くローテーションであるならば、Ｇ(Ｍ)でβ'からβへの有向枝 が存在する。このとき、β'はβのtype2の先行ローテーションであるという。 定義７０のノードの部分集合Ｓの要素がＳ以外に先行ノードを持たないとき、部分集合Ｓは閉じているとい い、ＳをClosedSubsetという。 安定結婚問題の解の持つ最も重要な性質の１つを次に示す。 補題２Ｇの各ClosedSubsetはＭの各安定マッチングと１対１対応である。 定義８安定マッチングＭに対応するClosedSubsetをＯＳ(Ｍ）と表現する。
３分散安定マッチング問題
近年、システムの巨大化、複雑化に伴い中央管理機構による集中管理の限界が見えて来ている。それに加え、 システムへの要求が多様になっており、柔軟性、多様性に富んだシステム機構が必要になってきている。その結 果、従来の集中管理型システムより柔軟な構造をもつ分散システムへの期待が高まっている［2]。しかし、シス －２７－テムを分散化した場合、分散型システムがうまく働くための鍵は分散したサブシステムをいかに協調させるかに ある。その場合、単純に協調させようとすると、各サブシステム間の組合せの数だけ統合の仕方があり、その設
計論は集中型システムよりかえって複雑になり、高価なことになってしまうことになりかねない[2]・
本節では、自律分散システムにおける各サブシステム間の組合せに注目し、上記の問題点を解決する方法の一 つとして、２章で紹介した「安定結婚問題[４Ｍの自律分散システムヘの適用を考慮し、安定結婚問題を自律分散 環境へ適用した「分散安定マッチング問題」の提案を行う。更に、分散安定マッチング問題を解く協調アルゴリ ズムである分散Gale-Shapleyアルゴリズムの提案、及び提案アルゴリズムによって得られる安定マッチングか ら、提案アルゴリズムの解析を行う。 3.1分散安定マッチング問題の定義 安定結婚問題では、２つの集合、男性グループおよび女`性グループが与えられ、各々のグループには同じ数の メンバーが属しており、男性グループと女性グループに共通に含まれるメンバーは存在しないものとする。加え て、各メンバーは、異なるグループに属する任意の二メンバーに対し、どちらが好ましいかを判断でき、その判断基準を基に全ての異なるグループに属するメンバーを順序付けたリスト(PL)をもっている。問題で定義して
いる安定マッチングは、任意のメンバーｐが現在のパートナー９１より好ましいメンバーγとペアとなることを望んだとしても、γはγにとってｐより好ましいメンバーをパートナーとしていることにより、ｐの希望に応え
ないことからマッチングが壊れないという特徴を持っている。安定結婚問題は、実社会の広い範囲に適用可能であり、また、数学的な興味もあることから、多くの研究者に高い関心を持たれている［5,6]・
本節では、安定結婚問題を自律分散システムに適用し、自律分散環境において安定マッチングを求める「分散 安定マッチング問題」の定義を行う。 分散安定マッチング問題は、安定結婚問題同様、同じメンバー数ｎからなる２つの集合、男性グループ、、女 性グループｗが与えられる。このとき、各々のグループに属する各メンバーは、自身とは異なるグループに属 するメンバーを好ましい順に列ぺたＰＬを持つ。 安定結婚問題を自律分散システムヘ適用する前に、本論文で想定する自律分散システムを次の様に定義する。 《自律分散システム》 1.システム全体を統合する管理機構をもたない。 2.システムを構成する分散要素は自律的に行動する。 3.任意の分散要素間で相互に通信することにより情報交換が可能な非同期システムである。 4.分散要素内の全ての命令は有限時間内で終了する。 5.通信遅延は有限である。 上記の「分散要素」とは、自律分散システムにおける「サブシステム」のことであり、特に「自律」であるこ とを強調して「個」と呼ぶこともある。安定マッチング問題における各メンバーを、上記の様な分散システムに おける分散要素と捉えることにより、分散システムへ安定結婚問題を適用する。 本研究では、分散安定マッチング問題を次のように定義する。 定義９自律分散システムにおいて、有限回のメッセージ通信と有限時間の計算により、次に示す初期状態から 最終状態へ導く協調アルゴリズムを開発することを目的とする問題を分散安定マッチング問題という。 初期状態 ・各メンバーは、他の全てのメンバーの識別子(ID）と所属しているグループを知っている。 。各プロセスは、自己のＰＬのみ持っている。 －２８－終了状態 ・各メンバーは、自身のパートナーを知っている。 ・分散システム全体として各メンバーの組み合わせは安定なマッチングとなっている。 3.2分散Gale-Shapleyアルゴリズム 分散安定マッチング問題を解く協調アルゴリズムとして、Gale-Shapley基本アルゴリズムを基にした分散Gale-Shapleyアルゴリズムの提案を行った［3]。この協調アルゴリズムにおいては、メンバー間で次のメッセージの 送受信を行う。 《基本通信メッセージ》 Propose:送信者の受信者に対するパートナー要請を意味する。 Accept:送信者が受信者のパートナー要請を受諾したことを意味する。 Reject：送信者が受信者のパートナー要請を断わったことを意味する。 Proposed:送信者がパートナー要請きれたことを受信者に対し伝える。 また、提案アルゴリズムにおいては、メッセージは次のコマンドにより送受信される。 《基本通信命令》 send(p,Mes)：メッセージＭｅｓをｐへ送る。 Receive(p,Mes):ｐからのメッセージＭｅｓを受け取る。 提案した分散Gale-Shapleyアルゴリズムは、二つのサブアルゴリズムからなっている。サブアルゴリズムの一 つは、男`性グループに属するメンバーが実行し、Proposeメッセージの送信を行う。もう一方のサブアルゴリズ
ムは、女`性グループに属するメンバーが実行し、受信したProposeメッセージに対しRejecetもしくはAccept
メッセージを送信する。先ず初めに、男性メンバーが実行するProposeメッセージ送信者用のアルゴリズムを 図３に示す。 以下に、図３のアルゴリズムの詳細について説明する。先ず、３行目においてランク変数ｊを初期化する。ランク変数ｉは自身のＰＬにおける順位(ランク）を示す
変数である。 ６行目では、自身のＰＬのｊ番目の異性メンバーを(パートナー)被要請者変数切に代入する。被要請者変数ｍは、Proposeメッセージの送信先となる異性メンバー、つまり自身のパートナーとなることを要請する（して
いる）メンバーを示す変数である。 ８行目で、異`性メンバーｕ)に対し、Proposeメッセージの送信を行う。 ９行目では、自身に届いたメッセージを取り込む。メッセージが届いていない場合には、届くまで待つ。 １２行目は、届いたメッセージがRejectメッセージの場合実行される。Rejectメッセージを受信したことから 被要請者ｕノヘのパートナー要請を断わられたこととなり、自身のＰＬにおいてｕﾉの次に位置する異`性メンバー へパートナー要請を行う為、ランク変数ｊに１加算し、５行目から１６行目を繰り返す。 １４行目は、届いたメッセージがAcceptメッセージの場合実行される。Acceptメッセージを受信したことか ら被要請者ｕノヘのパートナー要請が受諾きれたこととなり、パートナー要請を終了し、ループを抜ける。 １７行目で、パートナー要請を受諾したｕｊをパートナー変数partnerに代入し、アルゴリズムを終了する。 次に、女性メンバーが実行するProposeメッセージ受信者用のアルゴリズムを図４に示す。 以下に、図４のアルゴリズムの詳細についての説明を以下に示す。 －２９－ｐｒｏｃｅｄｕｒｅＭａｎｉｓ ｂｅｇｉｎ ｊ：＝１； ／＊jistherankofPL＊／ ｌｏｏｐ Ｔｕ：＝ｔｈｅｊ－ｔｈｍｅｍｂｅｒｏｆＰＬｉ ／*misthewomanmember*／ send(､,Propose)i Receive(ｍ,Mes)ｉ ｃａｓｅＭｅｓｉｓ ｗｈｅｎＲｅｊｅｃｔ： ｊ＝j＋Zi whenAccept： breaktheloop； ｅｎｄｃａｓｅｉ ｅｎｄｌｏｏｐ； partner：＝Ｔｕｉ ｅｎｄ １２３４５６７８９０１２３４５６７８ １１１１１１１１１ 図３:Proposeメッセージ送信者用分散Gale-Shapleyアルゴリズム 先ず、３行目において、（パートナー)要請者変数ｍを初期化する。要請者変数ｍは、受信したProposeメッ セージの送信者を示す変数である。 ５行目で、自身に届いたメッセージを取り込む。メッセージが届いていない場合には、届くまで待つ。 受信したメッセージがProposeメッセージであった場合、８行目において、既にProposeメッセージを受信し たことがあるかどうかを判定する。Proposeメッセージを受信したことがない場合、９行目で、要請者変数ｍに Proposeメッセージの送信者を代入し、１０行目で全女性メンバーにProposedメッセージを送信する。ProPose メッセージを受信したことがある場合、要請者変数ｍは、先に受信したProposeメッセージの送信者を示して いることから、先にProposeメッセージを送信してきた、と新たにProposeメッセージを送信してきたＰの どちらが自身にとって好ましいか、つまり自身のＰＬにおいて上位に位置するかを判定する。ｐのほうが、より 好ましい場合、１２行目でｍに対しRejectメッセージを送信し、１３行目でｍにＰを代入する。ｍのほうがＰ より好ましい場合、１５行目でｐに対しRejectメッセージを送信する。 受信したメッセージがProposedメッセージであった場合、１８行目で全女性メンバーからProposedメッセー ジを受信したかどうかを判定する。全女性メンバーからProposedメッセージを受信する迄、４行目から２３行目 を繰り返す。全女性メンバーから受信した場合、１９行目でｍに示される男性メンバーにAcceptメッセージを 送信し、２０行目でループを抜ける。 ２４行目で、パートナー要請を受諾したｍをパートナー変数partnerに代入し、アルゴリズムを終了する。
3.3分散Gale-Shapleyアルゴリズムの性質
本節では、３．２節で提案した分散Gale-Shapleyアルゴリズムについて考察する。提案した分散Gale-Shapley アルゴリズムによって導かれる安定マッチングについて次の補題を導くことができる。 補題３分散Gale-Shapleyアルゴリズムは、インスタンスおよび各メンバーの役割が同じ場合、常に同一の安定 マッチングを導く。 －３０－ｐｒｏｃｅｄｕｒｅＷＯＭＡＮｉｓ ｂｅｇｉｎ ｍ：＝nulli Ioop Receive(P,Mes)； ｃａｓｅＭｅｓｉｓ ｗｈｅｎＰｒｏｐｏｓｅ ｉｆｍ：＝nullthen m：＝ｐ； send(everywomanwhoparticipates,Proposedk elseifpreferptomthen send(ｍ,Reject)； ｍ,＝ｐ； else Send(p,Reject)i endi2 whenProposed： ifreceivedProposedfromeverywomａｎｔｈｅｎ Ｓｅｎｄ(ｍ,Accept)； ｂｒｅａｋｔｈｅｌｏｏｐｉ ｅｎｄｉ２ ｅｎｄｃａｓｑ ｅｎｄｌｏｏｐｉ ｐａｒｔｎｅｒ：＝ｍ； １２３４５６７８９０１２３４５６７８９０１２３４５ １１１１１１１１１１２２２２２２ eｎｄ 図４:Proposeメッセージ受信者用分散Gale-Shapleyアルゴリズム －３１－
証明本証明においては、男性メンバーをPropose送信側、女性メンバーをPropose受信側として分散Gale‐ Shapleyアルゴリズムを実行したと仮定し議論を進めていく。このとき、２度アルゴリズムを実行し、異なる安 定マッチングヘ導かれたと仮定する。 １度目のアルゴリズム実行過程をプロセスＡ、２度目をプロセスＢとしたとき、異なる安定マッチングヘ導 くには、次の事象の何れかが生じた場合である。 1.プロセスＡとＢにおいて、ある男性メンバーのProposeメッセージの送信先となる女性メンバーが異なる。 2.プロセスＡとＢにおいて、ある女'性メンバーのRejectメッセージの送信先となる男'性メンバーが異なる。 補題は、各メンバーのＰＬが同一である場合についてのものであることから、ＰＬの変更による送信先の変化 は生じない。
提案アルゴリズムより、男`性メンバーは自身のＰＬの最上位から順位にしたがってProposeメッセージを送
信することから、各男性メンバーｐのプロセスＡとＢでProposeメッセージの送信先が異なるというのは、ｐ
の女`性メンバーｑへのProposeメッセージに対し、プロセスＡではAcceptメッセージを受信するが、プロセ スＢではRejectメッセージを受信する、またはその逆の場合のみである。また、女`性メンバーがRejectメッセージを送信するのは、ＰＬのみに基づき、Proposeメッセージの受信順序
とは関係が無いことから、ＰＬが変わらない限りRejectメッセージを送信する男`性メンバーは変わらない。よっ て、常に同一の安定マッチングを導く。□ 常に導かれる安定マッチングの性質について次の定理を導くことができる。定理２分散Gale-Shapleyアルゴリズムによって導かれる安定マッチングは、Propose送信側にとってもっとも
優位な安定マッチングである。証明本証明においては、男`性メンバーをPropose送信側、女性メンバーをPropose受信側として分散Gale-Shapleyアルゴリズムを実行したと仮定し議論を進めていく。分散Gale-Shapleyアルゴリズムによって導かれ
る安定マッチングをＭ、ＭよりPropose送信側メンバーにとって優位な安定マッチングをＭノと仮定する。仮定より、Ｍ'および〃の間には、ローテーションが存在する。つまり、Ｍ'ルーＭが成り立つ。βに現わ
れる任意の男性メンバーｍは、Ｍ'におけるパートナーｕﾉ’に対し分散Gale-Shapleyアルゴリズム実行中に
Proposeメッセージを送信している。また、分散Gale-ShapleyアルゴリズムによってＭが導かれたことから、 tu'からRejectメッセージを受信している。ＵﾉﾉがRejectメッセージをｍに対し送信するには、より上位の男 性メンバーからProposeメッセージを受信した場合のみであり、アルゴリズムの性質に矛盾する。 よって、常にPropose送信側に最も優位な安定マッチングが導かれることが証明された。分散Gale-Shapleyアルゴリズムによって得られる安定マッチングは、基となるGale-Shapley基本アルゴリ
ズムと同様、男性メンバーがProposeを行い、女性メンバーがそれを受けるとき、得られる安定マッチングは、
男`性優先解となり、女'性メンバーがProposeを行い、男性メンバーがそれを受けるとき、得られる安定マッチン グは、女`性優先解となる。４マッチング再構成
分散安定マッチング問題においては、Gale-Shapley基本アルゴリズム［4]を基にした分散Gale-Shapleyアル
ゴリズム[3]により、安定マッチングを得ることが可能であるが、３．３節で示したように、Gale-Shapley基本ア
ルゴリズム同様、複数存在する安定マッチングの中で特定のマッチングしか得ることができない。本節では、任意の安定マッチングの状態から、異なる安定マッチングヘ遷移する手法であるマッチング再構成
について述べる。本研究では、現在、複数のメンバーによるマッチング再構成の実行について熟慮しているが、 －３２－本論文では、その基本となる、単一のメンバーのみによりマッチング再構成の実行ができるという仮定を設け、 その仮定におけるマッチング再構成が正しく異なる安定マッチングを導くための必要十分条件を示す。 分散安定マッチング問題においては、各メンバーは、「可能な限り好ましいメンバーをパートナーにすること を望む」という性質を持つことを前提条件としている。この前提条件より、現在のパートナーより好ましいメン バーが存在する場合、より良いメンバーをパートナーすることを切望すると考えることができる。本章では、パー トナーに不満を持つメンバーの自律的な行動により端を発するパートナー交換によって、よりよい安定なパート ナーとペアとなる安定マッチングを得る手法を提案する。 先ず、マッチング再構成の手法を定義する。 《マッチング再構成の定義》 定義１０任意の安定マッチングＭにおいて、メンバーＰが、現在のパートナーに対しRejectメッセージを送 信し、各メンバーが分散Gale-Shapleyアルゴリズムに基づいた行動をとるとき、Ｍとは異なる安定マッチング へ導かれる。この手法をマッチング再構成と呼ぶ。このときのパートナー交換の実行過程を再構成プロセスと呼 び､mrpiルと表現する。また、ｐをmrpll`の起動者という。 メンバーｐが、安定マッチングＭにおけるパートナーに対し自律的にRejectメッセージを送信したとき、再 構成プロセスが起動されたという。再構成プロセスによるパートナー交換の結果、起動者ｐが新たなパートナー を得た場合、起動前とは異なる安定マッチングヘ導かれている。このとき再構成プロセスは成功したという。一 方、ＰＬの最下位の異性メンバーからRejectメッセージを受信し、これ以上Proposeメッセージを送信する相 手がいないメンバーが現れた場合、起動者は新たなパートナーを得ることができず、この場合、起動前とは異な る安定マッチングへ導けなかったことになり、再構成プロセスは失敗したという［３１。 提案したマッチング再構成は、常に再構成プロセスは一つしか存在しないという仮定のもとで充分に実行する ことができる。つまり、パートナー交換は成功する。常に再構成プロセスは一つしか存在しないという仮定は、 再構成プロセスが複数存在する場合に比ぺ、最も単純なものである。本節では、この仮定のもと行われるシミュ レーションについて検証する。
定義’1マッチング再構成mTp粥の実行過程において、ローテーション伽に現われる(ハQ(ｊ)のペアのｐｉが
Rejectメッセージを伽におけるパートナー９，へ送信するとき、マッチング再構成においてローテーション伽 は起動されたという。 定義１２マッチング再構成ｍｒｐｉＷの実行過程で起動されたローテーション βｋ＝(PC,９０)(ハ91)…(ルー1ルー1） において、ｐ(i+,)ｍｏｄ７が9jからのPrOPOSeメッセージを受信した時、ローテーションβ虎は完了したと呼ぶ。 このとき、ｊ＝0,1,...,7-1とする。 補題４０をローテーションダイグラフとする。Ｇにおける任意のローテーションβは、βの先行ローテーショ ンが完了したときかつそのときに限り完了可能である。 証明マッチング再構成において、ローテーションβが起動されたと仮定する。定義６より、βの先行ローテー ションβ'が完了していない場合、βに現われるペアの中で形成されていないペア(ｍＭＵｊ)が存在する。βが完 了する為には、マッチング再構成の実行過程において、ｍｄからTDZまたはｕﾉzから川へのRejectメッセージ の送信が必要となるが、そのためには、β'が完了する必要がある。 また、ローテーションβが完了したと仮定すると、βに現われる全てのペアが形成されていたこととなり、そ れは、定義６よりβの全ての先行ローテーションが完了していることを意味する。よって、補題は証明された□ －３３－補題５ローテーションβの先行ローテーションβ'が起動されていない場合、βは、βが完了する以前にβ'を
起動する。証明本証明において、ローテーションβ＝(pMo)(p1,9,)…(ルー,ルー,）とし、ｐ,がｑ，に対しRejectメッ
セージを送信することによりマッチング再構成、叩協が起動するケースについて考える。この仮定は一般性を 失わない。 先ず始めに、（β',β)の関係がtypelである場合について考える。定義５よりβ'にペア(ハqp),(pq,9`)が現われ、βにペア(ハqi)が現われる。この場合､ｐ,および9`のＰＬ
は次のようになる。 ｐｚ：．．、９．－１．．．９１，．．．９ｐ・・・ ９ｉ：…ｐ９．．.ｐｊ・・・ｐ'－１．．．ここで、Ｐｌが９１へRejectメッセージを送信し、qjが分散Gale-Shapleyアルゴリズムに従ってProposeメッ
セージを送信する場合について考える。しかしながら、定義４より９１のパートナー要請は、９１のＰＬにお
いてｐ，からｐ２の間に位置する異`性メンバーには受諾されることはありえない。その結果、９，からのPropose
メッセージを受信した胸は、９２へRejectメッセージを送信し、９２は分散Gale-Shapleyアルゴリズムに従い
ProPoseメッセージを送信する。この過程を数回繰り返した後に、ｑｉ－１はｐｆへProposeメッセージを送信する。piはＰＬにおいて、現在のパートナー９ｐより上位に位置するｑｚ－１のプロポーズを受諾し、９ＰへRejectメッ
セージを送信する。これにより、β'が起動されることになる。次に、（β',/o)の関係がtype2である場合について考える。ここで、β'を次の様に仮定する。
β'＝(p6,96地1,91)…(pﾙｰ1,9ｶ-1）定義６より、次のｐｌと町のプリファレンスリストをみたすような'および』が存在する。
pji:…9;-,…9`…巧…
ｑ`:…p`…pji…p`+,…
ここで、Ｐｌが９１へRejectメッセージを送信し、ｑｊが分散Gale-Shapleyアルゴリズムに従ってProposeメッ
セージを送信する場合について考える。定義４より９１のパートナー要請は、９１のＰＬにおいてｐｌからｐ２の
間に位置する異性メンバーには受諾されることはありえない。その結果、９，からのProposeメッセージを受信
したＰ２は、９２へRejectメッセージを送信し、９２は分散Gale-Shapleyアルゴリズムに従いProposeメッセー
ジを送信する。この過程を数回繰り返した後に、qiはＰｉからのRejectメッセージを受信し、ｑｉのＰＬにおいて
仇の次に位置する異性メンバーヘProposeメッセージを送信する。定義４よりⅢはpjiより上位に位置する
全ての異性メンバーへのプロポーズは断わられ､PjiへProPoseメッセージを送信する。砂からのProposeメッ
セージを受信した坊は、現在のパートナーである必へRejectメッセージを送信する。これにより、β'が起動
されることになる。 □定理３ClosedSubsetCS'が安定マッチングＭに対応しているとし、ClosedSubsetCSpは、Ｃｓ'ｎｐを満た
すClosedSubsetの中で最小のClosedSubsetであると仮定する。ペア(川)が安定マッチングＭおよびロー
テーションβのそれぞれに現われ､Ｍにおいてｐがマッチング再構成を起動するとき、再構成プロセスmrpll‘
は安定マッチングＭｂ/OSbへ導く。 証明補題４および補題５より明らかである。定理４ClosedSubsetCSと対応する安定マッチングＭにおいてｐによって起動された再構成プロセスmrpll‘
は、起動者ｐとＭにおけるｐのパートナー９のペア(p’9)がローテーションβに現われるとき、且つそのと きに限り、異なる安定マッチングＭノヘ導く。このとき、Ｍ'は、βＵＣＳを含むClosedSubsetの中で最小の ClosedSubsetと対応する。 －３４－証明［十分性]定理３より、明らかである。 [必要性]定義４より明らかである。 ５まとめ 本論文では、自律分散システムにおける安定結婚問題の定義、および自律分散システムにおける安定結婚問題 を解く協調アルゴリズムの紹介、検討を行った。また、常に特定の安定マッチングが得られることから、任意の 安定マッチングから異なる安定マッチングへ遷移する手法の紹介、検討を行った。 今後は、電子商取引等で発生する商品と購買者との組合せ等の自律分散システムにおいて発生する諸組合せ問 題に対し、提案した手法の適用について研究を行う。
