b

DiscoverSearch
About
My stuff
Graphical Potential Games
2015·arXiv
Abstract
Abstract

Potential games, originally introduced in the early 1990’s by Lloyd Shapley, the 2012 Nobel Laureate in Economics, and his colleague Dov Monderer, are a very important class of models in game theory. They have special properties such as the existence of Nash equilibria in pure strategies. This note introduces graphical versions of potential games. Special cases of graphical potential games have already found applicability in many areas of science and engineering beyond economics, including artificial intelligence, computer vision, and machine learning. They have been effectively applied to the study and solution of important real-world problems such as routing and congestion in networks, distributed resource allocation (e.g., public goods), and relaxation-labeling for image segmentation. Implicit use of graphical potential games goes back at least 40 years. Several classes of games considered standard in the literature, including coordination games, local interaction games, lattice games, congestion games, and party-affiliation games, are instances of graphical potential games. This note provides several characterizations of graphical potential games by leveraging well-known results from the literature on probabilistic graphical models. A major contribution of the work presented here that particularly distinguishes it from previous work is establishing that the convergence of certain type of game-playing rules implies that the agents/players must be embedded in some graphical potential game.

Potential games [Monderer and Shapley, 1996] have become an inherently important class of models in game theory. Potential games have special properties such as the existence of Nash equilibria in pure strategies. By now, potential games are so fundamental and core to game theory that their study is of broad interest.

This note introduces graphical potential games, a graphical version of classical potential games. Implicit use of graphical potential games goes back at

least 40 years. Special cases of graphical potential games have already found applicability in many areas of science and engineering beyond economics. These areas include artificial intelligence and computer vision [Miller and Zucker, 1991, Yu and Berthod, 1995, Berthod et al., 1996], machine learning [Rezek et al., 2008], neural networks [Hopfield, 1982, Miller and Zucker, 1991], theoretical computer science, computational social science and sociology [Montanari and Saberi, 2009, 2010], and dynamical systems [Miller and Zucker, 1991, Zucker, 2001]. They have been effectively applied to the study and solution of important real-world problems such as routing and congestion in networks [Rosenthal, 1973], distributed resource allocation such as public goods [Heikkinen, 2006], relaxation-labeling for image segmentation [Rosenfeld et al., 1976, Miller and Zucker, 1991, Zucker, 2001, Yu and Berthod, 1995, Berthod et al., 1996], clustering and probabilistic inference in graphical models via learning in games [Rezek et al., 2008], equilibrium-selection in strategic settings [Young, 1993], the emergence of coordination from individual agent’s strategic behavior [Blume, 1995], the rate at which innovations and norms/conventions spread through a social network and the role of the network structure [Montanari and Saberi, 2009, 2010], and inference in Hopfield networks [Hopfield, 1982]. (Please refer to the given reference for details.) Several classes of games considered standard in the literature, including coordination games, local interaction games [Montanari and Saberi, 2009, 2010], lattice games [Blume, 1993], congestion games [Rosenthal, 1973], and party-affiliation games [Fabrikant et al., 2004], are instances of graphical potential games.

Potential games, like normal-form games, do not have an inherently compact, graphical representation, in contrast to graphical games [Kearns et al., 2001]. Not all potential games are non-trivial graphical games. In a graphical game, the payoff function of each player is a function of its neighbors in the game graph. Any definition of a graphical game must respect that. But the potential function of a potential game is global: it involves all players! That means that we can only use certain types of potential functions to define a graphical potential game.

This note provides several, strong characterizations of graphical potential games by leveraging well-known results from the literature on probabilistic graphical models. A major contribution of the work presented here that particularly distinguishes it from previous work is establishing that the convergence of certain type of game-playing rules implies that the agents/players must be embedded in some graphical potential game. At this point, it is best to delay the discussion of the most closely related work in economics and, more recently, computer science until the end of the paper.

This section introduces basic notation and concepts in graphical models and game theory.

