A Continuation Method for Nash Equilibria in Structured Games

1 Introduction

Game theory is a mathematical framework that describes in­ teractions between multiple rational agents and allows for reasoning about their outcomes. However, the complexity of standard game descriptions grows exponentially with the number of agents involved. For many multi-agent situations, this blowup presents a serious problem. Recent work in artificial intelligence [La Mura, 2000; Kearns et al., 2001; Koller and Milch, 2001] proposes the use of structured game representations that utilize a notion of locality of interaction; these representations allow a wide range of complex games to be represented compactly.

In this paper we consider the task of computing Nash equi­ libria for structured games. A Nash equilibrium is a strategy profile such that it is no agent's interest to deviate unilaterally. A naive approach to finding Nash equilibria is to convert the structured game into a standard game representation, and ap­ ply a standard game-theoretic solution algorithm [McKelvey and McLennan, 1996]. This approach is, in general, infea­ sible for all but the simplest games. We would like an algo­ rithm that exploits the structure in these game representations for efficient computation.

Daphne Koller

Stanford University koller@cs.stanford.edu

In this paper, we describe a set of algorithms that use con­ tinuation methods for solving structured games. These algo­ rithms follow a trajectory of equilibria of perturbed games until an equilibrium of the original game is found. Our algo­ rithms are based on the recent work of Govindan and Wil­ son [2002; 2003a; 2003b] (GW hereafter), which apply to standard game representations (normal-form and extensive­ form). We show how the structure of the games can be ex­ ploited to perform the key computational step of the algo­ rithms of GW.

Our methods address both graphical games [Kearns et al., 2001] and multi-agent influence diagrams (MAIDs) [Koller and Milch, 2001]. We present the first algorithm for finding exact equilibria in graphical games of arbitrary structure. We also provide the first algorithm that can take advantage of the fine-grained structure of MAIDs, and therefore can handle MAIDs which are significantly outside the scope of previous methods. We provide experimental results demonstrating the efficiency of our approach relative to previous methods.

2 Game Representations and Equilibria

2.1 Game Theory

We begin by briefly reviewing concepts from game theory used in this paper, referring to Owen [1995] for a good intro­ duction. A game defines an interaction between a set N of agents. Each agent n E N has a set of available strategies ~n. where a strategy determines the agent's behavior in the game. The precise definition of the set ~n depends on the game representation, as we discuss below. A strategy pro­ file a defines a strategy an E ~n for each n E N. Given a strategy profile a, the game defines a payoff G n (a) for each agent n E N. We use a_n to denote the strategy profiles of the agents n' E N - { n} . Similarly, we use ~-n to refer to the set of all strategy profiles of agents in N - { n}.

A solution to a game is a prescription of a strategy profile for the agents. The agent's goal is to maximize its payoff. Thus, a basic desideratum for a solution profile is stability - it should not be in any agent's interests to deviate from it. More precisely, the fundamental notion of a Nash equilib­ rium [Nash, 1951] is defined to be a strategy profile a such that, for all n E N, Gn(an,a-n) 2: �n(a~,a-n), for all other strategies a~ E ~n. Thus, if an agent knew that the oth­ ers were playing according to an equilibrium profile, it would have no incentive to deviate.

An E-equilibrium is a strategy profile such that no agent can improve its expected payoff by more than E by unilaterally changing its strategy. Unfortunately, finding an E-equilibrium is not necessarily a step toward finding an exact equilibrium: the fact that a is an E-equilibrium does not guarantee the ex­ istence of an exact equilibrium in the neighborhood of a.

Normal-Form Games

A general-sum normal-form game defines a simultaneous­ move multiagent scenario in which each agent independently selects an action and then receives a payoff that depends on the actions selected by all of the agents. More precisely, let G be a normal-form game with a set N of agents. Each agent n E N has a discrete action set Sn and a payoff array Gn with entries for every action profile in ITnEN Sn.

Equilibrium strategies often require that agents randomize their choice of action. A mixed strategy an is a probability distribution over Sn. The set ~n is the set of all mixed strate­ gies. The support of a mixed strategy is the set of actions in Sn that have non-zero probability. A strategy an for agent n is said to be a pure strategy if it has only a single action in its support. The set ~ of mixed strategy profiles is ITnEN ~n· A mixed strategy profile a E ~ is thus an m-vector, where m = LnEN ISnl · Every game is guaranteed to have at least one mixed-strategy equilibrium, and the number of equilibria may be exponential in the number of agents.

Extensive-Form Games

