"Best-Reply Mechanisms"

Speaker: Aviv Zohar
Date: Thursday, 29 November 2007
Time: 2pm
Place: Ross 201

Joint work: Noam Nisan, Michael Schapira and Aviv Zohar

Abstract:

In many real-world settings, strategic agents are instructed to follow
best-reply dynamics (economic markets, Internet protocols, etc.). Such
settings give rise to many questions: Will best-reply dynamics
converge or go on indefinitely? Will they converge quickly? What
happens in distributed and asynchronous settings in which
communication between players may be delayed or lost? Is it in the
best interest of the agents to follow best-reply dynamics?

We show that, for a superclass of dominance-solvable games, best-reply
dynamics converge within polynomial time to a pure Nash
equilibrium. Moreover, we show that convergence is assured even in
asynchronous settings.

We then study best-reply dynamics in the context of mechanism
design. We characterize a narrower subclass of games for which we
prove that best-reply dynamics are ex-post-Nash
incentive-compatible. We provide several examples of such games:
stable-roommates problems, network-routing games, first-price
auctions, and congestion-control games.