| Speaker: Arkadii Slinko Affiliation: Department of Mathematics Time: 4:00 pm Monday, 16 May, 2016 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 exponential in the number of players. We discuss the drawback of the concept of dimension and look at existing alternatives. This is a joint paper with Liam O’Dwyer. Last week it was presented at CoopMAS workshop and got the best paper award. |