Abstract
This research provides the first comprehensive computational complexity map for aggregating group preferences using $m$CP-nets. By analyzing Pareto and Majority voting schemes, the authors reveal that while many group decision tasks are technically intractable—falling into high levels of the Polynomial Hierarchy—some crucial problems are surprisingly efficient to solve.
Introduction: Preferences in Combinatorial Domains
In artificial intelligence, representing agent preferences is crucial for systems like recommenders or configuration tools. However, when choices involve multiple features—such as a dinner consisting of a main dish, a wine, and a dessert—the number of possible outcomes grows exponentially. This is known as a combinatorial domain.
CP-nets (Conditional Preference networks) are a popular framework for representing these preferences compactly using "ceteris paribus" (all else being equal) rules. For instance, an agent might prefer red wine over white wine, provided the main dish is meat. While single-agent CP-nets are well-understood, real-world AI often involves groups of agents. $m$CP-nets were designed to aggregate these individual preferences through voting.
Despite their introduction years ago, the exact computational cost of determining group preferences (dominance) or identifying the best outcomes (optimality) remained a mystery. This paper fills that gap by providing precise complexity bounds for these tasks.
Methodology
The authors perform a rigorous theoretical complexity analysis on a specific class of $m$CP-nets: those that are acyclic (no circular preferences), binary (features have only two values), and polynomially-connected (the relationship between features is not overly tangled).
They focus on two primary voting schemes:
- Pareto Voting: An outcome $A$ is better than $B$ only if every agent agrees.
- Majority Voting: An outcome $A$ is better than $B$ if a strict majority of agents prefer $A$ to $B$.
The researchers analyzed five specific computational tasks for each scheme: Dominance (preference of $A$ over $B$), Optimality (is $A$ undefeated?), Optimum (does $A$ defeat all others?), and Existence (does an optimal/optimum outcome exist?).
Key Insights
The study provides several critical insights into the nature of group preference aggregation:
- Refined Bounds: The paper pulls the complexity of these problems down from general exponential time (EXP) upper bounds into specific levels of the Polynomial Hierarchy.
- Tractability Surprises: While most problems are NP-hard or worse, Pareto voting offers significant efficiency for certain tasks. Checking if an outcome is the absolute best (Optimum) is in LOGSPACE, and checking if such an outcome exists is in P.
- Majority Voting Paradoxes: Unlike Pareto voting, where an optimal outcome always exists, the authors proved that in Majority voting, a group can end up with no optimal outcome at all—a voting paradox in combinatorial space.
- High-Level Complexity: Several majority-voting problems were found to be $\Sigma^p_2$ or $\Pi^p_2$-complete, making them significantly more difficult than standard NP-complete problems.
Complexity Results
The paper's findings are summarized in a definitive complexity table, highlighting the stark contrast between the two voting systems.
The results show that while determining if one outcome beats another is equally hard in both systems (NP-complete), finding the "best" outcome is vastly more complex in a majority system than in a unanimous (Pareto) one.
Conclusion and Future Work
The authors acknowledge that their analysis is restricted to acyclic, binary, polynomially-connected nets. Real-world preferences might be cyclic or involve features with many possible values, which could increase complexity further.
Future research directions include investigating the impact of constraints (e.g., impossible outcome combinations), extending the analysis to alternative voting schemes like rank-based voting, and developing approximation algorithms for intractable tasks to find "good enough" outcomes efficiently.
Summary updated