[博弈論書籍].two-sided.matching.theory

《[博弈論書籍].two-sided.matching.theory》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、Two-SidedMatchingTheoryM.UtkuünverBostonCollegeM.UtkuünverTwo-SidedMatchingTheoryIntroductiontotheTheoryofTwo-SidedMatchingToseewhichresultsarerobust,wewilllookatsomeincreasinglygeneralmodels.Evenbeforewelookatcomplexdesignproblems,wecangetaheadstartat?guringoutwhichareourmostapplica

2、bleresultsbydoingthissortoftheoreticalsensitivityanalysis.Discretemodels1Onetoonematching:the"marriage"model2manytoonematching(withsimplepreferences):the"collegeadmissions"model3manytoonematchingwithmoneyandcomplex(grosssubstitutes)preferencesTheselecturesontheoryfollowRothandSotomay

3、or(1990),andtheoremsarenumberedasinthebook.M.UtkuünverTwo-SidedMatchingTheoryOne-to-OneMatching:TheMarriageModelGaleandShapley,AMM(1962)Amarriagemarketisatriple(M,W,%)withMisa?nitesetofmenWisa?nitesetofwomen%=(%k)k2M[Wisapreferencepro?lewhere%misapreferencerelationoverW[fmg%wisaprefe

4、rencerelationoverM[fwgLetkbethestrictpreferencerelationderivedfrom%kikjmeansi%kjandnotj%ki.Ifagentk2M[Wpreferstoremainsingleratherthanbematchedtoagentj,i.e.ifkkj,thenjisunacceptabletok.(Ifanagentisnotindi?erentbetweenanytwoacceptablemates,orbetweenbeingmatchedandunmatched,we’llsay

5、he/shehasstrictpreferences.Sometheoremsbelowarevalidonlyforstrictpreferences.Ifotherwisementionedweassumethatpreferencesarestrict.)M.UtkuünverTwo-SidedMatchingTheoryOne-to-oneMatching:TheMarriageModelAnoutcomeofthemarriagemarketisamatchingm:M[W!M[Wsuchthatm(m)=wi?m(w)=mandforallmande

6、itherm(w)2M[fwgandm(m)2W[fmg.Amatchingmisblockedbyanindividualk2M[Wifkprefersbeingsingletobeingmatchedwithm(k),i.e.kkm(k).Amatchingmisblockedbyapair(m,w)2MWiftheyeachprefereachothertotheirpartnersunderm,i.e.wmm(m)andmwm(w).Amatchingisstableifitisn’tblockedbyanyindividualorpairofa

7、gents.AstablematchingisPareto-e?cient.M.UtkuünverTwo-SidedMatchingTheoryStabilityofMarriage:(xkcd.com)M.UtkuünverTwo-SidedMatchingTheory(Strong)Core,WeakCore,TheSetofStableMatchingsTheweakcoreisthesetofmatchingsmsuchthatthereexistsnomatchingnandcoalitionTM[Wsuchthatforallk2T,n(k)km

8、(k)andn(k)2T