In most work on multi-player game theory, payoffs are represented in tabular form: if agents play a game in which each player has (say) two actions available, the game is given by matrices, each of size, specifying the payoffs to each player under any possible combination of joint actions. For game-theoretic approaches to scale to large multi-agent systems, compact yet general representations must be explored, along with algorithms that can efficiently manipulate them
.
In this work, we introduce graphical models for multi-player game theory, and give powerful algorithms for computing their Nash equilibria in certain cases. An-player game is given by an undirected graph on vertices and a set of matrices. The interpretation is that the payoff to player
is determined entirely by the actions of player
and his neighbors in the graph, and thus the payoff matrix for playeris indexed only by these players. We thus view the global
-player game as being composed of interacting local games, each involving (perhaps many) fewer players. Each player’s action may have global impact, but it occurs through the propagation of local influences.
authors were at AT&T Labs. Authors’ email addresses: michael.kearns@syntekcapital.com, mlittman@research.att.com, satinder.baveja@syntekcapital.com.
For multi-stage games, there is a large literature on compact state-based representations for the different stages of the game, such as stochastic games or extensive form games (Owen 1995). Our focus is on representing one-stage, multi-player games.
There are many common settings in which such graphical models may naturally and succinctly capture the underlying game structure. The graph topology might model the physical distribution and interactions of agents: each salesperson is viewed as being involved in a local competition (game) with the salespeople in geographically neighboring regions. The graph may be used to represent organizational structure: low-level employees are engaged in a game with their immediate supervisors, who in turn are engaged in a game involving their direct reports and their own managers, and so on up to the CEO. The graph may coincide with the topology of a computer network, with each machine negotiating with its neighbors (to balance load, for instance).
There is a fruitful analogy between our setting and Bayesian networks. We propose a representation that is universal: any-player game can be represented by choosing the complete graph and the original
-player matrices. However, significant representational benefits occur if the graph degree is small: if each player has at most
neighbors, then each game matrix is exponential only in
rather than. The restriction to small degree seems insuffi-cient to avoid the intractability of computing Nash equilibria. All of these properties hold for the problem of representing and computing conditional probabilities in a Bayes net. Thus, as with Bayes nets, we are driven to ask the natural computational question: for which classes of graphs can we give efficient (polynomial-time) algorithms for the computation of Nash equilibria?
Our main technical result is an algorithm for computing Nash equilibria when the underlying graph is a tree (or can be turned into a tree with few vertex mergings). This algorithm comes in two related but distinct forms. The first version involves an approximation step, and computes an approximation of every Nash equilibrium. (Note that there may be an exponential or infinite number of equilibria.) This algorithm runs in time polynomial in the size of the representation (the tree and the associated local game matrices), and constitutes one of the few known cases in which equilibria can be efficiently computed for a large class of general-sum, multi-player games. The second version of the algorithm runs in exponential time, but allows the exact computation of all Nash equilibria in a tree. In an upcoming paper (Littman et al. 2001), we describe a polynomial-time algorithm for the exact computation of a single Nash equilibrium in trees. Our algorithms require only local message-passing (and thus can be implemented by the players themselves in a distributed manner).
Algorithms for computing Nash equilibria are well-studied. McKelvey and McLennan (1996) survey a wide variety of algorithms covering 2- and-player games; Nash equilibria and refinements; normal and extensive forms; computing either a sample equilibrium or exhaustive enumeration; and many other variations. They note that
-player games are computationally much harder than 2-player games, in many important ways. The survey discusses approximation techniques for finding equilibria in
-player games. Several of the methods described are not globally convergent, and hence do not guarantee an equilibrium. A method based on simplicial subdivision is described that converges to a point with equilibrium-like properties, but is not necessarily near an equilibrium or an approximate equilibrium. In contrast, for the restricted cases we consider, our algorithms provide running time and solution quality guarantees, even in the case of general-sum,
-player games.
Nash (1951), in the paper that introduces the notion of Nash equilibria, gives an example of a 3-player, finite-action game, and shows it has a unique Nash equilibria. Although all payoffs are rational numbers, Nash shows that the players’ action probabilities at the equilibrium are irrational. This suggests that no finite algorithm that takes rational payoffs and transforms them using addition, subtraction, multiplication, and division will be able to compute exact equilibrium policies in general. Thus, the existence of an exact algorithm for finding equilibria in games with treestructured interactions shows that these games are somewhat simpler than general-player games. It also suggests that approximation algorithms are probably unavoidable for general
-player games.
Several authors have examined graphical representations of games. Koller and Milch (2001) describe an extension of influence diagrams to representing-player games, and suggest the importance of exploiting graphical structure in solving normal-form games. La Mura (2000) describes a closely related representation, and provides globally convergent algorithms for finding Nash equilibria.
An
game is defined by a set ofmatrices
specifies the payoff to player when the joint action of the players is
Thus, each has
entries. If a game is given by simply listing the
entries of each of the
matrices, we will say that it is represented in tabular form.
The actions 0 and 1 are the pure strategies of each player, while a mixed strategy for playeris given by the probability
that the player will play 0. For any joint mixed strategy, given by a product distribution
, we define the expected payoff to player
as
whereindicates that each
and 1 with probability
We use
except in theth component, where the value has been changed to
. A Nash equilibrium for the game is a mixed strategy such that for any player
, and for any value
. (We say that
is a best response to
.) In other words, no player can improve their expected payoff by deviating unilaterally from a Nash equilibrium. The classic theorem of Nash (1951) states that for any game, there exists a Nash equilibrium in the space of joint mixed strategies (product distributions).
We will also use the standard definition for approximate Nash equilibria. An-Nash equilibrium is a mixed strategy
. (We say that
is an
-best response to
.) Thus, no player can improve their expected payoff by more than
by deviating unilaterally from an approximate Nash equilibrium.
An
is an undirected graph on
matrices
), called the local game matrices. Player
is represented by a vertex labeled
in
. We use
bors of playerin
—that is, those vertices such that the undirected edge
appears in
always includes
itself. The interpretation is that each player is in a game with only their neighbors in
. Thus, if
, the matrix
has
indices, one for each player in
, and if
the payoff towhen his neighbors (which include himself) play . The expected payoff under a mixed strategy
is defined analogously. Note that in the two-action case,
has
smaller than
Since we identify players with vertices in, and since it will sometimes be easier to treat vertices symbolically (such as and ) rather than by integer indices, we also use
to denote the local game matrix for the player identified with vertex
.
Note that our definitions are entirely representational, and alter nothing about the underlying game theory. Thus, every graphical game has a Nash equilibrium. Furthermore, every game can be trivially represented as a graphical game by choosing to be the complete graph, and letting the local game matrices be the original tabular form matrices. Indeed, in some cases, this may be the most compact graphical representation of the tabular game. However, exactly as for Bayesian networks and other graphical models for probabilistic inference, any time in which the local neighborhoods in can be bounded by, exponential space savings accrue. Our main results identify graphical structures for which significant computational benefits may also be realized.
In this section, we give an abstract description of our algorithm for computing Nash equilibria in trees (see Figure 1). By “abstract”, we mean that we will leave unspec-ified (for now) the representation of a certain data structure, and the implementation of a certain computational step. After proving the correctness of this abstract algorithm, in subsequent sections we will describe two instantiations of the missing details—yielding one algorithm that runs in polynomial time and computes approximations of all equilibria, and another algorithm that runs in exponential time and computes all exact equilibria.
If is a tree, we can orient this tree by choosing an arbitrary vertex to be the root. Any vertex on the path from a vertex to the root will be called downstream from that vertex, and any vertex on a path from a vertex to a leaf will be called upstream from that vertex. Thus, each vertex other than the root has exactly one downstream neighbor (child), and perhaps many upstream neighbors (parents). We use
to denote the set of vertices in that are upstream from
, including
Suppose that
. We let
denote the the subgraph induced by the vertices in
. If
will denote the subset of matrices of corresponding to the vertices in
, with the modifica-tion that the game matrix is collapsed by one index by fixing . We can think of a Nash equilibrium for the graphical game
as an equilibrium “upstream” from (inclusive), given that
Suppose some vertex
single child . We now describe the data structures sent from each to
, and in turn from to , on the downstream pass of the algorithm.
Each parent
. The table is indexed by the continuum of possible values for the mixed strategies
of
. The semantics of this table will be as follows: for any pair
will be 1 if and only if there exists a Nash equilibrium for
in which
. Note that we will slightly abuse notation by letting
refer both to the entire table sent from
, and the particular value associated with the pair
, but the meaning will be clear from the context.
Since and are continuous variables, it is not obvious that the table
can be represented compactly, or even finitely, for arbitrary vertices in a tree. As indicated already, for now we will simply assume a finite representation, and show how this assumption can be met in two different ways in later sections.
The initialization of the downstream pass of the algorithm begins at the leaves of the tree, where the computation of the tables is straightforward. If is a leaf and its only child, then if and only if is a best response to (step 2c of Figure 1).
Assuming for induction that each
sends the table
, we now describe how can compute the table
to pass to its child (step 2(d)ii of Figure 1). For each pair
is set to 1 if and only if there exists a vector of mixed strategies
a witness) for the parents
Note that there may be more than one witness for
on the downstream pass of the algorithm, will also keep a list of the witnesses for each pair
(step 2(d)iiA of Figure 1). These witness lists will be used on the upstream pass. Again, it is not obvious how to implement the described computation of
and the witness lists, sinceis continuous and universally quantified. For now, we assume this computation can be done, and describe two specific implementations later.
To see that the semantics of the tables are preserved by the abstract computation just described, suppose that this computation yields
be a witness for
for all(condition 1 above) ensures by induction that if
plays , there are upstream Nash equilibria in which each . Furthermore, is a best response to the local settings
Figure 1: Abstract algorithm TreeNash for computing Nash equilibria of tree graphical games. The description is incomplete, as it is not clear how to finitely represent the tables , or how to finitely implement step 2(d)ii. In Section 5, we show how to implement a modified version of the algorithm that computes approximate equilibria in polynomial time. In Section 6, we implement a modified version that computes exact equilibria in exponential time.
Therefore, we are in equilibrium upstream from. On the other hand, if
it is easy to see there can be no equilibrium in which . Note that the existence of a Nash equilibrium guarantees that
for at least one
The downstream pass of the algorithm terminates at the root, which receives tables
,
for all, and
The upstream pass begins by choosing any
, and then passing both
to each parent
. The interpretation is that will play
, and is instructing
to play
. Inductively, if a vertex receives a value to play from its downstream neighbor , and the value that
will play, then it must be that
. So chooses a witness to
their value as well as (step 3 of Figure 1). Note that the semantics of
ensure that is a best response to
.
We have left the choices of each witness in the upstream pass non-deterministic to emphasize that the tables and witness lists computed represent all the Nash equilibria. Of course, a random equilibrium can be chosen by making these choices random. We discuss the selection of equilibria with desired global properties in Section 7.
Theorem 1 Algorithm TreeNash computes a Nash equilibrium for the tree game
and witness lists computed by the algorithm represent all Nash equilibria of
In this section, we describe an instantiation of the missing details of algorithm TreeNash that yields a polynomial-time algorithm for computing approximate Nash equilibria for the tree game
arbitrarily precise with greater computational effort.
Rather than playing an arbitrary mixed strategy in
, each player will be constrained to play a discretized mixed strategy that is a multiple of
, for some
to be determined by the analysis. Thus, player
plays
and the joint strategy falls on the discretized -grid
each table (passed from vertex
to child) to be represented in discretized form as well: only the entries corresponding to the
-grid choices for and are stored, and all computations of best responses in the algorithm are modified to be approximate best responses. We return to the details of the approximate algorithm after establishing an appropriate value for the grid resolution
.
To determine an appropriate choice of(which in turn will determine the computational efficiency of the approximation algorithm), we first bound the loss in payoff to any player caused by moving from an arbitrary joint strategy
to the nearest strategy on the-grid.
Fix any mixed strategy
, and let
. We may write the expected payoff to
under
as:
where we simply define
. Note that
We will need the following preliminary lemma.
Lemma 2 Let
Proof: By induction on. Assume without loss of generality that
is a power of 2. The lemma clearly holds for
. Now by induction:
The lemma holds if
. Solving for
yields
Lemma 3 Let the mixed strategies
Proof: Applying Lemma 2 to each term of Equation (1) yields
where
Lemma 3 bounds the loss suffered by any player in moving to the nearest joint strategy on the-grid. However, we must still prove that Nash equilibria are approximately preserved:
Lemma 4 Let
let be the nearest (in
-grid. Then provided
Proof: Let
be a best response for player
to
. We now bound the difference
, which is accomplished by maximizing
and minimizing
Since
On the other hand, again by Lemma 3,
Thus,
Let us now choose to satisfy
Lemma 3), or
Lemma 4 finally establishes that by restricting play to the -grid, we are ensured the existence of an
-Nash equilibrium. The important point is that needs to be exponentially small only in the local neighborhood size
, not the total number of players
.
It is now straightforward to describe the details of our approximate algorithm ApproximateTreeNash. This algorithm is identical to algorithm TreeNash with the following exceptions:
Figure 2: An example game, and the tables computed by the downstream pass of algorithm ApproximateTreeNash. Each vertex in the tree is a player with two actions. Although we omit the exact payoff matrices, intuitively each “M” player maximizes its payoff by matching its child’s action, while each “O” player maximizes its payoff by choosing the opposite action of its child. The relative payoff for matching or unmatching is modulated by the parent values, and also varies from player to player within each vertex type. The grid figures next to each edge are a visual representation of the actual tables computed in the downstream pass of the algorithm, with the settings ; 1s are drawn as black and 0s as gray. Approximate Nash equilibria for the game are computed from the tables by the upstream pass of the algorithm. One example of a pure equilibrium is
; the tables represent a multitude of mixed equilibria as well.
, the table
will contain only entries for
and multiples of
.
All computations of best responses in algorithm TreeNash become computations of-best responses in algorithm ApproximateTreeNash.
Lemma 3 establishes that there will be such an approximate best response on the-grid, while Lemma 4 ensures that the overall computation results in an
-Nash equilibrium. For the running time analysis, we simply note that each table has entries, and that the computation is dominated by the downstream calculation of the tables (Step 2(d)ii of algorithm TreeNash). This requires ranging over all table entries for all
parents, a computation of order
Theorem 5 For any
Then ApproximateTreeNash computes an-Nash equilibrium for the tree game
. Furthermore, for every exact Nash equilibrium, the tables and witness lists computed by the algorithm contain an
-Nash equilibrium that is within
of this exact equilibrium (in
norm). The run- ning time of the algorithm is polynomial in
,
and , and thus polynomial in the size of
See Figure 2 for an example of the behavior of algorithm ApproximateTreeNash.
In this section, we describe an implementation of the missing details of algorithm TreeNash that computes exact, rather than approximate, equilibria. In the worst case, the algorithm may run in time exponential in the number of vertices. We remind the reader that even this result is nontrivial, since there are no finite-time algorithms known for computing exact Nash equilibria in general-sum, multi-party games.
As before, let
be the parents of
, and the child. We assume for induction that each table
passed from
to on the downstream pass can be represented in a particular way—namely, that the set of
pairs where
is a finite union of axis-parallel rectangles (or line segments or points, degenerately) in the unit square. We formalize this representation by assuming each
is given by an ordered list called the -list,
defining intervals of the mixed strategy . For each -interval
where each
, and these intervals are disjoint without loss of generality. By taking the maximum, we can assume without loss of generality that the number of sets
in the union associated with any
-interval is the same. The interpretation of this representation is that if and only if
implies
defining a horizontal strip of , while the associated union
defines vertical bars where the table is 1 within this strip.
We can assume that the tables
-list, by simply letting this common -list be the merging of the separate -lists. Applying algorithm TreeNash to this representation, we now must address the following question for the computation of in the downstream pass. Fix a -interval
. Fix any choice of
indices
range across the rectangular region , what is the set of values of for which some
is a best response to
Assuming
and (which is the more dif-ficult case), a value in
to and
only if the payoff for is identical to the payoff for , in which case any value in
(and thus any value in ) is a best response. Thus,
will be 1 across the region
, and the union of all such subsets of across all
choices of the -interval
, and all
choices of the indices
-interval and indices, the set is actually a union of at most two intervals of, allowing us to maintain the inductive hypothesis of finite union-of-rectangle representations.
Lemma 6 Let
be a player in any -player game against opponents
denote the expected payoff to
tinuous intervals in
Then is either empty, a continuous interval in
, or the union of two continuous intervals in
Proof: We begin by writing
Note that for any
is a linear function of
, as each term of the sum above includes only either
or
Since
is a linear function of
, it is a monotonic function of
; we will use this property shortly.
Now by the continuity of
if and only if
, where
and
First consider , as the argument for is symmetric. Now if and only if
is a monotonic function of each
, this maximum occurs at one of the
extremal points (vertices) of the region
. In other words, if we let
and define the extremal set
For any fixed
by linearity, and so
(and
as well) is either empty, an interval, or the union of two intervals. The same statement holds for
. Note that by the above arguments, can be computed in time exponential in
by exhaustive search over the extremal set .
Lemma 6 proves that any fixed choice of one rectangular region (where the table is 1) from each leads to at most 2 rectangular regions where
is 1. It is also easy to show that the tables at the leaves have at most 3 rectangular regions. From this it is straightforward to show by induction that for any vertex in the tree with child , the number of rectangular regions where
is at most
, where
and are the number of internal vertices and leaves, respectively, in the subtree rooted at. This is a finite bound (which is at most
at the root of the entire tree) on the number of rectangular regions required to represent any table in algorithm TreeNash. We thus have given an implementation of the downstream pass—except for the maintainence of the witness lists. Recall that in the approximation algorithm, we proved nothing special about the structure of witnesses, but the witness lists were finite (due to the discretization of mixed strategies). Here these lists may be infinite, and thus cannot be maintained explicitly on the downstream pass. However, it is not difficult to see that witnesses can easily be generated dynamically on the upstream pass (according to a chosen deterministic rule, randomly, non-deterministically, or with some additional bookkeeping, uniformly at random from the set of all equilibria). This is because given
, a witness is simply any
such that
Algorithm ExactTreeNash is simply the abstract algorithm TreeNash with the tables represented by unions of rectangles (and the associated implementations of computations
Figure 3: Example of a table produced by the exact algorithm. The table is the one generated for vertex 6 in Figure 2. Black cells indicate where the exact table is 1, while dark gray cells indicate where the approximate table is 1 for comparison. We see that the non-rectangular regions in Figure 2 are the result of the approximation scheme.
described in this section), and witnesses computed on the upstream pass. We thus have:
Theorem 7 Algorithm ExactTreeNash computes a Nash equilibrium for the tree game
tables computed by the algorithm represent all Nash equilibria of
in the number of vertices of.
To provide a feel for the tables produced by the exact algorithm, Figure 3 shows the exact table for vertex 6 in the graph game in Figure 2.
We have developed a number of extensions and generalizations of the results presented here. We describe some of them briefly, leaving details for the long version of this paper. At this writing, we have verified these extensions only for the approximation algorithm, and are working on the generalizations for the exact algorithm.
Multiple Actions. For ease of exposition, our approximation algorithm was presented for tree games in which players have only two actions available to them. By letting the tables computed in the downstream pass of this algorithm be of the size necessary to represent the crossproduct of the action spaces available to and , we can recover the same result (Theorem 5) for the multiple-action case. The computational cost in the multiple-action case is exponential in the number of actions, but so is the size of the local game matrices (and hence the size of the representation of the tree game).
Vertex Merging for Sparse Graphs. The extension to multiple actions also permits the use of our approximation algorithm on arbitrary graphs. This is analogous to the use of the polytree algorithm on sparse, non-tree-structured Bayes nets. As in that case, the main step is the merging of vertices (whose action set will now be the product action space for the merged players) to convert arbitrary graphs into trees. To handle the merged vertices, we must ensure that the merged players are playing approximate best responses to each other, in addition to the upstream and downstream neighbors. With this additional bit of complexity (again proportional to the size of the representation of the final tree) we recover our result (Theorem 5).
As with the polytree algorithm, running time will scale exponentially with the largest number of merged players, so it is vital to minimize this cluster size. How best to accomplish this we leave to future work.
Special Equilibria. The approximation algorithm has the property that it finds an approximate Nash equilibrium for every exact Nash equilibrium. The potential multiplicity of Nash equilibria has led to a long line of research investigating Nash equilibria satisfying particular properties. By appropriately augmenting the tables computed in the downstream pass of our algorithm, it is possible to identify Nash equilibria that (approximately) maximize the following measures in the same time bounds:
Social Optimum: Total expected reward, summed over all players.
Welfare Optimum: Expected reward to the player whose expected reward is smallest.
Equilibria with any of these properties are known to be NPhard to find in the exact case, even in games with just two players (Gilboa and Zemel 1989).
I. Gilboa and E. Zemel. Nash and correlated equilibria: some complexity considerations. Games and Economic Behavior, 1: 80–93, 1989.
Daphne Koller and Brian Milch. Multi-agent influence diagrams for representing and solving games. Submitted, 2001.
Pierfrancesco La Mura. Game networks. In Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence (UAI), pages 335–342, 2000.
M. Littman, M. Kearns, and S. Singh. 2001. In preparation.
Richard D. McKelvey and Andrew McLennan. Computation of equilibria in finite games. In Handbook of Computational Economics, volume I, pages 87–142. 1996.
J. F. Nash. Non-cooperative games. Annals of Mathematics, 54: 286–295, 1951.
Guillermo Owen. Game Theory. Academic Press, UK, 1995.