Communication Complexity of Mixed-Nash Equilibria

« SIEPR & Microsoft Conference On Internet Economics

Communication Complexity of Mixed-Nash Equilibria

September 28, 2009 by algorithmicgametheory

In a previous post I discussed the communication complexity of reaching a pure Nash equilibrium. The communication complexity model aims to capture the basic information transfer bottleneck between the different players in a games, abstracting away the question of incentives, and focusing on the need of communicating the different preferences (utilities) of the players that are assumed to initially be privately known. The previous post introduced the model of communication complexity and applied it to the question of finding a pure Nash equilibrium (if it exists). The bottom line was that, in the general case, essentially all information about the utilities must be transferred and no “shortcuts” are possible. In a multi-player game this amount of information is exponential in the number of players, implying that convergence to equilibrium, in general, is impractical, and special properties of the game must be used in order to reach equilibrium in reasonable time (one such property was demonstrated: dominance-solvable games).

This post discusses the issue of convergence to a mixed Nash equilibrium, as studied by Sergiu Hart and Yishay Mansour in How Long to Equilibrium? The Communication Complexity of Uncoupled Equilibrium Procedures. The setting, as in my previous post, has each one of $n$ players holding his utility function $u_i : S_1 \times ... \times S_n \rightarrow \Re$ , where each $S_j$ is the set of strategies of player $j$ , and for ease of notation lets have $|S_j|=m$ for all $j$ . We will assume that all utilities are finitely represented, i.e. are rational numbers, say with $k$ -bit numerator and denominator. Can a mixed Nash equilibrium be found by communicating significantly less than $m^n \cdot k$ bits — the size of each utility function? Maybe it can be done by communicating only a polynomial (in $n$ , $m$ , and $k$ ) bits? This would be a necessary condition for efficient convergence of any (uncoupled) dynamics between the players.

Before we look deeper into at this question, let us look at the similar problem of finding a correlated equilibrium. In this case it turns out that a polynomial amount of communication suffices and thus only a tiny fraction of the private information needs to be transferred. You can see a previous post of mine for background on correlated equilibrium.

The Communication Complexity of Correlated Equilibrium

Let us recall that a correlated equilibrium is a probability distribution on the strategy profiles $p : S_1 \times ... \times S_n \rightarrow \Re$ that satisfies linear inequalities of the following form: for every player $i$ , and every two strategies of $i$ , $s_i, s'_i$ : $\sum_{s_{-i}} p(s_i,s_{-i}) u_i(s_i,s_{-i}) \ge \sum_{s_{-i}} p(s_i,s_{-i}) u_i(s'_i,s_{-i})$ , where the sum ranges over all strategy profiles $s_{-i}$ of the other players. The interpretation is that $s_i$ is indeed a best-reply to the conditional distribution $p(s_i,\cdot)$ on $s_{-i}$ .

[Edited on Oct 2nd: Albert Xin Jiang was kind enough to point out that the next paragraph is, well, wrong, so I’m striking it out. In order to show that finding a correlated equilibrium can be done with low communication complexity, one must run the Ellipsoid algorithm on the dual LP (which has polynomial many variables) rather than on the primal (which has exponentially many variables). How to do so effectively is shown in a paper by Papadimitriou and Roughgarden, and Hart and Mansour show that the algorithm can be implemented with low communication.]

As being a correlated equilibrium is defined by a set of linear inequalities, we can find a correlated equilibrium using linear programming. Let us see how the players can jointly run the Ellipsoid LP algorithm while keeping the amount of communication in check. The Ellipsoid algorithm runs in time polynomial in $m$ , $n$ , and $k$ as long as it has access to a separation oracle. Such an oracle must be able to answer queries of the following form: given an unfeasible point, in our case a candidate distribution $p$ , it must find a constraint, in our case a player $i$ and strategies $s_i, s'_i$ , where the corresponding inequality is violated by $p$ . The main point is that each of the inequalities can be checked by a single player since it depends only on a single utility function. Thus to implement the separation oracle, each player must either report a violated constraint or a single bit specifying that all his constraints are satisfied — all together taking $O(n + \log m)$ bits of communication. When the algorithm terminates — after a polynomial number of steps (polynomial in $n$ , $m$ , and $k$ ) — all players know the answer, which is a correlated equilibrium. (Note that even though a correlated equilibrium is an exponential-sized object, it will turn out to have a polynomial-sized support.)