Basic Notation. Denote by  x ≡ (x1, x2, . . . , xn) an n-dimensional vector and by  x−i ≡ (x1, . . . , xi−1, xi+1, . . . , xn) the same vector without component i. Similarly, for every set  S ⊂ [n] ≡ {1, . . . , n}, denote by  xS ≡ (xi : i ∈ S) the (sub-)vector formed from x using only components in S, such that, letting  Sc ≡[n] − Sdenote the complement of S, we can denote  x ≡ (xS, xSc) ≡ (xi, x−i) for every i. If  A1, . . . , Anare sets, denote by  A ≡ ×i∈[n]Ai, A−i ≡ ×j∈[n]−{i}Ajand  AS ≡ ×j∈SAj.

Graph Terminology and Notation. Let G = (V, E) be an undirected graph, with finite set of n vertices or nodes V = [n] and a set of (undirected) edges E. For each node i, let  N(i) ≡ {j | (i, j) ∈ E}be the set of neighbors of i in G, not including i, and  N(i) ≡ N(i) ∪ {i}the set including i. A clique C of G is a set of nodes with the property that they are all mutually connected: for all  i, j ∈ C, (i, j) ∈ E; in addition, C is maximal if there is no other node k outside C that is also connected to each node in C, i.e., for all  k ∈ V − C, (k, i) /∈ Efor some  i ∈ C.

Another useful concept in the context of this note is that of hypergraphs, which are generalizations of regular graphs. A hypergraph G = (V, E) is defined by a set of nodes V and a set of  hyperedges E ⊂ 2V. We can think of the hyperedges as cliques in a regular graph.

2.1 Graphical Models

Graphical models [Koller and Friedman, 2009] are an elegant marriage of statistics and graph theory that has had tremendous impact in the theory and practice of modern statistics. It has permitted effective modeling of large, structured high-dimensional complex systems found in the real world. The language of graphical models allows us to capture the probabilistic structure of complex interactions between individual entities in the system. The core component of the model is a graph in which each node i corresponds to a random variable  Xiand missing edges express conditional independence assumptions about those random variables in the probabilistic system.

2.1.1 Markov Random Fields, Gibbs Distributions and the Hammersley-Clifford Theorem

A joint probability distribution P is called a Markov random field (MRF) with respect to an undirected graph G if for all x, for every node  i, P(Xi = xi | X−i= x−i) =  P(Xi = xi | XN(i) = xN(i)).In that case, the neighbors/variables  XN(i)form the Markov blanket of node/variable  Xi.

A joint distribution P is called a Gibbs distribution with respect to a an undirected graph G if it can be expressed as P(X = x) = �C∈CΦC(xC) for some functions ΦCindexed by a clique  C ∈ C, the set of all (maximal) cliques in G, and mapping every possible value  xCthat the random variables  XCassociated with the nodes in C can take to a non-negative number.

Let us say that joint probability distribution P is positive if it has full support (i.e., P(x) > 0 for all x).

Theorem 1. [Hammersley-Clifford] [Hammersley and Clifford, 1971] Let P be a positive joint probability distribution. Then, P is an MRF with respect to G if and only if P is a Gibbs distribution with respect to G.

In the context of the theorem, the functions ΦCare positive, which allows us to define MRFs in terms of  local potential functions {φC}over each clique C in the graph. Define the function Ψ(x) ≡ �C∈C φC(xC). Let us refer to any function of this form as a Gibbs potential with respect to G. Thanks to the Hammersley-Clifford Theorem, a more familiar expression of an MRF is P(X = x) ∝exp(�C∈C φC(xC)) = exp(Ψ(x)).

2.2 Game Theory and Graphical Games

Let V = [n] denote a finite set of n players in a game. For each player  i ∈ V, let  Aidenote the (finite) set of actions or pure strategies that i can play. Let A denote the set of  joint actions, x ≡ (xi, . . . , xn) ∈ Adenote a joint action, and xithe individual action of player i in x. Denote by  x−ithe joint action of all the players except i, such that  x ≡ (xi, x−i). Let  Mi : A → Rdenote the payoff function of player i.

