マッチングモデル
田村 明久…l川l………l………l……ll州Il…………………ll川Illll州Il川IIM川Il………l…………llll州l州l川Il州Il…………llll…………ll川Ill…………ll川l…ll川Ill川Il……l州l…………………ll…州州…l（1，2，3，4）の場合のマッチングの例で，組を成す男女
1． はじめにを辺で結んでいる．

ご存知の方も多いと思うが，臨床研修医の研修病院

安定結婚モデルでは，結婚させた組が離婚しないよへの割当てを全国的な規模で行うシステムが昨年からうなある種の安定性が提案されている．この安定性を始動した［1］．研修医は希望する病院に優先順序を付導入するために，各人は異性に対して好みの順番を持け，痛院は研修希望者に優先順序を付ける．そのもとつとする．ここでは文献［2］で扱われている状況よりで研修L矢からも病院からも不満が出ない割当てを求め

少し融通を持たせ，同程度に好きである状況（無差か一．このシステムではGale・Shapley［2］による安別）を許すことにする．与えられたマッチングガに定結婚モデルが利用されている．研修医の集合と病院

対して，ズでは組とならない男性オと女性ノが存在の集合を例とするような交わりを持たない二つの主体

し，才は方のパートナーよりもノを好み，ノもズでの集合を考え，異なる集合に属する主体間の割当てやのパートナーよりも∠を好むならば，才とノがより好物の売り買いを扱う市場モデルはtwo−Sided match−

ましい相手との再婚を望むとみなし，Xは不安定でingmarketなどと総称されている（本稿ではマッチあると定義する（パートナーと同程度に好きな異性とングモテリレと呼ぶことにする）．マッチングモデルには，離婚してまで再婚する意志がないとしている）．

は，先の安定結婚モデルとShapley・Shubik［3］によマッチングが上の意味で不安定でないとき，安定である割当ゲームという二つの標準的なモデルがある．割るという（無差別を許す場合には他にも安定性が定義

当ゲームでは主体間の貨幣のやり取りを許すが，安定されるが，これらと区別するために弱安定ということ結婚モデルではそれを許さないのが最大の相違点であもある）．Gale・Shapleyは，無差別がない場合に安る．本稿では，安定結婚モデル，割当ゲームおよびこ定マッチングを求めるアルゴリズムを提案することで，れらを特殊ケースとして含むモデルについて考える．

その存在を構成的に示している．無差別を許す場合も同様の議論が通用し，常に安定マッチングが存在する．

2．安定結婚モデル

安定マッチングの存在証明については，非構成的なも安定結婚モデルでは，交わりを持たない二つの集合を男性から成る集合〟と女性から成る集合Ⅳとしのとして不動点定理を用いたものもある（例えば文献［4］参照）．てしばしば説明がなされるので，本稿でもそれに従う割当ゲームの設定と合わせるために，次では安定結ことにする．話を簡単にするために，男女の人数はそ婚モデルの安定性の別表現を与える．まず各人の異性れぞれ邦人とする．

に対する好みの順番を正実数により表す．具体的には，「結婚」とあるように，〃対の男女の組を作り，それぞれの組を結婚させる状況を想定する．安定結婚モ

男性才∈〟の女性ノ∈Ⅳに対する評価を恥＞0で表し，恥＞α〜々のときかつそのときに限りオはノを々よ

デルでは一夫一婦制を前提とし，構成した男女の組の集合ではどの人もちょうど一つの組に含まれるようにしたい．この条件を満たす男女の組の集合をマッチン
グと呼ぶことにする．図1は，〟＝（α，∂，C，の，彷′＝
たむら あきひさ
慶應義塾大学捜L学部〒223−8522横浜市港北lズ【1ごf3−14−1
2005年41j〜j一

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

（29）24丁り好むとし，αむ＝伽のときオはノと々を同程度に好ートナーよりも好ましい存在となり，マッチングの組むとする．また女性ノ∈Ⅳの男性グ∈〟に対する評み替えを希望するためズは不安定であると言える．

価を占iJ＞0で表し，上と同様に好みの順番と対応さまとめると，（al）のもとで（a2）と（a3）が成立するなせる．このとき，マッチングズが安定であることのらば，単独の希望で組を解消したり，男女の組の希望定義は，次の条件を満たす乃次元ベクトルヴ＝（射】ブ∈によりマッチングが壊されることはない．

