The Price of Matching Selfish Vertices

Abstract

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.

We changed the perspective of our paper and now look at the minimum-cost perfect matching problem through the price of anarchy (PoA) and price of stability (PoS) lens. Our previous results can be seen as analyzing the PoS of minimum-cost perfect matching and we now added an analysis of the PoA of this problem