The Price of Matching Selfish Vertices

Yuval Emek, Tobias Langner, Roger Wattenhofer

We analyze the setting of minimum-cost perfect matchings with selfish vertices through the price of anarchy (PoA) and price of stability (PoS) lens. The underlying solution concept used for this analysis is the Gale-Shapley stable matching notion, where the preferences are determined so that each player (vertex) wishes to minimize the cost of her own matching edge.

Knowledge Graph



Sign up or login to leave a comment