An extensive-form game is represented by a tree in which each node represents a choice either of an agent or of nature. Each of nature's choice nodes is associated with a probability distribution over its outgoing branches. Each leaf z E Z of the tree is associated with a vector of payoffs G(z), where Gn(z ) denotes the payoff to agent nat leaf z. The choices of the agents and nature dictate which path of the tree is fol­ lowed and therefore the payoffs to the agents.

The decision nodes belonging to each agent are partitioned into information sets, where each information set is a set of states among which the agent cannot distinguish. Thus, an agent's strategy must take the same action at all nodes in the same information set. We define an agent history H n (y) for a node y in the tree and an agent n to be a sequence containing the information sets traversed in the path from the root to y , and the action selected at each one. Thus, two nodes have the same agent-n history if the paths used to reach them are indistinguishable to n. (The paths may differ in other ways, such as nature's decisions or the decisions of other agents.) We make the common assumption of perfect recall: an agent does not forget information known nor the choices made at previous decisions. More precisely, if two nodes y, y' are in the same information set for agent n, then Hn(Y) = Hn(Y').

We need a representation of a strategy for an extensive­ form game; unlike the case of normal-form games, there are several quite different choices. For our purposes, the most appropriate representation is the sequence form [Koller and Megiddo, 1992; von Stengel, 1996]. Here, the strategy an for an agent n is represented as a vector of real values of size hn, one for each distinct history Hn(z) for a leaf z in the tree. The number an ( H n ( z)), abbreviated an ( z ), is the product of the probabilities controlled by agent n along the history Hn.

From this representation, we can easily derive the probability of taking an action at a particular information set.

The set of sequence form strategies for agent n is therefore a subset of R hn, where hn is at most the number of leaves in the tree. The set of legal sequence form strategies ~n for agent n is defined by a set of linear constraints on vec­ tors in R hn . The set of sequence form strategy profiles is then defined as ~ = ITnEN ~n· The payoff to agent n in an extensive-form game can be shown to be

Thus, the payoffs are a sum, over the leaves in the tree, of the payoff at a leaf times the product of the sequence form param­ eters for that leaf. 1 Importantly, this expression has a similar multi-linear form to the payoff in a normal-form game, but us­ ing sequence form strategies rather than mixed strategies. In an extensive form game satisfying perfect recall, any mixed strategy equilibrium can be represented using an essentially equivalent sequence form strategy profile.

2.2 Structured Representations

Graphical Games

The size of the payoff arrays required to describe a normal­ form game grows exponentially with the number of agents. Kearns et al. [2001] introduced the framework of graphical games, which provide a more structured representation based on probabilistic graphical models. Graphical games capture local structure in multi-agent interactions, allowing a com­ pact representation for scenarios where each agent's payoff is only affected by a small subset of other agents. Examples of interactions where this structure occurs include agents that in­ teract along organization hierarchies and agents that interact according to geographic proximity.

A graphical game is described like a normal-form game. The basic representation (slightly generalized) is a directed graph with one node for each agent. An edge from agent n' to agent n in the graph indicates that agent n's payoffs depend on the action of agent n'. More precisely, we define Famn to be the set of agents consisting of n itself and its parents in the graph. The agent's payoff Gn is an array indexed only by the actions of the agents in Famn. Thus, the description of the game is exponential in the in-degree of the graph and not in the total number of agents. In this case, we use ~-n and S_n to refer to strategy profiles of the agent in Famn - { n} .

Multi-agent Influence Diagrams

The description length of extensive-form games often also grows exponentially with the number of agents. In many situations this large tree can be represented more com­ pactly. Multi-agent influence diagrams (MAIDs) [Koller and Milch, 2001] allow a structured representation of games in­ volving time and information by extending influence dia­ grams [Howard and Matheson, 1984] to the multi-agent case.

A MAID is represented as a directed acyclic graph over nodes of three types: chance, decision, and utility. (Utility nodes are assumed to have no children.) Chance nodes repre­ sent nature's actions, and a conditional probability distribu­ tion (CPD) is associated with each such node, describing the distribution over outcomes of that variable conditioned on the values of its parents. Each decision node is associated with a single agent. The parents of a decision node represent the variables whose values are known to the agent when mak­ ing that decision. Thus, an agent's decision rule for a node can specify a different strategy for each assignment of values to the node's parents. In effect, each such assignment corre­ sponds to an information set. A randomizing decision rule for a decision node is simply a CPD: a distribution over its values for each instantiation of its parents.

