Introduction
In many artificial intelligence applications, such as committee voting, bundle allocation, or multi-winner elections, agents express preferences over individual items (alternatives). However, the system's goal is often to select or rank sets of these items. This transition from individual preferences to set-based preferences is known as "lifting."
A central challenge in social choice theory is ensuring that these lifted preferences are consistent and satisfy desirable properties, or axioms. This paper investigates the computational complexity of identifying "well-behaved" families of sets—those that consistently allow for preference lifting across all possible underlying item rankings.
The Preference Lifting Framework
The process of preference lifting involves several stages, moving from individual voter preferences to a collective decision rule.
As illustrated in Figure 1, voters provide their preferences over objects. A "lifting procedure" then translates these into preferences over sets of objects. Finally, a voting rule is applied to these set-based preferences to determine an outcome.
To maintain consistency, researchers often rely on axioms such as:
- Dominance (Dom): Adding a preferred item to a set makes the set better.
- Independence (Ind): Adding the same item to two different sets should not change their relative ranking.
Classic impossibility results, such as the Kannai-Peleg theorem, show that these axioms cannot always be satisfied if we attempt to rank all possible non-empty subsets of a large enough set of alternatives. However, in many practical scenarios, we only care about a specific family of sets (e.g., committees of a fixed size $k$).
Problem Definition: Strong Orderability
The paper focuses on the concept of strong orderability. A family of sets is considered strongly orderable if, for every possible linear preference order over individual items, there exists a valid preference order over the sets in that family that satisfies the chosen axioms (e.g., Dominance and Independence).
This "strong" requirement is critical for voting systems where the rules and the valid domain of sets must be established before voters submit their individual rankings.
Methodology
The author employs theoretical computational complexity analysis to determine the difficulty of recognizing these desirable families. The study considers various combinations of axioms (Dominance + Independence vs. Dominance + Strict Independence) and different requirements for the resulting set-order (Total Order vs. Partial Order).
To establish hardness, the paper utilizes reductions from several known hard problems:
- SAT and $\Pi^p_2$-SAT: Used to prove NP-hardness and $\Pi^p_2$-completeness for families of sets that are explicitly listed.
- TAUT (Tautology): Used to establish coNP-completeness for recognizing families that allow for partial orders.
- Succinct Representations: The author applies the "Conversion Lemma" to analyze cases where a family of sets is defined implicitly (e.g., via a Boolean circuit) rather than being explicitly enumerated.
Complexity Results
The main findings of the paper reveal that recognizing strongly orderable families is computationally demanding, often reaching the upper levels of the polynomial hierarchy or even exponential time.
As shown in Figure 2, the complexity varies significantly based on the requirements:
- Total vs. Partial Orders: Requiring a total order (where every set is comparable) is generally harder ($\Pi^p_2$-complete) than requiring only a partial order (coNP-complete).
- The Succinctness Penalty: In combinatorial voting, the number of possible sets is often exponential relative to the number of items. If the family of sets is represented succinctly (e.g., by a rule or circuit), the complexity jumps to NEXP-hard or NEXP-complete.
These results suggest that it is generally impossible to efficiently verify if a proposed voting domain will allow for consistent preference lifting.
Discussion and Future Work
The findings are primarily "negative," highlighting the inherent intractability of the general recognition problem. This suggests several paths for future research:
- Restricted Classes: Researchers should look for specific, restricted classes of set families (e.g., those defined by graph-theoretic properties) that might be easier to handle computationally.
- Alternative Axioms: While this work focuses on Dominance and Independence, future studies could explore the complexity of recognizing families under other common social choice axioms.
- Practical Succinctness: While general succinct representations lead to exponential complexity, there may be less expressive but practically useful representations that avoid this blow-up.
- Integration with Voting Rules: Further research is needed to understand how these lifted partial orders interact with specific voting rules like Borda or Condorcet in combinatorial settings.
In conclusion, while lifting preferences is a powerful tool for multi-agent decision-making, the task of ensuring that a chosen domain of sets is "well-behaved" is a significant computational hurdle.
Summary updated