Voting on Multiattribute Domains with Cyclic Preferential Dependencies

Lirong Xia, Vincent Conitzer, Jérôme Lang

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:

  1. 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.
  2. 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).
Example of H-composition generating an induced graph from local voter preferences.

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.

Transfer of axiomatic properties between local and global voting rules.

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

Abstract

In group decision making, often the agents need to decide on multiple attributes at the same time, so that there are exponentially many alternatives. In this case, it is unrealistic to ask agents to communicate a full ranking of all the alternatives. To address this, earlier work has proposed decomposing such voting processes by using local voting rules on the individual attributes. Unfortunately, the existing methods work only with rather severe domain restrictions, as they require the voters' preferences to extend acyclic CP-nets compatible with a common order on the attributes. We first show that this requirement is very restrictive, by proving that the number of linear orders extending an acyclic CP-net is exponentially smaller than the number of all linear orders. Then, we introduce a very general methodology that allows us to aggregate preferences when voters express CP-nets that can be cyclic. There does not need to be any common structure among the submitted CP-nets. Our methodology generalizes the earlier, more restrictive methodology. We study whether properties of the local rules transfer to the global rule, and vice versa. We also address how to compute the winning alternatives.
BibTeX
@inproceedings{xia2008voting,
  author = {Lirong Xia and Vincent Conitzer and Jérôme Lang},
  title = {{Voting on Multiattribute Domains with Cyclic Preferential Dependencies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure