Scientific Publications Database

Article Title: Optimal Risk in Multiagent Blind Tournaments
Authors: Perkins, Theodore J.
Journal: AAMAS '19: PROCEEDINGS OF THE 18TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS Volume
Date of Publication:2019
Abstract:
In multiagent blind tournaments, many agents compete at an individual game, unaware of the performance of the other agents. When all agents have completed their games, the agent with the best performance-for example, the highest score, or greatest distance, or fastest time-wins the tournament. In stochastic games, an obvious and time honoured strategy is to maximize expected performance. In tournaments with many agents, however, the top scores may be far above the expected score. As a result, maximizing expected score is not the same as maximizing the chance of winning the tournament. Rather, a riskier strategy, which increases the chance of obtaining a top score while possibly sacrificing some expected score, may offer a better chance of winning. In this paper, we study how an agent should optimally adapt its strategy based on the size of the tournament in which it is competing. Our solution involves first approximating the agent's pool of opponents as a collection of known or estimated strategies. Second, score distributions are computed for those strategies, and the distributions are convolved to obtain a distribution for the maximum score of the agent's opponents. Finally, a strategy that maximizes the chance of exceeding the opponents' scores is computed. As a demonstration, we study optimal tournament-size adaptation in online Yahtzee tournaments involving as few as one and as many as ten thousand opponents. We find that strategies change dramatically over that range of tournament sizes, and that in large tournaments, an agent adopting the optimally risky strategy can nearly double its chance of winning.