1 For notational simplicity, Gn (z) includes nature's probabilities.

Each utility node is associated with an agent, and repre­ sents a component in that agent's payoff. The utility node takes real values as a deterministic function of its parents. Thus, that component of the agent's payoff depends only on a subset of the variables in the MAID. The agent's overall util­ ity is the sum of the utilities obtained at its different utility nodes. It is easy to show that a MAID defines an extensive­ form game. If we use CPDs and decision rules that are tree­ structured, then the MAID representation is no larger than the corresponding extensive-form representation, and is expo­ nentially smaller in many cases. Note that a graphical game is simply a MAID where each agent has a single decision node and a single utility node, and where the parents of an agent n's utility node are the decision nodes for the agents in Famn.

3 Continuation Methods

We begin with a high-level overview of continuation meth­ ods, referring the reader to [Watson, 2000] for a more detailed discussion. Continuation methods work by solving a simpler perturbed problem and then tracing the solution as the mag­ nitude of the perturbation decreases, converging to a solution to the original problem.

More precisely, let A be a scalar parameterizing a contin­ uum of perturbed problems. When A = 0, the perturbed prob­ lem is the original one; when A = 1, the perturbed problem is one for which the solution is known. Let w represent the vector of real values of the solution. For any perturbed prob­ lem defined by A, we characterize solutions by the equation F(w, A) = 0, where F is a real-valued vector function (so that 0 is a vector of zeros). The function F is such that if F(w, A) = 0 holds then w is a solution to the problem per­ turbed by A.

The continuation method traces solutions along the mani­ fold of solution pairs (w, A) satisfying F(w, A) = 0. Specif­ ically, if we have a solution pair (w, A), we would like to trace that solution to adjacent solutions. Differential changes to w and A must cancel out so that F remains equal to 0. Thus, locally, changes dw and dA along the path must obey 'VwF(w, A) dw = -dA \i'>. F(w, A), which is equivalent to the matrix equation

If the matrix [V wF V>.F] has a null-space of rank 1 every­ where, the curve is uniquely defined. If properly constructed, the curve starting at A = 1 is guaranteed to cross A = 0, at which point the corresponding value of w is a solution to the original problem. A continuation method begins at the known solution for A = 1 . The null-space of the Jacobian V F at a current solution (w , A) defines a direction, along which the solution is moved by a small amount. The process then re­ peats, tracing the curve until A = 0. The cost of each step in this computation, given the Jacobian, is cubic in the size of the Jacobian, due to the required matrix operations.

Continuation methods involve the tracing of a dynamical system through the continuous variation of the parameter A. For computational purposes, discrete steps must be taken. As a result, error inevitably accumulates as the path is traced. One can use several techniques to reduce the error, which we do not describe for lack of space. Unfortunately, these tech­ niques can potentially send the algorithm into a cycle, and in practice they occasionally do. If the algorithm cycles, random restarts and a decrease in step size can improve convergence.

4 Continuation Methods for Games

We now review the work of Kohlberg and Mertens [1986] and GW on applying the continuation method to the task of finding equilibria in games. These algorithms form the ba­ sis for our extension to structured games, described in the next section. The continuation method perturbs the game by adding A times a fixed bonus to each agent's payoffs, such that an agent's bonus depends only on its own actions. If the bonuses are large enough (and unique), the bonuses dominate the original game structure, and the agents need not consider their opponents' plays. Thus, for A = 1, the perturbed game has only one equilibrium: each agent plays the action with the largest bonus. We then use the continuation method to follow a path in the space of A and equilibrium profiles for the re­ sulting perturbed game, decreasing A until it is zero; at this point, the corresponding strategy profile is an equilibrium of the original game. We now make this intuition more precise.

4.1 Normal Form Games

In order to apply Eq. (2), we need to characterize the equi­ libria of perturbed games as the zeros of a function F . We first define an auxiliary function measuring the benefit of de­ viating from a given strategy profile. Specifically, V(a) is a vector payoff function of the payoff to agent n for deviating from the mixed strategy profile a by playing each actions :

We now define a retraction operator R : IRm -t I: to be an operator that maps arbitrary m-vectors w to the point in the space I: of mixed strategies which is nearest to w in Euclidean distance. As outlined in the structure theo­ rem of Kohlberg and Mertens [1986], an equilibrium a is recoverable from a + V (a) by the retraction operator R: R(a + V(a)) = a. In fact, this condition is a full charac­ terization of equilibria. Thus, we can define an equilibrium as a solution to the equation a= R(a + V(a)). Conversely, if a = R(w) and w = a+ V(a) we have the equivalent condition that w = R(w) + V(R(w)). Thus, we can search for a point w E IRm which satisfies this equality, in which case R( w) is guaranteed to be an equilibrium.

