2016/05/17 by Liam O’Dwyer, Arkadii Slinko, O'Dwyer, Liam +1
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Artificial Intelligence in Games #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Sports Analytics and Performance
paper · pdf · doi:10.48550/arxiv.1605.05114
openalex publication_date 2016/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The concept of dimension in simple games was introduced as a measure of the remoteness of a given game from a weighted game. Taylor and Zwicker (1993) demonstrated that the dimension of a simple game can grow exponentially in the number of players. However, the problem of worst-case growth of the dimension in complete games was left open. Freixas and Puente (2008) showed that complete games of arbitrary dimension exist and, in particular, their examples demonstrate that the worst-case growth of dimension in complete games is at least linear. In this paper, using a novel technique of Kurz and Napel (2016), we demonstrate that the worst-case growth of dimension in complete simple games is exponential in the number of players.