There are a variety of compact representations for large game inspired by probabilistic graphical models in AI and machine learning [La Mura, 2000, Kearns et al., 2001, Koller and Milch, 2003, Leyton-Brown and Tennenholtz, 2003, Jiang and Leyton-Brown, 2008]. This paper’s context is graphical games [Kearns et al., 2001], a simple but powerful model inspired by probabilistic graphical models such as MRFs.

A graphical game [Kearns et al., 2001] is defined by an undirected graph (V, E) and a set of local payoff hypermatrices  {M ′i:  AN(i) → R | i ∈ V }. Each node  i ∈ Vin the graph corresponds to a player in the game and its payoff function  Mi(x) ≡ M ′i(xN(i)) is defined by its local payoff hypermatrix M ′i, a function of the actions of the players in the neighborhood N(i) of i only, which includes i. A hypergraphical game [Papadimitriou, 2005] is defined by a hypergraph (V, E) and sets of “local” payoffs hypermatrices of the form {M ′i,C:  AC → R | C ∈ E, i ∈ C}. Let  Ci ≡ {C ∈ E | i ∈ C}be the set of cliques in which i participates. The payoff function of player i in a hypergraphical game is defined as  Mi(x) ≡ �C∈Ci M ′i,C(xC). Note that the payoff function of player i only depends directly on the actions of players in its neighborhood N(i) =  ∪C∈CiC = {j ∈ V | i, j ∈ Cfor some  C ∈ E}, which includes i. A polymatrix game [Janovskaja, 1968] is a hypergraphical game in which  C = {{i, j} | i, j ∈ V, j ̸= i}, which is the set of cliques of pairs of nodes involving the player and every other player. If, instead, the hyperedge set of each player is some (possibly different) subset of  {{i, j} | j ∈ V, j ̸= i}, then let us call the game a graphical polymatrix game. Finally, let us say that a hypergraphical game is hyperedge-symmetric if, in addition, for every hyperedge C containing players i, j in the game, we have that  M ′i,C=  M ′j,C ≡ M ′C; if, in particular, the hypergraphical game is a graphical polymatrix game, then let us say that the game is pairwise-symmetric.

This section introduces graphical potential games (and other related subclasses) and provides some structural properties and characterizations of such games. Previous work in probabilistic graphical models facilitate the derivations of the results.

Definition 1. Consider a graph G with (non-inclusive) neighbor sets N(i) for each payer i. For any graphical game with graph G, and for each player i, consider some function  fi : R × AN(i) → R. Let us say that the function  fiis a (conditional) preference-order-preserving transform for player i if  fi(v, xN(i)) is a (strictly) monotonically increasing function of v for every  xN(i) ∈ AN(i). 1Let us call the transform (unconditionally) linear with respect to some positive weight  wiif it takes the form  fi(v, xN(i)) =  wiv. Let us denote by  f −1ithe corresponding (conditional) inverse function of  fi; that is,  f −1i : R × AN(i) → Rsuch that for all  v ∈ Rand  xN(i) ∈ AN(i), we have  f −1i (fi(v, xN(i)), xN(i)) = v. Denote by  f ≡ {fi}and  f −1 ≡ {f −1i }the set of preference-order-preserving transforms  fiand their inverses, respectively, one for each player i. Let us say that a function Ψ is a f-transformed potential for a graphical game with neighbor sets {N(i)} and local payoff matrices  {M ′i}if for all  i, xN(i), and xi, x′i, M ′i(xi, xN(i))−M ′i(x′i, xN(i)) =  fi(Ψ(xi, x−i)−Ψ(x′i, x−i), xN(i)) .Let us call a graphical game with a f-transformed potential a graphical f-transformed potential game.