We now define the game perturbation and associated con­ tinuation method. For a target game G with payoff function V, we create an easily soluble perturbed game by adding an :n-vector. b of .uniqu~ bonuses that agents receive for play­ mg certam actwns, mdependently of what all other agents do. In perturbing the game G by b, we arrive at a new game G + b in which for each 8 E Sn, and for any t E S_n, (G + b)n(8, t) = Gn(8, t) +b ·. If we make b sufficiently large, then G + b has a unique equilibrium, in which each agent plays the pure strategy 8 for which b8 is maximal.

Now, let V be the payoff function for the target game G. The induced payoff function V + )..b is also perturbed from V by >-.b. Thus, the form of our continuation equation is:

We have that V + )..b is the payoff function for the perturbed gan:~ G.+ >-.b, so F(w, >-.) is zero if and only if R(w) is an eqmhbnum of G + >-.b. At ).. = 0 the game is unperturbed, so F( w, 0) = 0 iff R( w) is an equilibrium of G.

The expensive step in the continuation method is the cal­ culation of the Jacobian 'V wF, required for the computation that maintains the constraint of Eq. (2). Here, we have that ~ wF =I- (I+ 'VV)'V R, where I is them x m identity ma­ tr.Ix. The hard part is the calculation of 'VV. For pure strate­ gies 81 E Sn 1 and 82 E Sn 2 , the value at location (81 82) in 'VV(a) is equal to the expected payoff to agent n1 ~hen it plays the pure strategy 8I, agent n2 plays the pure strategy 82, and all other agents act according to the strategy profile a:

Computing Eq. (4) requires a number of multiplications which is exponential in the game size; the sum is over the exponentially large space S-n 1 -n2 = IT N { } S·. , nE - n1,n2 t

4.2 Extensive Form Games

The same method applies to extensive-form games, using the sequence form parameterization of strategies. We first need to define the bonus vector, and the retraction operator which allows us to characterize equilibria.

The bonus vector in the extensive-form adds a bonus for each sequence of each agent. GW show that a sufficiently large bonus guarantees a unique equilibrium for the perturbed game. The retraction operator R takes a general vector and projects it onto the valid region of sequence forms. As all of the constraints are linear, the projection amounts to a decom­ posable quadratic program (QP) that can be solved quickly. We employ standard QP methods. The Jacobian of the retrac­ tion is easily computable from the set of active constraints.

The solution for the sequence form is now surprisingly similar to that of the normal-form. The key property of the sequence form strategy representation is that the payoff func­ tion is a multi-linear function of the extensive-form parame­ ters, as shown in Eq. (1). The elements of the Jacobian 'VV also have the same general structure. In particular the element corresponding to sequence 81 for agent n1 and sequence 52 for agent n2 is

where Zs1 ,s2 is the set of leaves that are consistent with the sequences s1 (for agent nt) and 82 (for agent n2). We take Zs1,s2 to be the empty Set (and hence 'VV = 0) if St and 8 2 are incompatible. Eq. (5) is precisely analogous to Eq. (4) for normal-form games. We have a sum, over outcomes of the utility of the outcome multiplied by the strategy prob~bilities for all other agents. Note that this sum is over the leaves of the tree, which may be exponential in the number of agents.

Zero-probability actions in extensive-form games give rise to an additional subtlety. Such actions induce a probability of zero for entire trajectories in the tree, possibly leading to equilibria based on unrealizable threats and other undesirable phenomena. For us, they can also lead to bifurcations in the con~inuation path, preventing convergence. Thus, we con­ stram all sequence form parameters to be greater than or equal to E for some small E. This constraint ensures that the contin­ uation path is a 1-manifold. The algorithm thus finds an equi­ lib~~um to a pe~rbed game, where agents have a small prob­ abihty of choosmg an unintended action. As E tends to zero, these equilibria converge to perfect equilibria of the original game [Owen, 1995], a (nonempty) subset of all equilibria. For E small enough, continuity implies that there is always an exact perfect equilibrium in the vicinity of the perturbed equilibrium, which can easily be found using local search.

4.3 Path Properties

In the case of normal-form games, the structure theorem of Kohlberg and Mertens [1986] implies that, with probability one over all choices for b, the path of the algorithm is a one­ manifold without boundary. GW provide an analogous struc­ ture theorem that guarantees the same property for extensive­ form games. Figure 1(a) shows an abstract representation of t?e path followed by the continuation method. The equilib­ num for large positive ).. is unique, so the one-manifold can­ not double back to the side of ).. = oo. Furthermore, the perturbed games along the path can have only a finite number of discrete equilibria, so the path cannot travel back and forth indefinitely. Therefore, it must cross the ).. = 0 hyperplane at least once, yielding an equilibrium. In fact, the path may cross multiple times, yielding many equilibria in a single run. As the path must eventually continue to the).. = -oo side it will find an odd number of equilibria when run to completi~n.

