
CMUISRI06121
Institute for Software Research
School of Computer Science, Carnegie Mellon University
CMUISRI06121
Factoring Games to Isolate Strategic Interactions
George B. Davis, Michael Benisch,
Kathleen M. Carley, Norman M. Sadeh
September 2006
CMUISRI06121.pdf
Keywords: Strategically aware technology, strategic network
formation, computational game theory
Some systems of selfinterested agents (i.e. games) contain incentive
structures that could allow agents to assemble a strategy from several
independent or nearly independent decisions, rather than considering the
entire game at once. We present an algebra, distinct from previous compact
game representations, which captures this by reinterpreting any normal
form game as the result of a product operation on factor
games. Factor
games isolate independent strategic interactions, in that
actions taken in one do not affect outcomes of the others. We give a
polynomial expected time algorithm to discover all factors of a game
with bounded payouts, and prove that a variety of solution concepts,
including Nash equilibrium, can be computed on factors and easily
reconstituted for the product.
In some games, this independence structure may occur only approximately.
We therefore define an approximate compact form, epsilonfactoring, which
isolates strategic interactions that are nearly independent. The
product of Nash equilibria in εfactors is an εequilibria
in the approximated game. Finding the εfactoring that isolates
a specific interaction with minimal ε characterizes the cost
of reasoning about it independently.
20 pages
