\documentclass{sig-alternate}
% \documentstyle[times,nips01e,natbib,epsf]{article}

\usepackage{times,epsf}
\usepackage{algorithmic} 
\usepackage{algorithm}

%\input{psfig}
\usepackage{psfig}

%\usepackage{natbib}
\usepackage{amsmath}
%\usepackage{algorithmic} 
%\usepackage{algorithm}
%\usepackage{comment}

\def\Exp {{\bf E}}
\def\Pr  {{\bf Pr}}
\def\matset {{\cal M}}
\def\up {{\rm Up}}

\bibliographystyle{plainnat}

\newcommand{\comment}[1]{}
\newcommand{\ignore}[1]{}
\newcommand{\hs}{\enspace}
\newcommand{\hhs}{\thinspace}
\newcommand{\diverges}{\uparrow}
\newcommand{\converges}{\downarrow}
\newcommand{\inter}{\bigcap}
\newcommand{\real}{\ifmmode {\rm R} \else ${\rm R}$ \fi}
\newcommand{\nat}{\ifmmode {\rm N} \else ${\rm N}$  \fi}
\newcommand{\tot}{\ifmmode {\cal T} \else ${\cal T}$ \fi}
\newcommand{\sigstar}{\ifmmode \Sigma^{\ast} \else $\Sigma^{\ast}$ \fi}
\renewcommand{\star}{\ast}
\newcommand{\eqstar}{=^\ast}
\newcommand{\eqa}{=^a}
\newcommand{\eqk}{=^k}
\newcommand{\iok}{\exists_k^{\infty}}
\newcommand{\aek}{\forall_k^{\infty}}
\newcommand{\inn}{\ifmmode \in \else $\in$ \fi}
\renewcommand{\phi}{\ifmmode \varphi \else $\varphi$ \fi}
\renewcommand{\le}{\ifmmode \leq \else $\leq$ \fi}
\renewcommand{\ge}{\ifmmode \geq \else $\geq$ \fi}
\renewcommand{\ne}{\ifmmode \neq \else $\neq$ \fi}
\newcommand{\lt}{\ifmmode < \else $<$ \fi}
\newcommand{\gt}{\ifmmode > \else $>$ \fi}
\newcommand{\eq}{\ifmmode = \else $=$ \fi}
\newcommand{\half}{\ifmmode \frac{1}{2} \else $\frac{1}{2}$ \fi}
\newcommand{\oneovern}{\ifmmode \frac{1}{n} \else $\frac{1}{n}$ \fi}
\newcommand{\nseqm}{M_1,M_2,\ldots,M_n}
\newcommand{\ra}{\ifmmode \rightarrow \else $\rightarrow$ \fi}
\newcommand{\imp}{\ifmmode \Rightarrow \else $\Rightarrow$ \fi}
%LEO: (?)\newcommand{\implies}{\ifmmode \Rightarrow \else $\Rightarrow$ \fi}
% \newcommand{\qed}{\ifmmode \;\; {\rm QED} \else QED \fi}
\newcommand{\pr}{\Pr}
\renewcommand{\notin}{\ifmmode \not\in \else $\not\in$ \fi}
% \newtheorem{theorem}{Theorem}[chapter]
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newlength{\thislabel}
\newcommand{\labsize}[1]{\settowidth{\thislabel}{#1}}
\def\lablistlabel#1{\rm #1\hfil}
\newenvironment{lenlist}[1]{
\labsize{#1}
\envbegin{list}{}{%
  \setlength{\labelwidth}{\thislabel}
 % \setlength{\baselineskip}{0.35\baselineskip}
  \setlength{\itemindent}{0pt}
  \setlength{\labelsep}{1em}
  \setlength{\rightmargin}{2em}
  \setlength{\leftmargin}{4em} %{\thislabel}
   % \addtolength{\leftmargin}{\labelsep}
  \setlength{\listparindent}{0pt}
  \let \makelabel \lablistlabel}
}{\envend{list}}

\def\and{\unskip\enspace{\rm and}\enspace}

%\newtheorem{corollary}{Corollary}
%\newtheorem{lemma}{Lemma}
%\newtheorem{proposition}{Proposition}
%\newtheorem{theorem}{Theorem}
\newcommand{\myvec}[1]{\ensuremath{\boldsymbol{#1}}}
\newcommand{\mymat}[1]{\ensuremath{\boldsymbol{#1}}}
\newcommand{\sketchbox}[1]{\noindent \fbox{\parbox{\textwidth}{#1}}}
\newcommand{\qedsymb}{\hfill{$\Box$}}
%\newenvironment{proof}{\begin{trivlist}
%\item[\hspace{\labelsep}{\bf\noindent Proof: }]
%}{\qedsymb\end{trivlist}}
%\newcommand{\qed}{\hfill{$\Box$}}
%\newenvironment{mynotes}{\begin{comment}}{\\ 
%\end{comment}}
%\excludecomment{mynotes}
\newenvironment{allnotes}{\begin{trivlist}
\item[\hspace{\labelsep}{\bf\noindent NOTE: }]
}{\bf\noindent ENDNOTE \end{trivlist}}
\newenvironment{tmpnotes}{}{}
\renewcommand{\algorithmiccomment}[1]{{\em #1}}
\DeclareMathOperator*{\argmax}{argmax}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\Pa}{Pa}
\DeclareMathOperator*{\pa}{pa}
\DeclareMathOperator*{\Var}{Var}
\DeclareMathOperator*{\Cov}{Cov}
\DeclareMathOperator*{\E}{E}
\DeclareMathOperator*{\KL}{KL}
\DeclareMathOperator*{\myL}{L}
\DeclareMathOperator*{\SIS}{SIS}
\DeclareMathOperator*{\Times}{\mbox{\LARGE $\times$}}

\newcommand{\lne}{\ifmmode \equiv_{\textrm{LN}} \else $\equiv_{\textrm{LN}}$  \fi}
\newcommand{\pe}{\ifmmode \equiv_{\textrm{EP}} \else $\equiv_{\textrm{EP}}$  \fi}

%\newtheorem{thm}{Theorem}[section]

\begin{document}

\conferenceinfo{EC'03,} {June 9--12, 2003, San Diego, California, USA.}
\CopyrightYear{2003}
\crdata{1-581113-679-X/03/0006}

% Start of patch
\def\more-auths{%
\end{tabular}
\begin{tabular}{c}}
% End of patch
%
%
\title{Correlated Equilibria in Graphical Games}
%
\numberofauthors{2} % NOTE! There are now '2' authors (Rous and Richards).
                    % The other authors (Unson and Siedun), although they may format underneath,
		    % are not in the author count -- they are merely being 'patched in'.
		    % Doing it this way will create a "2X2" arrangement -- aesthetically more appealing
		    % than 3 authors across the top and a single author centered below.
		    % However, if your desire is to truly have a "3 & 1" arrangement, then I think there's
		    % enough information provided here to permit you to achieve this.
%
\author{\alignauthor Sham Kakade\\
       \affaddr{Gatsby Neuroscience Unit} \\
       \affaddr{University College London} \\
       \email{sham@gatsby.ucl.ac.uk}
\alignauthor Michael Kearns\\
       \affaddr{Computer and Information Science} \\
       \affaddr{University of Pennsylvania} \\
       \email{mkearns@cis.upenn.edu}
%
% Here are the 'other' authors simply being 'patched in'...
%
\vskip1pc  % optional
\more-auths
\alignauthor John Langford\\
      \affaddr{IBM Research} \\
      \affaddr{TJ Watson} \\
      \email{jcl@cs.cmu.edu}
%
\alignauthor Luis Ortiz\\
       \affaddr{Computer and Information Science} \\
       \affaddr{University of Pennsylvania} \\
       \email{leortiz@linc.cis.upenn.edu}
%
}
% 
% 
\maketitle
%


\iffalse
\title{Correlated Equilibria in Graphical Games}

\numberofauthors{1}

\author{
\alignauthor 
	Sham Kakade,
	Michael Kearns,
	John Langford,
	Luis Ortiz
	\thanks{Author affiliations: 
		S. Kakade, Gatsby Computational Neuroscience Unit, University College London;
		M. Kearns, Computer and Information Science, University of Pennsylvania;
		J. Langford, IBM Research, TJ Watson;
		L. Ortiz, Computer and Information Science, University of Pennsylvania.
		Email addresses:
			{\tt sham@gatsby.ucl.ac.uk};
			{\tt mkearns@cis.upenn.edu};
			{\tt jcl@cs.cmu.edu};
			{\tt leortiz@linc.cis.upenn.edu}.
	}\\
%(if needed)\\
}

\iffalse
\author{
\alignauthor Sham~Kakade \\ % \thanks{http://www.cs.rutgers.edu/{\huge $_{_{\tilde{\ }}}$}allender}\\
  \affaddr{Gatsby Computational Neuroscience Unit}\\
  \affaddr{University College London}\\
  \email{sham@gatsby.ucl.ac.uk}\\
\alignauthor Michael Kearns \\ % \thanks{http://www.cis.upenn.edu/{\huge $_{_{\tilde{\ }}}$}mkearns}\\
  \affaddr{Computer and Information Science}\\
  \affaddr{University of Pennsylvania}\\
\email{mkearns@cis.upenn.edu} \\
\alignauthor Luis Ortiz\\ % \thanks{http://www.cis.upenn.edu/{\huge $_{_{\tilde{\ }}}$}mkearns}\\
  \affaddr{Computer and Information Science}\\
  \affaddr{University of Pennsylvania}\\
\email{leortiz@linc.cis.upenn.edu} \\
\alignauthor John Langford\\
  \affaddr{IBM Research}\\
  \affaddr{TJ Watson}\\
\email{jcl@cs.cmu.edu} \\
%(if needed)\\
}
\fi

\date{5 Feb 2003}
\maketitle
\fi

\begin{abstract}
We examine correlated equilibria in the recently introduced formalism
of graphical games, a succinct representation for multiplayer games.
We establish a natural and powerful relationship between the graphical
structure of a multiplayer game and a certain Markov network
representing distributions over joint actions. Our first main result
establishes that this Markov network succinctly represents all
correlated equilibria of the graphical game up to expected payoff
equivalence. Our second main result provides a general algorithm for
computing correlated equilibria in a graphical game based on its
associated Markov network. For a special class of graphical games that
includes trees, this algorithm runs in time polynomial in the
graphical game representation (which is polynomial in
the number of players and exponential in the graph degree).
\end{abstract}

\category{F.2.0}{Analysis of Algorithms and Problem Complexity}{General}

\terms{Algorithms, Theory, Economics}

\keywords{Game Theory, Correlated Equilibria, Graphical Games,
	Graphical Models}

\section{Introduction}

Graphical games are a compact representation of multiplayer games that
exploit a graph-theoretic or network structure of strategic
interaction among the participants.  A number of recent papers
have established
algorithms for computing Nash equilibria directly on the graph
representation, including provably efficient algorithms for
computing all approximate Nash equilibria in tree-structured games
\cite{kearns01}
\cite{littman02},
and convergent heuristics for general graphs that seem to exhibit
promising experimental behavior
\cite{ortiz03}
\cite{Vickrey02}.
Just as graphical models for
probabilistic inference (such as Bayesian and Markov networks) have
revolutionized the applicability of probabilistic modeling in a wide
variety of domains, graphical games are part of an overarching program
to develop compact models, and algorithms that exploit them, in order
to create a richer computational toolbox for game theory
\cite{koller01}
\cite{lamura00}.

Like much of the history of game theory generally, the study of
graphical games so far has been dominated by Nash's classical notion
of equilibrium, for which it always suffices to consider product
distributions over the players' joint actions.  In this paper, we
examine {\em correlated equilibria\/} \cite{aumann74} in graphical
games, which allow arbitrary joint distributions. 
Correlated equilibria offer a number of conceptual and
computational advantages over Nash equilibria, including the facts
that new and sometimes more ``fair'' payoffs can be achieved, that
correlated equilibria can be computed efficiently for games in
standard normal form, and that correlated equilibria are the
convergence notion for several natural learning algorithms
\cite{foster99}. Furthermore, it has been argued that correlated
equilibria are the natural equilibrium concept consistent with the
Bayesian perspective \cite{aumann87}\cite{foster97}. In this paper, we
present a series of fundamental results examining the representational
and computational issues that arise when considering correlated
equilibria in the compact language of graphical games.

The first issue that arises in this investigation is the problem of
{\em representing\/} correlated equilibria. Unlike Nash equilibria,
even in very simple graphical games there may be correlated equilibria
of essentially arbitrary complexity (for instance, any mixture distribution of
Nash equilibria is a correlated equilibrium). Since one of our primary
goals is to maintain the succinctness of graphical games, some way of
addressing this distributional complexity is required. For this we
turn to another graphical formalism --- namely, undirected graphical
models for probabilistic inference, also known as {\em Markov
networks\/}.

Our main results establish a natural and powerful relationship between a graphical
game and a certain associated Markov network. Like the graphical game, the
associated Markov network is a graph over the players.
While the interactions between vertices in
the graphical game are entirely {\em strategic\/} and given by local payoff matrices,
the interactions in the associated Markov network are entirely {\em probabilistic\/} 
and given by local potential
functions. 
% While not isomorphic to the graph of the game, 
The graph of the associated Markov
network 
retains the parsimony of the
graphical game.

Our first main result shows that the associated Markov network is
sufficient for representing {\em any\/} correlated equilibria of the
graphical game, up to expected payoff equivalence.  In other words,
the fact that a multiplayer game can be succinctly represented by a
graph implies that its entire space of correlated equilibria, up to
payoff equivalence, can be represented graphically with comparable
succinctness.  This basic result establishes a new sense in which
graphical games are a powerful formalism, and highlights the natural
relationship between computational game theory and modern
probabilistic modeling.

Our second main result establishes the {\em computational\/} benefits
of this relationship. The fact that correlated equilibria are
characterized by a set of linear inequalities is not helpful for
unrestricted multiplayer games, since in general there are an
exponential number of such inequalities. Here again the graphical
representations reap benefits. We show that a graphical game gives
rise to a small set of linear inequalities (comparable in size to the
game representation itself) with a non-empty feasible region that
includes all correlated equilibria.  In the case that the associated
Markov network is {\em chordal\/}, 
which includes graphical games that are trees
as a special case, we prove that any point in the feasible region can
be efficiently mapped to a correlated equilibrium on the associated
Markov network, thus yielding a polynomial time algorithm for
computing correlated equilibria in a large class of graphical
games. This algorithm also applies generally to non-chordal graphs,
but in the worst case may require an exponential increase in the
Markov network size.

% MK: please keep below for now
\iffalse
Outline for the introduction:
\begin{itemize}
\item Begin by reviewing main advantages of graphical games:
	allow natural {\em structure} to be explicitly and compactly modeled in large
	multiparty games, and provide algorithms for exploiting this structure; quickly
	review specific works
\item Observe that work on GGs so far, and indeed the entire history of game theory
	more generally, has been dominated by the study of Nash equilibria
\item Briefly mention (will be elaborated on later) the interesting differences
	and advantages of {\em correlated} equilibria: can achieve payoffs not
	achievable as Nash, can compute efficiently in traditional matrix representation,
	may represent a natural type of cooperation, etc.
\item This paper: a set of results examining the representational and computational 
	issues arriving when we consider CEs in GGs.
\item First issue of importance: when considering NE in GGs, no matter how large/complex
	the game, NE always have a compact representation since they are just product
	distributions. CEs may be, in principle and reality, arbitrary, extremely complex
	joint distributions over joint actions, even when the underlying GG is very
	simple. Thus need to also have a compact representation of the CEs.
\item We turn to the most natural and well-developed representation, graphical models
	for joint distributions. We choose to work in the setting of undirected GMs or
	Markov nets, but all results have analogues in the directed language of Bayesian
	networks.
\item Our results demonstrate and exploit natural and interesting
	relationships between the underlying graph of the game, and the ``minimal'' Markov
	network required to represent the CEs of the game.
\item Quick summary of main results:
	\begin{itemize}
	\item Introduction of the minimal MN for a GG
	\item Proof that this minimal MN suffices to represent all CE up to EPE
	\item Proof that this minimal MN really is minimal
	\item In the case that the GG is a tree, a linear-feasibility algorithm
		that will compute a CE in time polynomial in the size of the GG,
		and also provides a compact description of all CE for the GG
	\item Other algorithmic results we probably won't have time to get to (?)
	\end{itemize}
\item Promise for a future paper (maybe in one of the Jan conferences?):
	\begin{itemize}
	\item Examination of the use of ``hidden variables'' in the CE representation
		that can simplify rep, or model shared exogenous information in the
		game (will at least mention this in this paper)
	\item Alternative algorithms?
	\end{itemize}
\end{itemize}
\fi

\section{Background and Preliminaries}

\subsection{Game Theory and Notions of Equilibria}

% MK: we've gotta add little bits like this, I think.
A multiplayer game consists of $n$ players, each with a finite set of
{\em pure strategies\/} or actions available to them, along with a
specification of the {\em payoffs\/} to each player.  Throughout the
paper, we use $A_i$ as a variable representing the chosen action of
player $i$, and $a_i$ as a specific value of $A_i$.  For simplicity we
assume a binary action space, so $a_i \in \{0,1\}$. (The generalization
of our results to the multi-action setting is straightforward.)  The
payoffs to player $i$ are given by a table or matrix $M_i$, indexed by
the joint action $\vec{a} \in \{0,1\}^n$. The value $M_i(\vec{a})$,
which we assume without loss of generality to lie in the interval
$[0,1]$, is the payoff to player $i$ resulting from the
joint action $\vec{a}$. Multiplayer games described in this way are referred to as
{\em normal form\/} games.

A number of different notions of {\em equilibria\/} have been proposed for
normal form games, including {\em Nash equilibria\/} and {\em correlated equilibria\/}.
We begin with the latter because it is more general and our main interest.

Correlated equilibria \cite{aumann74} can be viewed as distributions
$P(\vec{a})$ over joint actions satisfying a certain conditional
expectation property.  Let 
\[
 P|a_i \equiv \Pr_{\vec{A}\sim P}[A_1,...,A_n |
	A_i = a_i]
\]
denote the conditional distribution over actions given the
event that $A_i = a_i$.  Let $\vec{a}[i:b]$ be the vector $\vec{a}$,
but with the $i$th component fixed to $b \in \{0,1\}$.

\begin{definition} 
\label{CEdef}
A {\em correlated equilibrium (CE)\/} for a normal form game is a
distribution $P(\vec{a})$ over actions satisfying
\begin{eqnarray*}
\lefteqn{\forall i \in \{1,...,n\}, \forall a_i,a' \in \{0,1\}:} & & \\
& & \Exp_{\vec{a} \sim P|a_i}[M_i(\vec{a})] 
	\geq \Exp_{\vec{a} \sim P|a_i}[M_i(\vec{a}[i:a'])] 
\end{eqnarray*}
\end{definition}

Intuitively, in a CE the action played by any player is a best response (in
the expected payoff sense) to
the conditional distribution over the other players given that action, and thus
no player has a {\em unilateral\/} incentive to deviate from playing their
role in the CE. Note that a CE may be an arbitrarily complex joint distribution.
In contrast, a {\em Nash equilibrium\/} \cite{nash51} is a special case of CE in
which we demand that $P$ be a product distribution
($P(\vec{a}) =
\prod_{i=1}^n P_i(a_i)$ for some distributions $P_i$),
so every player acts
independently of all others.

Nash equilibria have been extensively studied in the game theory
literature, including in the context of graphical games (defined
shortly). However, as discussed in the Introduction, CE offer a number
of interesting conceptual and computational advantages not shared by
Nash equilibria.  One of the most interesting aspects of CE is that
they broaden the set of ``rational'' solutions for normal form games
without the need to address often difficult issues such as stability
of coalitions and payoff imputations \cite{aumann87}.  The traffic
signal is often cited as an informal everyday example of CE, in which
a single bit of shared information allows a fair split of waiting
times \cite{owen95}. In this example, no player stands to gain
greater payoff by unilaterally deviating from the correlated play, for instance
by ``running a light''.

\subsection{Graphical Games}

In a {\em graphical game\/} \cite{kearns01}, each player $i$ is
represented by a vertex in an undirected\footnote{Undirected graphs
are used for simplicity.  A directed graphical game where each edge
denotes ``$i$ affects the payoff of $j$'' is more complicated but may
result in a sparser graph and further representational savings~\cite{Vickrey02}. The results presented in this paper have natural extentions to directed graphical games.} graph
$G$.  We use $N(i) \subseteq \{1,\ldots,n\}$ to denote the {\em
neighborhood\/} of player $i$ in $G$ --- that is, those vertices $j$
such that the edge $(i,j)$ appears in $G$. By convention $N(i)$ always
includes $i$ itself as well. If $\vec{a}$ is a joint action, we use
$\vec{a}^{~i}$ to denote the induced vector of actions just on the
players in $N(i)$.

\begin{definition} A {\em graphical game\/} is a pair $(G,\matset)$,
where $G$ is an undirected graph over the vertices $\{1,\ldots,n\}$,
and $\matset$ is a set of $n$ {\em local game matrices\/}. For any
joint action $\vec{a}$, the local game matrix $M_i \in \matset$ specifies the payoff
$M_i(\vec{a}^{~i})$ for player $i$, which depends only on the actions
taken by the players in $N(i)$.
\end{definition}

Graphical games are a potentially more compact way of representing
games than standard normal form. In particular, rather than requiring size
exponential in the number of players $n$, a graphical game requires size
exponential only in the size $d$ of the largest local neighborhood. Thus if
$d << n$, the graphical representation is exponentially smaller than the
normal form. Note that we can represent any normal form game as a graphical
game by letting $G$ be the complete graph, but the representation is most
useful when a considerably sparser graph can be found. 

\section{Correlated Equilibria in Graphical Games: Representation}

Specifying a CE as a table of joint probabilities over the binary
actions requires $2^n - 1$ parameters. One might hope that if we have
a compact graphical game then we could also concisely represent the
CE.  Unfortunately, arbitrary high-order correlations might exist in a
CE, even for a concisely represented game
\footnote{For example, the CE of a game always include all mixture
distributions of Nash equilibria, so any game with an exponential
number of Nash equilibria can yield extremely complex CE. Such games
can be easily constructed with very simple graphs.}.

However, we shall show that there is a natural {\em subclass\/} of the
set of all CE, based on {\em expected payoff equivalence\/}, whose
representation size is linearly related to the representation size
of the graphical game. Note that merely finding distributions giving
the same payoffs as the CE is not especially interesting {\em
unless\/} those distributions are themselves CE. In other words, we do
not want to only compactly {\em describe\/} the payoffs achievable
under CE; we want to be able to {\em prescribe\/} CE strategies
(joint distributions) yielding these payoffs.  Our primary tool for accomplishing this goal
will be the notion of local neighborhood equivalence, or the
preservation of local marginal distributions. Below we establish that
local neighborhood equivalence both implies payoff equivalence and
preserves CE.  In the following subsection, we describe how to
represent this natural subclass in a certain {\em Markov network\/},
where the structure of the Markov network is closely related to the
structure of the graphical game.

\subsection{Expected Payoff Equivalence and Local Neighborhood Equivalence}

\begin{definition} 
Two distributions $P$ and $Q$ over joint actions $\vec{a}$ 
are {\em expected payoff equivalent}, denoted $P
\pe Q$, if $P$ and $Q$ yield the same expected payoff vector:
for each $i$, $\Exp_{\vec{a} \sim P}[M_i(\vec{a}^{~i})] = \Exp_{\vec{a}
	\sim Q}[M_i(\vec{a}^{~i})]$.
\end{definition} 

Payoff equivalence of two distributions is, in general, dependent upon
the reward matrices of a graphical game. Let us consider the following
(more stringent) equivalence notion, which is based only on the graph $G$ of a game.

\begin{definition} 
For a graph $G$, two distributions $P$ and $Q$ over joint actions $\vec{a}$ 
are {\em local neighborhood
equivalent\/} with respect to $G$, denoted $P \lne Q$, if for all players $i$,
and for all settings $\vec{a}^{~i}$ of $N(i)$, $P(\vec{a}^{~i}) = Q(\vec{a}^{~i})$.
\end{definition}
In other words, the marginal distributions over all local neighborhoods
defined by $G$ are identical. 
Since the graph is always clear from context, we shall just write $P\lne Q$.
The following lemma establishes that local neighborhood equivalence is
indeed a more stringent notion of equivalence than expected payoff.

\begin{lemma}
For all graphs $G$, for all joint distributions $P$ and $Q$ on 
actions, and for all graphical games with graph $G$, if $P \lne Q$ then $P
\pe Q$. Furthermore, there exists payoff matrices $\matset$ such that
for the graphical game $(G,\matset)$, if $P \not \lne Q$ then $P \not
\pe Q$.
\label{lne-imply-pe}
\end{lemma}

\begin{proof}
The first statement follows from the observation that the expected
payoff to player $i$ depends only on the marginal distribution of
actions in $N(i)$.  To prove the second statement, if $P \not \lne Q$,
then there must exist a player $i$ and a joint action $\vec{a}^{~i}$
for its local neighborhood which has a different probability under $P$
and $Q$. Simply set $M_i(\vec{a}^{~i})=1$ and $M_{i}=0$
elsewhere. Then $i$ has a different payoff under $P$ and $Q$, and so
$P \not \pe Q$.
\qed
\end{proof}

Essentially, local neighborhood equivalence implies payoff
equivalence, but the converse is not true in general (though there
exists some payoff matrices where the converse is correct).

Let $\mathcal{CE}(G,\matset)$ denote the set of of all correlated equilibria
for a graphical game $(G,\matset)$. We now establish that local neighborhood
equivalence also preserves CE. It is important to note that this result
does {\em not\/} hold for expected payoff equivalence.

\begin{lemma}
For any graphical game $(G,\matset)$, if $P \in \mathcal{CE}(G,\matset)$ and $P \lne
	Q$ then $Q \in \mathcal{CE}(G,\matset)$.
\label{ce-lne}
\end{lemma}

\begin{proof}
The lemma follows by noting that the correlated equilibrium
expectation equations are only dependent upon the marginal distributions of 
local neighborhoods, which are preserved in $Q$.
\qed
\end{proof}

While explicitly representing {\em all\/} CE is infeasible even in
simple graphical games, we next show that we 
{\em can\/} concisely
represent, in a single model, all CE {\em up to local neighborhood (and therefore payoff) 
equivalence\/}.  The amount of space required is comparable to that
required to represent the graphical game itself, and allows us to
explore or enumerate the different outcomes achievable in the
space of CE.

\subsection{Correlated Equilibria and Markov Nets}

In the same way that graphical games provide a concise language for
expressing local interaction in game theory, {\em Markov networks\/}
exploit undirected graphs for expressing local interaction in probability
distributions. It turns out that (a special case of) Markov networks
are a natural and powerful language for expressing the CE of 
a graphical game, and that there
is a close relationship between the 
graph of the game and its associated Markov
network graph. We begin with the necessary definitions.

\begin{definition}
A {\em local Markov network\/} is a pair $M \equiv (G, \Psi)$ where
\begin{enumerate}
\item $G$ is an undirected graph on vertices $\{1,\ldots,n\};$
\item $\Psi$ is a set of {\em potential functions\/}, one for each
	local neighborhood $N(i)$, mapping
	binary assignments of values of $N(i)$ to
	the range $[0,\infty):$
	  \[ \Psi \equiv \{ \psi_i: \{\vec{a}^{~i}\} \rightarrow [0,\infty).\} \]
\end{enumerate}
Here $\{\vec{a}^{~i}\}$ is simply the set of all $2^{|N(i)|}$ settings to $N(i)$.
\end{definition}

A local Markov network $M$ compactly represents a probability distribution
$P_M$ as follows.  For any binary assignment $\vec{a}$ to the vertices, define
\[
P_M(\vec{a}) \equiv \frac{1}{Z}\left(\prod_{i=1}^n
	\psi_i(\vec{a}^{~i})\right)
\]
where $Z = \sum_{\vec{a}} \prod_{i=1}^n \psi_i(\vec{a}^{~i}) > 0$ is the
normalization factor. 

Note that any joint distribution can be represented as a local Markov
network on a sufficiently dense graph. (Note that if we let $G$ be the
complete graph then we simply have a single potential function
over the entire joint action space $\vec{a}$.) 
However, if $d$ is the size of
the maximal neighborhood in $G$, then the representation size of a
distribution in this network is $O(n 2^d)$, a considerable savings
over a tabular representation if $d << n$.

Local Markov networks are a special case of Markov networks, a
well-studied probabilistic model in AI and statistics
\cite{pearl88}.  A Markov network is typically defined with
potential functions ranging over settings of maximal cliques in the
graphs. Another approach we could have taken is to transform the graph
$G$ to a graph $G'$ which forms cliques of the local neighborhoods
$N(i)$, and then used standard Markov networks over $G'$ as opposed to
local Markov networks over $G$.  However,
this can sometimes result in an unnecessary exponential blow-up of the
size of the model when the resulting maximal cliques are much larger
than the original neighborhoods. As the following lemma shows, for our
purposes, it is sufficient to define the potential functions over just
local neighborhoods (as in our definition) rather than maximal cliques
in $G'$, which avoids this potential blow-up. (However, we
will sometimes find it useful to discuss $G'$ at various points when
connecting with the Markov network literature.)

The following technical lemma, which is the cornerstone of our first
main theorem below, establishes that a local Markov network always suffices
to represent a distribution up to local neighborhood equivalence.

\begin{lemma}
For all graphs $G$, and for all joint distributions $P$ over joint actions,
there exists a distribution $Q$ that is representable as a
local Markov network with graph $G$ such that $Q \lne P$ with respect
to $G$.
\label{mn-lne}
\end{lemma}

The proof is provided in the appendix. The main result of this section
now follows from the previous lemmas, and shows that we can represent
any correlated equilibria of a graphical game $(G,\matset)$, up to
payoff equivalence, with a local Markov network $(G,\Psi)$.

\begin{theorem} 
\label{CERep}
(CE Representation Theorem) For all graphical games $(G,\matset)$, and for
all distributions $P \in \mathcal{CE}(G,\matset)$, there exists a
distribution $Q$ such that:
\begin{enumerate}
	\item $Q \in \mathcal{CE}(G,\matset)$;
	\item $Q \pe P$;
	\item $Q$ can be represented as a local Markov network
		with graph $G$.
\end{enumerate}
\end{theorem}

Note that the representation size for any local Markov network with graph $G$
is linear in the representation size of the graphical game, and thus
we can represent the CE of the game parsimoniously.

\section{Correlated Equilibria in Graphical Games: Algorithms}

Having established in Theorem~\ref{CERep} that a concise graphical game yields
a concise representation of its CE up to payoff equivalence, we now turn our
attention to algorithms for {\em computing\/} CE. In the
spirit of our results thus far, we are interested in algorithms that can
efficiently exploit the compactness of graphical games.

It is well-known that it is possible to compute CE via linear
programming in time polynomial in the standard {\em non-compact\/}
normal form.  In this approach, one variable is introduced for every
possible joint action probability $P(\vec{a})$, and the constraints enforce both the CE
condition and the fact that the variables must define a 
probability distribution. It is not hard to verify that the
constraints are all linear and there are $O(2^n)$ variables and
constraints in the binary action case.  By introducing any linear
optimization function, one can get an algorithm based on linear
programming for computing a single exact CE that runs in time
polynomial in the size of the normal-form representation of the game
(that is, polynomial in $2^n$).

For graphical games this solution is clearly unsatisfying, since it
may require time exponential in the size of the graphical game.  What
is needed is a more concise way to express the CE and distributional
constraints --- ideally, linearly in the size of the graphical
game representation. We shall show that this is indeed possible for
tree graphical games (and more generally for game graphs $G$ where a
Markov network on the graph $G'$ --- obtained by forming cliques of
the neighborhoods of $G$ --- can be represented by a local
Markov network on $G$ and $G'$ is chordal). The basic idea is to express both the CE and
distributional constraints entirely in terms of the local marginals,
rather than the global probabilities of joint actions.
We begin with a lemma establishing that doing so for the CE
constraints is straightforward. 
% Let $P(\vec{a}^{~i})$ denote the
% marginal distribution $\Pr_{\vec{a}\sim P}[\vec{a}^{~i}]$.

\begin{lemma} 
\label{CE-local}
For all graphical games $(G, \matset)$, and for all action distributions
$P$, $P \in \mathcal{CE}(G,\matset)$ if and only if for all players i
and actions $a, a'$:
\[
\sum _{\vec{a}^{~i} : {a}^{i}_{i} = a}
	P(\vec{a}^{~i})M_{i}(\vec{a}^{~i})\geq 
	\sum _{\vec{a}^{~i} :
	{a}^{i}_{i} = a} P(\vec{a}^{~i})M_{i}(\vec{a}^{~i}[i:a']).
\]
\end{lemma}
\begin{proof}
Due to the locality of the $M_{i}$, the CE constraint
condition (Definition~\ref{CEdef}) simplifies to using only local
expectations: 
\[
E_{\vec{a} \sim P|a_i=a} M_i(\vec{a}) = E_{\vec{a}^{~i} \sim P(\vec{a}^{~i}|a_i=a)} M_i(\vec{a}^{~i})
\]
Since $P(a_i=a)$ is a constant, we can multiply this on both sides of
the equation and prove the ``if'' direction.  For the ``only if''
direction, reverse the derivation. \qed
\end{proof}

Furthermore, for the case in which the game graph is a tree, it
suffices to introduce linear distributional constraints over only the
local marginals, along with {\em consistency\/} constraints on the
{\em intersections\/} of local marginals. We thus have the following
three categories of local constraints defining our linear
program:\\

\noindent
{\bf Variables:\/} For every player $i$ and every
assignment $\vec{a}^{~i}$, there is a variable $P_i(\vec{a}^{~i})$.\\
{\bf LP Constraints:}
\begin{enumerate}
\item {\em CE Constraints:\/} for all players $i$ and actions $a, a'$,
\[
\sum _{\vec{a}^{~i} : {a}^{i}_{i} = a}
	P_i(\vec{a}^{~i})M_{i}(\vec{a}^{~i})\geq 
	\sum _{\vec{a}^{~i} :
	{a}^{i}_{i} = a} P_i(\vec{a}^{~i})M_{i}([\vec{a}^{~i}[i:a'])
\]
\item {\em Neighborhood Marginal Constraints:\/} for all players $i$,
\[
\forall \vec{a}^{~i}: \,\,\, P_i(\vec{a}^{~i}) \geq 0; \,\,\, 
\sum_{\vec{a}^{~i}} P_i(\vec{a}^{~i}) = 1
\]
\item {\em Intersection Consistency Constraints:\/} 
for all players $i$ and $j$, and for any assignment $\vec{y}^{~ij}$ to 
the {\em intersection neighborhood\/} $N(i) \cap N(j)$,
\begin{eqnarray*}
P_i(\vec{a}^{~ij}) & \equiv & \sum_{\vec{a}^{~i}: \vec{a}^{~ij} = \vec{y}^{~ij}}
	P_i(\vec{a}^{~i}) \\
	& = &
	\sum_{\vec{a}^{~j}: \vec{a}^{~ij} = \vec{y}^{~ij}}
	P_j(\vec{a}^{~j})\\
	& \equiv & P_j(\vec{a}^{~ij}) 
\end{eqnarray*}
\end{enumerate}
Choices for the objective function are discussed below.

Note that if $d$ is the size of the largest neighborhood, this system
involves $O(n 2^d)$ variables and $O(n 2^d)$ linear inequalities,
which is linear in the representation size of the original graphical
game, as desired.

It is clear that any 
CE must satisfy these constraints. Here we must solve the inverse problem:
given only a set of marginal assignments
$\{P_i(\vec{a}^{~i})\}$ satisfying the constraints, we would like to
construct a CE. Of course, by Lemma~\ref{CE-local}, if we can find
a distribution $Q$ whose marginals match the assignments
($\forall i,
\forall \vec{a}^{~i}, Q(\vec{a}^{~i}) = P_i(\vec{a}^{~i})$),
then $Q$ must be a CE. In general finding such a $Q$ may be a
difficult problem (and may have no solution), but for tree graphical
games, it turns out that any solution to the constraints yields a
unique joint distribution that can be represented in a the local Markov
network. The following lemma states this.

\begin{lemma}(Consistent Tree) 
\label{lem:ct}
For all graphical games $(G,\matset)$ in which $G=(V,E)$ is a tree, and for
all assignments $\{ P_i(\vec{a}^{~i}) \}$ satisfying the consistency
equations, there is a unique joint distribution $Q$, defined by 
\begin{equation}
\label{decomp-dist}
% \Pr_{\vec{a} \sim Q}[\vec{a}] 
Q(\vec{a})
\equiv \frac{\prod_{i\in V}
P_i(\vec{a}^{~i})}{\prod_{(i,j)\in E; i < j } P_i(\vec{a}^{~ij}) }
\end{equation}
such that 
$Q \in \mathcal{CE}(G,\matset)$ and
$Q$ is representable as a local Markov network with graph
$G$. Furthermore, the marginals of $Q$ will be consistent with the assignment:
$\forall
i, \vec{a}^{~i}, 
% \Pr_{\vec{a} \sim Q}[\vec{a}^{~i}] =
Q_i(\vec{a}^{~i}) =
P_i(\vec{a}^{~i})$.
\end{lemma}

% Note that when $N(i) \cap N(j)$ is the empty set, $P_i(\vec{a}^{~ij}) = 1$.

\begin{proof} 
Given the graph $G = (V,E)$, we construct a graph $G' = (V,E')$ where
$E' = \{(i,j) : \exists k \in V: i\neq j,\{i,j\} \subseteq N(k)\}.$ Thus, $G'$
has a clique for each local neighborhood in $G$.  $G'$ is a chordal
graph\footnote{A chord is an edge which connects two nonadjacent nodes
in a cycle.  A chordal graph is an undirected graph where every cycle
larger than 3 has a chord.} and every maximal clique $C \in G'$ is a
subset of some neighborhood ($\exists i:\,\,\,C \subseteq N(i)$). From
this, Theorem 2.6 of~\cite{DawidandLauritzen93} implies that the
joint distribution $Q$ is unique, consistent and is representable by a local
Markov network with graph $G$.

To see that $Q \in \mathcal{CE}(G,\matset)$, note that $\forall i,
\vec{a}^{~i}, 
% \Pr_{\vec{a} \sim Q}[\vec{a}^{~i}] = P_i(\vec{a}^{~i})$
Q(\vec{a}^{~i}) = P_i(\vec{a}^{~i})$
implies that the correlated equilibrium constraints hold for $Q$. \qed
\end{proof}

This result allows us to keep the number of constraints linear in the
graphical game size, and an efficient LP algorithm emerges.  Before
presenting this algorithm, we note that for trees, we have compactly
specified the convex polytope of {\em all\/} CE up to local
neighborhood (and therefore payoff) equivalence. Let
$\mathcal{CE}_{local}(G,\matset)$ be the set of all distributions $Q$:
\[
Q(\vec{a}) \equiv 
	\frac{\prod_{i\in V} P_i(\vec{a}^{~i})}{\prod_{(i,j)\in E; i < j} P_i(\vec{a}^{~ij}) }
\]
obtained by ranging over all
solutions $\{ P_i(\vec{a}^{~i}) \}$ to the consistency constraints.
The following theorem shows that this set is expected
payoff equivalent to $\mathcal{CE}(G,\matset)$.

\begin{theorem} 
(Completeness) For all graphical games $(G,\matset)$ such that $G$ is
a tree, we have $\mathcal{CE}_{local}(G,\matset) \subseteq
\mathcal{CE}(G,\matset)$; and if $P
\in \mathcal{CE}(G,\matset)$ then there exists a $Q \in
\mathcal{CE}_{local}(G,\matset)$ such that $P \pe Q$.
\end{theorem}

\begin{proof}
Lemma \ref{lem:ct} gives us $\mathcal{CE}_{local}(G,\matset) \subseteq
\mathcal{CE}(G,\matset)$.
The remainder of the proof is constructive.  Given $P$, first define:
\[
% Q_i(\vec{a}^{~i}) \equiv \Pr_{\vec{a} \sim P} ( \vec{a}^{~i})
Q_i(\vec{a}^{~i}) \equiv P( \vec{a}^{~i})
\]
then construct $Q$ using Equation \ref{decomp-dist}.  By construction,
we have $Q \in \mathcal{CE}_{local}(G,\matset)$ and $P \pe Q$ holds
by Lemma~\ref{lem:ct}. 
\qed
\end{proof}


Finally, to define a concrete LP algorithm we must simply
specify an appropriate linear optimization function.  
One possibility is choosing a correlated equilibrium with the
highest total expected payoff over all players:
\[
\max_{\textrm{subject to the constraints on }
	 P_i(\vec{a}^{~i})} \sum_i \sum _{\vec{a}^{~i}}
	 P_i(\vec{a}^{~i})M_{i}(\vec{a}^{~i}).
\]

Our main algorithmic result follows.

\begin{theorem}
\label{thm:time}
(Efficient Tree Algorithm) For all tree graphical games $(G,\matset)$ and all
linear objective functions $F(\{ P_i(\vec{a}^{~i}) \})$, linear programming
computes a CE in time polynomial in the size of the graphical game. The
CE computed can be varied by varying the objective function $F$.
\end{theorem}

Hence, the algorithm is polynomial in $n$ and exponential in $d$ for
trees. For the multiple action setting, it is straightforward to see that
the previous complexity result still holds.

\section{Discussion and Extensions}

While Theorem~\ref{thm:time} establishes that we can efficiently
compute different CE by varying the chosen linear optimization
function, an even more powerful result follows by combining the
convexity of the class $\mathcal{CE}_{local}(G,\matset)$ with the
results of \cite{dyer91}, who provide an efficient algorithm for
sampling nearly uniformly from an arbitrary convex body. 
This yields a method for sampling CE in
$\mathcal{CE}_{local}(G,\matset)$ nearly uniformly in time polynomial
in the size of a tree graphical game.  
\iffalse
Such a sampling method is
useful in enumerating many different CE, which might be desirable if
we wish to generate CE that are not Nash equilibria.
\fi

An important advantage of the Markov net formalism for representing CE
(that we will elaborate on in
future work) is the ability to immediately infer various conditional
independences and probabilistic semantics from the graph alone. Indeed,
this is perhaps the main power of graphical models for probabilistic
inference, and the results presented here import that power into the
domain of game theory. As just one example, let $G$ be the graph of the
game, and $G'$ be the graph obtained by forming cliques of local
neighborhoods in $G$. Let $i$ and $j$ be any two players in the game,
and let $S$ be any set of players forming a cut of $G'$ such that $i$
and $j$ lie in different components. Then classical Markov net semantics,
combined with our results, establish that for any CE, there exists
a local neighborhood equivalent CE in which the distribution on $a_i$
is independent of $a_j$ given the actions in $S$. In other words, the
Markov net derived from the game graph allows us to easily ``read off''
which conditional dependencies are essential, and which are spurious,
in representing all CE. We expect that many other interesting and
powerful interactions between the strategic and probabilistic
aspects of CE will emerge with further study. 

\section{Acknowledgements}

We give warm thanks to Dean Foster for numerous helpful discussions,
and to Stuart Geman for his help with the proof of Lemma 3.

\bibliography{games}

\section{Appendix}

{\bf Proof of Lemma~\ref{mn-lne}:}
The objective is to find a single distribution $Q$ that is consistent
with the players local neighborhood  marginals under $P$ and
is also a Markov network with graph $G$. It is an immediate
consequence of previous work on maximum entropy models
(see~\cite{Bergeretal96}) that the maximum entropy distribution $Q^{*}$, subject
to $P \lne Q^{*}$, is a local Markov network.

More formally, we show that the solution to the following constrained
maximum entropy problem is representable in $G$:
\[
Q^* = \argmax_Q H(Q) \equiv \argmax_Q \sum_{\vec{a}} Q(\vec{a}) \log(1/Q(\vec{a}))
\]
subject to
\begin{enumerate}
\item $Q(\vec{a}^{~i}) = P(\vec{a}^{~i})$, for all $i, \vec{a}^{~i}$.
\item $Q$ is a proper probability distribution.
\end{enumerate}
Note first that this problem always has a unique answer since $H(Q)$
is strictly concave and all constraints are linear. In addition, the
feasible set is non-empty, as it contains $P$ itself.

To get the form of $Q^*$, we solve the optimization problem by
introducing the Lagrange multipliers $\vec{\lambda} \equiv
(\lambda_{i,\vec{a}^{~i}}, \forall i, \vec{a}^{~i})$ to take care of
the neighborhood marginal constraints (condition 1), and $\beta$ to
take care of the normalization constraint (condition 2). The
optimization becomes
\begin{eqnarray*}
Q^* &=& \argmax_{Q,\vec{\lambda},\beta} L(Q,\vec{\lambda},\beta)\\
    &\equiv& \argmax_{Q,\vec{\lambda},\beta} H(Q) + 
		\sum_{i \in V} \sum_{\vec{a}^{~i}} \lambda_{i,\vec{a}^{~i}} (Q(\vec{a}^{~i}) - P(\vec{a}^{~i})) \\
    & & \hspace{0.25in} + \beta (\sum_{\vec{a}}  Q(\vec{a}) - 1)
\end{eqnarray*}
where $Q(\vec{a})$ is constrained to be positive. Here, $L$ is the
Lagrangian function.

First note that for all $\vec{a}$, if $P(\vec{a}) = 0$, then
$Q^*(\vec{a}) = 0$. A necessary condition for $Q^*$ is that $\partial
L/\partial Q(\vec{a})|_{Q = Q^*} = 0$, for all $\vec{a}$ such that $P(\vec{a}) >
0$.  After taking derivatives and some algebra, this condition
implies, for all $\vec{a}$,
\[
Q^{*}_{\vec{\lambda}}(\vec{a}) = (1/Z_{\vec{\lambda}}) \prod_{v=1}^n
I[P(\vec{a}^{~i}) \neq 0] \exp(\lambda_{i,\vec{a}^{~i}})
\]
where $I[P(\vec{a}^{~i}) \neq 0]$ is an indicator function which
evaluates to $1$ iff $P(\vec{a}^{~i}) \neq 0$. We use the subscript
$\vec{\lambda}$ on $Q^{*}_{\vec{\lambda}}$ and $Z_{\vec{\lambda}}$ to
explicitly denote they are parameterized by the Lagrange
multipliers. 

It is important to note at this point that regardless of the value of
the Lagrange multipliers, each $\lambda_{i,\vec{a}^{~i}}$ is only a
function of the $\vec{a}^{~i}$s (that are consistent with
$\vec{a}$). Let the dual function $F(\vec{\lambda}) \equiv
L(Q^{*}_{\vec{\lambda}}(\vec{a}),
\vec{\lambda},0)$, and let $\vec{\lambda}^{*}$ maximize this function.
Note that those $\lambda_{i,\vec{a}^{~i}}$ that correspond to
$P(\vec{a}^{~i}) = 0$ are irrelevant parameters since
$F(\vec{\lambda})$ is independent of them.  So for all $i$ and
$\vec{a}^{~i}$ such that $P(\vec{a}^{~i}) = 0$, we set
$\lambda^{*}_{i,\vec{a}^{~i}} = 0$.  For all $i, \vec{a}^{~i}$, we
define the functions $\psi^*_i(\vec{a}^{~i}) \equiv I[P(\vec{a}^{~i})
\neq 0]
\exp(\lambda^*_{i,\vec{a}^{~i}})$. Hence, we can express the maximum
entropy distribution $Q^*$ as, for all $\vec{a}$,
\[
Q^{*}_{\vec{\lambda}^{*}} = (1/Z_{\vec{\lambda}^*}) \prod_{i=1}^n
\psi^*_i(\vec{a}^{~i})
\]
which completes the proof. \qed


\end{document}

\begin{thebibliography}{16}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{{\tt #1}}\fi

\bibitem[Aumann(1974)]{aumann74}
R.J. Aumann.
\newblock Subjectivity and correlation in randomized strategies.
\newblock {\em Journal of Mathematical Economics}, 1, 1974.

\bibitem[Aumann(1987)]{aumann87}
R.J. Aumann.
\newblock Correlated equilibrium as an expression of {B}ayesian rationality.
\newblock {\em Econometrica}, 55, 1987.

\bibitem[Berger et~al.(1996)Berger, Pietra, and Pietra]{Bergeretal96}
A.~Berger, S.~Della Pietra, and V.~Della Pietra.
\newblock A maximum entropy approach to natural language processing.
\newblock {\em Computational Linguistics}, 22\penalty0 (1), March 1996.

\bibitem[Dawid and Lauritzen(1993)]{DawidandLauritzen93}
A.~P. Dawid and S.~L. Lauritzen.
\newblock Hyper {M}arkov laws in the statistical analysis of decomposable
  graphical models.
\newblock {\em The Annals of Statistics}, 21\penalty0 (3):\penalty0 1271--1317,
  September 1993.

\bibitem[Dyer et~al.(1991)Dyer, Frieze, and Kannan]{dyer91}
M.~Dyer, A.~Frieze, and R.~Kannan.
\newblock A random polynomial time algorithm for approximating the volume of a
  convex body.
\newblock {\em JACM}, 38\penalty0 (1):\penalty0 1--17, 1991.

\bibitem[Foster and Vohra(1997)]{foster97}
D.~Foster and R.~Vohra.
\newblock Calibrated learning and correlated equilibrium.
\newblock {\em Games and Economic Behavior}, 1997.

\bibitem[Foster and Vohra(1999)]{foster99}
D.~Foster and R.~Vohra.
\newblock Regret in the on-line decision problem.
\newblock {\em Games and Economic Behavior}, pages 7 -- 36, 1999.

\bibitem[Kearns et~al.(2001)Kearns, Littman, and Singh]{kearns01}
M.~Kearns, M.~Littman, and S.~Singh.
\newblock Graphical models for game theory.
\newblock In {\em Proceedings of the Conference on Uncertainty in Artificial
  Intelligence}, pages 253--260, 2001.

\bibitem[Koller and Milch()]{koller01}
Daphne Koller and Brian Milch.
\newblock Multi-agent influence diagrams for representing and solving games.
\newblock {\em Games and Economic Behavior}.
\newblock To appear.

\bibitem[{La Mura}(2000)]{lamura00}
P.~{La Mura}.
\newblock Game networks.
\newblock In {\em Proceedings of the 16th Conference on Uncertainty in
  Artificial Intelligence (UAI)}, pages 335--342, 2000.

\bibitem[Littman et~al.(2002)Littman, Kearns, and Singh]{littman02}
M.~Littman, M.~Kearns, and S.~Singh.
\newblock An efficient exact algorithm for singly connected graphical games.
\newblock In {\em Neural Information Processing Systems}, 2002.

\bibitem[Nash(1951)]{nash51}
J.~F. Nash.
\newblock Non-cooperative games.
\newblock {\em Annals of Mathematics}, 54:\penalty0 286--295, 1951.

\bibitem[Ortiz and Kearns(2003)]{ortiz03}
L.~Ortiz and M.~Kearns.
\newblock Nash propagation for loopy graphical games.
\newblock In {\em Neural Information Processing Systems}, 2003.
\newblock To appear.

\bibitem[Owen(1995)]{owen95}
G.~Owen.
\newblock {\em Game Theory}.
\newblock Academic Press, UK, 1995.

\bibitem[Pearl(1988)]{pearl88}
J.~Pearl.
\newblock {\em Probabilistic Reasoning in Intelligent Systems}.
\newblock Morgan Kaufmann, 1988.

\bibitem[Vickrey and Koller(2002)]{Vickrey02}
D.~Vickrey and D.~Koller.
\newblock Multi-agent algorithms for solving graphical games.
\newblock In {\em Proceedings of the National Conference on Artificial
  Intelligence (AAAI)}, 2002.

\end{thebibliography}
