The efficiency of best-response dynamics

DOI10.1007/978-3-319-66700-3_15zbMATH Open1403.91066arXiv2002.11461OpenAlexW2745722716MaRDI QIDQ681867FDOQ681867

Authors: Michal Feldman, Yuval Snappir, Tami Tamir 

Publication date: 13 February 2018

Abstract: Best response (BR) dynamics is a natural method by which players proceed toward a pure Nash equilibrium via a local search method. The quality of the equilibrium reached may depend heavily on the order by which players are chosen to perform their best response moves. A {em deviator rule} $S$ is a method for selecting the next deviating player. We provide a measure for quantifying the performance of different deviator rules. The {em inefficiency} of a deviator rule $S$ is the maximum ratio, over all initial profiles $p$, between the social cost of the worst equilibrium reachable by $S$ from $p$ and the social cost of the best equilibrium reachable from $p$. This inefficiency always lies between $1$ and the {em price of anarchy}. We study the inefficiency of various deviator rules in network formation games and job scheduling games (both are congestion games, where BR dynamics always converges to a pure NE). For some classes of games, we compute optimal deviator rules. Furthermore, we define and study a new class of deviator rules, called {em local} deviator rules. Such rules choose the next deviator as a function of a restricted set of parameters, and satisfy a natural condition called {em independence of irrelevant players}. We present upper bounds on the inefficiency of some local deviator rules, and also show that for some classes of games, no local deviator rule can guarantee inefficiency lower than the price of anarchy.

Full work available at URL: https://arxiv.org/abs/2002.11461

Recommendations

• Dynamic inefficiency: anarchy without stability
• On the impact of fair best response dynamics
• The speed of convergence in congestion games under best-response dynamics
• Best-response dynamics, playing sequences, and convergence to equilibrium in random games
• The Speed of Convergence in Congestion Games under Best-Response Dynamics

zbMATH Keywords

price of anarchycongestion gamesbest-response dynamicsdeviator rules

Mathematics Subject Classification ID

Evolutionary games (91A22) Games involving graphs (91A43)

Cited In (12)

• Best response equivalence
• Best response dynamics improve sustainability and equity outcomes in common-pool resources problems, compared to imitation dynamics
• Dynamic inefficiency: anarchy without stability
• Implementation in adaptive better-response dynamics: towards a general theory of bounded rationality in mechanisms
• Using Temporal Dummy Players in Cost-Sharing Games
• Complexity and optimality of the best response algorithm in random potential games
• Imperfect best-response mechanisms
• Optimal learning dynamics of multiagent system in restless multiarmed bandit game
• Infinite-duration poorman-bidding games
• The power of one evil secret agent
• Best-response dynamics, playing sequences, and convergence to equilibrium in random games
• A note on best response dynamics.

This page was built for publication: The efficiency of best-response dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q681867)