Algorithmic Game Theory - handout2
Uriel Feige, Robert Krauthgamer, Moni Maor · 2008
In class we showed the well known algorithm for finding a stable matching (a.k.a. stable marriage) of Gale and Shapely [GS62]. This algorithm is also presented in Chapter 10 in [NRTV], in Wikipedia, and elsewhere. Consider the following game with 2n players, n men and n women, each having his/her own preference list over partners of the other sex. In this game, every man and every woman supplies a preference list (either their true preference list, or some other preference list), the outcome of the game is the matching produced by the stable matching algorithm when run on the supplied preference lists (the algorithm where the unengaged men propose), and the payoff for a player is the rank (in the player’s list) of the partner assigned to the player. An interesting question is whether the players have incentives to play truthfully in this game. Namely, is it always to the benefit of a player to report his or her true preference list, or may the player win a better partner (from the player’s point of view) by reporting a different preference list? 1. Show that all players following the strategy of reporting their true preference lists is not necessarily a Nash equilibrium of the game. Namely, show an example (n = 3 suffices for this purpose), where a woman can benefit (eventually be matched by the algorithm to a man that she prefers more) by reporting a preference list that is different from her true preference list. 2. Prove that this game always has some pure Nash equilibrium (though as question 1 shows, in this Nash equilibrium some players might not be reporting their true preferences).