Solving Weighted Voting Game Design Problems Optimally: Representations, Synthesis, and Enumeration

Bart de Keijzer, Tomas B. Klos, Yingqian ZhangarXiv 2012 · arXiv

Introduction

In a weighted voting game (WVG), players are assigned numerical weights, and a "quota" is established. A coalition of players wins if their combined weight meets or exceeds this quota. While this system is common in corporate boards and international bodies like the EU Council, it harbors a fundamental paradox: a player’s weight (their share of votes) rarely corresponds directly to their power (their ability to turn a losing coalition into a winning one).

Consider a three-player game with weights $[50, 49, 1]$ and a quota of $51$. Despite the disparity in weights, the player with $1\%$ of the votes has exactly the same power as the player with $49\%$, as both are equally necessary to help the $50\%$ leader reach the quota. This discrepancy gives rise to the inverse power index problem: given a target distribution of influence, how can we determine the specific weights and quota that match that distribution as closely as possible? This paper provides a definitive algorithmic framework for solving this design problem optimally.

The Representation and Synthesis Challenge

The authors first address the mathematical representations of these games. A WVG can be described by its winning coalitions, but more efficiently by its "minimal winning coalitions" (those that would lose if any member left) or its "maximal losing coalitions."

Through their research, the authors established a new impossibility result: it is impossible to efficiently convert between "roof coalitions" (the bare minimum needed to win) and "ceiling coalitions" (the maximum possible to still lose) in polynomial time. To navigate these complexities, they refined the Hop-Skip-and-Jump Algorithm, which finds all maximal losing coalitions from a list of minimal winning ones. This step is essential for verifying whether a specific game structure can actually be represented by weights, a property known as being "threshold."

The Graded Poset and Anytime Enumeration

The core innovation of this work lies in the discovery that the set of all canonical weighted voting games forms a graded poset (a partially ordered set). This mathematical structure reveals that power distributions are not an infinite continuum but a finite, structured hierarchy. By proving this structure exists, the authors transformed what was previously a chaotic search problem into a systematic traversal of a mathematical graph.

Leveraging this, they developed an anytime algorithm for game synthesis. Because the algorithm enumerates games by "climbing" the poset, it can be stopped at any moment to return the best-fitting game found so far. If allowed to run to completion, it guarantees a global optimum—a significant improvement over previous "local search" heuristics that often became trapped in sub-optimal solutions.

Key Results and Complexity

The research significantly advances the theoretical bounds of game enumeration:

  • Complexity Reduction: The authors improved the time complexity for enumerating weighted voting games from "doubly exponential" to "quadratic exponential" ($O(2^{n^2})$). Their algorithm is "output-polynomial," meaning its speed is proportional to the number of games it identifies.
  • Exact Enumeration: The study provided the exact number of unique canonical weighted voting games for up to $n=8$ players. For $n=8$, the authors identified exactly 2,730,166 distinct games.
  • Design Accuracy: In practical experiments with 10 players, a breadth-first search variant of the algorithm found games with a very low error (Euclidean distance of approximately $0.05$ from the target) within just one minute of computation.

Limitations and Future Directions

Despite these breakthroughs, the "curse of dimensionality" remains a factor. The number of possible games grows so rapidly that full enumeration becomes intractable as the number of players increases. For a 9-player game, a full search requires approximately one month of compute time. For larger systems (e.g., $n=20$), the anytime property is less effective because the error does not converge to a low value quickly enough for real-time application.

The authors suggest that future research should focus on "pruning" the poset—developing mathematical methods to skip large clusters of games that are guaranteed to be far from the target power distribution. This would allow the algorithm to maintain its optimality while scaling to larger, more complex voting bodies.

Summary updated

Abstract

We study the inverse power index problem for weighted voting games: the problem of finding a weighted voting game in which the power of the players is as close as possible to a certain target distribution. Our goal is to find algorithms that solve this problem exactly. Thereto, we study various subclasses of simple games, and their associated representation methods. We survey algorithms and impossibility results for the synthesis problem, i.e., converting a representation of a simple game into another representation. We contribute to the synthesis problem by showing that it is impossible to compute in polynomial time the list of ceiling coalitions (also known as shift-maximal losing coalitions) of a game from its list of roof coalitions (also known as shift-minimal winning coalitions), and vice versa. Then, we proceed by studying the problem of enumerating the set of weighted voting games. We present first a naive algorithm for this, running in doubly exponential time. Using our knowledge of the synthesis problem, we then improve on this naive algorithm, and we obtain an enumeration algorithm that runs in quadratic exponential time (that is, O(2^(n^2) p(n)) for a polynomial p). Moreover, we show that this algorithm runs in output-polynomial time, making it the best possible enumeration algorithm up to a polynomial factor. Finally, we propose an exact anytime algorithm for the inverse power index problem that runs in exponential time. This algorithm is straightforward and general: it computes the error for each game enumerated, and outputs the game that minimizes this error. By the genericity of our approach, our algorithm can be used to find a weighted voting game that optimizes any exponential time computable function. We implement our algorithm for the case of the normalized Banzhaf index, and we perform experiments in order to study performance and error convergence.
BibTeX
@misc{keijzer2012solving,
  author = {Bart de Keijzer and Tomas B. Klos and Yingqian Zhang},
  title = {{Solving Weighted Voting Game Design Problems Optimally: Representations, Synthesis, and Enumeration}},
  year = {2012},
  eprint = {1204.5213},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.5213},
}
Figure