Best-Response Mechanisms

Full textClick to download.
CitationICS 2011
AuthorsNoam Nisan
Michael Schapira
Gregory Valiant
Aviv Zohar


Under many protocols-- in computerized settings and in economics settings-- participants repeatedly "best responds" to each others' actions until the system "converges" to an equilibrium point. We ask when does such myopic "local rationality" imply "global rationality", i.e., when is it best for a player, given that the others are repeatedly best-responding, to also repeatedly best-respond? We exhibit a class of games where this is indeed the case. We identify several environments of interest that fall within our class: models of the Border Gateway Protocol (BGP), that handles routing on the Internet, and of the Transmission Control Protocol (TCP), and also stable-roommates and cost-sharing, that have been extensively studied in economic theory.

Back to publications
Back to previous page