Using Reasoning Patterns to Simplify Games

Dimitrios Antos, Avi Pfeffer

In complex strategic situations decision-making agents interact with many other agents and have access to many pieces of information throughout their play. This usually leads to game solving being a very complex, almost intractable procedure. Moreover, algorithms for solving games usually fail to explain how the various equilibria come about and how ``plausible" they are. Reasoning patterns try to capture the strategic thinking of agents and formalize the usage of the various information or evidence they obtain during their interactions. Identifying reasoning patterns can lead to a significant refinement over the full range of equilibria, as well as considerable computational savings in solving the game. Here we present a polynomial-time algorithm that simplifies the original game by iteratively identifying non-effective (ignorable) decision nodes and removing redundant information edges. In some cases, this can lead to exponential-time savings in computing an equilibrium, yet some -potentially efficient- equilibria may be lost in the process.

Subjects: 3.4 Probabilistic Reasoning; 15.5 Decision Theory

Submitted: Apr 2, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.