TL;DR
This paper explores the computational landscape of "perpetual voting"—a system where a group makes a sequence of collective decisions over time. While maximizing total group satisfaction (utilitarian welfare) is computationally easy, the authors prove that ensuring fairness (egalitarian or Nash welfare) is NP-complete even in simple scenarios, though they identify specific conditions where these "fairer" outcomes remain reachable.
What Problem Does This Paper Address?
In traditional voting, we usually think of a single event: electing a president or choosing a movie for tonight. But many real-world scenarios involve perpetual voting, where the same group makes decisions repeatedly (e.g., a group of friends choosing daily meals on a two-week trip, or a committee scheduling recurring tasks).
In a single round, a simple majority vote might leave 49% of the people unhappy. In a perpetual setting, however, we have the opportunity to "make it up" to the losers of round one by picking their preferences in round two. The challenge is defining and computing what a "good" outcome looks like over time. The authors look at three classic welfare objectives:
- Utilitarian: Maximize the total sum of everyone's happiness.
- Egalitarian: Maximize the happiness of the least satisfied person (preventing anyone from being ignored).
- Nash: Maximize the product of everyone's happiness (a middle ground that balances total utility and individual fairness).
Methods
The authors model this using an approval-based framework: in each round, every voter provides a set of candidates they approve of. An agent's utility is simply the number of rounds in which one of their approved candidates was chosen.
To analyze the difficulty of maximizing these utilities, the authors employ Computational Complexity Theory. They specifically look at:
- Classical Complexity: Is the problem solvable in polynomial time (P) or is it NP-complete?
- Parameterized Complexity: If the problem is generally hard, does it become easy if we fix certain variables, like the number of voters ($n$) or the number of rounds ($\ell$)? They use classes like FPT (Fixed-Parameter Tractable) and W[2]-hard to map these boundaries.
- Algorithmic Design: They propose greedy algorithms and Integer Linear Programming (ILP) constructions to find solutions or approximations.
Datasets
As a theoretical "Student Abstract," this paper does not use empirical datasets or benchmarks. It focuses on mathematical proofs and algorithmic analysis within a formal model.
Key Insights and Ideas
- The "Tyranny of the Majority" is Easy to Compute: Maximizing utilitarian welfare is trivial—you just pick the most popular candidate in every single round. However, this is often "unfair" because a consistent majority can shut out a minority forever.
- Fairness is Hard: The moment you try to be fair (Egalitarian or Nash welfare), the problem becomes NP-complete. Surprisingly, this holds true even if there are only two candidates to choose from in each round.
- Voters vs. Rounds: The complexity behaves differently depending on what is "small."
- If you have a small number of voters, finding an egalitarian solution is efficient (Fixed-Parameter Tractable).
- If you have a small number of rounds, the problem is still technically solvable in polynomial time (Slicewise Polynomial), but it's much "harder" in a parameterized sense (W[2]-hard), meaning the runtime grows much more aggressively as the number of rounds increases.
- The Strategyproofness Trade-off: There is a fundamental tension between fairness and honesty. While the simple utilitarian greedy approach is strategyproof (voters have no incentive to lie), any deterministic mechanism that tries to maximize Egalitarian or Nash welfare can be gamed by savvy voters.
Key Results
- NP-Completeness: Proved that EGAL and NASH welfare maximization are NP-complete, even for the simplest case of $m=2$ candidates and a target utility of $\lambda=1$.
- EGAL is FPT in $n$: Using an ILP-based approach, they showed that if the number of agents is small, we can solve the egalitarian problem efficiently.
- Approximation: Since EGAL is hard, they provide an approximation algorithm that achieves a factor of $1/(4 \log n)$ of the optimal egalitarian welfare, provided utilities are "augmented" (starting everyone at a baseline of 1 to avoid division-by-zero issues).
- Proportionality (PROP): They define a notion of proportionality (everyone gets at least a fair share of their "approvable" rounds) and prove that such an outcome always exists and can be found with a simple greedy algorithm.
Limitations and Future Work
The authors note several open paths:
- The Nash Gap: While they proved EGAL is FPT in the number of agents, the same remains unproven for NASH welfare due to the non-linear nature of the Nash objective (which involves products or logs).
- Generalizing Welfare: The paper introduces a "p-mean welfare" objective that encompasses all three types; future work could explore the complexity of this general function for values of $p$ other than $1, 0,$ or $-\infty$.
- Utility Definitions: The results might change if "utility" is defined differently (e.g., if voters have different weights or if some rounds are more important than others).
Summary updated