. I~ both normal-form and extensive-form games, the path IS piece-wise polynomial, with each piece corresponding to a different support set of the strategy profile. These pieces are called support cells. The path is not smooth at cell bound­ aries, due to discontinuities in the Jacobian of the retrac­ tion operator, and hence in \7 wF, when the support changes. Thus, in following the path, care must be taken to step up to these boundaries exactly.

In the case of two agents, the path is piece-wise linear and, rather than taking steps, the algorithm can jump from "elbow" to "elbow" along this path. When this algorithm is applied to a two-agent game and a particular bonus vector is used, the steps from support cell to support cell that the algorithm takes are exactly equal to the pivots of the Lemke-Howson solution algorithm [Lemke and Howson, 1964] for two-agent games, and the two algorithms find precisely the same set of solu­ tions. Thus, the continuation method is a strict generalization of the Lemke-Howson algorithm that allows different pertur­ bation rays and games of more than two agents.

4.4 Iterated Polymatrix Approximation

Because perturbed games may themselves have an exponen­ tial number of equilibria, and the path may wind back and forth through any number of them, the continuation algorithm can take a while to trace its way back to a solution to the orig­ inal game. We can speed up the algorithm using an initializa­ tion procedure based on the iterated polymatrix approxima­ tion (IPA) algorithm of GW. A polymatrix game is a normal­ form game where the payoffs to a agent n are equal to the sum of the payoffs from a set of two-agent games, each involving nand another agent. Polymatrix games can be solved quickly using the Lemke-Howson algorithm [1964].

Given a normal-form game G and a strategy profile r7, we can construct a polymatrix game Pu whose Jacobian at r7 is the same as the Jacobian of G's payoff function V at r7. The game Pu is a linearized approximation to G around r7, and can be computed efficiently from the Jacobian of G. GW pro­ vide an iterative algorithm that, in each step, takes a profile r7 and improves it using the solution of the polymatrix approx­ imation Pu . This algorithm is not guaranteed to converge, but in practice, it quickly moves "near" a good solution. We then construct a perturbed game close to the original game for which this approximate equilibrium is an exact equilibrium. The continuation method is then run from this starting point to find an exact equilibrium of the original game.

5 Exploiting Structure

As mentioned above, the calculation of 'VV at each step of the algorithm consumes most of the time. Both in normal-form and (in the worst case) in extensive-form games, it requires time that is exponential in the number of agents. However, as we show in this section, when using a structured represen­ tation such as a graphical game or a MAID, we can effec­ tively exploit the structure of the game to drastically reduce the computational time required.

5.1 Graphical Games

Consider the computation of the normal-form Jacobian in Eq. (4). The key insight is that the choice of strategy for an agent outside the family of n 1 does not affect Gn 1 · This ob­ servation allows us to compute the n 1 entries in the Jacobian locally, considering only n 1 's family. More precisely, we can consider two cases. If n2 ~ Famn 1 , then

Recalling that S-n 1 is a vector of actions only of Famn 1 - { n}, we see that this computation is exponential only in the family size of n 1 . Furthermore, this value does not depend on s2 or n2, and can therefore be calculated once and copied for all agents n2 rf_ Famn 1 and for all choices of their strategies. If n2 E Famn 1 , then we simply have:

Letting f be the maximal family size, and d the maximal number of actions per agent, we have that the computation of the Jacobian requires time O(INIJdf + INI 2 ) .

5.2 MAIDs

The Jacobian for MAIDs

To find equilibria in MAIDs, we extend the sequence form continuation method of Section 4.2. As above, our key task is computing the Jacobian of Eq. (5). The Jacobian has an entry for each pair of sequences in the game (one for each agent). We therefore begin by noting that the sequence form repre­ sentation for MAIDs with perfect recall is no larger than the agent's decision rules for that MAID. Due to perfect recall, the last decision node (in topological order) must have in­ coming edges from all of its previous actions and all parents of previous actions. Moreover, it must have an information set for any distinct agent history. Thus, the agent's decision rule for that final decision has the same size as the sequence form. Hence, the dimension m of the m x m Jacobian ma­ trix is linear in the size of the MAID (where size, as usual, includes the size of the parameterization).

