Some systems of self-interested 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, epsilon-factoring, 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

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu