Abstract
Actual individual preferences are neither complete nor antisymmetric in general; therefore, any robust social choice rule must accept at least quasi-orders as admissible input. This paper argues that the traditional notion of "indifference" in individual preferences is often misleading and should be replaced by the distinct concepts of "equivalence" and "undecidedness." Within this framework, ten types of majority and minority arguments of varying strengths are analyzed, leading to social choice rules that accommodate profiles of arbitrary reflexive relations. These rules are evaluated against several conditions, including "immunity from binary arguments." Furthermore, the paper proves that any choice function satisfying two weak Condorcet-type conditions can be rendered both composition-consistent and idempotent, all while maintaining polynomial time complexity.
Introduction
Traditional social choice theory—the mathematical foundation for voting and collective decision-making—frequently relies on the assumption that individuals possess "total orders" of preferences. In this idealized model, every voter can rank every possible option from best to worst without ties or logical loops. However, Jobst Heitzig posits that this assumption is fundamentally unrealistic for real-world applications. Human preferences are often "messy," characterized by gaps where information is missing or cycles where criteria conflict.
The Reality of Individual Preferences
Heitzig identifies three primary challenges to the traditional model:
- Incompleteness: Voters are often "undecided" because they lack the necessary information to compare two options, which is distinct from "indifference," where they value both options equally.
- Cyclicity: Preferences can be circular (e.g., preferring A to B, B to C, but C to A) due to the multi-dimensional nature of decision-making.
- Complexity: Standard social choice models struggle to process these inputs without sacrificing logical consistency or becoming computationally intractable.
A central philosophical contribution of this work is the distinction between undecidedness and indifference. While indifference is a vote to retain both options, undecidedness is a request to delegate the decision to others who may possess more information.
Methodology: Binary Arguments and Majority Types
The paper develops a framework centered on binary arguments. Rather than simply aggregating top-choice votes, the proposed rules evaluate whether a majority (or a significant minority) prefers one alternative over another.
Ten Types of Majority
Heitzig defines a spectrum of ten "strengths" for arguments. These range from Absolute Majorities, based on the total number of voters, to Proportional and Persuaded Majorities, which specifically account for undecided voters. This allows for a nuanced approach where, in certain contexts, a strict minority preference might block a majority if the majority's preference is weak or the undecided population is large.
Immunity from Binary Arguments ($Im_A$)
A core axiom introduced is Immunity from Binary Arguments. This principle states that an alternative $x$ should only be rejected if there exists a "better" alternative $y$ that cannot itself be countered by a sequence of similar arguments leading back to $x$. This effectively generalizes the concept of a "top cycle" to more abstract preference structures.
Composition-Consistency and Computational Efficiency
A significant hurdle in social choice is ensuring that results remain consistent when alternatives are grouped. Heitzig addresses this through Theorem 5, which proves that any social choice rule satisfying basic fairness and neutrality axioms can be modified to satisfy Composition-Consistency (CC). This means the outcome does not change if similar alternatives are clustered (e.g., "Action Movies" vs. "Comedies") before a final choice is made.
Furthermore, the paper provides a recursive algorithm to ensure idempotency—ensuring the choice set remains stable if the rule is applied to the result a second time.
Crucially, the paper demonstrates that these complex, recursive rules are computationally efficient. The choice sets can be calculated in polynomial time ($O(k^6 n)$), where $k$ is the number of alternatives and $n$ is the number of voters. This ensures that the framework is not just a theoretical exercise but is viable for real-world software implementation.
Conclusion
By moving beyond the "perfect ranking" assumption, Heitzig provides a robust mathematical framework for social choice that mirrors the complexity of human decision-making. While the paper acknowledges limitations regarding strategic voting and the challenges of explaining complex outcomes to human users, the proof of polynomial time complexity and the formalization of "undecidedness" represent significant steps forward in the field of collective choice.
Summary updated