Approximating Nash Equilibria in Tree Polymatrix Games

Introduction

The complexity of equilibrium computation is a central area of research in algorithmic game theory. Recent years have seen significant progress in this line of work, especially in the context of two-player games . Furthermore, the computation of approximate Nash equilibrium in games over networks has emerged as an important research direction . Motivation for studying such multiplayer games stems in part from the prevalence and importance of large networks of interconnected, self-interested agents.

The prototypical family of large network games is that of polymatrix games. These games merge two classical concepts, two-player games and networks. In a polymatrix game, each player corresponds to a node in a network, and each edge encodes a two-player game between the two endpoints of the edge. A player’s payoff is the sum of her payoffs across the bimatrix games (edges) she participates in. Polymatrix games capture complex settings with arbitrarily many players while keeping the description complexity of the game polynomially small in the number of players. Computation of equilibria for polymatrix games is hence a natural test case, and has emerged at the boundary of computational tractability.

The seminal PPAD hardness reductions for computing $\varepsilon$-Nash equilibriaIn an $\varepsilon$-Nash equilibrium, a player can gain at most $\varepsilon$ by unilaterally deviating from her current strategy. by Daskalakis, Goldberg, and Papadimitriou along with their extensions by Chen, Deng, and Teng to two-player games were crucially developed within the context of polymatrix games.These hardness result hold for polynomially small $\varepsilon$. Recently, Rubinstein strengthened these inapproximability guarantees by establishing that there exists a constant $\varepsilon$ such that finding an $\varepsilon$-Nash equilibrium in polymatrix games over bipartite graphs of constant degree is computationally hard. Our positive algorithmic result is inspired by this work and explores the boundary between tractability and intractability of $\varepsilon$-Nash computation in polymatrix games.

The study of equilibria in polymatrix games has had a long history . To avoid hardness, most algorithmic results have focused on structured subclasses of polymatrix games. These include polymatrix generalizations of zero-sum games where exact Nash equilibria can be computed in polynomial time . Games on trees is another family of multiplayer games that has received attention . The proposed algorithm in finds an exact Nash equilibrium in two-action games on paths and runs in polynomial time, but in the case of trees the running time may be exponential even if the degree of the underlying tree is bounded. In contrast, we study computation of approximate Nash equilibrium in trees of arbitrary degree, and develop an algorithm that runs in quasi-polynomial time. Finally, some interesting progress has been made in the case of general polymatrix games as well, where it has been shown that a $(0.5+\varepsilon)$-Nash equilibrium of a polymatrix game can be computed in time polynomial in the input size and $1/\varepsilon^{2}$ .

We develop a quasi-polynomial time algorithm for approximating Nash equilibrium in polymatrix games over trees under a mild renormalizing assumption on the players’ payoffs. Specifically, instead of normalizing the entries of each bimatrix game to lie in $$, which results in each player$i$’s payoff depending linearly on its degree, we normalize them to lie in$[0,1/\text{degree}(i)]$, so that players’ total payoffs lie in$$. Our results actually extend even under weaker renormalization conditions; see Section 2 for details. We show that, given an$n$-player,$m$-action normalized polymatrix game over a tree, we can find an$\varepsilon$-Nash equilibrium of the game in expected time

Our approach immediately implies a polynomial time approximation scheme for computing Nash equilibria when the number of actions per player is constant. The case of standard bimatrix games can be trivially captured in our setting via a single-edge polymatrix game. Further, for trees of constant degree our framework yields an algorithm that finds an $\varepsilon$-Nash equilibrium in time $m^{O\left(\frac{\log m+\log n}{\varepsilon^{2}}\right)}$. Note that in the single edge case (i.e., the case of standard bimatrix games) this running-time bound matches the best known upper bound for approximating Nash equilibria .

