Hardness of Approximation Between P and NP. Aviad Rubinstein
Читать онлайн книгу.
the natural parameter of the problem, the length of the input to the oracle, which equals the logarithm of the number of nodes. In the oracle model, it is not hard to prove that there are no better algorithms.
Let us consider the computational analog of the black-box oracle model: the oracles S and P are implemented as explicit (“white-box”) circuits, which are given as the input to the algorithm. This is the END-OF-A-LINE problem, which is the starting point for most of our reductions. The computational class PPAD (which stands for Polynomial Parity Argument in Directed graphs) is the class of search problems reducible to END-OF-A-LINE.
Definition 1.1
END-OF-A-LINE [Daskalakis et al. 2009a]. Given two circuits S and P, with m input bits and m output bits each, such that P(0m) = 0m ≠ S(0m), find an input x ∈ {0, 1}m such that P(S(x)) ≠ x or S(P(x)) ≠ x ≠ 0m.
How hard is END-OF-A-LINE? We believe that it is likely to be very hard, almost as hard as the black-box variant. This belief is backed by relativized separations [Morioka 2003] and cryptographic hardness [Bitansky et al. 2015, Garg et al. 2016, Hubácek and Yogev 2017], as well as zero algorithmic progress, even on special cases, since it was first introduced in Papadimitriou [1994]. More importantly, we are embarrassingly bad at gaining insight to a circuit’s functionality by looking at its structure (with some notable exceptions in cryptography [Barak 2004])—hence it seems reasonable to conjecture that the white-box variant is easier than the blackbox problem.
Even more embarrassing is our inability to prove computational intractability. Essentially all “proofs” of computational intractability (including the ones in this book) are conditional; i.e., we assume that some problem is hard (e.g., END-OF-A-LINE or SATISFIABILITY), and reduce it to a new problem we want to “prove” is hard. The intractability of the new problem only holds conditioned on the intractability of the original hard problem. Without first resolving whether P = NP, we cannot prove that END-OF-A-LINE is indeed hard. Furthermore, even merely proving that END-OF-A-LINE is NP-hard would already imply unlikely consequences like NP = coNP [Megiddo and Papadimitriou 1991]. The ultimate reason we believe that END-OF-A-LINE is intractable is that we have no idea how to prove it.
Once we believe that END-OF-A-LINE is indeed intractable, any problem that is PPAD-complete, i.e., “at least as hard as END-OF-A-LINE,” is also intractable. The celebrated works of Chen et al. [2009b] and Daskalakis et al. [2009a] prove that finding an exact Nash equilibrium is PPAD-complete. In Section 1.3 we describe some variants of approximate Nash equilibrium that are also PPAD-complete.
We conclude this section with a few problems (other than variants of Nash equilibrium) that we show are also PPAD-hard:
• Finding an approximate fixed point of an implicit function; Brouwer’s fixed point theorem, which guarantees the existence of a fixed point, lays the mathematical foundation for the rest of our PPAD-complete problems.
• Finding an approximate market equilibrium, which is the conceptual foundation of neoclassical economics.
• Finding an Approximate Competitive Equilibrium from Equal Incomes (A-CEEI), which is an algorithmic problem of practical interest due to its use for allocating classes to students (CourseMatch).
1.1.1 Brouwer’s Fixed Point
Brouwer’s fixed point theorem, together with its generalizations (in particular, Kakutani’s fixed point theorem), is the basis for many of the equilibrium concepts in game theory and economics. It states that any continuous function f from a compact convex set (in particular, the n-dimensional hypercube) to itself has a fixed point, i.e., a point x* such that f (x*) = x*. Just like in the case of a Nash equilibrium and the odd-degree vertex, the existence does not come with an algorithm for finding the fixed point. Brouwer eventually became so unsatisfied with the non-constructive nature of his proof that he founded intuitionism, a formalism of mathematics mandating constructive proofs [Iemhoff 2016].
Before we discuss the computational tractability of finding a fixed point, there are two subtle but important technicalities that we have to clear. The first is that finding an exact fixed point may be “obviously” intractable when all the fixed points are irrational. Fortunately there is a natural notion6 of approximate fixed point: find x such that f (x) ≈ x. The second issue is that we want a finite description of the input to our algorithm. Naively, one can define the value of the function on a grid, but then the set is no longer convex and a fixed point might not exist at all (see, e.g., Roughgarden and Weinstein [2016]). It turns out that a better way to define the input is as an arithmetic circuit: this gives a local and easy-to-verify guarantee that the function is indeed continuous.
Admittedly, there is something dissatisfying about proving computational hardness of “circuit problems”: we are going to prove that this problem is PPAD-hard, i.e., no easier than END-OF-A-LINE—but the reason we believe in the first place that END-OF-A-LINE is intractable is that we don’t know how to gain insight to the functionality of the circuit from staring at its structure. Nevertheless, we begin with the complexity of Brouwer’s fixed point because: this is a fundamental question; it is the starting point of many of our reductions; and, as we discuss later, even the black-box hardness in this case is highly non-trivial.
We know of two algorithms for computing an approximate Brouwer fixed point: there is Scarf’s algorithm [Scarf 1967], but its running time may be exponential in the description of the function; the same holds for brute-force search.
On the complexity side, Daskalakis et al. [2009a] proved that even in three dimensions, finding an exponentially close approximation (x such that ∥f(x) – x∥∞ ≤ 2−n, where n is the size of the input) is PPAD-complete; Chen and Deng [2009] proved the same problem continues to be hard even with only two dimensions. Notice that with a constant number of dimensions, any weaker approximation desideratum becomes trivial for brute-force search. Chen et al. [2009b] showed that in n dimensions, polynomial approximations are also PPAD-complete. We will later prove that even constant approximations are PPAD-complete, i.e., there exists some absolute constant ε > 0 such that it’s hard to find an x for which ∥f(x) − x∥∞ ≤ ε; this is already a significant improvement over the existing state of the art.
We can prove an even stronger form of inapproximability for finding a Brouwer fixed point: so far, we characterized the approximate fixed point with ℓ∞-norm, which means that f(x) and x must be close in every coordinate. Our main result in this regard (Theorem 4.2) is that even if we only require that f(x) and x are close in most of the coordinates, finding such x and f(x) remains PPAD-complete.
1.1.2 Market Equilibrium
Supply and demand is central to our modern understanding of economics: when demand exceeds supply, raising the price makes it less attractive to consumers and more attractive to producers, thereby reducing demand and increasing supply. Vice versa if the supply exceeds the demand. This simple idea marks the birth of neoclassical economics [Jevons 1866, Menger 1871, Walras 1874], and continues to inspire us today when we reason about free market economies. Since the consumption and production of one good depends on other goods, we are interested in a market equilibrium: a vector of prices where the supply and demand of every good matches.
The supply and demand argument has many weak spots, one of which is Giffen goods [Marshall 1895]: Consider a poor 19th-century English family consuming 10,000 calories a day from meat and bread. They prefer to eat meat, but the bread is cheaper—so they spend their daily income on 6 loaves of bread and 4 pounds of meat (each provides 1,000 calories). What happens if the price of bread increases? They have less free money to spend on the preferred luxury good