We can generalize the terminology of Monderer and Shapley [1996] to graphical games. Let w be a positive weight vector. If the transformed  fiof each player i is (unconditionally) linear with weight  wi, then Ψ is called a (weighted) w-potential for the game. If  wi= 1 for all i, then Ψ is called an (exact) potential. Finally, let us say that Ψ is an ordinal potential for a graphical game with neighbor sets {N(i)} and local payoff matrices  {M ′i}if it satisfy the following condi- tion:  M ′i(xi, xN(i))−M ′i(x′i, xN(i)) >0 if and only if Ψ(xi, x−i)−Ψ(x′i, x−i) >0 for all  i, xi, x′iand  xN(i). Let us refer to a graphical game with a (weighted) w-potential, (exact) potential or ordinal potential as a graphical (weighted) w-potential, (exact) potential or ordinal potential game, respectively.

The following theorem characterizes graphical f-transformed potential games: the potential function is the sum of local potential functions over each (maximal) clique in the game graph.

Theorem 2. Every potential of a graphical transformed potential game with graph G is a Gibbs potential with respect to G.

Proof. The proof is based on an application of the Hammersley-Clifford Theorem (Theorem 1). Let Ψ be the f-transformed potential of the graphical game. Define P as a joint probability distribution such that  P(X = x) ∝exp(Ψ(x)) for all x. (Thus, P is positive.) The following derivation shows that P is an MRF with respect to the game graph G: for all  i, xi, x−i,

image

Hence, by the Hammersley-Clifford Theorem (Theorem 1), P is also a Gibbs distribution with respect to the graph G of the game. In particular, let C be the set of (maximal) cliques of G. There exist a local potential function  φ′Cfor each (maximal) clique  C ∈ Cdefining a global potential function Ψ′as Ψ′(x) = �C∈C φ′C(xC) such that  P(X = x) ∝exp(Ψ′(x)). Let  Z = �xexp(Ψ(x)) and Z′= �xexp(Ψ′(x)) be the normalizing constant when expressing P in terms of Ψ and Ψ′, respectively, denote by  c ≡ln(Z/Z′), a constant. Then we have that for all x, Ψ(x) = Ψ′(x) + c. Defining local potential for Ψ as, for example, φC(xC) ≡ φ′C(x) + c/|C| completes the proof.

In view of the strong equivalence established by the last theorem, let us refer to a graphical transformed potential game as a transformed Gibbs-potential game (with the same graph); and similarly for weighted and exact potentials. Whether every graphical ordinal potential game has an (equivalent) ordinal Gibbs potential is left open. So, let us define an ordinal Gibbs-potential game as a graphical game that has a Gibbs potential with respect to the graph of the game.

The following definitions are useful to present the main corollary of the last theorem.

Definition 2. Given an n-dimensional positive weight vector w, let us say that a game with payoff hypermatrices  {M 1i }is w-scaled payoff-difference equivalent to another game with the same players and payoff hypermatrices  {M 2i }if for all  i, x−i, xi, x′i, we have that  M 1i(xi, x−i) − M 1i(x′i, x−i) =  wi(M 2i(xi, x−i) −M 2i(x′i, x−i)). If w is the vector of all 1’s, then let us simply say that the game is payoff-difference equivalent to the other. 2

Definition 3. Let us say that a graph has totally disconnected or open neighborhoods if for every node of the graph, every subgraph induced by the neighbors of the node is the empty graph; in other words, there is no edge connecting any pair of neighbors of any node in the graph; formally, if E is the edge set, then for all i and  j, k ∈ N(i), j ̸= k, we have (j, k) /∈ E.

Some simple examples of graphs with totally disconnected neighborhoods are trees, cycles, and grids.

Corollary 1. Any w-weighted Gibbs-potential game with graph G and potential Ψ is w-scaled payoff-difference equivalent to a hyperedge-symmetric hypergraphical game in which each hyperedge is a (maximal) clique C in G and has as corresponding hypermatrix the local potential associated to C in Ψ. If, in addition, G has totally disconnected neighborhoods then the equivalence is to pairwise-symmetric graphical polymatrix games. 3

