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

arrow_drop_up

Comments

Sign up or login to leave a comment