Speaker: Arkadii Slinko
Affiliation: Department of Mathematics
Title: Growth of dimension in complete simple games
Date: Monday, 16 May 2016
Time: 4:00 pm
Location: Clock Tower 032

Simple games are used to model a wide range of situations from decision making in committees to reliability of systems made from unreliable components and McCulloch-Pitts units in threshold logic. Weighted voting games are a natural and practically important class of simple games, in which each agent is assigned a numerical weight, and a coalition is winning if the sum of weights of agents in that coalition achieves a certain threshold.

The concept of dimension in simple games was introduced by Taylor and Zwicker in 1993 as a measure of remoteness of a given simple game from a weighted game. They 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 the important class of 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 (2015), we demonstrate that the worst-case growth of dimension in complete games is at least polynomial in the number of players. Whether or not it can be exponential remains an open question.

This is a joint paper with Liam O’Dwyer.

Everyone welcome!