It is important to note the implication of the last corollary. In general, there is no reason to expect, a priori, just from the definition of a graphical potential game with, say for example, a tree graph that the differences in payoff matrix for a player would not be arbitrary functions of the action of the player and those of its neighbors. The corollary tells us that this is not possible in this case: the payoff hypermatrices difference must be sums of simple pairwise matrices, each being a simple 2-dimensional matrix depending on the actions of the player and one of its neighbors. The same holds for cycles, grids and similar structures, and their corresponding generalizations, including those to higher dimensions. The following proposition completes the connection in the reverse direction.

Proposition 1. Any hyperedge-symmetric hypergraphical game is a graphical Gibbs-potential game.

Let us consider a sequential process of play in which there is a pre-specified order by which the players play and at each time step t exactly one player plays by choosing an action  xti. 4In the sequel, let us take the sequence of play to be, without loss of generality, the sequence 1, 2, . . . , n. Let us say that a player has a (time-homogeneous, first-order) Markov playing scheme if it has a (possibly randomized) policy, or plan, by which the agent selects an action based only on the last actions played by the other players; more formally, if the policy  piis a conditional probability distribution  pi(xi | x−i) such that if player i is to play at time t + 1 and  xt−iare the last joint-actions that player i observed the others take, then player i chooses to play action  xt+1i = xiwith probability  pi(xi | xt−i) (i.e.,  xt+1i ∼ pi(. | xt−i)).  5For a graphical game, let us further say that the playing scheme is local if it only depends on the last actions of its neighbors in the game graph.

Property 1. In a graphical game with graph G, the sequential process of play generated by Markov playing schemes of the type described above, and that are local with respect to G, is equivalent to realizations generated by running the Gibbs sampler [Geman and Geman, 1984] with conditional distributions given by the individual player’s playing scheme.

For every round r = 1, 2, . . . composed of consecutive time steps of length n, denote by  zr= (zr1, . . . , zrn) the play (joint-action) outcome at round r, so that for all  i, zri=  x(r−1)n+ii(i.e., the joint-action generated during round r by the sequential process of play). Let us refer to the total sequence generated by  zrfor r = 1, 2, . . . , T as the empirical play up to round T (i.e., after nT rounds). Let us say that an empirical play (conditionally) converges starting from an initially assigned play  x0if the empirical joint-probability distribution defined by the empirical play converges (almost surely) to some joint probability distribution as we let the sequential process of play run for an infinite number of rounds (i.e., for every joint-action x, if we denote the empirical distribution of play after T rounds as �P T(x) ≡ 1T�Tr=11[zr= x], then �P ∞(x) ≡limT →∞ �P T(x) exists, with probability one.) Let us refer to a set of playing schemes, one for each player, as a playing procedure for the game. Furthermore, let us say that a playing procedure is consistent (or globally convergent) if the empirical play generated is convergent to the same joint distribution �P ∞(x) from any initial joint play  x0.

