A Little Anarchy Never Hurt Anyone: Beyond Worst-Case Equilibria in Games

The seminar concerns central theme of game theory research in recent decade, that has focused on deriving bounds on the worst-case performance of equilibria in noncooperative games. These bounds are called "Price of Anarchy" bounds since they quantify the worst-case harm (the "price") resulting from uncoordinated decentralized decision making ("anarchy"). The Price of Anarchy has been analyzed in a wide variety of systems (auctions, distributed resource allocation, network routing); in much recent literature, designing agent incentives or payoff functions to optimize the Price of Anarchy has been a central research goal. However, comparatively little work has focused on understanding the practical relevance of worst-case equilibria themselves. Are worst-case equilibria likely? Are they stable? Do distributed decision-making algorithms converge to them?

In fact, our recent work suggests that worst-case equilibria may be substantially less "scary" than previously thought. Indeed, many known worst-case equilibria occur only on game instances which are finely-tuned: perturbing agent behavior on these instances often leads to dramatic improvements in efficiency. The work shows that this feature is an intrinsic property of many types of game. First, for a large class of games, we prove a fundamental tradeoff between the efficiency of equilibria and their stability: we show that if agents are highly satisfied with their actions at a particular equilibrium (i.e., the equilibrium is highly stable), then that equilibrium must be of relatively high efficiency. Second, we propose a paradigm of distributed algorithm design which exploits this tradeoff to ensure that agents never (or rarely) converge to worst-case equilibria. Finally, we discuss the exciting new research directions which are suggested by these results.

Bio: Philip N. Brown is a Visiting Professor at Politecnico di Torino and an Associate Professor in the Department of Computer Science at the University of Colorado Colorado Springs. Philip received the Bachelor of Science in Electrical Engineering in 2007 from Georgia Tech. He received the Master of Science in Electrical Engineering in 2015 from the University of Colorado at Boulder under the supervision of Jason R. Marden, where he was a recipient of the University of Colorado Chancellor’s Fellowship. He received the PhD in Electrical and Computer Engineering from the University of California, Santa Barbara under the supervision of Jason R. Marden. He received the 2018 CCDC Best PhD Thesis Award from UCSB, the Best Paper Award from GameNets 2021, and prestigious early-career awards from the Air Force Office of Scientific Research (YIP, 2023), National Science Foundation (CAREER, 2025), and the Army Research Office (ECP, 2025). Philip is interested in complex strategic interactions in networked systems of agents, and studies these with a combination of game theory and machine learning. Key application areas include smart transportation systems, human-machine teaming, and space domain awareness.