Techniques. We develop a dynamic program to find an approximate Nash equilibrium of the given tree polymatrix game. The idea is to root the underlying tree and process it in a bottom-up manner. For each node/player $p$ we maintain a set of mixed strategies—i.e., probability distributions over player’s actions—that can be extended into a “partial” (approximate) equilibrium of the subtree rooted at the node. That is, for each mixed strategy assigned to $p$ there exist mixed strategies for the descendants of $p$ under which no descendant can benefit more than $\varepsilon$, in expectation, by unilateral deviation. We find such extendable mixed strategies of a player $p$ after processing all of its children; in other words, we start from the leaves of the tree and move towards the root. Note that such an extendable mixed strategy for the root corresponds to an approximate Nash equilibrium of the game. Also, it is worth pointing out that the tree structure enables us to find partial equilibria of disjoint subtrees separately. In particular, the fact that the utilities of players depend only on the actions of its parent and its children implies that disjoint subtrees can be processed separately.

In and of itself, using a dynamic program to find an approximate Nash equilibrium over a tree is a natural idea. In fact, similar approaches have been adopted in prior work; see, e.g., . The key technical contribution in this paper is to show that the update step in the dynamic program can be performed in quasi-polynomial time. To do this, we focus on a specific set of mixed strategies $U$, which is the set of all uniform distributions with support size polynomial in the approximation parameter $\varepsilon$ and logarithmic in the number of players and the number of actions; see Section 2 for a formal definition. It was shown in that every multiplayer game admits an $\varepsilon$-Nash equilibrium wherein the mixed strategy of each player is contained in $U$. Hence, given an $n$-player game, an exhaustive search over the set $U^{n}$ is guaranteed to find an approximate Nash equilibrium. But, such a search runs in time exponential in $n$. We show that for tree polymatrix games, an exponential-time exhaustive search can be bypassed. The idea is to follow the above mentioned dynamic program and consider, for each player $p$, mixed strategies in the set $U$ that can be extended into partial equilibria of the subtree rooted at $p$. To perform the update step in the dynamic program we employ a linear program that, interestingly, gives a tight characterization of mixed strategies that can be extended. Together, these ideas lead us to a quasi-polynomial time approximation algorithm.

Notation and Preliminaries

We study games with $n$ players and $m$ actions per player.We assume that each player has $m$ actions for ease of presentation. The developed result directly extends to the case wherein the number of actions of each player is different. Write $[n]$ and $[m]$ to denote the set of players and the set of actions of each player, respectively. The utilities of the players are normalized between and $1$; in particular, for each player $p$ we have utility $u_{p}:[m]^{n}\rightarrow$. Let $\Delta^{m}$ be the set of probability distributions over $[m]$. In addition, for mixed strategy profile $x=(x_{q})_{q\in[n]}\in\Delta^{m}\times\ldots\times\Delta^{m}$, we denote the expected utility of player $p$ by $u_{p}(x)$. Following standard notation, we use $x_{-p}$ to denote the mixed strategy profile of all players besides $p$.

A mixed strategy profile $x=(x_{q})_{q\in[n]}$, where each $x_{q}\in\Delta^{m}$, is said to be an $\varepsilon$-Nash equilibrium iff for every player $p\in[n]$ and action $a\in[m]$ we have $u_{p}(x)\geq u_{p}(a,x_{-p})-\varepsilon$.

Here, setting $\varepsilon=0$ gives us the definition of a Nash equilibrium.

As mentioned above, the utility of each player is normalized between and $1$. A typical way to accomplish this normalization (see, e.g., ) is to assume that for each player $p\in[n]$ the associated payoff matrices, $A_{p,q}$s, are entry-wise between and $1$, and the utility of player $p$ with degree $d$ (in the graph) is obtained by dividing the sum of the payoffs by $d$, i.e., $u_{p}(a_{1},a_{2},\ldots,a_{n}):=\frac{1}{d}\sum_{q:(p,q)\in E}\ e_{a_{p}}^{T}\ A_{p,q}\ e_{a_{q}}$. This normalization ensures that the same approximation guarantee is achieved for all players, irrespective of their degrees. If, instead, one assumes that entry-wise the $A_{p,q}$s are between and $1$ and simply add the payoffs $e_{a_{i}}^{T}A_{p,q}e_{a_{j}}$, then the approximation guarantee for players with higher degree—since $\varepsilon$ is the same of all the players—is stronger. This would lead to an undesirable, nonuniform approximation bound.