〟），γ＝（ゎレ∈Ⅳ）が存在することと書き換えられる割当ゲームにおける安定マッチングの存在は線形計画問題に対する双対定理と解の整数性により示すことのは明らかであろう：（ml）qi＝auand71＝bt，for（i，j）∈X，ができる．男性集合〟，女性集合Ⅳと利益ベクトル（m2）qi≧auorタ1≧bむfor（i，j）∈MxW，α，占により定義される割当問題の線形計画問題として

ただし〟×W′は男女の組全体から成る集合とする．
（ml）を男性才と女性ノが結婚することによってそれぞれ恥れという収入を得ると解釈すると，（m2）はの定式化
最大化 ∑ （αむ＋∂む）∬む（f，ノ）∈〟×lγ

制 約 ∑Jゎ≦1（ブ∈〃）J∈lγ

どの男女の組に対しても2人が同時により大きな収入∑∬ゎ≦1（ノ∈Ⅳ）を得ることはないことを意味している．

i∈〟∬む≧0（（∠，ノ）∈〟×Ⅳ）

3．割当ゲームとその双対問題

割当ゲームでも主体の集合を安定結婚モデル同様に同じ大きさの男性集合〟と女性集合Ⅳとしよう．

最小化 ∑射＋∑n ∫∈〃ノ∈抑
制 約 射＋れ≧恥十∂ゎ（（ダ，ノ）∈〃×Ⅳ）

前節の後半部分と同様に，各男女の組（オ，ノ）に対し二射≧0 （オ∈〃）つの正実数αゎ，∂び＞0が与えられているとする．割当n≧0 （ノ∈Ⅳ）

ゲームでは，これらの実数はグとノが組んだときにそを考える．主問題の実行可能領域は非空で有界である

れぞれ恥と∂ゎという利益を上げることができるとから必ず最適解が存在する．主問題の目的関数のすべ解釈する．割当ゲームでもマッチングの安定性を考えての係数が正であり，〟とⅣの大きさが同じため主るが，利益の供与が許されている点が安定結婚モデル

問題の最適解は第1，第2制約をすべて等号で満たす．の設定と大きく異なる．すなわち，マッチングズのさらに，主問題の任意の最適基底解ご＊のすべての成男女の組（才，ノ）は2人の総利益恥＋∂ゎを配分し，そ分が整数となることが知られている．第1，第2制約

れぞれの収入断とれを得る．割当ゲームでは，次のよりJ＊の各成分は0か1となり，J芸＝1を満たす組

条件を満たす男性の収入ベクトルq＝（射け∈〟）と女（才，ノ）全体の集合はマッチングズ＊となる．一方，双性の収入ベクトルγ＝（れレ∈Ⅳ）が存在するとき，マ対定理より双対問題も最適解を持つ．双対問題の最通ッチングズは安定であると定義する：

解をq＊，γ＊とすると，これらが（a2）と（a3）を満た（al）射十れ＝恥＋∂むfor（才，ノ）∈ズ，すことは，双対問題の制約より明らかである．さらに，（a2）qi≧Ofori∈Mand71≧Oforj∈W，J＊とす＊，γ＊は相補性条件を満たすので，X＊内の組（a3）射＋わ≧恥＋∂ゎfor（オ，ノ）∈〟×Ⅳ．

（オ，ノ）に対し，双対問題の第1制約は等号で成立しけ（al）は先に述べたようにマッチング内の組は総利益ればならない．すなわち，X＊，￠＊，γ＊は（al）も満を配分できることを意味する（安定結婚モデルのたす．まとめると，主問題の最適基底解は安定マッチ（ml）と比較していただきたい）．（a2）は，負の収入ングを与え，安定マッチングの存在が示せる．逆に割を得るくらいならば誰とも組まず収入0の方がましで当ゲームの安定マッチングは，主問題の最適基底解をあり，その場合に又は安定とは言えないことを意味与える．

する．（a3）は，どの男女の組もq，γの下での合計収次に割当ゲームの安定性を女性側から男性側への利入を上回る利益を得ることができないことを主張して益供与額に注目して見直してみる．マッチングを構成いる．もし（a3）が不成立ならば，ある組（オ，ノ）が存在する前の状況を想定し，各男女の組（才，ノ）はもし組ん

し射＋れ＜αむ＋れとなる．このとき，オとノは総利だならばノからオにれだけ利益供与をすると約束し益恥＋∂むを適当に配分することで共に収入を増やすたとする（実際には九＞0なら女性から男性に利益ことができる．すなわち，オとノは互いにズでのパ
248（30）オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

供与が行われ，れ＜0ならば男性から女性に利益供与

