The Taub Faculty of Computer Science Events and Talks

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.