The degree-normalized scaling mentioned above is equivalent to the assumption that for player $p\in[n]$, with degree $d$, the matrices $A_{p,q}$s are contained in $[0,1/d]^{m\times m}$ and $u_{p}(a_{1},\ldots,a_{n}):=\sum_{q:(p,q)\in E}\ e_{a_{p}}^{T}\ A_{p,q}\ e_{a_{q}}$. In this paper we in fact consider a more general setup in which, for a player with degree $d$, entries of $A_{p,q}$s are between and $\max\left\{\frac{1}{d},\frac{\varepsilon}{2\sqrt{6d\log m}}\right\}$. Here, again we assume that for each action profile $a$ we have $u_{i}(a)\in$. Developing a quasi-polynomial time algorithm without an entry-wise assumption (i.e., without requirement (i) in the following definition) remains an interesting direction for future work.

Let $\mathcal{G}$ be an $n$-player $m$-action polymatrix game over graph $G=(V,E)$ and with payoff matrices $A_{p,q}$ and $A_{q,p}$, for $(p,q)\in E$. Given parameter $\varepsilon$, we say that $\mathcal{G}$ is normalized iff for each player $p\in[n]$ we have (i) the entries of $A_{p,q}$s are contained in $\left[0,\max\left\{\frac{1}{d},\frac{\varepsilon}{2\sqrt{6d\log m}}\right\}\right]$; here $d$ is the degree of player $p$ in $G$, and (ii) for every action profile $(a_{1},\ldots,a_{n})\in[m]^{n}$, the utility $u_{p}(a_{1},\ldots,a_{n}):=\sum_{q:(p,q)\in E}\ e_{a_{p}}^{T}\ A_{p,q}\ e_{a_{q}}$ is between and $1$.

Given mixed strategies of the neighbors of a player $p$, say $(x_{q})_{q:(p,q)\in E}$, $x_{p}\in\Delta^{m}$ is said to be an $\varepsilon$-best response of $p$ against $(x_{q})_{q:(p,q)\in E}$ if $p$ cannot benefit more than $\varepsilon$ in expectation by deviating from $x_{p}$, i.e.,

This paper studies polymatrix games in which the underlying graph $G$ is a tree. Note that a polymatrix game with exactly two players over a single edge $(p,q)\in E$—which is trivially a tree—corresponds to a bimatrix game between players $p$ and $q$. Hence, computation of an approximate Nash equilibrium in tree polymatrix games is at least as hard as computation of approximate Nash equilibrium in bimatrix games. Therefore, our running-time benchmark for finding an $\varepsilon$-Nash equilibrium is quasi-polynomial: $m^{O\left(\frac{\log m}{\varepsilon^{2}}\right)}$, which is the best known upper bound for approximating Nash equilibria in bimatrix games .

Uniform Probability Distributions.

A probability distribution $x\in\Delta^{m}$ is said to be $b$ uniform if it is a uniform distribution over a size-$b$ multiset of $[m]$. Write $U\subset\Delta^{m}$ to denote the set of all $\left(\frac{8\left(\ln m+\ln n-\ln\varepsilon+\ln 8\right)}{\varepsilon^{2}}\right)$-uniform probability distributions. Note that

As mentioned above, the work of Babichenko et al. establishes that every $n$-player $m$-action game admits an $\varepsilon$-Nash equilibrium $x=(x_{q})_{q\in[n]}$ such that $x_{q}\in U$ for all $q\in[n]$. Hence, an exhaustive search over the set $U^{n}$ is guaranteed to find an $\varepsilon$-Nash equilibrium. Note that the running time of such a search is $m^{O\left(\frac{n\left(\log m+\log n-\log\varepsilon\right)}{\varepsilon^{2}}\right)}$, which is exponential in $n$. In contrast to this exponential-time algorithm, we show that for tree polymatrix games an approximate Nash equilibrium can be computed in expected time $m^{O\left(\frac{\log m(\log m+\log n-\log\varepsilon)}{\varepsilon^{4}}\right)}$, which is quasi-polynomial in $n$ and $m$.

Next we state McDiarmid’s inequality . We use this concentration bound to prove our main result.

Quasi-Polynomial Time Algorithm

This section develops the dynamic program that finds an approximate Nash equilibrium. We will consider $G$ to be a rooted tree and process it in a bottom-up manner. We start with players all whose descendants are leaves, and then iteratively proceed onto the remaining players.

