Multidimension: a dimensionality extension of simple games
Open Access
- 20 October 2023
- journal article
- research article
- Published by Springer Nature in Computational and Applied Mathematics
- Vol. 42 (8) , 1-30
Abstract
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.Keywords
Funding Information
- Ministerio de Economía y Competitividad (PID2019-104987GB-I00)
- Ministerio de Economía y Competitividad (JUVOCO)
- FONDECYT de Iniciación (11200113)
- Agencia Estatal de Investigación (PID-2020-112581GB-C21, MOTION)
- Catalan Government (2021 SGR 01419 ALBCOM, 2021 SGR 01419 ALBCOM)
- Catalan Government (2021 SGR 01419 ALBCOM)
This publication has 27 references indexed in Scilit:
- On the complexity of problems on simple gamesRAIRO - Operations Research, 2011
- Weighted games without a unique minimal representation in integersOptimization Methods and Software, 2010
- Dimension of complete simple games with minimumEuropean Journal of Operational Research, 2008
- Computational aspects of monotone dualization: A brief surveyDiscrete Applied Mathematics, 2008
- On the dimension of simple monotonic gamesEuropean Journal of Operational Research, 2006
- On the inference of semi-coherent structures from dataComputers & Operations Research, 2005
- A characterization of weighted votingProceedings of the American Mathematical Society, 1992
- Threshold hypergraphsDiscrete Mathematics, 1985
- A class of simple gamesDuke Mathematical Journal, 1958
- Theory of Games and Economic BehaviorReview of Economics and Statistics, 1947