We next tum to the computation of the Jacobian entries. Eq. (5) can be rewritten as

A leaf node z in the extensive-form game is simply an as­ signment x to all of the variables in the MAID, and Gn 1 (z) is n1 's utility given x. The sequence probability r7n(z) is the product of the probabilities for the decisions of agent n in the assignment x . Thus, Eq. (8) is an expectation of Gn 1 (z) /[r7n 1 (z )r7n2 (z )]. The expectation is overthe distribu­ tion defined by the Bayesian network Bu whose structure is the same as the MAID, and where the agents' decision nodes have CPDs determined by r7.

The agent's utility Gn 1 (z) is the sum of its utility nodes. Due to linearity of expectation, we can perform the computa­ tion separately for each of the agent's utility nodes, and then simply add up the separate contributions. Thus, we assume from here on, without loss of generality, that n 1 has only a single utility node U.

The value of r7n, (z) (i = 1, 2) depends only on the values of the set of nodes Dn, consisting of ni 's decision nodes and their parents. Thus, instead of computing the probabilities for all assignments to all variables, we need only to compute the marginal joint distribution over U, Dnl' and Dn 2 From this distribution, we can compute the expectation in Eq. (5).

Using Bayesian Network Inference

Our analysis above reduces the required computations sig­ nificantly. We need only compute one joint distribution for every pair of agents n1, n2. This joint distribution is the one defined by the Bayesian network Bu. Naively, this compu­ tation requires that we execute Bayesian network inference /N/ 2 times: once for each ordered pair of agents n1 , n2 . For­ tunately, we can exploit the structure of the MAID to perform this computation much more efficiently.

The basis for our method is the clique tree algorithm of Lauritzen and Spiegelhalter [1998]. A clique tree for a Bayesian network B is a data structure defined over an undi­ rected tree over a set of nodes C. Each node Ci E C is a subset of the nodes in B called a clique. The clique tree satisfies cer­ tain important properties. It must be family preserving: for each node X in B, there exists a clique Ci E C such that X and its parents are a subset of Ci. It also satisfies a separation requirement: if c2 blocks the path from c 1 to c3' then, in the distribution defined by B, we have that the variables in C1 are conditionally independent of those in c3 given those in c2.

Each clique maintains a data structure, called a potential, which is an unnormalized distribution over the variables in Ci. The size of the potential for Ci is therefore exponential in I ci /. The clique tree inference algorithm proceeds by passing messages from one clique to another in the tree. The mes­ sages are used to update the potential in the receiving clique. After a process in which messages have been sent in both directions over each edge in the tree, the tree is said to be calibrated; at this point, the potential of every clique ci con­ tains precisely the joint distribution over the variables in ci according to B.

We can use the clique tree algorithm to perform inference over Bu. Now, consider the final decision node for agent ni. Due to the perfect recall assumption, all of ni 's previous de­ cisions and all of their parents are also parents of this decision node. The family preservation property therefore implies that Dn, is fully contained in some clique. Thus, the expectation of Eq. (8) requires the computation of the joint distribution over three cliques in the tree: the one containing U, the one containing Dn 1 , and the one containing Dn 2 · We need to compute this joint distribution for every pair of agents n1 , n2 .

The first key insight is that we can reduce this problem to one of computing the joint marginal distribution for all pairs of cliques in the tree. Assume we have computed PB(Ci , Ci) for every pair of cliques Ci, Ci. Now, consider any triple of cliques C1, C2, C3. There are two cases: ei­ ther one of these cliques is on the path between the other two, or not. In the first case, assume without loss of gen­ erality that C2 is on the path from C1 to C3. In this case, by the separation requirement, we have that PB(Ct, c2, C3) = PB(Ct,C2)PB(C2,C3)/PB(C2). In the second case, there exists a unique clique c· which blocks the paths between any pair of these cliques. Again, by the separation property, C* renders these cliques conditionally independent, so we can use a similar method to compute PB ( cl, c2, c3).