Write $\mathcal{C}(q)$ and $\mathcal{D}(q)$ to denote the set of children and the set of descendants of player $q$, respectively. The iterative process maintains a set $U_{p,q}(z)$ for each parent-child pair $(p,q)\in E$ and each $z\in U$.Recall that $U$ is the set of all $O\left(\frac{\log m+\log n-\log\varepsilon}{\varepsilon^{2}}\right)$-uniform probability distributions. Intuitively, $U_{p,q}(z)$ denotes the set of mixed strategies for player $q$ that can be extended into a “partial” $\varepsilon$-Nash equilibrium of the subtree rooted at $q$. Here $p$, the parent of $q$, is playing mixed strategy $z$ and might not be best responding. Formally, the inductive definition of the sets $U_{p,q}(z)$s is as follows:

If $q$ is a leaf player (i.e., $q$ corresponds to a leaf in tree $G$), then $U_{p,q}(z):=\{y\in U\mid y$ is an $\varepsilon$-best response of $q$ against $z\}$.

Else, if $q$ is a not a leaf player, we define $U_{p,q}(z):=\{y\in U\mid$ there exist mixed strategies $(x_{c})_{c\in\mathcal{C}(q)}\in\prod_{c\in\mathcal{C}(q)}U_{q,c}(y)$ such that $y$ is an $\varepsilon$-best response of $q$ against $(x_{c})_{c\in\mathcal{C}(q)}$ and $z\}$; here, mixed strategy $z$ is associated with parent player $p$.

We also define the set $U_{r}$ for the root $r$ of tree $G$: $U_{r}:=\{y\in U\mid$ there exist mixed strategies $(x_{c})_{c\in\mathcal{C}(r)}\in\prod_{c\in\mathcal{C}(r)}U_{r,c}(y)$ such that $y$ is an $\varepsilon$-best response of $r$ against $(x_{c})_{c\in\mathcal{C}(r)}\}$.

If $y\in U_{p,q}(z)$ and $q$ is not a leaf, then, by the above definition, there exist mixed strategy profiles $(x_{c})_{c\in\mathcal{C}(q)}\in\prod_{c\in\mathcal{C}(q)}U_{q,c}(y)$ such that $y$ is an $\varepsilon$-best response of $q$ against $(x_{c})_{c\in\mathcal{C}(q)}$ and $z$. We will use $E_{p,q}(z,y)$ to denote such a collection of mixed strategies, $(x_{c})_{c\in\mathcal{C}(q)}$.

Along these lines, for the root $r$ of the tree $G$ we define $E_{r}(y)$, for each $y\in U_{r}$, to be a collection of mixed strategies $(x_{c})_{c\in\mathcal{C}(r)}\in\prod_{c\in\mathcal{C}(r)}U_{r,c}(y)$ such that $y$ is an $\varepsilon$-best response of $r$ against $(x_{c})_{c\in\mathcal{C}(r)}$.

Note that mixed strategies in $E_{p,q}(z,y)$ extend $y$ into a “partial” $\varepsilon$-Nash equilibrium of the subtree rooted at $q$. Specifically, we can inductively use $E_{p,q}(z,y)$, then $E_{q,c}(y,x_{c})$, for each $c\in\mathcal{C}(q)$, and so on, to determine mixed strategies $(x_{s})_{s\in\mathcal{D}(q)}$ for each descendant $s\in\mathcal{D}(q)$ such that no player in the subtree rooted at $q$ can benefit more than $\varepsilon$, in expectation, by deviating unilaterally. Here we do not assert that the parent player $p$ is at an approximate equilibrium. In addition, note that the utilities of all the players $s\in\mathcal{D}(q)\cup\{q\}$ depend only on the mixed strategies of players in $\mathcal{D}(q)\cup\{p,q\}$ and, hence, these utilities can be determined even if the mixed strategies of players in $[n]\setminus\left(\mathcal{D}(q)\cup\{p,q\}\right)$ are unspecified.

Following the definition of $U_{p,q}(z)$, Algorithm 1 constructs these sets and extensions $E_{p,q}(z,y)$ for all parent-child pairs $(p,q)\in E$ and $z\in U$ in a bottom-up manner. At the end, the algorithm uses the set $U_{r}$ defined for the root $r$ to find an $\varepsilon$-Nash equilibrium of the game. Overall, the applicability of the sets $U_{p,q}$ and $E_{p,q}$ is established in Lemma 1 below.

