Hardness of Approximation Between P and NP. Aviad Rubinstein

Чтение книги онлайн.

СКАЧАТЬ

      The first obstacle for NP-hardness is the totality of Nash equilibrium. When we say that Satisfiability or the Traveling Salesperson Problems are NP-hard, we formally mean that it is NP-hard to determine whether a given formula has a satisfying assignment, or whether a given network allows the salesperson to complete her travels within a certain budget. In contrast, by Nash’s theorem an equilibrium always exists. Deciding whether an equilibrium exists is trivial, but we still don’t know how to find one. This is formally captured by an intermediate complexity class called PPAD.

      The second obstacle for NP-hardness is an algorithm (the worst kind of obstacle for intractability). The best known algorithms for solving NP-hard or PPAD-hard problems require exponential ≈ 2n) time, and there is a common belief (formulated a few years ago as the “Exponential Time Hypothesis” [Impagliazzo et al. 2001]) that much faster algorithms do not exist. In contrast, an approximate Nash equilibrium can be found in quasi-polynomial (≈ n^{log n}) time. Notice that this again places the complexity of approximate Nash equilibrium between the polynomial time solvable problems in P and the exponential time required by NP-hard problems. Therefore, approximate Nash equilibrium is unlikely to be NP-hard—or even PPAD-hard, since we know of no quasi-polynomial algorithm for any other PPAD-hard problem.

      As illustrated in the last two paragraphs, approximate Nash equilibrium is very far from our standard notion of intractability, NP-hardness. In some sense, it is one of the computationally easiest problems that we can still prove to be intractable—it lies at the frontier of our understanding of intractability. Unsurprisingly, the techniques we had to master to prove the intractability of approximate Nash equilibrium are useful for many other problems. In particular, we also prove hardness of approximation for several other interesting problems that either belong to the class PPAD or have quasi-polynomial time algorithms.

1.1 PPAD: Finding a Needle You Know Is in the Haystack

      Consider a directed graph G. Each edge contributes to the degree of the two vertices incident on it. Hence the sum of the degrees is twice the number of edges, and in particular it is even. Now, given an odd-degree vertex v, there must exist another odd-degree vertex. But can you find one? There is, of course, the trivial algorithm, which simply brute-force enumerates over all the graph vertices.

Now suppose G further has the property⁴ that every vertex has in- and out-degree at most 1. Thus, G is a disjoint union of lines and cycles. If v has an outgoing edge but no incoming edge, it is the beginning of a line. Now the algorithm for finding another odd degree node is a bit more clever—follow the path to the end—but its worst case is still linear in the number of nodes.

In the worst case, both algorithms run in time linear in the number of vertices. When the graph is given explicitly, e.g., as an adjacency matrix, this is quite efficient compared to the size of the input. But what if the graph is given as black-box oracles S and P that return, for each vertex, its successor and predecessor in the graph? The amount of work⁵ required for finding another odd-degree vertex by the exhaustive algorithm, or the path-following algorithm, is still linear in the number of vertices, but now this number is exponential in 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(0^m) = 0^m ≠ S(0^m), find an input x ∈ {0, 1}^m such that P(S(x)) ≠ x or S(P(x)) ≠ x ≠ 0^m.

      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 СКАЧАТЬ