Let us say that a player i with payoff function  Miuses a smooth best- response (SBR) playing scheme piwith respect to a (conditional) preference-order-preserving transform  fi : R × A−i → R, if for all  x−i, we have  pi(xi |x−i) ∝exp(fi(Mi(xi, x−i), x−i). If, instead, the  fi’s above are such that the ratio  pi(xi | x−i)/pi(x′i | x−i) = exp(fi(Mi(xi, x−i)−Mi(x′i, x−i), x−i)), then let us call the scheme a smooth best-response-difference (SBRD) playing scheme. 6Recall from the previous discussion that, for a graphical game, a player’s (playing) scheme is local with respect to the game graph, if it only depends on the actions of its neighbors in that graph. In the case of SBR and SBRD schemes, in general, this requires that the domain of the second argument to  fibe  AN(i). Finally, let us say that the game has a (local, Markov) playing procedure if every player uses a (local, Markov) playing scheme.

The following theorems and corollaries provide another characterization of graphical potential games.

Theorem 3. Any graphical game with graph G that has a consistent (Markov) local SBR playing procedure is an ordinal Gibbs-potential game with graph G. If, in particular, the transform  fiused by each player i is (unconditionally) linear with weight 1/wi, then the game is a w-weighted Gibbs-potential game. If the playing procedure is SBRD, instead of SBR, then the game is a  f −1-transformed Gibbs-potential game, where  f −1denote the inverses of the transforms f used by the players for the SBRD scheme.

Proof. As noted in Property 1, the playing procedure is equivalent to the Gibbs sampler. The Markov chain associated with the Gibbs sampler is regular because all the conditional probabilities associated with the players’ schemes are positive. Because the procedure is convergent the limiting empirical distribution of play �Pis the (unique) MRF consistent with the conditional probability distributions. Because �Pis positive, by the Hammersley-Clifford Theorem (Theorem 1), �Pis also a Gibbs distribution with respect to the graph of the game G. Denote by �Ψ the Gibbs potential of �P. Also, denote by �Zi(x−i) ≡ �x′iexp(�Ψ(x′i, x−i)) the normalizing constant for the marginal dis-

tribution over all the variables except i with respect to �P. Similarly, denote by  Zi(xN(i)) ≡ �x′iexp(fi(M ′i(x′i, xN(i)), xN(i))) the normalizing constant of

the player’s scheme. The conditionals of MRF �Pmust satisfy the following condition:

image

From the last equality, we obtain that for all  xi, x−i,

image

Because the second term on the right hand side of the last equation does not depend on  xi, we can obtain that for all  x−iand every pair  xi, x′i,

image

Because the  fi’s are (strictly) monotonically increasing with their first argument,

we have

image

This completes the proof of the first statement. The second statement in the theorem follows by noting that in the case of (unconditionally) linear transforms with weight  wi, we have that the left-hand side of Equation 1 above becomes  fi(M ′i(xi, xN(i)), xN(i))−fi(M ′i(x′i, xN(i)), xN(i)) = wiM ′i(xi, xN(i)) − wiM ′i(x′i, xN(i)) =  wi(M ′i(xi, xN(i)) − M ′i(x′i, xN(i))).The case of SBRD procedure is similar, but simpler:

image

The next proposition completes the characterization of transformed Gibbspotential games as exactly those that have consistent local Markov SBRD playing procedures.

Proposition 2. Any f-transformed Gibbs-potential game with graph G has a consistent Markov SBRD playing procedure that is local with respect to G and each player uses the inverse transforms of f in their playing scheme. If, in particular, the game is a w-weighted Gibbs-potential game, then it also has an SBR procedure with the same properties.

Whether the last theorem extends to graphical ordinal potential games is left open.

Closing Remarks on Related Work. A connection, obtained independently from the one in this paper, between potential games and MRFs appeared in previous work in economics and game theory [Ellison, 1993, Blume, 1993, Kandori et al., 1993, Young, 1993, Blume, 1995], and more recently in the theoretical CS community [Montanari and Saberi, 2009, 2010].

In all that previous work, the interest and goal for making the connection is different than the one here. Roughly speaking, their connection was via very specific “game-playing rules” (e.g., the logit rule and its limiting version, the so called myopic/deterministic/strict best-response rule) on very specific classes of games (e.g., coordination games). Their interest was the nature of the steady state induced by playing some specific-type of rule in some specific kind of game, and sometimes also establishing bounds on the convergence rate to steady state behavior [Montanari and Saberi, 2009, 2010]. That previous work showed that the steady state of running such a rule in a specific type of graphical game called a local interaction game is an MRF with respect to the graph of the specific type of game.

The results presented here are more general in the type of game-playing procedures considered for the characterization. This work does not study limiting cases such as (myopic/deterministic/strict) best-response, nor does it study convergence rates.

No previous work provides a connection in the other direction: if certain type of game-playing rule converges, then the players must be embedded in some graphical potential game.

From a technical perspective, by invoking known results from probabilistic graphical models (e.g., Hammersley-Clifford Theorem [Hammersley and Clifford, 1971, Besag, 1974] and convergence of the Gibbs sampler [Geman and Geman, 1984]), the derivation of our results simplified considerably. Interestingly, the proofs for the previous results appear to be specific versions of those typically used to prove the “hard” direction of the Hammersley-Clifford Theorem. 7

This appendix contains all the proofs left out of the main body of the paper.

A.1 Proof of Corollary 1

The proof follows from Theorem 2 by applying the respective definitions. For the last statement of the corollary, in particular, note that the maximal cliques of a graph with disconnected neighborhoods are exactly the edges of the graph. Hence, each local potential is pairwise in that case, and the payoff difference is the sum of differences of local pairwise potentials, as is the case in any graphical polymatrix games, by definition.

A.2 Proof of Proposition 1

For each hyperedge C in the hypergraphical game, define a corresponding local potential  φC(xC) ≡ M ′C(xC) as the local-clique payoff matrix for C. Defining the Gibbs potential using those local potentials and with the graph being the primal graph of the hypergraph, which is an undirected graph with the same vertex set as the hypergraph but where there is an edge between two nodes if there is a hyperedge containing both nodes. 8

A.3 Proof of Proposition 2

Let Ψ be the Gibbs potential of the game. Define the SBRD playing scheme for each player using the inverse  f −1iof the corresponding game transform, such that

image

where the second equality follows from the definition of transformed potential games. The scheme is local by construction. Because Ψ is a Gibbs potential, by the Hammersley-Clifford Theorem (Theorem 1), there is a positive joint (global) MRF consistent with the conditional distributions induced by the scheme. Hence, running the Gibbs sampler will always converge, regardless of initial conditions. Because the playing procedure is equivalent to running the Gibbs sampler (Property 1), the corresponding empirical distribution of play will always converge to the same Gibbs distribution with potential Ψ. Thus, the procedure will be consistent.

In the special case of a w-weighted Gibbs-potential game, then each player i’s scheme takes the form

image

which corresponds to an SBR with a (unconditionally) linear transform with weight 1/wi.

Marc Berthod, Zoltan Kato, Shan Yu, and Josiane Zerubia. Bayesian image classification using Markov random fields. Image and Vision Computing, 14(4):285 – 295, 1996. ISSN 0262-8856. doi: DOI:10.1016/0262-8856(95) 01072-6.

8Note that in this case, because we are going in the “reverse” direction, local potential

functions do not need to be over maximal cliques.

Julian Besag. Spatial interaction and the statistical analysis of lattice systems. Journal of the Royal Statistical Society. Series B (Methodological), 36(2):192– 236, 1974. ISSN 00359246. URL http://www.jstor.org/stable/2984812.

Lawrence E. Blume. The statistical mechanics of strategic interaction. Games and Economic Behavior, 5(3):387 – 424, 1993. ISSN 0899-8256. doi: http://dx.doi.org/10.1006/game.1993.1023. URL http://www.sciencedirect.com/science/article/pii/S0899825683710237.

Lawrence E. Blume. The statistical mechanics of best-response strategy revision. Games and Economic Behavior, 11(2):111 – 145, 1995. ISSN 0899-8256. doi: http://dx.doi.org/10.1006/game.1995.1046. URL http://www.sciencedirect.com/science/article/pii/S0899825685710469.

Glenn Ellison. Learning, local interaction, and coordination. Econometrica, 61(5):pp. 1047–1071, 1993. ISSN 00129682. URL http://www.jstor.org/stable/2951493.

Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The complexity of pure Nash equilibria. In  STOC ’04: Proceedings of the Thirty-Sixth AnnualACM Symposium on Theory of Computing, pages 604–612, New York, NY, USA, 2004. ACM.

D. Fudenberg and D. Levine. The Theory of Learning in Games. MIT Press, 1999.

Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. Pattern Analysis and Machine Intelligence, IEEE Transactions on, PAMI-6(6):721–741, Nov. 1984.

J.M. Hammersley and P. Clifford. Markov fields on finite graphs and lattices. Unpublished, 1971.

T. Heikkinen. A potential game approach to distributed power control and scheduling. Comput. Netw., 50(13):2295–2311, September 2006. ISSN 1389-1286. doi: 10.1016/j.comnet.2005.09.010. URL http://dx.doi.org/10.1016/j.comnet.2005.09.010.

J J Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences of the United States of America, 79(8):2554–2558, 1982. URL http://www.pnas.org/content/79/8/2554.abstract.

E. B. Janovskaja. Equilibrium situations in multi-matrix games. Litovsk. Mat. Sb., 8:381–384, 1968.

Albert Xin Jiang and Kevin Leyton-Brown. Action-graph games. Technical Report TR-2008-13, University of British Columbia, September 2008. URL http://www.cs.ubc.ca/cgi-bin/tr/2008/TR-2008-13.

Michihiro Kandori, George J. Mailath, and Rafael Rob. Learning, mutation, and long run equilibria in games. Econometrica, 61(1):pp. 29–56, 1993. ISSN 00129682. URL http://www.jstor.org/stable/2951777.

S. Karlin and H. M. Taylor. A First Course in Stochastic Processes. Academic Press, San Diego, second edition, 1975.

Michael J. Kearns, Michael L. Littman, and Satinder P. Singh. Graphical mod- els for game theory. In  UAI ’01: Proceedings of the 17th Conference in Un-certainty in Artificial Intelligence, pages 253–260, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.

Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. Adaptive Computation and Machine Learning. MIT Press, 2009.

Daphne Koller and Brian Milch. Multi-agent influence diagrams for representing and solving games. Games and Economic Behavior, 45(1):181–221, 2003.

Pierfrancesco La Mura. Game networks. In Proceedings of the 16th Annual Conference on Uncertainty in Artificial Intelligence (UAI-00), 2000.

Kevin Leyton-Brown and Moshe Tennenholtz. Local-effect games. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI), pages 772–777, 2003.