Let $\mathcal{G}$ be a polymatrix game over a tree $G=(V,E)$. Given sets $U_{p,q}(z)$—for each parent-child pair $(p,q)\in E$—and mixed strategy collections $E_{p,q}(z,y)$—for $y\in U_{p,q}(z)$—along with a mixed strategy profile $\hat{y}\in U_{r}$ and associated collection $E_{r}(\hat{y})$ for the root $r$, we can find an $\varepsilon$-Nash equilibrium of the game $\mathcal{G}$ in time polynomial in $|U|$.

The lemma is implied directly by the underlying definitions. For each parent-child pair $(p,q)\in E$ there exists at least one set $U_{p,q}$ which is nonempty: as mentioned above, every $n$-player $m$-action game admits an $\varepsilon$-Nash equilibrium $(\hat{x}_{q})_{q\in[n]}$ where each $\hat{x}_{q}\in U$. Hence, in particular, $\hat{x}_{q}\in U_{p,q}(\hat{x}_{p})$. Moreover, we have $\hat{x}_{r}\in U_{r}$.

In fact to find an $\varepsilon$-Nash equilibrium we can start with the given mixed strategy profile $x_{r}=\hat{y}$ then, for each $c\in\mathcal{C}(r)$, pick the corresponding mixed strategy $x_{c}$ in $E_{r}(x_{r})$. The definition of $E_{r}(x_{r})$ implies that $x_{c}$ can be extended to obtain an $\varepsilon$-Nash equilibrium of the subtree rooted at $c$. We can in fact find such an $\varepsilon$-Nash equilibrium by proceeding inductively down the tree; in particular, by setting $x_{s}$ for $s\in\mathcal{C}(c)$ to be the strategy associated with $s$ in $E_{r,c}(x_{r},x_{c})$). The definitions of $E_{p,q}$s ensure that this inductive process will run to completion and find an $\varepsilon$-Nash equilibrium of the subtree rooted at $c$. By repeating the process for each $c\in\mathcal{C}(r)$ we will find a mixed strategy $x_{p}$ for each player $p\in[n]$. Furthermore, the definitions of the underlying sets also imply that the found mixed strategy profile $(x_{p})_{p\in[n]}$ is an $\varepsilon$-Nash equilibrium. ∎

Algorithm 1 tests whether $y\in U_{p,q}(z)$ (i.e., tests whether there exist mixed strategy profiles $(x_{c})_{c\in\mathcal{C}(q)}\in\prod_{c\in\mathcal{C}(q)}U_{q,c}(y)$ such that $y$ is an $\varepsilon$-best response of $q$ against $(x_{c})_{c\in\mathcal{C}(q)}$ and $z$) in Step 8, and the same idea is employed in Step 17. In particular, if the number of children of $q$ is $\Omega\left(\frac{\log m}{\varepsilon^{2}}\right)$ then Algorithm 1 uses the following linear-programming relaxation LP($p,q,z,y$) to perform this test. The other case, wherein $|\mathcal{C}(q)|=o\left(\frac{\log m}{\varepsilon^{2}}\right)$, is addressed directly via exhaustive search, see proof of Theorem 1 for details.

Formally, Lemma 2 below establishes that the feasibility of the linear program LP($p,q,z,y$) implies the required containment $y\in U_{p,q}(z)$, when $|\mathcal{C}(q)|=\Omega\left(\frac{\log m}{\varepsilon^{2}}\right)$. Note that LP($p,q,z,y$) is parameterized by players $p$ and $q$ along with mixed strategies $z$ and $y$. In addition, inequality (3) in LP($p,q,z,y$) enforces that $y$ is an $\varepsilon/2$-best response against $\sigma_{c}$s and $z$. Also, if for some player $c\in\mathcal{C}(q)$ the set $U_{q,c}(y)$ is empty, then LP($p,q,z,y$) is trivially infeasible.

