M.Sc Thesis
M.Sc Student Hashavit Anat Unbiased Rational Decision Making in Multiple-Adversary Environments Department of Computer Science Professor Shaul Markovitch

Abstract

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 prefers winning over losing but is 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 with unbounded resources should take our approach and not that of the existing Paranoid or MaxN algorithms. We then expand our framework to a resource-bounded

agent, where winning probabilities are estimated using both manual and machine learning techniques, and show empirical results supporting our claims.