[博弈论书籍].two-sided.matching.with.partial.information

《[博弈论书籍].two-sided.matching.with.partial.information》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Two-SidedMatchingwithPartialInformationBAHARAKRASTEGARI,UniversityofBritishColumbiaANNECONDON,UniversityofBritishColumbiaNICOLEIMMORLICA,NorthwesternUniversityKEVINLEYTON-BROWN,UniversityofBritishColumbiaThetraditionalmodeloftwo-sidedmatchingassumesthatall

2、agentsfullyknowtheirownpreferences.Asmarketsgrowlarge,however,itbecomesimpracticalforagentstopreciselyassesstheirrankingsoverallagentsontheothersideofthemarket.Weproposeanovelmodeloftwo-sidedmatchinginwhichagentsareendowedwithknownpartiallyorderedpreferenc

3、esandunknowntruepreferencesdrawnfromknowndistributionsconsistentwiththepartialorder.Thetruepreferencesarelearnedthroughinterviews,revealingthepairwiserankingsamongallinterviewedagents,performedaccordingtoacentralizedinterviewpolicy,i.e.,analgorithmthatadap

4、tivelyschedulesinterviews.Ourgoalisforthepolicytoguaranteebothstabilityandoptimalityforagivensideofthemarket,withrespecttotheunderlyingtruepreferencesoftheagents.Asinterviewsarecostly,weseekapolicythatminimizesthenumberofinterviews.Weintroducethreeminimiza

5、tionobjectives:(veryweak)dominance,whichminimizesthenumberofinterviewsforanyunderlyingtruepreferenceprole;Paretooptimality,whichguaranteesthatnootherpolicydominatesthegivenpolicy;andoptimalityinexpectationwithrespecttothepreferencedistribution.Weformulate

6、ourproblemasaMarkovdecisionprocess,implyinganalgorithmforcomputinganoptimal-in-expectationpolicyintimepolynomialinthenumberofpossiblepreferenceorderings(andthusexponentialinthesizeoftheinput).Wethenderivestructuralpropertiesofdominantpolicieswhichwecallopt

7、imalitycerticates.WeshowthatcomputingaminimumoptimalitycerticateisNP-hard,suggestingthatoptimal-in-expectationand/orParetooptimalpoliciescouldbeNP-hardtocompute.Finally,werestrictattentiontoasettinginwhichagentsononesideofthemarkethavethesamepartiallyord

8、eredpreferences(butpotentiallydistinctunderlyingtruepreferences),andinwhichagentsmustinterviewbeforematching.Inthisrestrictedsetting,weshowhowtoleveragetheideaofminimumoptimalitycerticatestodesignacomputatio