Douglas A. Miller and Steven W. Zucker. Copositive-plus Lemke algorithm solves polymatrix games. Operations Research Letters, 10(5):285 – 290, 1991. ISSN 0167-6377. doi: DOI:10.1016/0167-6377(91)90015-H.

Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14(1):124 – 143, 1996.

A. Montanari and A. Saberi. Convergence to equilibrium in local interaction games. In  Foundations of Computer Science, 2009. FOCS ’09. 50th AnnualIEEE Symposium on, pages 303–312, 2009. doi: 10.1109/FOCS.2009.64.

Andrea Montanari and Amin Saberi. The spread of innovations in social networks. Proceedings of the National Academy of Sciences, 2010. doi: 10.1073/pnas.1004098107. URL http://www.pnas.org/content/early/2010/11/10/1004098107.abstract.

Christos H. Papadimitriou. Computing correlated equilibria in multi-player games. In  STOC ’05: Proceedings of the Thirty-Seventh Annual ACM Sym-posium on Theory of Computing, pages 49–56, 2005.

Iead Rezek, David S. Leslie, Steven Reece, Stephen J. Roberts, Alex Rogers, Rajdeep K. Dash, and Nicholas R. Jennings. On similarities between inference in game theory and machine learning. J. Artif. Intell. Res. (JAIR), 33:259–283, 2008. URL http://dblp.uni-trier.de/db/journals/jair/jair33.html#RezekLRRRDJ08.

Azreil Rosenfeld, Robert A. Hummel, and Steven W. Zucker. Scene labeling by relaxation operations. IEEE Transactions of Systems, Man, and Cybernetics, SMC-6(6), June 1976.

R. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65–67, 1973.

H. Peyton Young. The evolution of conventions. Econometrica, 61(1):pp. 57–84, 1993. ISSN 00129682. URL http://www.jstor.org/stable/2951778.

S. Yu and M. Berthod. A game strategy approach for image labeling. Computer Vision and Image Understanding, 61(1):32 – 37, 1995. ISSN 1077-3142. doi: DOI:10.1006/cviu.1995.1003.

Steven W. Zucker. Relaxation labeling: 25 years and sill iterating. In L. S. Davis, editor, Foundations of Image Understanding, chapter 10, pages 289– 322. Kluwer Academic Publishers, Boston, 2001.


Designed for Accessibility and to further Open Science