Thus, we have reduced the problem to one of computing the marginals over all pairs of cliques in a calibrated clique­ tree. We can use dynamic programming to execute this pro­ cess efficiently. We construct a table that contains PB ( ci, Cj) for each pair of cliques Ci, Ci. We construct the table in or­ der of length of the path from Ci to Ci. The base case is when Ci and Ci are adjacent in the tree. In this case, we have that PB(Ci, Cj) = PB(Ci)PB(Ci)/ PB(CinCi)· The probability expressions in the numerator are simply the clique potentials in the calibrated tree. The denominator can be obtained by marginalizing either of the two cliques. For cliques Ci and Ci that are not adjacent, we let Ck be the node adjacent to Ci on the path from Ci to Ci. The clique Ck is one step closer to Ci, so, by construction, we have already computed P(Ci, Ck)· We can now apply the separation property again:

Let f be the number of cliques in the tree, and d be size of the largest clique (the number of entries in its potential). The cost of calibrating the clique tree for Bu is O(fd) . The cost of computing Eq. (9) for all pairs of cliques is 0(£ 2 d 3 ) . Finally, the cost of computing the Si, s i entry of the Jacobian is O(d 4 ). In games where interactions between the agents are highly structured, the size d of the largest clique can be a constant even as the number of agents grows. In this case, the complexity grows only quadratically in the number of cliques, and hence also in the number of agents.

6 Results

6.1 Graphical Games

We compared two versions of our algorithm: cant, the sim­ ple continuation method, and I PA+cont, the continuation method with the IPA initialization. We compared our results to the published results of the the algorithm of Vickrey and Koller [2002] (VK hereafter). The VK method only returns E-equilibria, but their approach is the only one · that applies to graphical games whose interaction structure is not a (bi­ connected) tree and for which timing results are available. The VK paper contains several different algorithms. We com­ pared against the algorithm which had the smallest approxi­ mation error for a given problem.

Following VK, our algorithms were run on two classes of games, of varying size. The Road game, denoting a situa­ tion where agents must build in land plots along a road, is played on a 2-by-L grid; each agent has three actions, and its payoffs depend only on the actions of its (grid) neighbors. Following VK, we constructed a game where the payoff for an agent is simply the sum of payoffs of games played sepa­ rately with its neighbors, and where each such subgame has the payoff structure of rock-paper-scissors. This game is, in fact, a polymatrix game, and hence is very easy to solve us­ ing our methods. We also experimented with a ring graph with three actions per agent and random payoffs.

For each class of games, we chose a set of game sizes to run on. For each, we selected, randomly in cases where the pay­ offs were random, a set of at least ten (and up to one hundred for MAIDs) test games to solve. We then solved each game with a different random perturbation vector, b, and recorded the time and number of iterations necessary to reach the first equilibrium. We then averaged over test cases. The error bars show the variance due to the choice of perturbation vec­ tor and, for random games, the choice of game. For smaller games, the algorithms always converged to an equilibrium. In about 40% of the larger games (more than 20 agents), the al­ gorithms did not converge on the first trial; in these cases, we restarted the same game with a different random perturbation vector. On average, about 2 restarts were sufficient for these difficult games. In a few large graphical games (e.g. 9% of games with 45 agents), IPA did not converge after 10 restarts; in these cases we did not record results for IPA+cont. In the other restarted cases, we recorded the time for the converging run. Our results are shown in Figures 2(a,b).

In all cases, our algorithm found an equilibrium with error at most w- 12 , essentially machine precision. In the Road games, we compared against the times for VK using their hill climbing method which found €-equilibria with error of w- 4 . In these games, the cont method is more efficient for smaller games, but then becomes more costly. Due to the polymatrix nature of this game, the IPA+cont solves it immediately with the Lemke-Howson algorithm, and is therefore significantly less expensive than VK.

In the random-payoff ring games, VK had an equilibrium error of about 0.01 using their cost minimization method with a grid discretization of 1/3. Here, our algorithms are more ef­ ficient than VK for smaller games (up to 20-30 agents), with IPA+cont performing considerably better than cont. How­ ever, the running time of our algorithms grows more rapidly than that ofVK, so that for larger games, they become imprac­ tical. Nevertheless, our algorithms performed well in games with up to 50 agents and 3 actions per agent, games which were previously intractable for exact algorithms.

Here, we also plotted the number of iterations and time per iteration for cont in Figures 2(c,d). The number of itera­ tions varies based both on the game and perturbation ray cho­ sen. However, the time per iteration is almost exactly cubic as predicted. We note that, when IPA is used, the continuation method converges almost immediately (within a second).

6.2 MAIDs

