An Unbiased Rational Decision Making Procedure for Multiple-Adversary Environments

Anat Hashavit (M.Sc. Thesis Seminar)

Wednesday, 24.08.2011, 13:00

Taub 601

Advisor: Prof. S. Markovitch

In binary-utility games, an agent can have only two possible utility values for final
states, 1 (win) and 0 (lose). We define an unbiased rational agent as one that seeks to
maximize its utility value, but is equally likely to choose between states with the same
utility value. In particular, it will prefer winning over losing but will be indifferent as to
which winning ( or losing state) is chosen. This induces a probability distribution over the
game tree, from which an agent can infer its probability to win. A single adversary binary
game is one where there are only two possible outcomes, so that the winning probabilities
remain binary values. In this case, the rational action for an agent is to play minimax.
In this work we focus on the more complex, multiple-adversary environment, where an
agent is met with at least two adversaries. We propose a new algorithmic framework where
agents try to maximize their winning probabilities. We begin by theoretically analyzing
why an unbiased rational agent should take our approach in an unbounded environment
and not that of the existing Paranoid or MaxN algorithms. We then expand our framework
to a resource-bounded environment, where winning probabilities are estimated, and show
empirical results supporting our claims.