Skip to main content

Stable Matching, Friendship, and Altruism

Elliot Anshelevich ( Rensselaer Polytechnic Institute )

We will discuss both integral and fractional versions of "correlated stable matching" problems. Each player is a node in a social network and strives to form a good match with a neighbouring player; the player utilities from forming a match are correlated. We consider the existence, computation, and inefficiency of stable matchings from which no pair of players wants to deviate. We especially focus on networks where players are embedded in a social context, and may incorporate friendship relations or altruism into their decisions. When the benefits from a match are the same for both players, we show that incorporating the well-being of other players into their matching decisions significantly improves the quality of stable solutions. Furthermore, a good stable matching always exists and can be reached quickly. We extend these results to more general matching rewards, when players matched to each other may receive different utilities from the match. For this more general case, we show that incorporating social context (i.e., "caring about your friends") can make an even larger difference, and greatly reduce the price of anarchy. Finally, we extend most of our results to network contribution games, in which players can decide how much effort to contribute to each incident edge, instead of simply choosing a single node to match with.

Speaker bio

Elliot Anshelevich is an Associate Professor in Computer Science at Rensselaer Polytechnic Institute. He received his Ph.D. from Cornell University in 2005, working under the direction of Jon Kleinberg and Eva Tardos. After receiving the NSF Postdoctoral Fellowship in Mathematics, he spent a year at Princeton University working with Moses Charikar. His research interests focus on algorithmic game theory, and more generally algorithms for large decentralised networks. Particular interests include: network design problems with self-interested agents, local and decentralized routing algorithms, approximation algorithms, networked markets, and information propagation in both social and computer networks.

 

 

Share this: