Abstract: We consider a framework for preference aggregation on multiple binary issues, where agents' preferences are represented by (possibly cyclic) CP-nets. We focus on the majority aggregation of the individual CP-nets, which is the CP-net where the direction of each edge of the hypercube is decided according to the majority rule. First we focus on hypercube Condorcet winners (HCWs); in particular, we show that, assuming a uniform distribution for the CP-nets, the probability that there exists at least one HCWis at least 1-1/e, and the expected number of HCWs is 1. Our experimental results confirm these results. We also show experimental results under the Impartial Culture assumption. We then generalize a few tournament solutions to select winners from (weighted) majoritarian CP-nets, namely Copeland, maximin, and Kemeny. For each of these, we address some social choice theoretic and computational issues.
Introduction
In traditional social choice, voters rank a set of candidates. However, many real-world decisions involve multiple related issues—such as a city council deciding on a new park, a stadium, and a tax hike simultaneously. With $p$ binary issues, the number of possible outcomes grows exponentially ($2^p$), making it impossible for voters to provide a full linear ranking. Furthermore, issues are often interdependent; a voter might only support a new park if the tax hike is rejected. This paper addresses the challenge of combinatorial preference aggregation by utilizing CP-nets to represent these complex dependencies and proposing a "hypercubewise" approach to finding group winners.
The Hypercubewise Framework
To manage the exponential state space, the authors use CP-nets (Conditional Preference networks). These allow voters to express preferences locally (e.g., "I prefer $S$ over $\bar{S}$ regardless of $T$").
In the proposed Hypercubewise Aggregation, every possible combination of choices is viewed as a vertex on a high-dimensional cube (a hypercube). An edge exists between two vertices if they differ by exactly one issue. For every such edge, the group uses a majority vote to decide the direction of the preference. This creates a directed graph over the hypercube, where the goal is to identify a Hypercube Condorcet Winner (HCW)—an outcome that beats all its immediate neighbors in a majority vote.
Theoretical and Experimental Insights
The research explores the likelihood of these winners existing under different probabilistic models. Two primary insights emerge from the theoretical analysis of uniform distributions:
- The "1/e" Rule: Under a uniform distribution of preferences, the probability that at least one HCW exists is at least $1 - 1/e$ (approximately 63.2%). This suggests that local winners are remarkably common even in random environments.
- Decisiveness: The expected number of HCWs in a random hypercube is exactly one. This is a significant finding, as it suggests the method is highly decisive and rarely results in a tie or a lack of a clear winner.
Experimental simulations confirm these theoretical bounds. As shown in the data, the average number of HCWs remains remarkably stable near 1.0, regardless of the number of issues involved.
Tournament Solutions and Complexity
When a single HCW does not exist, the authors generalize classic tournament solutions—Copeland, Maximin, and Kemeny—to the hypercube structure (H-Copeland, H-maximin, and H-Kemeny). While these provide robust ways to select winners, they introduce significant computational hurdles. The authors prove that determining winners under these rules is often NP-complete or coNP-complete, though practical implementations can often be handled via SAT-solvers.
Conclusion
Hypercubewise aggregation offers a promising path for multi-issue voting by focusing on local, manageable comparisons rather than global rankings. While the "Impartial Culture" model can lead to an explosion of winners as issues increase, the uniform distribution model demonstrates that HCWs are both likely to exist and likely to be unique. Future work will look toward extending this framework to non-binary issues and exploring additional tournament solutions like Slater or Banks scores.
Summary updated