Let player $p$ be the parent of player $q$ in a normalized polymatrix game over rooted tree $G=(V,E)$. Also, let the number of children of $q$, $|\mathcal{C}(q)|=\Omega\left(\frac{\log m}{\varepsilon^{2}}\right)$. Then, the feasibility of the linear program LP($p,q,z,y$), for mixed strategies $z,y\in U$, implies that $y\in U_{p,q}(z)$. Moreover, using a feasible solution of LP($p,q,z,y$) we can find mixed strategy profiles $E_{p,q}(z,y)$ via a sampling algorithm whose expected running time is polynomial in $|U|$.

Given that the underlying game is normalized (see Definition 2) and $d=\Omega\left(\frac{\log m}{\varepsilon^{2}}\right)$, each entry of $A_{q,c}$ is between and $\frac{\varepsilon}{2\sqrt{6d\log m}}$.

This entry-wise bound implies that for any $c\in\mathcal{C}(q)$ and $\chi_{1},..,\chi_{c},..,\chi_{d},\chi^{\prime}_{c}\in U$ the following Lipscihtz condition holds for $f_{j}$:

Using McDiarmid’s inequality (see Section 2) we get that

Say that mixed strategies $x_{c}\in U_{q,c}(y)$, for $c\in\mathcal{C}(q)$, satisfy event $\mathcal{E}$. Next we will show that $y$ is an $\varepsilon$-best response of $q$ against $(x_{c})_{c\in\mathcal{C}(q)}$, and $z$. Overall, this implies that $y\in U_{p,q}(z)$, and we can set $E_{p,q}(z,y)=(x_{c})_{c\in\mathcal{C}(q)}$.

Using inequality (4) for each $j$ in the support of distribution $y\in\Delta^{m}$, we have

Note that $y$ satisfies inequality (3) in the linear program, i.e., $y$ is an $\varepsilon/2$-best response against $\sigma_{c}$s and $z$. Using inequalities (4) and (5) to bound the change in the left-hand-side of (3) and the right-hand-side of (3) respectively, we get that $y$ is an $\varepsilon$-best response against $x_{c}$s and $z$:

Therefore, if LP($p,q,z,y$) is feasible then $y\in U_{p,q}(z)$. Also, note that the size of LP($p,q,z,y$) is at most $O(nm|U|)$, therefore we can solve the linear program in time polynomial in $|U|$. As mentioned above, given a feasible solution of LP($p,q,z,y$), to obtain $E_{p,q}(y,z)$ (i.e., a collection of mixed strategies $(x_{c})_{c\in\mathcal{C}(q)}$ that satisfy $\mathcal{E}$) the expected number of times that we need to sample is at most two. This establishes the running time bound stated in the lemma, and we get the desired claims. ∎

Given an $n$-player $m$-action normalized polymatrix game over a tree, Algorithm 1 determines an $\varepsilon$-Nash equilibrium of the game in expected time

Let $G=(V,E)$ be the underlying tree of the given normalized polymatrix game. First, we will prove that Algorithm 1 necessarily finds a mixed strategy in $U_{r}$, for the root $r$ of $G$, in the specified amount of time. Hence, via lemma 1, we get that Algorithm 1 successfully finds an $\varepsilon$-Nash equilibrium of the game.

As mentioned above, it was established in that every $n$-player $m$-action game admits an $\varepsilon/2$-Nash equilibrium $(\hat{x}_{q})_{q\in[n]}$ where each $\hat{x}_{q}\in U$.The change from $\varepsilon$-Nash equilibrium to $\varepsilon/2$-Nash equilibrium can be easily addressed by adjusting the size of $U$. Hence, for each parent-child pair $(p,q)\in E$ there exists at least one set $U_{p,q}$ which is nonempty; in particular, $\hat{x}_{q}\in U_{p,q}(\hat{x}_{p})$. Moreover, for $z=\hat{x}_{p}$ and $y=\hat{x}_{q}$ the relaxation LP($p,q,z,y$) is guaranteed to be feasible. Therefore, contingent on the fact that the “if” condition in Step 8 and 17 is performed correctly, we get that Algorithm 1 is guaranteed to move up the tree with non-empty $U_{p,q}$s and, finally, find a mixed strategy in $U_{r}$.

