File(s) stored somewhere else
Please note: Linked content is NOT stored on Carnegie Mellon University and we can't guarantee its availability, quality, security or accept any liability.
Factoring Games to Isolate Strategic Interactions
journal contribution
posted on 2007-01-01, 00:00 authored by George B. Davis, Michael Benisch, Kathleen CarleyKathleen Carley, Norman SadehGame theoretic reasoning about multi-agent systems has been made more tractable by algorithms
that exploit various types of independence in agents’ utilities. However, previous work has assumed
that a game’s precise independence structure is given in advance. This paper addresses the
problem of finding independence structure in a general form game when it is not known ahead of
time, or of finding an approximation when full independence does not exist. We give an expected
polynomial time algorithm to divide a bounded-payout normal form game into factor games that
isolate independent strategic interactions. We also show that the best approximate factoring can
be found in polynomial time for a specific interaction that is not fully independent. Once known,
factors aide computation of game theoretic solution concepts, including Nash equilibria (or ǫequilibria
for approximate factors), in some cases guaranteeing polynomial complexity where previous
bounds were exponential.