AAAI08-275.pdf

AAAI Conferences

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 noneffective (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.



Using Reasoning Patterns to Helps Humans Solve Complex Games

AAAI Conferences

We propose a novel method for helping humans make good decisions in complex games, for which common equilibrium solutions may be too difficult to compute or not relevant. Our method leverages and augments humans' natural use of arguments in the decision making process. We believe that, if computers were capable of generating similar arguments from the mathematical description of a game, and presented those to a human decision maker, the synergies would result in better performance overall. The theory of reasoning patterns naturally lends itself to such a use. We use reasoning patterns to derive localized evaluation functions for each decision in a game, then present their output to humans. We have implemented this approach in a repeated principal-agent game, and used it to generate advice given to subjects. Experimental results show that humans who received advice performed better than those who did not.



Networks of Influence Diagrams: A Formalism for Representing Agents ' Beliefs and Decision-Making Processes

AAAI Conferences

This paper presents Networks of Influence Diagrams (NID), a compact, natural and highly expressive language for reasoning about agents' beliefs and decision-making processes. NIDs are graphical structures in which agents' mental models are represented as nodes in a network; a mental model for an agent may itself use descriptions of the mental models of other agents. NIDs are demonstrated by examples, showing how they can be used to describe conflicting and cyclic belief structures, and certain forms of bounded rationality. In an opponent modeling domain, NIDs were able to outperform other computational agents whose strategies were not known in advance. NIDs are equivalent in representation to Bayesian games but they are more compact and structured than this formalism. In particular, the equilibrium definition for NIDs makes an explicit distinction between agents' optimal strategies, and how they actually behave in reality.