Dr. Alex Fabrikant,
In many models of multi-agent interaction — whether in distributed
protocols, markets, politics, etc — participants repeatedly pick a
“best response” to the others’ actions. This foundational
“best-response dynamics” model has been the focus of decades of game
theory work, along with more sophisticated notions of long-term
strategies. But for many real-life settings, like internet protocols
and global markets, the agents are more handicapped than even in
classical best response: agents often act _asynchronously_, i.e.
before learning about some of the other agents’ recent actions. In
most kinds of distributed systems, removing this asynchrony would
require significant, often impractical engineering costs. At this
natural meeting point of the game theory tradition and distributed
systems practice, we tackle these questions:
(1) What properties characterize systems where best-response dynamics
are guaranteed to always converge to an equilibrium, even under
(2) What is the (computational and communication) complexity of
checking a system for 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 in
two natural settings: multi-party interactions with binary strategy
choices per agent, and 2-party interactions with arbitrarily large
strategy spaces. This allows both practical algorithms for verifying
convergence, with independently-interesting application to tractably
verifying convergence of asynchronous Boolean circuits with feedback.
This is joint work with Roee Engelberg, Michael Schapira, and David Wajc.
Alex is a research scientist at Google, working on various algorithmic
problems in data mining. Most of his previous work centers on modeling
and understanding multi-agent selfish interactions in general and in
internet routing in particular. He got his Ph.D. from Berkeley in