TL;DR
This paper tackles the "voting game design problem," aiming to create fair voting systems where players' influence matches a desired distribution. The authors develop an efficient algorithm to enumerate all possible weighted voting games, enabling them to find optimal game designs that closely match target influence profiles, a significant improvement over previous methods.
What Problem Does This Paper Address?
Imagine designing a voting system for a committee, a company board, or even an international organization. How do you ensure that each member's influence is "fair"? Simply assigning weights based on, say, share ownership or number of votes might not reflect true influence. This is where "power indices" come in, attempting to quantify a player's a priori power in a voting game. The "voting game design problem," specifically the "inverse problem," asks: given a desired distribution of power (a target power index), how can we design a weighted voting game (a system with players, weights, and a quota) whose actual power distribution is as close as possible to the target? The challenge lies in the vast number of possible voting games and the difficulty of efficiently enumerating them to find the optimal one.
Methods
The core of this paper is a novel enumeration algorithm for weighted voting games. Instead of directly working with potentially infinite weighted representations, the authors exploit a specific partial order on games based on their minimal winning coalitions. This allows them to build up the set of all possible canonical weighted voting games systematically, starting from the simplest game (no winning coalitions) and incrementally adding minimal winning coalitions. This "bottom-up" approach, combined with optimizations like focusing on "ceiling coalitions" and using the "Hop-Skip-and-Jump" algorithm for game verification, leads to an algorithm that runs in output-polynomial time. This means the time it takes to find a solution is roughly proportional to the size of the output, a significant improvement.
Datasets
Not discussed in the paper. The paper focuses on theoretical algorithm development and uses synthetic instances for experiments.
Key Insights and Ideas
- A Structured Approach to Enumeration: The paper introduces a new partial order on weighted voting games based on their minimal winning coalitions. This structure is crucial for efficiently enumerating all possible games.
- "Bottom-Up" Game Construction: By starting with the simplest game and incrementally adding minimal winning coalitions, the authors create a systematic way to discover all possible games.
- Output-Polynomial Time: The developed algorithm is not only efficient but also runs in output-polynomial time, meaning its runtime scales well with the size of the solution it produces. This is a strong theoretical guarantee.
- Anytime Algorithm: The algorithm has an "anytime" property, meaning it can be stopped at any point to provide the best solution found so far, with the quality improving the longer it runs.
Key Results
- The paper presents a doubly exponential algorithm for enumerating monotonic simple games.
- A significant improvement is achieved with a singly exponential (specifically, $O^*(2^{O(n^2)})$) algorithm for enumerating weighted voting games.
- This enumeration algorithm forms the basis for an exact "anytime" algorithm for the power index voting game design problem, which runs in output-polynomial time.
- Experiments were conducted for up to 8 players, showing that the number of minimal winning coalitions is often much smaller than the theoretical maximum.
- The experiments also demonstrated that errors in approximating target power indices decrease as the number of players increases, though worst-case errors can still be significant.
Limitations and Future Work
- Scalability: While the algorithm is theoretically efficient, its practical application is limited to a small number of players (currently up to 8-9) due to the exponential nature of the problem. Extrapolating to 10 players suggests runtimes of tens to thousands of years with the current implementation.
- Future Work: The authors suggest several avenues for future research:
- Improving the algorithm's speed to handle more players, potentially by further exploring the partial order to prune search spaces.
- Investigating greedy or heuristic search methods within the partial order that might still offer optimality or approximation guarantees.
- Using the developed algorithm as a postprocessing step for existing algorithms to refine solutions.
- Exploring the computational complexity of the voting game design problem and its approximability.
Summary updated