組（〆，ノ）は総利益α〜ノ十∂りを配分することを意味してが行われる）．このれをノから才への手付と呼ぶこといる．（g2）の解釈は（a2）と同じである．（g3）が不成にする．マッチングズが安定であるための必要十分立とすると，ある（オ，ノ）∈〟×Ⅳとc∈［竺わ，和］が存条件は，次の条件を満たす手付ベクトル♪＝（れけ∈在し，射＜恥＋cかつりく∂ゎーCが成り立つ．この〃，ノ∈Ⅳ）が存在することである：

とき，（gl）を仮定するならば（オ，ノ）任芽であり，ダと（pl）aL，＋れ＝maX（alh＋Pz・klk∈W）≧O for（i，ノは上下限を満たす手付cによリ2八とも収入を増やすことができる．これは，♪の」Fではダとハこはガノ）∈方，（p2）biJ−れ＝maX（b烏j−Dhj［k∈M）≧O for（i，が満足できるマッチングではないことを意味する．
次に安定結婚モデルと割当ゲームの安定性が上記のノ）∈ズ．
この特徴付けは次のように示せる．方が安定マッチングであるならば，（al），（a2），（a3）を満たすべク安定性の特殊ケースとなることを示す．

まずは，安定結婚モデルとの関係を示すために

トルq，γが存在する．ベクトル♪を，各（ブ，ノ）∈〟×

旦＝（0，0，‥・，0），Ⅳに対しれ＝∂ゎーゎと定める．（al）より（オ，ノ）∈ズ

斤＝（0，0，…，0）に対し須＝勒十れが成立するので，（a2）は（pl），である場合，すなわち利益供与が許されない場合を考（p2）における恥＋れ，∂揖−れの非負性を保証する．

える．このとき，（gO）から手付ベクトル♪のすべてれの定義より，すべての（オ，ノ）∈〟×Ⅳに対しゎ＝の成分は0であるから，（gl）は（ml）と同じ主張とな∂〜ノーれが成立するので（p2）における等号は自明に成る．また所与のベクトルα，∂の非負性から，（g2）

立する．さらに，この事実と（al），（a3）が（pl）の等は（gl）から誘導される．（g3）におけるcも0でなけ号を導く．逆に，マッチングXに対して（pl），ればならないので，（g3）は（m2）と同一となる．した（p2）を満たすべクトル♪が存在したとする．（才，ノ）∈がって，竺，斤を上記のように定めれば，本節のモデズに対して，射＝恥＋れ，71＝∂〜ノー九とq，rを定め

ルにおける安定性は，安定結婚モデルの安定性と等佃ると（al），（a2），（a3）が成立する（すべての男女はとなる．

Xのある組に含まれるのです，γは定義される）．

4．手付に上下限制約を持つモデル
この節では，先に述べた安定結婚モデルと割当ゲー割当ゲームとの関係を示すために旦＝（−∞，−∞，…，−∞），斤＝（＋∞，＋∞，…，＋∞）である場合，すなわち手付に全く制約がない場合を考

ムの安定性を特殊ケースとして含むような安定性を考える．このとき，（gO）は恒真であり，（gl），（g2）はえる．〟，杯′，α，ろが所与というのは，節2，節3それぞれ（al），（a2）と同じ主張である．（g3）とと同様とする．本節のモデルでは，さらに手付に上下（a3）の同値性は，限の制約がある場合を扱う．各（7，ノ）∈〟×Ⅳに対し，

酌＋り＜αり＋れ声＝＝⇒動≦和を満たす空わ∈RUト∞）と庁わ∈RU（＋∞）に∃c∈R：須＜αゎ十c，り＜占〜ノ岬Cより手付れの下限と上限を表すとする．
本節では，マッチングー方が安定であるとは，次の条件を満たす手付ベクトル♪∈R〟×Ⅳが存在することという関係より示せる．したがって，旦，庁を上記のように定めれば，本節のモデルにおける安定性は，割当ゲームの安定性と等価となる．
安定結婚モデルでも割当ゲームでも安定マッチングと定義する：（gO）旦まノ≦れ≦庁むfor（g，ノ）∈〟×Ⅳ，は常に存在したが，本節のモデルでも安定マッチング（gl）qi＝al，＋Dij and71＝bij−Z）ij for（i，j）∈

は存在するであろうか．実は，より一般的なモデル［5，6］に対する結果から本節のモデルでの安定マッチング

一方，（g2）qi≧Ofori∈Mand71≧Oforj∈W，の存在が系として導かれる．金子［5］では，特性関数（g3）qz・≧at，＋c or71≧biJ−C for（i，j）∈Mx

により抽象化されたモデルが提案され，そのモデルにおけるコアの存在が示されている．本節のモデルと金ll ．