Koller and Milch [2001] define a relevance graph over the decision nodes in a MAID, where there is an edge from D1 to D2 if the decision rule at D1 impacts the choice of decision rule at D2 . They show that the task of finding equilibria for a MAID can be decomposed, in that only decision nodes in the same strongly connected component in the relevance graph must be considered together. However, their approach is un­ able to deal with structure within a strongly connected com­ ponent, and they resorted to converting the game to extensive form, and using a standard equilibrium solver. Our approach addresses the complementary problem, dealing specifically with this finer-grained structure. Thus, we focused our exper­ iments on MAIDs with cyclic relevance graphs.

We ran our algorithms on two classes of games, with vary­ ing sizes. The first, a simple chain, alternates between deci­ sion and chance nodes with each decision node belonging to a different agent. Each agent has two utility nodes, each con­ nected to its decision node and to a neighbor's (except for the end agents who have one utility node for their single neigh­ bor). All probability tables and payoff matrices are random. Our second example is shown in Figure l(b). It is an exten­ sion of the graphical road game from above. Each agent must submit plans simultaneously (P1-Pn) for the type of building (home or store) that they will build along a road. However, building (B1-Bn) proceeds from left to right and so before committing to a build, an agent can see a noisy estimate of the plans of the agent to its left (E1-En). Agents would pre­ fer to be the first one to start a new type of building (i.e., be different than their left neighbors, but the same as their right neighbors). They also take a penalty if their building and plan decisions differ. Carefully chosen payoffs ensure non-trivial mixed strategies.

Figures 3(a,b) show the running times for computing an equilibrium as the number of agents is increased for both types of games. We compared our results to those achieved by converting the game to extensive-form and running Gam­ bit, a standard equilibrium computation package. Our timing results for Gambit do not include the time for the conversion to extensive-form.

Figures 3(c,d) show the number of iterations and running time per iteration for the case of the two-stage road game. The running time per iteration is once again well fit by a cu­ bic. The variance is mainly due to the execution of the retrac­ tion operator whose running time depends on the number of strategies in the support.

7 Discussion and Conclusions

In the last few years, several papers have addressed the is­ sue of finding equilibria in structured games. For graphical games, the exact algorithms proposed so far apply only to the very restricted class of games where the interaction structure

(b)

(c)

6

#of agents

(d)

Figure 3: Results for MAIDs: (a) Running times for the chain MAID. Results for two-stage Road MAID: (b) running time; (c) number of iterations; (d) time per iteration.

is an undirected tree, and where each has only two possible actions [Kearns et al., 2001; Littman et al., 2002].

There have been several algorithms proposed for the com­ putation of €-equilibria in general graphical games, most of which (implicitly or explicitly) define an equilibrium as a set of constraints over a discretized space of mixed strate­ gies, and then use some constraint solving method: Keams et al. [2001] use a tree-propagation algorithm; Vickrey and Koller [2002] use variable elimination methods (VKl); and Ortiz and Kearns [2003] use arc-consistency constraint prop­ agation followed by search. Vickrey and Koller [2002] also propose a gradient ascent algorithm (VK2). The running times of KLS and VKl both depend on the tree-width of the graph, whereas the running times of our algorithm, VK2, and OK depend on the degree of the graph. However, these latter three algorithms all require multiple iterations and no bounds are currently known on the number of iterations required.

For MAIDs, Koller and Milch [200 1] (KM) define a no­ tion of independence between agents' decision, and provide an algorithm that can decompose the problem based on fairly coarse independence structure. Our algorithm is able to ex­ ploit a much finer-grained structure, resolving an open prob­ lem left by KM. La Mura [2000] (LM) proposes a continu­ ation method for finding one or all equilibria in a G net, a representation which is very similar to MAIDs. This pro­ posal only exploits a very limited set of structural proper­ ties (a strict subset of KM and of our algorithm) . The pro­ posal was also never implemented, and several issues regard­ ing non-converging paths seem unresolved.

We have presented an algorithm for computing exact equi­ libria in structured games. Our algorithm is based on the methods of GW, but shows how the key computational steps in their approach can be performed much more efficiently by exploiting the game structure. Our method allows us to pro­ vide the first exact algorithm for general graphical games, and the first algorithm that takes full advantage of the indepen­ dence structure of a MAID. Our methods can find exact equi­ libria in games with large numbers of agents, games which were previously intractable for exact methods.

Acknowledgments. This work was supported by ONR MURI Grant N00014-00-1-0637, and by Air Force contract F30602-00-2-0598 under DARPA's TASK program.