Hardness of Approximation Between P and NP. Aviad Rubinstein

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

СКАЧАТЬ 14.1 and 14.2 extend the results of Frances and Litman [1998] and Papadimitriou and Yannakakis [1986] to show that the VC and Littlestone’s Dimensions cannot even be approximately computed in polynomial time.

       1.2.4 Signaling

      Many classical questions in economics involve extracting information from strategic agents. Lately, there has been growing interest within algorithmic game theory in signaling: the study of how to reveal information to strategic agents (see, e.g., [Cheng et al. 2015, Dughmi 2014, Dughmi et al. 2013, Emek et al. 2014, Miltersen and Sheffet 2012] and references therein). Signaling has been studied in many interesting economic and game theoretic settings. Among them, ZERO-SUM SIGNALING proposed by Dughmi [2014] stands out as a canonical problem that cleanly captures the computational nature of signaling. In particular, focusing on zero-sum games clears away issues of equilibrium selection and computational tractability of finding an equilibrium.

       Definition 1.3

      ZERO-SUM SIGNALING [Dughmi 2014]. Alice and Bob play a Bayesian zero-sum game where the payoff matrix M is drawn from a publicly known prior. The signaler Sam privately observes the state of nature (i.e., the payoff matrix), and then publicly broadcasts a signal φ(M) to both Alice and Bob. Alice and Bob Bayesian-update their priors according to φ(M)’s and play the Nash equilibrium of the expected game; but they receive payoffs according to the true M. Sam’s goal is to design an efficient signaling scheme φ (a function from payoff matrices to strings) that maximizes Alice’s expected payoff.

      Dughmi’s main result proves that assuming the hardness of the PLANTED CLIQUE problem, there is no additive Fully Polynomial Time Approximation Scheme (FPTAS) for ZERO-SUM SIGNALING. The main open question left by Dughmi [2014] is whether an additive PTAS exists. Here we answer this question in the negative: we prove that assuming the ETH [Impagliazzo et al. 2001], obtaining an additive-∈-approximation (for some constant ∈ > 0) requires quasi-polynomial time . This result is tight thanks to a recent quasi-polynomial time algorithm by Cheng et al. [2015]. Another important advantage of our result is that it replaces the hardness of PLANTED CLIQUE with a more believable worst-case hardness assumption (see, e.g., the discussion in Braverman et al. [2015]).

1.3 Approximate Nash Equilibrium

      The main result in this book rules out the PTAS (polynomial time approximation schemes) for two-player Nash equilibrium. Consider a game between two players, each choosing between a large number (n) of actions. The inputs to the algorithm are two n × n matrices with entries in [0, 1]. The goal is to find, for every constant ε, an ε-approximate Nash equilibrium; i.e., a mixed strategy for each player, such that either player can gain at most ε by deviating to a different strategy.

      This has been the central open question in equilibrium computation for the past decade. There were good reasons to be hopeful: there was a quasi-polynomial time [Lipton et al. 2003], a series of improved approximation ratios [Bosse et al. 2010, Daskalakis et al. 2007, 2009b, Kontogiannis et al. 2009, Tsaknakis and Spirakis 2008], and several approximation schemes for special cases [Alon et al. 2013, Barman 2015, Daskalakis and Papadimitriou 2009, Kannan and Theobald 2007]. Our main result settles this question in the negative:

Theorem 1.1

      Main theorem. There exists a constant ϵ > 0 such that, assuming ETH for PPAD, finding an ϵ-approximate Nash equilibrium in a two-player n × n game requires time .

      We supplement Theorem 1.1 with a series of other hardness of approximation results for Nash equilibrium in related settings, further establishing the point that even approximate Nash equilibria are intractable. First, we consider different sources of complexity. Our main result shows intractability of approximate Nash equilibria when the complexity of the game arises from each player choosing among many actions. In Theorems 5.1 and 5.2, we prove that in games where each player only has two actions, the complexity can arise from a large number of players; finding an approximate Nash equilibrium in n-player, binary action games is PPAD-hard (settling another open question from Daskalakis’s thesis [Daskalakis 2008]). Alternatively, even if there are only two players and the number of actions is constant, a different source of complexity can be the players’ uncertainty; finding an approximate Bayesian Nash equilibrium in such incomplete information games is also PPAD-hard (Corollary 8.1).

      We also prove intractability in different models: query complexity, communication complexity, and uncoupled dynamics (settling a long list of open questions from Babichenko [2012, 2016], Chen et al. [2017], Fearnley et al. [2013], Hart and Mansour [2010], Hart and Nisan [2013], Nisan [2009a], Roughgarden and Weinstein [2016]. The main advantage of these results is that they are unconditional, i.e., they do not rely on complexity assumptions such as ETH for PPAD, or P ≠ NP. In particular, in the setting where each player knows her own utility function, even computationally unbounded players have to communicate almost all their private information in order to reach even an approximate equilibrium.

1. In fact, “more than six decades” is an understatement: Irving Fisher’s thesis from 1891 dealt with the closely related question of convergence to market equilibria [Brainard and Scarf 2000].

2. Assuming P ≠ PPAD; see the discussion in the next section about this assumption.

3. Under a complexity assumption stronger than P ≠ PPAD that we call the Exponential Time Hypothesis (ETH) for PPAD; see Section 1.2 for details.

4. This guarantee is actually without loss of generality [Papadimitriou 1994], but this is not so important for our purposes.

5. Here work is measured by the number of oracle calls rather than running time; indeed this model will be the starting point of our reductions for query and communication complexity.

6. There is also a stricter notion that requires x to be close to an x* for which f(x*) = x* exactly. See, e.g., Etessami and Yannakakis [2010].

7. Both the approximate Caratheodory’s theorem and the resulting algorithm have been described by many researchers (e.g., [Arora et al. 2012, Lipton et al. 2003]); however, the presentation in Barman [2015] is our favorite.

      2

      Preliminaries

Notation

      We use 0n (respectively 1n) to denote the length-n vectors whose value is 0 (1) in every coordinate. For vectors x, y ∈ ℝn, we let

      denote СКАЧАТЬ