Stable Matching, Friendship, and Altruism ElliotAnshelevich RensselaerPolytechnicInstitute(RPI),Troy,NewYork Jointworkwith:OnkarBhardwaj(RPI),SanmayDas(WashU),MartinHoefer(MPI),YonatanNaamad(Princeton) Stable Matching Alsoknownas (cid:147)stable marriage" Classic gametheoryandalgorithmicproblem Applications: residentsandhospitals,studentsandschools, kidneymatching,... Motivation Stablematchingwithcardinalutilities Studentstoldto chooseprojectpartnersfor class Stablepartnerassignment: Notwostudentsshouldwanttoleavetheirpresentpartnerandbe partnerswitheachother (atleastoneofthemshouldbeunwilling) Motivation Stablematchingwithcardinalutilities Studentstoldto chooseprojectpartnersfor class Stablepartnerassignment: Notwostudentsshouldwanttoleavetheirpresentpartnerandbe partnerswitheachother (atleastoneofthemshouldbeunwilling) Adam 100 Eve Adam 100 Eve Adam 100 Eve 90 90 90 STABLE 90 90 Unstable 90 Assignment Assignment Juliet 55 Romeo Juliet 55 Romeo Juliet 55 Romeo Stable Matching with Cardinal Utilities Model Undirectedgraph,weightson theedges(denotedr ) uv Nodestoldto choosetheirpartners u,v partnersthenbothgetrewardr uv Nopartnerthen0reward Stability No(cid:147)blocking pair" (x;y) ablockingpairifx prefersy overits currentpartnerandvice versa. For now,higherpreference=morereward I. First Goal of this Talk Understand some basic properties of this "nice" stable matching model Doesastable matchingexist? Whatis the qualityof stable matchings? Canweimprovetheirquality? Adam 100 Eve Adam 100 Eve Adam 100 Eve 90 90 90 STABLE 90 90 Unstable 90 Assignment Assignment Juliet 55 Romeo Juliet 55 Romeo Juliet 55 Romeo I. First Goal of this Talk Understand some basic properties of this "nice" stable matching model Doesastable matchingexist? Yes: Greedymatchingsarestable. Whatis the qualityof stable matchings? Canweimprovetheirquality? Adam 100 Eve Adam 100 Eve Adam 100 Eve 90 90 90 STABLE 90 90 Unstable 90 Assignment Assignment Juliet 55 Romeo Juliet 55 Romeo Juliet 55 Romeo Quality of Stable Matchings Adam 100 Eve Adam 100 Eve Adam 100 Eve 90 90 90 STABLE 90 90 Unstable 90 Assignment Assignment Juliet 55 Romeo Juliet 55 Romeo Juliet 55 Romeo Quality of a matching Valueof matching: v(M) = P r (uv)2M uv Price of Anarchy: PoA= v(MOPT) v(Mworst;stable) Price of Stability: PoS = v(MOPT) v(Mbest;stable) I. First Goal of this Talk Understand some basic properties of this "nice" stable matching model Doesastable matchingexist? Yes: Greedymatchingsarestable. Whatis the qualityof stable matchings? Canweimprovetheirquality? Bounds on PoA, PoS v(M) =P r (uv)2M uv Price of Anarchy= v(MOPT) v(Mworst;stable) Price of Stability = v(MOPT) v(Mbest;stable) I. First Goal of this Talk Understand some basic properties of this "nice" stable matching model Doesastable matchingexist? Yes: Greedymatchingsarestable. Infact,stablematchingsareexactlythegreedymatchings. Whatis the qualityof stable matchings? Canweimprovetheirquality? Bounds on PoA, PoS v(M) =P r (uv)2M uv Price of Anarchy= v(MOPT) v(Mworst;stable) Price of Stability = v(MOPT) v(Mbest;stable)