A Dichotomy Theorem on the Existence of Efficient or Neutral Sequential Voting Correspondences

Lirong Xia, Jérôme LangIJCAI 2009

Introduction

In collective decision-making, groups often face complex choices involving multiple interdependent issues. For instance, a city council might need to decide on both the type of a new public facility (e.g., a park or a library) and its specific location (e.g., North or South). As the number of issues increases, the set of possible outcomes grows exponentially, making it impractical for voters to provide a complete ranking of all combinations. To manage this complexity, "sequential voting" is often employed, where issues are decided one by one.

This paper investigates the theoretical limits of sequential voting systems. Specifically, it explores whether these systems can simultaneously satisfy fundamental democratic criteria: Efficiency (Pareto Efficiency)—ensuring that if everyone prefers outcome A over B, B is not chosen—and Neutrality—ensuring the system does not inherently favor any particular outcome.

The Challenge of Multi-Issue Voting

The primary difficulty in multi-issue domains is the explosion of the alternative space. If there are $n$ binary issues, there are $2^n$ possible outcomes. For a voter to rank these linearly is a significant cognitive burden. Sequential voting simplifies this by breaking the decision into a sequence of local votes. However, this simplification introduces a risk: the outcome of the first vote may fundamentally change a voter's preference for subsequent issues.

Previous research into single-winner voting rules established that achieving efficiency and neutrality in such domains often leads to a dictatorship. This paper extends this inquiry to voting correspondences, which are rules that can output a set of tied winners rather than a single winner.

The Framework of CP-nets

To model these complex preferences, the authors utilize Acyclic CP-nets (Conditional Preference Networks). CP-nets are a graphical tool from artificial intelligence designed to represent conditional dependencies between preferences. For example, a voter might prefer white wine if the main course is fish, but red wine if it is beef.

Voter preference profiles demonstrating conditional preferences in a multi-issue domain.

The figure above illustrates how preferences are structured in this framework. Each voter has a ranking over the primary issue (e.g., $x_1, x_2, x_3$) and conditional preferences for the secondary issue ($y$ vs $\bar{y}$) based on the outcome of the first. The paper focuses on the sequential composition of local voting correspondences, testing whether the aggregate result maintains desirable axiomatic properties.

The Dichotomy Theorem

The central contribution of this research is the "Dichotomy Theorem." The authors prove that the "curse" of sequential voting—the trade-off between fairness and efficiency—is nearly universal.

The Two-Binary-Issue Exception

The theorem identifies a singular, narrow exception: the case where there are exactly two issues, and each issue is binary (having only two possible values). In this specific scenario, it is possible to construct a sequential voting system that is fair, efficient, and non-dictatorial. For instance, a sequential composition of two majority rules works effectively here.

The Collapse into Impossibility

As soon as the problem complexity increases—either by adding a third binary issue or by making one of the two issues non-binary (e.g., choosing between three types of parks)—the system collapses. The authors demonstrate that any sequential correspondence that aims to be efficient or neutral must fall into one of three undesirable categories:

  1. Dictatorship: The outcome is determined solely by one voter's preferences.
  2. Anti-dictatorship: The outcome is determined by the voter who likes it the least.
  3. Trivial Correspondence: The system simply declares every possible outcome a winner, providing no meaningful decision.

Key Results

The paper formalizes these findings through two primary theorems:

  • Theorem 5 (Correspondences): Establishes the dichotomy for systems that allow ties. Except for the two-binary-issue case, efficient or neutral sequential correspondences are restricted to dictatorships, anti-dictatorships, or trivial rules.
  • Theorem 6 (Rules): For single-winner rules, a non-dictatorial, anonymous rule is efficient or neutral if and only if there are exactly two binary issues and the number of voters is odd.

These results show that the flexibility of allowing multiple winners (correspondences) does not provide an escape from the impossibility results that plague single-winner rules in multi-issue domains.

Conclusion and Future Directions

This theoretical work highlights a fundamental limitation in the design of sequential voting systems for AI and social choice. While sequential voting is a practical necessity for high-dimensional decision spaces, it is mathematically impossible to guarantee both efficiency and neutrality outside of extremely simple cases.

Future research may look into relaxing the assumption of fixed voting orders or exploring the computational complexity of "near-optimal" rules. Additionally, the impact of strategic voting—where voters misrepresent their preferences on early issues to influence later outcomes—remains a critical area for further investigation.

Summary updated

BibTeX
@inproceedings{xia2009dichotomy,
  author = {Lirong Xia and Jérôme Lang},
  title = {{A Dichotomy Theorem on the Existence of Efficient or Neutral Sequential Voting Correspondences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
}
Figure