Specifically, the correctness of the “if” condition (which we establish below) ensures that for an $\varepsilon/2$-Nash equilibrium $(\hat{x}_{p})_{p\in[n]}$ and the sets $U_{p,q}$s populated by the algorithm we have $\hat{x}_{q}\in U_{p,q}(\hat{x}_{p})$ for every parent-child pair $(p,q)\in E$. This follows via an inductive argument over levels of the tree: if $q$ is a leaf node then $\hat{x}_{q}$ is an $\varepsilon$ best response against $\hat{x}_{p}$ and we get the desired containment $\hat{x}_{q}\in U_{p,q}(\hat{x}_{p})$. Furthermore, using the induction hypothesis that $\hat{x}_{c}\in U_{q,c}(\hat{x}_{q})$ for all $c\in\mathcal{C}(q)$, we get that the “if” condition in Step 8 will be satisfied for $\hat{x}_{q}$ and $\hat{x}_{p}$, i.e., the algorithm will include $\hat{x}_{q}$ in $U_{p,q}(\hat{x}_{p})$ and the inductive claim holds. In particular, this observation implies that the algorithm will never encounter the situation wherein the set $U_{p,q}(x)$ is remain empty for all $x\in U$ after the for loops, i.e., the algorithm will always run to completion. It is also relevant to note that the algorithm can set $E_{p,q}(\hat{x}_{q},\hat{x}_{p})$ to be any tuple $(x_{c})_{c\in\mathcal{C}(q)}$ that satisfies satisfies the best response condition for $\hat{x}_{q}$ and $\hat{x}_{p}$. That is, it is not necessary that the algorithm sets $E_{p,q}(\hat{x}_{q},\hat{x}_{p})=(\hat{x}_{c})_{c\in\mathcal{C}(q)}$. But still, the above mentioned argument goes though and we get that the algorithm always runs to completion.

The “if” condition in Step 8 and 17 is performed $O(n|U|^{2})$ times. Next we show that the “if” condition is verified correctly in expected time $|U|^{O\left(\frac{\log m}{\varepsilon^{2}}\right)}$. This overall establishes the stated claims.

If the number of children of a player $q$ is $o\left(\frac{\log m}{\varepsilon^{2}}\right)$ then we can go over the entire set $\prod_{c\in\mathcal{C}(q)}U_{q,c}(y)$ in time $|U|^{o\left(\frac{\log m}{\varepsilon^{2}}\right)}$ and determine whether the “if” condition in Step 8 is satisfied. The same argument works in Step 17, if the number of children of the root $r$ is $o\left(\frac{\log m}{\varepsilon^{2}}\right)$.

For the remainder of the proof we consider the other case wherein the number of children of $q$ (or the root $r$) is $\Omega\left(\frac{\log m}{\varepsilon^{2}}\right)$. In this case we verify the “if” condition in Step 8 (and Step 17) by solving the linear-programming relaxation LP($p,q,z,y$) and employing Lemma 2. Note the the size of LP($p,q,z,y$) is $O(n|U|)$ and hence (again, via Lemma 2) in expected time polynomial in $|U|$ we can test if $y\in U_{p,q}(z)$ and find $E_{p,q}(z,y)$. Recall that this test is guaranteed to succeed for the $\varepsilon/2$-Nash equilibrium $(\hat{x}_{q})_{q\in[n]}$, since the corresponding LP($p,q,z,y$)s will be feasible. Hence, we get that Algorithm 1 proceeds up the tree with $\hat{x}_{q}$s, and eventually after processing the root $r$ finds an $\varepsilon$-Nash equilibrium of the game.

Steps 8 and 17 are executed $O(n|U|^{2})$ times, and the expected running time of these steps is $|U|^{O\left(\frac{\log m}{\varepsilon^{2}}\right)}$. These observations establish the time complexity of the algorithm and complete the proof. ∎

Acknowledgements

This work was supported by NSF grants CNS-0846025, CCF-1101470, CNS-1254169, CNS-1518941, SUTD grant SRG ESD 2015 097, along with a Microsoft Research Faculty Fellowship, a Google Faculty Research Award, a Linde/ SISL Postdoctoral Fellowship and a CMI Wally Baer and Jeri Weiss postdoctoral fellowship. Katrina Ligett gratefully acknowledges the support of the Charles Lee Powell Foundation. The bulk of this work was conducted while the authors were at Caltech. The authors also collaborated on this paper while visiting the Simons Institute for the Theory of Computing.

References