The traditional representations of games using the extensive form or the
strategic (normal) form obscure much of the structure that is present in
real-world games.  In this paper, we propose a new representation language
for general multi-player games --- <I>multi-agent influence diagrams
(MAIDs)</I>.  This representation extends graphical models for probability
distributions to a multi-agent decision-making context.  MAIDs explicitly
encode structure involving the dependence relationships among variables.  As
a consequence, we can define a notion of <I>strategic relevance</I> of one
decision variable to another: <I>D'</I> is <I>strategically relevant</I> to
<I>D</I> if, to optimize the decision rule at <I>D</I>, the decision maker
needs to take into consideration the decision rule at <I>D'</I>.  We provide
a sound and complete graphical criterion for determining strategic
relevance.  We then show how strategic relevance can be used to detect
structure in games, allowing a large game to be broken up into a set of
interacting smaller games, which can be solved in sequence.  We show that
this decomposition can lead to substantial savings in the computational cost
of finding Nash equilibria in these games.
<p>