While this low-communication algorithm can not be viewed as natural dynamics that efficiently converge to a correlated equilibrium, it does point out that some dynamics that converge efficiently do exist. The question of finding natural dynamics then gets more pressing and indeed it turns out that natural dynamics do exist as well: dynamics based on regret minimization (see my previous post.)

Mixed-Nash Equilibria

Now, once we have what to aim for — a similarly low-communication way of reaching a mixed-Nash equilibrium — let us look at the problem carefully again. First, we must recall that Nash equilibria may be irrational even if all utilities are rational, so a Nash equilibrium can not be “printed” as binary numbers in any finite time. Still, in our communication complexity formulation this shouldn’t be a problem since any representation of the equilibrium is in principle acceptable as long as it is uniquely determined by the communication. Closely related to this is the fact that the representation of a Nash equilibrium in an $n$ -player game may require exponentially many bits of precision, even if the utilities themselves have only short descriptions. As before, while the required precision itself is not a lower bound on the communication complexity, Hart and Mansour do show how to use this precision to obtain a lower bound. Below I give a different, somewhat stronger proof.

Let us start with the following 2-player bi-strategy game, where $0<r<1$ is an arbitrary parameter.

r, 0 0, r

0, 1-r 1-r, 0

It is easy to see that the only Nash equilibrium of this game has each player choosing his second strategy with probability exactly $r$ and his first with probability $1-r$ . This family of games suffices for giving a tight lower bound for the special case of two-player ( $n=2$ ) bi-strategy ( $m=2$ ) games.

Lemma: The communication complexity of finding a Nash equilibrium in two-player bi-strategy games, where all utilities are given by $k$ -bit integers, is $\Theta(k)$ .

The upper bound is trivial and the lower bound is implied by games of the previous form where $r$ ranges over all fractions of the form $r = x/2^k$ , for integer $0 <x < 2^k$ since each of these games has a different (unique) answer giving $2^k$ different such answers, which thus requires at least $k$ bits of communication just to get all possibilities.

The dependence of the communication complexity on $m$ , the number of strategies of each player, is still unclear. However, Hart and Mansour show that the dependence on the number of players, $n$ , is exponential. The basic idea is that with $n$ players we can get doubly-exponential many different answers. A clean way to show this is to “simulate” utilities of representation length $k=2^{\Theta(n)}$ , and then invoke the previous bound.

Win-Lose Simulation Lemma: For every $n$ -player game with utilities that are $k$ -bit integers, there exists an $(n + 3\log k)$ -player game, with the following properties:

The new game is a win-lose game, i.e. all utilities are 0 or 1.
Each of the first $n$ players has the same set of strategies as in the original game. The utility of each of these players is fully determined (in an easy manner) by his utility in the original game.
Each of the final $3 \log k$ players has 2 strategies. The utilities of each of these are constants not depending on the original game at all.
The Nash equilibria of the new game are in 1-1 correspondence with those of the original game: the mixed strategies of each of the first $n$ players are identical, while the strategies of the final $3\log k$ players are fixed constants independent of the game.

From this we immediately get our theorem.

Theorem: The communication complexity of finding a Nash equilibrium in $n$ -player bi-strategy win-lose games is $2^{\Theta(n)}$ .

The upper bound is trivial and the lower bound is implied by the lower bound on 2-player games with $k$ -bit utilities via this reduction using $n=2+3\log k$ players.

Proof of Win-Lose Simulation lemma

It remains to prove the simulation lemma. We will do so in three steps: first construct a fixed game whose unique equilibrium has exponentially low probabilities, then use this game to simulate games with utilities that are all powers of two, and finally use these to simulate general games with integer utilities.

The first step of the reduction is the following construction:

Construction: for each $t$ there exist $(2t)$ -player win-lose bi-strategy games such that the unique Nash equilibrium has, for each $1 \le i \le t$ , players $2i-1$ and $2i$ choosing their first strategy with probability exactly $2^{-2^{i-1}}$ .

