Condorcet domain diversity measured by distance to random votes
Outer Diversity of Condorcet Domains
Computer Science and Game TheoryArtificial IntelligenceMultiagent Systems
Summary
Condorcet domains are special groups of rankings of candidates where any election using those rankings avoids inconsistent majority outcomes. The authors study how diverse these domains are by measuring how far random votes are from the closest ranking in the domain. They analyze small candidate sets numerically and provide mathematical results for larger cases. This helps understand the structure and limits of consistent voting systems.
What this means in practice
- •For voting system designers: Improve design of voting methods that guarantee consistent majority outcomes by understanding ranking diversity constraints.
- •For algorithm developers for preference aggregation: Use insights on ranking distances in Condorcet domains to optimize algorithms ensuring transitive majority in grouped preferences.
A theory result. No direct application yet.
Authors
Piotr Faliszewski, Jan Jabrocki, Mateusz Słuszniak, Krzysztof Sornat, Stanisław Szufa, Tomasz Wąs
Abstract
A Condorcet domain is a set of rankings over a given candidate set, such that every election that consists only of (an odd number of) votes from the domain has a transitive majority relation. We study outer diversity of Condorcet domains, i.e., a measure that quantifies expected swap distance from a random vote to a closest one in the domain. We numerically analyze outer diversity for maximal Condorcet domains with few candidates, and then we establish its asymptotic behavior for several special domains, mostly obtaining theoretical results.