Multidimension: a dimensionality extension of simple games

In voting theory and social choice theory, decision systems can be represented as simple games, i.e., cooperative games defined through their players or voters and their set of winning coalitions. The weighted voting games form a well-known strict subclass of simple games, where each player has a voting weight so that a coalition wins if the sum of weights of their members exceeds a given quota. Since the number of winning coalitions can be exponential in the number of players, simple games can be represented much more compactly as intersections or unions of weighted voting games. A simple game’s dimension (codimension) is the minimum number of weighted voting games such that their intersection (union) is the given game. It is known there are voting systems with a high (co)dimension. This work introduces the multidimension as the minimum size of an expression with intersections and unions on weighted voting games necessary to obtain the considered simple game. We generalize this notion to subclasses of weighted voting games and analyze the generative properties of these subclasses. We also characterize the simple games with finite generalized multidimension over the set of weighted voting games without dummy players. We provide a comprehensive classification for simple games up to a certain number of players. These results complement similar classification results for generalized (co)dimensions. Our results show how generalized multidimension allows representing more simple games and more compactly, even for a small number of players and for subclasses.
"Xavier Molinero was partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) and the European Union (FEDER funds) [PID2019-104987GB-I00, JUVOCO]. Fabián Riquelme was supported by the Fondecyt de Iniciación 11200113 from ANID, Chile. Maria Serna was partially supported by the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION]. Xavier Molinero, Salvador Roura, and Maria Serna were also partially supported by the Catalan government [2021 SGR 01419 ALBCOM]"
Peer Reviewed
Postprint (published version)