Rational decision making in a multiple-adversary environment
Anat Hashavit and Shaul Markovitch
In binary-utility games, an agent can have only two possible utility values for final states, 1 (win) and 0 (loose). An adversarial binary game is one where for each final state there must be at least one winning and one loosing agent. In such games, a rational agent obviously prefers wining states over loosing states, but is equally likely to choose between winning (or loosing) states. This induces a probability distribution over the game tree, from which an agent can infer its probability to win. In a single-adversary binary game there are only two possible outcomes and so the winning probabilities remain binary values. In this case, playing minimax is the rational way an agent should act. 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 a theoretical analysis which explains why our approach is the way a rational agent should act in an unbounded environment, and not the existing Paranoid or MaxN algorithms. We continue by expanding our framework to a resource-bounded environment, where winning probabilities are estimated, and show empirical results supporting our claims.