At the time, Abe was preparing for the launch of Course Match, a system that implements a heuristic algorithm for A-CEEI to assign students to courses at the Wharton School (University of Pennsylvania). Chapter 10, based on joint work with Abe and Christos, is devoted to the complexity of A-CEEI.
A-CEEI, like the rest of the problems in Part III, belongs to a special class (PPAD) of intractable problems that are total: their solution always exists, but it is hard to find it. Given our current understanding of computational complexity, this implies that they are unlikely to be NP-hard. In Part IV we move on to a different category of intractable problems: those that can be solved in quasi-polynomial (nlog(n)) time; this is typically prohibitively slow to implement even in moderate sized instances, but it is much faster than what we know or conjecture for problems like Satisfiability. This suggests that these problems are also not NP-hard. In both cases, proving intractability for problems that are not NP-hard requires both the right conditional assumptions (P ≠ PPAD and the “Exponential Time Hypothesis”), as well as special techniques.
The most difficult result in this book, for approximate Nash equilibrium (Part V), lies in the intersection of the PPAD problems from Part III and the quasi-polynomial time problems from Part IV. It combines ideas from both parts, together with new and old techniques from across theoretical computer science. It resolves an outstanding open problem that, as a student, I didn’t really mean to solve. Well … I’m glad I tried!
Acknowledgments
This book is based on my Ph.D. dissertation [Rubinstein 2017c], completed at University of California, Berkeley, with the wise advice of Christos Papadimitriou. My dissertation, in turn, was based on the following publications:
• “Inapproximability of VC Dimension and Littlestone’s Dimension” [Manurangsi and Rubinstein 2017].
• “Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder” [Rubinstein 2017b].
• “Detecting Communities Is Hard (And Counting Them is Even Harder)” [Rubinstein 2017a].
• “ETH Hardness for Densest-k-Subgraph with Perfect Completeness” [Braverman et al. 2017].
• “Communication Complexity of Approximate Nash Equilibria” [Babichenko and Rubinstein 2017].
• “Settling the Complexity of Computing Approximate Two-Player Nash Equilibria” [Rubinstein 2016].
• “Inapproximability of Nash Equilibrium” [Rubinstein 2015].
• “The Complexity of Fairness Through Equilibrium” [Othman et al. 2016].
I am indebted to Christos and all my co-authors: Yakov Babichenko, Mark Braverman, Young Kun Ko, Pasin Manurangsi, Abraham Othman, and Omri Weinstein.
I am also grateful to Boaz Barak, Shai Ben-David, Jonah Brown-Cohen, Karthik C. S., Yang Cai, Alessandro Chiesa, Paul Christiano, Constantinos Daskalakis, Shaddin Dughmi, Mika Goos, Rishi Gupta, Elad Haramaty, Noam Nisan, Prasad Raghavendra, Tselil Schramm, Madhu Sudan, Luca Trevisan, Michael Viderman, and anonymous reviewers, for commenting on, correcting, and inspiring much of the content of this book.
The writing of this book was supported in part by the MSR Ph.D. Fellowship (and wonderful MSR summer internships).
This has been an amazing journey. I am most grateful for the opportunities I had to share it with my family and friends.
Aviad Rubinstein
Cambridge, MA
March 2019
PART I
OVERVIEW
1
The Frontier of Intractability
The combination of vast amounts of data, unprecedented computing power, and clever algorithms allows today’s computer systems to drive autonomous cars, beat the best human players at chess and Go, and live stream videos of cute cats across the world. Yet computers can fail miserably at predicting outcomes of social processes and interactions, elections being only the most salient example. And this is hardly surprising, as there are two potent reasons for such unpredictability: One reason is that human agents are driven by emotions and hormones and billions of neurons interacting with a complex environment, and as a result their behavior is extremely hard to model mathematically. The second reason is perhaps a bit surprising, and certainly closer to the concerns of this book: Even very simple and idealized models of social interaction, in which agents have extremely clear-cut objectives, can be intractable.
To have any hope of reasoning about human behavior on national and global scales, we need a mathematically sound theory. Game theory is the mathematical discipline that models and analyzes the interaction between agents (e.g., voters) who have different goals and are affected by each other’s actions. The central solution concept in game theory is the Nash equilibrium. It has an endless list of applications in economics, politics, biology, etc. (e.g., [Aumann 1987]).
By Nash’s theorem [Nash 1951], an equilibrium always exists. Furthermore, once at a Nash equilibrium, players have no incentive to deviate. The main missing piece in the puzzle is:
How do players arrive at an equilibrium in the first place?
After many attempts by economists for more than six decades1 (e.g., [Brown 1951, Foster and Young 2006, Hart and Mas-Colell 2003, Kalai and Lehrer 1993, Lemke and Howson 1964, Robinson 1951, Scarf 1967, Shapley 1964]), we still don’t have a satisfying explanation.
About ten years ago, the study of this fundamental question found a surprising answer in computer science: Chen et al. [2009b] and Daskalakis et al. [2009a] proved that finding a Nash equilibrium is computationally intractable.2 And if no centralized, specialized algorithm can find an equilibrium, it is even less likely that distributed, selfish agents will naturally converge to one. This casts doubt over the entire solution concept.
For the past decade, the main remaining hope for Nash equilibrium has been approximation. The central open question in this field has been:
Is there an efficient algorithm for finding an approximate Nash equilibrium?
We give a strong negative resolution to this question: our main result rules out efficient approximation algorithms for finding Nash equilibria.3
Our theorem is the latest development in a long and intriguing technical story. The first question we computer scientists ask when encountering a new algorithmic challenge is: is it in P, the class of polynomial time (tractable) problems; or is it NP-hard, like Satisfiability and the Traveling Salesperson Problem (where the best known algorithms require exponential time)? Approximate Nash equilibrium falls into neither category; its complexity lies between P and NP-hard—hence the title of our book. Let us introduce
