Abstract
In multiattribute voting, groups decide on multiple related issues simultaneously, resulting in an outcome space that grows exponentially with the number of attributes. While previous research utilized acyclic CP-nets to manage this complexity, such models are often too restrictive for real-world preferences. This paper proposes H-composition (Hypercubewise composition), a novel framework that allows for cyclic dependencies and aggregates local preferences into global decisions. We demonstrate that H-composition generalizes previous sequential methods while maintaining computational feasibility through choice set functions like the Schwartz set.
Introduction
Multiattribute voting occurs when voters must decide on several interconnected attributes—for instance, deciding whether to build a pool and a tennis court, where the preference for one may depend on the outcome of the other. With $n$ binary issues, there are $2^n$ possible outcomes, making it impossible for voters to rank every option.
To address this, researchers have historically used Conditional Preference networks (CP-nets). However, traditional CP-net models require dependencies to be acyclic and force a uniform order of issues across all voters. This paper identifies that acyclic CP-nets represent only an exponentially small fraction of possible preferences, failing to capture the complexity of realistic voter behavior.
Methodology: The H-composition Framework
The authors introduce H-composition to aggregate preferences without requiring fixed ordering or acyclicity. The framework operates in two primary stages:
- Induced Graph Generation: A local voting rule (e.g., Majority) is applied to each attribute to determine preferences between outcomes differing by only that attribute. This results in a directed graph where nodes are outcomes and edges represent local wins.
- Choice Set Selection: Because the induced graph may contain cycles (e.g., A beats B, B beats C, and C beats A), a choice set function—such as the Schwartz, Smith, or Copeland set—is used to identify the final winner(s).
To handle the computational burden, the authors provide Process 1, an algorithm that efficiently computes winners by decomposing the induced graph into smaller components when dependencies allow.
Theoretical Insights and Property Transfer
A central contribution of this work is the "Acyclic Myth" proof. The authors mathematically demonstrate that as the number of attributes increases, the probability that a random ranking fits an acyclic CP-net approaches zero. This necessitates the move toward cyclic models.
Furthermore, the paper explores how axiomatic properties of voting rules transfer between local and global contexts. Properties such as Anonymity and Homogeneity are shown to transfer automatically, while others like Neutrality or Consistency may not, depending on the direction of the transfer.
Key Results
- Theorem 1: Formally establishes that the ratio of linear orders extending an acyclic CP-net to the total possible orders is exponentially small ($O((2^{0.2})^{-|X|})$).
- Generalization: H-composition is proven to be a true generalization of sequential voting. In cases where voter preferences are acyclic and consistent, H-composition yields the same results as traditional methods.
- Efficiency: While finding a winner in a cyclic domain is generally PSPACE-complete, the "Process 1" algorithm achieves polynomial time complexity relative to the size of the largest dependency partition.
Conclusion and Future Work
While H-composition provides a robust path forward for complex voting domains, challenges remain. The general case for cyclic dependencies is still computationally expensive (PSPACE-complete). Future research may extend this framework from picking winners to generating full social welfare rankings or exploring how it handles voters with partial orders or indifferences.
Summary updated