2012/04/25 by Elliot Anshelevich, Anshelevich, Elliot, Onkar Bhardwaj +3
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Multiagent Systems (cs.MA)
paper · pdf · doi:10.48550/arxiv.1204.5780
openalex publication_date 2012/04/25 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We study stable matching problems in networks where players are embedded in a\nsocial context, and may incorporate friendship relations or altruism into their\ndecisions. Each player is a node in a social network and strives to form a good\nmatch with a neighboring player. We consider the existence, computation, and\ninefficiency of stable matchings from which no pair of players wants to\ndeviate. When the benefits from a match are the same for both players, we show\nthat incorporating the well-being of other players into their matching\ndecisions significantly decreases the price of stability, while the price of\nanarchy remains unaffected. Furthermore, a good stable matching achieving the\nprice of stability bound always exists and can be reached in polynomial time.\nWe extend these results to more general matching rewards, when players matched\nto each other may receive different utilities from the match. For this more\ngeneral case, we show that incorporating social context (i.e., "caring about\nyour friends") can make an even larger difference, and greatly reduce the price\nof anarchy. We show a variety of existence results, and present upper and lower\nbounds on the prices of anarchy and stability for various matching utility\nstructures. Finally, we extend most of our results to network contribution\ngames, in which players can decide how much effort to contribute to each\nincident edge, instead of simply choosing a single node to match with.\n