Social Choice Under Incomplete, Cyclic Preferences Majority/Minority-Based Rules, and Composition-Consistency

Jobst HeitzigSSRN 2002

TL;DR

This paper proposes a new framework for social choice theory that accommodates incomplete and cyclic individual preferences, moving beyond traditional assumptions of completeness and transitivity. It introduces a family of majority/minority-based social choice rules that are robust to these complexities and demonstrates their desirable properties, including immunity from binary arguments and polynomial time complexity.

What Problem Does This Paper Address?

Traditional social choice theory often assumes that individuals have complete and transitive preferences (i.e., they can always compare any two alternatives and their preferences are consistent). However, real-world decision-making often involves incomplete preferences (where individuals may be undecided between some options) and cyclic preferences (where preferences can form loops, e.g., A > B, B > C, and C > A). This paper addresses the challenge of designing social choice mechanisms that can handle these more realistic, yet complex, preference structures. It argues that the traditional notion of "indifference" is misleading and should be replaced by concepts of "equivalence" and "undecidedness."

Methods

The paper introduces ten types of majority and minority "arguments" of varying strengths, which are then used to define social choice rules. These rules take profiles of arbitrary reflexive relations (representing individual preferences) as input and output a set of acceptable alternatives. A key aspect of the methodology is the concept of "immunity from binary arguments," where a choice is considered acceptable if it can withstand challenges from a majority or minority. The authors also explore various axiomatic conditions, such as composition-consistency, idempotency, and Condorcet-type conditions, and prove that their proposed rules satisfy many of these desirable properties. The paper also introduces a notion of "generalized components" for relations, which is used to develop a recursive rule that ensures consistency across different levels of aggregation.

Datasets

Not discussed in the paper. The paper focuses on theoretical frameworks and axiomatic properties rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Beyond Completeness and Transitivity: The paper convincingly argues that real-world preferences are often incomplete and cyclic, and that social choice theory must adapt to these realities.
  • Equivalence vs. Indifference: The distinction between "equivalence" (alternatives are considered equally good) and "undecidedness" (no preference expressed) is crucial for handling incomplete preferences.
  • Majority/Minority Arguments as Building Blocks: The paper shows how to construct social choice rules from a rich set of majority and minority arguments, allowing for nuanced decision-making.
  • Immunity from Binary Arguments: This concept provides a robust way to ensure that chosen alternatives are "defendable" against challenges, even in the presence of complex preferences.
  • Generalized Components: The introduction of generalized components offers a novel way to decompose complex preference structures and ensure consistent decision-making across different levels of aggregation.

Key Results

  • The paper defines ten types of majority and minority relations, capturing different strengths and forms of collective opinion.
  • It proves that social choice rules based on these arguments can be made composition-consistent and idempotent.
  • All proposed rules are shown to have polynomial time complexity, making them computationally feasible.
  • The paper demonstrates that even with incomplete and cyclic preferences, desirable axioms like Condorcet-type conditions can be satisfied.
  • A recursive rule construction based on generalized components is introduced, ensuring consistency across different levels of aggregation.

Limitations and Future Work

  • Strategic Voting: The paper acknowledges that strategic voting is not addressed and suggests it as an area for future research.
  • Experimental Investigations: The authors highlight the need for "experimental" investigations using stochastic simulations to compare rules in practice, especially when axiomatic approaches alone are insufficient.
  • Interviewing Techniques: The paper points to the need for efficient interviewing techniques to elicit arbitrary individual preference relations, which would be crucial for implementing these rules in practice.
  • "On-the-fly" Simulations: The authors mention that initial simulations suggest certain types of rules (e.g., those based on D and R) are more likely to yield deterministic choices, but more extensive simulations are needed.
  • Generating Random Preference Profiles: For simulations involving large sets of alternatives, generating uniformly distributed random samples of acyclic or transitive relations remains a challenge.

Summary updated

Abstract

Actual individual preferences are neither complete (=total) nor antisymmetric in general, so that at least every quasi-order must be an admissible input to a satisfactory choice rule. It is argued that the traditional notion of "indifference" in individual preferences is misleading and should be replaced by equivalence and undecidedness. In this context, ten types of majority and minority arguments of different strength are studied which lead to social choice rules C that accept profiles of arbitrary reflexive relations. These rules are discussed by means of many familiar, and some new conditions, including immunity from binary arguments. Moreover, it is proved that every choice function satisfying two weak Condorcet-type conditions can be made both composition-consistent and idempotent, and that all the proposed rules have polynomial time complexity.
BibTeX
@misc{heitzig2002social,
  author = {Jobst Heitzig},
  title = {{Social Choice Under Incomplete, Cyclic Preferences Majority/Minority-Based Rules, and Composition-Consistency}},
  year = {2002},
  howpublished = {SSRN},
}
Figure