On the Dimensionality of Voting Games ---
A Complexity-Theoretic Analysis
Authors: Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, and Michael Wooldridge
Abstract:
In a \emph{yes/no voting game}, a set of voters must determine whether
to accept or reject a given alternative. \emph{Weighted voting
games} are a well-studied subclass of yes/no voting games, in which
each voter has a weight, and an alternative is accepted if the total
weight of its supporters exceeds a certain threshold. Weighted voting
games are naturally extended to $k$-vector weighted voting games,
which are intersections of $k$ different weighted voting games: a
coalition wins if it wins in every component game. The
dimensionality, $k$, of a $k$-vector weighted voting game can be
understood as a measure of the complexity of the game. In this paper,
we analyse the dimensionality of such games from a complexity
theoretic angle. We consider the problems of
\emph{equivalence}, (checking whether two given voting games
have the same set of winning coalitions), and \emph{minimality},
(checking whether a given $k$-vector voting game can be simplified by
deleting one of the component games, or, more generally, is equivalent
to a $k'$-weighted voting game with $k'