Proof: for $t=1$ , this is exactly “matching pennies”, i.e. the $2 \times 2$ game described above for $r=1/2$ (after scaling by a factor of 2). Now for the induction step we start with $t-1$ pairs of players as promised by the induction hypothesis, and we keep these players’ utilities completely independent of the soon to be introduced 2 new players, so we know that in every Nash equilibrium of the currently constructed $2t$ -player game these will still mix exactly as stated by the fact above for $t-1$ . In particular the last pair of players in the $(2t-2)$ -player game choose their first strategy with probability $2^{-2^{t-2}}$ . The point is that with these players in place, we can easily simulate the $2 \times 2$ game above for $r=2^{-2^{t-1}}$ . To simulate a “ $r$ entry”, we define the utility as 1 when the last pair of players in the $(2t-2)$ -player game play their first strategy (which happens with probability $2^{-2^{t-2}} \times 2^{-2^{t-2}} = 2^{-2^{t-1}} = r$ ) and 0 otherwise, while to define a $1-r$ entry we define the opposite.

Our next step is to simulate (in the sense of the lemma) games where all utilities are powers of two in the range $1, 2, 4 , ..., 2^k$ , equivalently, after scaling, in the range $1, 1/2, 1/4, ..., 2^{-k}$ . This is done by adding to the original players $t=2\log k$ players as defined in the construction above. We can now replace each utility of the original players of the form $2^{-x}$ where $x$ ‘s binary representation is $x = \sum_{i=1}^{t} x_i 2^{i-1}$ with a utility of 1 whenever, for every $i$ with $x_i=1$ , new player $2i$ plays his first strategy,(and 0 otherwise). This happens with probability $\Pi_{i|x_i=1} 2^{-2^{i-1}} = 2^{-\sum_{i |x_i=1} 2^{i-1}} = 2^{-x}$ , as needed.

Our final step is simulating games with utilities that are general $k$ -bit integers by games that have all their utilities powers of two, as in the previous step. This is done by adding another $\log k$ bi-strategy players, paired into $\log k/2$ independent “matching pennies” games, and thus each of them always evenly mixes between his two strategies. To simulate a utility of $y=\sum_{i=1}^k y_i 2^{i-1}$ in the original game, we give, in the new game, a utility of $y_i 2^{i-1}$ whenever the $\log k$ new players played a sequence of strategies which is the binary representation of $i$ (and 0 otherwise). The expected value is exactly $y/k$ , completing the simulation (as the scaling by a factor of $k$ does not matter).

What remains?

The previous lower bound leaves much to be desired: while it does give an exponential lower bound in the input parameters, this is done at the cost of having an exponentially long output. If we also take the output length into account (in any representation) then the bound is no more than linear — trivial. Indeed, in the formal description of the computational Nash equilibrium problem, one formally has an input parameter $\epsilon$ that specifies how close to an equilibrium do we demand the output to be, and the algorithm is allowed to run in time that is polynomial in $\log \epsilon$ . (See a previous post on the subtleties of this approximation parameter $\epsilon$ .) Taking this approach, the lower bound is trivial too as it is bounded from above by $\log\epsilon$ .

Thus, the main open problem that remains is that of determining the communication complexity of finding a mixed-Nash equilibrium when the precision required at the output is only polynomial in the other parameters.

Posted in Uncategorized | Tagged complexity of equilibria, technical | 4 Comments

4 Responses

on September 30, 2009 at 4:25 pm | Reply Anonymous

Nice article. You might wish to correct “loose” to “lose” in several places.
- on September 30, 2009 at 4:38 pm | Reply algorithmicgametheory
  
  thanks. done.
on October 1, 2009 at 2:22 am | Reply Albert

Dear Prof Nisan,

Thanks for the fascinating post. A comment regarding communication complexity of correlated equilibria: although every game has a correlated equilibrium with polynomial-sized support, in general there are also correlated equilibria with exponential-sized supports. In particular, if you run the ellipsoid method directly on the LP, the generated candidate solutions will have exponential-sized supports. Then communicating these vectors to the individual players becomes problematic.

Perhaps what you had in mind was Papadimitriou’s (STOC 2005) algorithm, which applies the ellipsoid method on the dual LP. Although the dual problem has exponential number of constraints, a separation oracle can be constructed that only requires each player to compute certain expected utilities and submit a short vector. (As an aside, this separation oracle has interesting connections to swap-regret-minimizing learning algorithms.)
- on October 1, 2009 at 9:17 pm | Reply algorithmicgametheory
  
  oops, you are right. I’ll fix it. thanks.

Comments RSS

Turing's Invisible Hand

Computation, Economics, and Game Theory

Communication Complexity of Mixed-Nash Equilibria