Computational efficiency. Can the allocation be computed from the data in polynomial time?
Competitive Equilibrium from Equal Incomes (CEEI) [Foley 1967, Thomson and Varian 1985, Varian 1974] is a venerable mechanism with many attractive properties: In CEEI all agents are allocated the same amount of “funny money”; next they declare their preferences, and then a price equilibrium is found that clears the market. The market clearing guarantees Pareto efficiency and feasibility. The mechanism has a strong, albeit technical, ex post fairness guarantee that emerges from the notion that agents who miss out on a valuable, competitive item will have extra funny money to spend on other items at equilibrium. Truthfulness is problematic—as usual with market mechanisms—but potential incentives for any individual agent to deviate are mitigated by the large number of agents. However, CEEI only works when the resources to be allocated are divisible and the utilities are relatively benign. This restriction has both benefits and drawbacks. It ensures computational feasibility, because CEEI can be computed in polynomial time with a linear or convex program, depending on the utilities involved [Devanur et al. 2008, Ghodsi et al. 2011, Varian 1974]; on the other hand, it is easy to construct examples in which a CEEI does not exist when preferences are complex or the resources being allocated are not divisible. Indeed, both issues arise in practice in a variety of allocation problems, including shifts to workers, landing slots to airplanes, and the setting that we focus on here, courses to students [Budish 2011, Varian 1974].
It was shown in Budish [2011] that an approximation to a CEEI solution, called A-CEEI, exists even when the resources are indivisible and agent preferences are arbitrarily complex, as required by the course allocation problems one sees in practice. The approximate solution guaranteed to exist is approximately fair (in that the students are given almost the same budget), and approximately Pareto efficient and feasible (in that all courses are filled close to capacity, with the possible exception of courses with more capacity than popularity). This result seems to be wonderful news for the course allocation problem. However, there is a catch: Budish’s proof is non-constructive, as it relies on Kakutani’s fixed point theorem.
A heuristic search algorithm for solving A-CEEI was introduced in Othman et al. [2010]. The algorithm resembles a traditional tâtonnement process, in which the prices of courses that are oversubscribed are increased and the prices of courses that are undersubscribed are decreased. A modified version of this algorithm that guarantees courses are not oversubscribed is currently used by the Wharton School (University of Pennsylvania) to assign their MBA students to courses [Budish et al. 2014]. While it has been documented that the heuristic algorithm often produces much tighter approximations than the theoretical bound, on some instances it fails to find even the guaranteed approximation [Budish 2011 (Section 9)].
Thus A-CEEI is a problem where practical interest motivates theoretical inquiry. We have a theorem that guarantees the existence of an approximate equilibrium—the issue is finding it. Can the heuristic algorithms currently used to assign Wharton MBAs to their courses be replaced by a fast and rigorous algorithm for finding an approximate CEEI? Theorem 10.3 answers this question in the negative, showing that computing an A-CEEI is PPAD-complete.
1.2 Quasi-Polynomial Time and the Birthday Paradox
The following bilinear optimization meta-problem captures a wide range of applications, from areas like statistics Sparse Principle Component Analysis (Sparse PCA), graph theory (Clique), and game theory (Nash equilibrium):
For all the applications we consider, once we fix some y*, finding the best feasible x that maximizes x⊤Ay* is a tractable problem. (Similarly, if we were given a good x*, finding a matching y is easy.) But optimizing x and y simultaneously is NP-hard. What about approximations?
Caratheodory’s theorem states that a point v in the convex hull of n points in ℝd can be written as a convex combination of d + 1 points. In general, d + 1 points are necessary, but this number can be reduced drastically if we are willing to settle for approximation. In particular, Barman7 [2015] proves an approximate Caratheodory’s theorem that requires only r = O(ρ/ε2) points to express a point v̂ such that ∥v̂ − v∥p < ε, assuming the n points belong to a unit ℓp-ball. In particular, v̂ can be written as an average over a multi-set of r out of the n points.
Viewing the columns of A as n vectors in ℝn, Barman observes that (after proper normalization) the point v = Ay* is in their convex hull. If we only want to approximately solve the bilinear optimization (1.1), we drastically reduce the dimension of the problem by enumerating over all choices of v̂, and for each v̂ solving the optimization problem Av̂. It turns out that in order to guarantee a good additive approximation of (1.1), we need to set p ≈ log n. The dominant term in the running time of this meta-algorithm is the enumeration over all choices of v̂ (all multi-sets of the columns of A), which takes approximately
The above meta-algorithm provides evidence that the approximate variant of all those problems is much easier than solving them exactly: in particular we believe that NP-hard (respectively, PPAD-hard) problems like 3-SAT (resp. END-OF-A-LINE) require approximately 2n time. This belief is formulated by the Exponential Time Hypothesis, or ETH [Impagliazzo et al. 2001] (resp. ETH for PPAD [Babichenko et al. 2016]). The reasons we believe in ETH are similar to the ones outlined in the previous section for our belief that END-OF-A-LINE is intractable: on one hand, we have a combination of unconditional lower bounds in analogous models and little or no progress on algorithms; on the other hand, we are “forced” to believe it because we have no idea how to prove it (in particular, ETH implies the much weaker P ≠ NP).
However, quasi-polynomial time is still both unrealistic to implement in practice, and does not meet our gold standard of polynomial time in theory. The main question we address in this section is:
Can the quasi-polynomial time be improved to polynomial time?
For Sparse PCA this is indeed possible [Alon et al. 2013, Asteris et al. 2015, Chan et al. 2016]. But for several other problems we can prove that, assuming ETH, quasi-polynomial time is actually necessary:
• Finding a k-subgraph that is almost a clique; this is one of the most fundamental approximation problems in theoretical computer science.
• Finding and counting stable communities in a friendship graph; this problem received a lot of attention in recent years with the emergence of online social networks.
• Finding an approximately optimal signaling scheme; this resolves a recent open question by Dughmi.
• Computing the VC and Littlestone’s Dimensions of a binary concept class, two of the most fundamental quantities in learning theory.
A common approach to all our proofs is the birthday repetition framework due to Aaronson et al. [2014]: construct a reduction from 3-SAT to any of the above problems, with reduction size