子のモデルの関係を説明するのはそれほど安易ではな

C∈R with7TL，≦c≦庁zJ．

（gO）は手付が上下限制約を満たすという条件であり，いためここでは避けるが，金子のモデルでのコアの存（gl）は（手付の上下限制約の下で）マッチング内の在から本節のモデルでの安定マッチングの存在が導か

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

（31）249

れることだけを述べておく．

があるかという興味がある．

文献［6］は，手付に上下限制約を持たせるというア

ここでは理論的な側面から，安定結婚モデル，割当イデアを導入し離散凸解析［7，8］を応用することで，ゲームそして手付に上下限制約を持つモデルの安定性多くのマッチングモデルを含むモデルを提案し，そのを簡単に紹介したが，安定結婚モテルも割当ゲームもモデルにおける安定マッチングの存在を示している．

現実問題への応用が多数なされている．例えば，安定

実は，本節のモデルはこのモデルの簡略版であり，こ結楯モデルは医師の病院への割振りや研究室配属などのことからも本節のモデルでの安定マッチングの存在実用場面で利用されている．割当ゲームも学生の授業が導かれる．また文献［6］の結果より，安定マッチン科目への割振りに利用される［9］など，実用面での利グの特徴付けとして（pl），（p2）の拡張に当たるもの用も多い．手付に上下限制約を持つモデルは，安定結が得られる．マッチングXが安定であるための必要婚モデルと割当ゲームの自然な拡張であると思うが，十分条件は，次の条件を満たす手付ベクトルA〟×

これについても何らかの応用があればと願うばかりでⅣの部分集合E肌 且Ⅳが存在することである：

ある．

（gO′）旦≦♪≦庁，ズ⊆E〟∩且Ⅳ，E〟UEⅣ＝〟×
参考文献

Ⅳ，（gl′）侮＋九＝maX（α摘＋毎l（ダ，々）∈且〟）≧O［1］医師臨床研究マッチング協議会，財団法人医療研修推進財団，http：／／www．jrmp．jp／．

for（才，ノ）∈ガ，（g2′）∂ゎーれ＝maX（占烏ノー♪々Jl（々，ノ）∈EⅣ）≧O［2］D．GaleandL．S．Shapley：Co11egeadmissionsandthestabilityofmarriage，771eAmericanMathematicalfor（g，ノ）∈ズ，（g3′）九＝革メfor（i，j）∈（MxW）＼EM and Pij＝庁びfor（才，ノ）∈（〟×Ⅳ）＼E肌（gO′）〜（g3′）の詳しい説明は紙数の都合上割愛する〟わ摘め，69，9−15（1962），［3］L．S．Shapley and M．Shubik：The assignment
gameI：The core，InternationalJoumalqf Game乃eoり，1，111−130（1972）．

が，この特徴付けの利点は安定マッチングを求めるに［4］T．Fleiner：Afixedpointapproachtostablematch−はこれらの条件を満たすガ，♪，E肌 EⅣを求めればingsandsomeapplications，Mathematicsqf（砂e7dions

良いことである．事実，文献［6］における安定マッチ

斤gseα汀ゐ，28，103−126（2003）．

ングの存在証明は構成的なもので，Gale・Shapley［5］M．Kaneko：Thecentralassignmentgameandthe［2］の提案したアルゴリズムと最大量みマッチングをassignment markets，Joumald MathematicalEco一求めるアルゴリズムを複合したアルゴリズムが（gO′）

〜（g3′）を拡張した条件を満たすものを常に求めると

乃0∽才cs，10，205−232（1982）．

［6］S．FujishigeandA．Tamura：Atwo−Sideddiscrete−
COnCaVe market with bounded side payments：Anいう議論である．

approachbydiscreteconvexanalysis，RIMSPreprint

5．おわりに1470，Kyoto University，2004．http：／／www．kurims．

安定結婚モデルと割当ゲームに対しては安定マッチングの存在証明に非構成的なものがある．先にも触れたが，安定結婚モデルに対しては不動点定理を用いたものが存在する．節3で説明したように，割当ゲームに対しては最適化での諸定理がある．文献［6］のモデルに対しても，非構成的な安定マッチングの存在証明250（32）kyotoLu．aCjp／home＿page／preprint／1ist／［7］室田一雄：離散凸解析（共立出版，東京，2001）．

［8］K．Murota：Disc77？te Conuer Ana如is（Society forIndustrialand Applied Mathematics，Philadelphia，2003）．

［9］今野浩：数理決定法入門−キャンパスのOR（朝倉書店，東京，1992）．

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