Best-response dynamics out of sync: complexity and characterization
Venue
EC, ACM (2013), pp. 379-396
Publication Year
2013
Authors
Roee Engelberg, Alex Fabrikant, Michael Schapira, David Wajc
BibTeX
Abstract
In many computational and economic models of multi-agent interaction, each
participant repeatedly "best-responds" to the others' actions. Game theory research
on the prominent "best-response dynamics" model typically relies on the premise
that the interaction between agents is somehow synchronized. However, in many
real-life settings, e.g., internet protocols and large-scale markets, the
interaction between participants is asynchronous. We tackle the following important
questions: (1) When are best-response dynamics guaranteed to converge to an
equilibrium even under asynchrony? (2) What is the (computational and
communication) complexity of verifying guaranteed convergence? We show that, in
general, verifying guaranteed convergence is intractable. In fact, our main
negative result establishes that this task is undecidable. We exhibit, in contrast,
positive results for several environments of interest, including complete,
computationally-tractable, characterizations of convergent systems. We discuss the
algorithmic implications of our results, which extend beyond best-response dynamics
to applications such as asynchronous Boolean circuits.
