Abstract
In multi-issue decision-making, voter preferences often depend on the outcomes of related variables. Standard approval voting fails to capture these dependencies, while full preference rankings lead to a combinatorial explosion. This paper introduces Conditional Approval (CA) ballots, which allow voters to approve options based on the values assigned to parent variables in a dependency graph. We propose three voting rules—Conditional Minisum, Conditional Minimax, and Sequential Conditional Approval Voting (SCAV)—and analyze their computational complexity, axiomatic properties, and performance bounds.
Introduction: The Challenge of Combinatorial Domains
Collective decision-making often involves choosing a combination of items, such as electing a committee, setting dates for multiple meetings, or choosing a multi-course menu. A significant hurdle in these "combinatorial domains" is preferential dependency: a voter's approval of one item may depend on the selection of another (e.g., approving red wine only if steak is the main course).
Standard approval voting, where items are voted for in isolation, cannot capture these nuances. Conversely, asking voters to rank every possible combination of outcomes leads to a "combinatorial explosion" that is cognitively overwhelming and computationally impossible to manage.
Conditional Approval Ballots
The authors propose Conditional Approval (CA) ballots to bridge this gap. In this system, a voter provides a set of approved values for a variable $X$, conditioned on the values of its "parent" variables in a dependency graph. This allows for a structured expression of preference without requiring a full ranking of all possible outcomes.
Voting Rules and Complexity
Three specific rules are defined to aggregate these ballots and determine a winner:
- Conditional Minisum: Selects the outcome that minimizes the total number of "disagreements" (instances where the final choice for a variable was not in a voter's approved set for that specific context) across all voters.
- Conditional Minimax: An egalitarian approach that finds the outcome minimizing the maximum number of disagreements any single voter must endure.
- Sequential Conditional Approval Voting (SCAV): A more efficient, step-by-step process. Given a fixed order of variables, voters approve values for the first variable, a winner is picked, and then voters approve values for the next variable based on that winner, and so on.
Key Insights and Results
- The Complexity Jump: While standard minisum approval voting is computationally easy, Conditional Minisum is NP-hard, even if dependencies are simple (each variable has only one parent). However, the problem can be translated into a Maximum Satisfiability (MaxSAT) problem, allowing the use of powerful off-the-shelf solvers.
- Axiomatic Properties: The paper proves that both Minisum and SCAV satisfy standard fairness criteria such as reinforcement (consistency across subgroups) and monotonicity (additional approvals cannot cause a winner to lose).
- Sequential Efficiency vs. Optimality: SCAV is significantly faster to compute than the global Minisum rule but may result in more total disagreements. For binary choices on $p$ issues, the disagreement score of an SCAV winner is at most $p$ times worse than the Minisum optimal.
- Strategyproofness: While simple approval voting is often resistant to tactical voting, the addition of conditions makes the system manipulable. Even the Minisum rule is shown to be "$\delta$-manipulable."
Conclusion
Conditional Approval voting offers a flexible framework for complex group decisions by treating approval as a structured utility function. While it introduces new computational challenges, the mapping to MaxSAT and the use of sequential rules provide paths for practical implementation. Future research is needed to address the cognitive burden of complex dependencies and the impact of variable ordering in sequential rules.
Summary updated