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