PaperlayerView exact revision on arXiv

Source-linked AI summary

Outer Diversity of Condorcet Domains

Piotr Faliszewski, Jan Jabrocki, Mateusz Słuszniak, Krzysztof Sornat, Stanisław Szufa, Tomasz Wąs

arXiv:2610.00720v1cs.GTcs.AIcs.MA

TL;DR

The paper asks how outer diversity measures Condorcet domains’ coverage of possible rankings and how that measure behaves across domains. It analyzes maximal domains with six candidates and derives results for special families, including asymptotic behavior. Outer diversity tracks never-middle conditions more strongly than domain size, and the authors suggest GS/cat has the highest value among Condorcet domains.

  • Problem

    The paper studies how outer diversity can characterize Condorcet domains beyond their size, since larger domains do not necessarily have higher outer diversity.

    Source: §1 · pp. 1–2

  • Method

    The authors analyze maximal Condorcet domains with six candidates and derive asymptotic results and exact computation methods for selected domain families.

    Source: §1 · p. 2

  • Results

    Outer diversity correlates strongly with the number of never-middle conditions but weakly with domain size, and the authors suggest GS/cat has the highest value among Condorcet domains.

    Source: §5 · p. 11

  • Takeaways & Limitations

    Single-peaked domains on trees can, in the limit, be as outer-diverse as the general domain, despite being weak Condorcet domains.

    Source: §1 · p. 2

    The authors leave unproved the conjectured limit that Black’s single-peaked domain’s outer diversity tends to zero; efficiently generating Arrow’s single-peaked domains is also unclear.

    Source: §3.1 · p. 7, §4 · p. 11

Abstract

from arXiv · show

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.

1 Introduction

The paper studies outer diversity as a measure of how closely a Condorcet domain covers all possible rankings, then analyzes its values and computation. It connects diversity to domain structure and reports theoretical results for special domains, including single-peaked domains on trees.

1 Introduction

  • The paper motivates outer-diversity analysis as a way to understand how never conditions influence Condorcet-domain properties, an influence it says is only partially understood.Source: §1 · p. 2
  • A domain’s vote count need not predict its outer diversity: the 224-vote largest eight-candidate domain is less diverse than some 128-vote group-separable domains.Outer diversity is presented as a more direct measure of voters’ ability to express their views.Source: §1 · p. 2
  • The authors extend prior computations from up to 20 to up to 100 candidates, give an exact formula for GS/cat, and provide exact algorithms where earlier work used sampling-based approximations.They do not consider all the domains covered by the earlier work.Source: §1 · p. 2
  • Single-peaked-on-a-tree domains can, in the limit, be as outer-diverse as the general domain.These domains are weak Condorcet: odd-voter elections from them have a Condorcet winner.Source: §1 · p. 2

2 Preliminaries

The preliminaries define the election and domain concepts used in the paper, characterize Condorcet domains through never conditions, and introduce the domain families and outer-diversity measure studied.

2.1 Domains

  • A Condorcet domain contains rankings such that every election with an odd number of its votes has a transitive majority relation; maximality means no outside vote can be added while preserving that property.A weak Condorcet domain instead guarantees a Condorcet winner in every such election.Source: §2.1 · p. 3
  • A domain is Condorcet exactly when every candidate triple satisfies at least one never-top, never-middle, or never-bottom condition.Peak-pit domains require, for every triple, either a never-top or never-bottom condition; Fishburn domains specify such conditions by candidate position in an ordering.Source: §2.1 · p. 3
  • The section distinguishes path-based Black single-peaked domains from Arrow’s generalization, and also considers tree-based single-peaked domains, which are weak Condorcet but not Condorcet.Source: §2.1 · p. 4
  • Single-crossing domains order votes so that, for each candidate pair, votes preferring one over the other form a prefix or suffix; these domains are Condorcet and belong to the peak-pit class.Single-peaked domains on graphs with cycles are not weak Condorcet.Source: §2.1 · p. 4
  • Group-separable domains are generated by binary trees and are Condorcet domains satisfying never-middle conditions, though not every domain satisfying those conditions is group-separable.Source: §2.1 · p. 4

2.2 Outer Diversity

  • Outer diversity is one minus twice the average normalized swap distance from a uniformly random ranking to its nearest domain member.Swap distance is the minimum number of adjacent-candidate swaps needed to transform one ranking into another.Source: §2.2 · p. 5

3 Outer Diversity of Domains With a Few Candidates

The section examines enumerated six-candidate maximal Condorcet domains alongside single-crossing and SP/T domains, comparing outer diversity across domain families and tree structures.

3.1 Maximal Condorcet Domains

  • Among 256895 maximal six-candidate domains, outer diversity is strongly correlated with the number of satisfied never-middle conditions (PCC = 0.714).The enumeration includes 9939 peak-pit domains and 12 domains defined by never-middle conditions only.Source: §3.1 · pp. 5–6
  • Cardinality correlates weakly with outer diversity (PCC=0.345): Fishburn’s 45-vote domain has diversity 0.538, versus the 0.495 mean and GS/cat’s 0.649.Source: §3.1 · p. 7
  • Black’s SP has the highest diversity among Arrow’s SP domains for six candidates, while GS/cat leads GS domains and diversity rises with tree height.GS/cat has the highest outer diversity among GS domains for each candidate count from 3 to 16.Source: §3.1 · p. 7

3.2 Single-Crossing Domains

  • For up to 9 candidates, maximal single-crossing-domain diversity distributions from uniform sampling and Szufa et al. [2025] are near-identical.The uniform sampler uses O(m·m!) preprocessing and samples in O(m^3) time.Source: §3.2 · p. 8

3.3 Single-Peakedness on a Tree

  • For 3–9 candidates, SP/T diversity falls as tree diameter grows (PCC −1 to −0.931), and star trees maximize it; their domains can exceed Condorcet-domain sizes.SP/T domains are weak Condorcet domains.Source: §3.3 · pp. 8–9

4 Asymptotic Behavior of Outer Diversity

The section establishes asymptotic outer-diversity results for several special domains and gives exact algorithms for computing or optimizing diversity in group-separable domains. The results include vanishing diversity for polynomial-size domains, a limit of one-half for GS/cat, and a bound tending to zero for GS/bal; the limit for SP remains unproved.

Numerical analysis

  • Figure 3 plots diversity against candidate count up to 100; SP and SC use approximate sampling, while GS/cat, GS/bal, and SP/star use exact algorithms.The figure uses a logarithmic x-axis and shades two standard deviations for sampling-based computations.Source: §4 · p. 9, Figure 3 · p. 9
  • SP/star outer diversity approaches 1, whereas SP, SC, and GS/bal appear to approach 0; the SP limit remains theoretically unconfirmed.For sufficiently many candidates, SP diversity is lower than GS/bal diversity.Source: §4 · pp. 9, 11

Asymptotic behavior

  • Outer diversity tends to 0 for every sequence of domains with polynomially many rankings, including single-crossing domains, whose sizes are O(m²).The section reports the polynomial-size result as a generalization of an earlier constant-size result.Source: §4 · p. 9

Computing GS diversity

  • An O(m⁴)-time algorithm computes outer diversity for any GS domain specified by a binary tree, using aggregated local costs and a bottom-up recurrence.The dynamic program groups votes by the sum of positions occupied by one child block; its table has O(m⁴) states.Source: §4 · p. 10

Optimizing GS diversity

  • GS/cat and GS/bal have the highest and lowest outer diversity among GS domains with up to 100 candidates, respectively.An O(m⁴)-time optimization algorithm searches over root splits and combines optimal subtrees.Source: §4 · p. 10

Asymptotic behavior

  • GS/cat outer diversity approaches 1/2, while GS/bal outer diversity is O(1/pm) and therefore tends to 0.The GS/cat formula is computable in O(m) time; GS/bal has no easy exact-formula route via the general algorithm.Source: §4 · pp. 10–11

SP/star and weak Condorcet domains

  • SP/star includes every vote that ranks the star-center candidate first or second, and weak Condorcet domains are expected to realize diversity values densely from 0 to 1.The dense-range expectation is based on an analogous argument using star graphs with one leaf replaced by a path.Source: §4 · p. 11

5 Conclusions

The conclusions relate outer diversity more strongly to never-middle conditions than to domain size, and identify GS/cat as a likely diversity leader among Condorcet domains. The appendix also represents single-crossing domains as maximal chains in a swap graph and samples those chains uniformly.

5 Conclusions

  • Outer diversity appears strongly correlated with the number of never-middle conditions, but only weakly correlated with domain size.The findings suggest GS/cat has the highest outer diversity among Condorcet domains, while Black’s single-peaked domain likely leads among Arrow’s single-peaked domains.Source: §5 · p. 11
  • Weak Condorcet domains can have outer diversity approaching 1, as with SP/star, whereas the authors do not believe such high values occur for Condorcet domains.The nonexistence of such high values for Condorcet domains is not formally established.Source: §5 · p. 11

A.1 Proof of Theorem 3.4

  • A single-crossing domain is a maximal chain in the swap DAG, whose nodes are votes and whose edges are adjacent swaps directed away from a reference vote.The DAG has m! nodes and O(m·m!) edges.Source: §A.1 · p. 14
  • Choosing each successor with probability proportional to its number of maximal chains yields a uniformly sampled single-crossing domain in O(m³) time.The chain counts are computed by dynamic programming in O(m·m!) time.Source: §A.1 · p. 14

A.2 Proof of Theorem 4.1

The proof handles polynomial-size domains by relating nearest-vote distances to the distribution of swap distances from a fixed vote. It also derives an O(m⁴)-time computation for GS domains by aggregating local costs over tree positions and combining subtree contributions.

A.2 Proof of Theorem 4.1

  • The proof bounds distance to the nearest domain vote by examining the closest ⌊m!/|Dm|⌋ votes around a fixed vote and their conditional expected swap distance.It uses the Lehmer code to express random swap distance as a sum of independent variables, then applies Hoeffding’s inequality.Source: §A.2 · pp. 15–16
  • For domains Dm of polynomial size, the proof establishes that the normalized average swap distance ansd(Dm) tends to 1/2.The argument assumes |Dm| = Θ(m^k) for a fixed positive k and |Dm| > 2.Source: §A.2 · pp. 14, 17

A.3 Proof of Theorem 4.3

  • For GS trees, distance decomposes into local costs for ordering child blocks and independent costs inside the two subtrees.Grouping votes by the position sum of one child block allows the local contributions to be aggregated rather than enumerating all votes.Source: §A.3 · pp. 18–19
  • The GS computation uses a dynamic-programming table with O(m⁴) states and computes out-div(GS(T)) in O(m⁴) time.The table counts position subsets by cardinality and index sum; local and subtree contributions are then combined.Source: §A.3 · pp. 18, 20

A.4 Proof of Theorem 4.5

The proof reduces optimizing outer diversity over the tree domains GS(T) to minimizing or maximizing the total swap distance S(T). A dynamic program over root splits finds both extrema in O(m^4) time.

A.4 Proof of Theorem 4.5

  • A tree attaining Mmin(m) minimizes S(T) and therefore maximizes out-div(GS(T)).S(T) is the total swap distance from all votes to GS(T).Source: §A.4 · p. 20
  • After computing split costs F(a,t), the algorithm fills Mmin in increasing order of a and stores minimizing splits to reconstruct an optimal tree.Computing F takes O(m^4) time in total, while filling Mmin takes O(m^2), so the overall running time is O(m^4).Source: §A.4 · pp. 20–21
  • The recurrence minimizes over all root splits, combining the optimal subtree values Mmin(t) and Mmin(a − t).The proof establishes the recurrence by showing both that joining optimal subtrees gives an upper bound and that an optimal tree's root split gives the reverse bound.Source: §A.4 · pp. 20–21
  • Both a tree maximizing and a tree minimizing out-div(GS(T)) can be found in O(m^4) time.The algorithm uses the same dynamic program with maxima instead of minima for the minimizing tree.Source: §A.4 · p. 21

A.5 Proof of Theorem 4.6

The proof computes outer diversity for the caterpillar-tree domain by applying the tree algorithm from Theorem 4.3. It uses the caterpillar's successive one-leaf splits to calculate local contributions and then combine them recursively.

A.5 Proof of Theorem 4.6

  • The proof computes out-div(GS/catm) by applying the algorithm from Theorem 4.3 to the caterpillar tree.It uses the notation established in that theorem's proof.Source: §A.5 · p. 21
  • At each internal node xq, the caterpillar has a leaf child and a child xq−1, with q leaves below xq.The proof may take the leaf as the left child because swapping children does not change the induced GS domain.Source: §A.5 · p. 22
  • For each xq, the proof computes its local contribution F(xq) and uses it in the recurrence for S(xq).The calculation uses A(q,1,s) = 1 and fxq(s) = min{s − 1,q − s}.Source: §A.5 · p. 22

A.6 Proof of Theorem 4.8

The proof expresses the swap cost of separating two candidate sets through their cross-set ranking score, then analyzes that cost across the splits of a binary tree. It uses covariance calculations and a balanced-tree property to aggregate the local contributions.

A.6 Proof of Theorem 4.8

  • For disjoint candidate sets A and B, the separation cost is the smaller of the swaps needed to put all of A before B or all of B before A.The A,B-score counts pairs in which a candidate from A precedes one from B; its range is 0 to |A|·|B|.Source: §A.6 · p. 23
  • At an internal node, the choice of ordering its two child sets is independent of the ordering choices at other internal nodes.This independence allows the proof to exchange the minimum over domain votes with the sum over internal nodes.Source: §A.6 · p. 24
  • The covariance between the two indicated ranking comparisons on three distinct candidates is 1/12.Among the six orderings, the centered-product value is 1/4 in four cases and −1/4 in two.Source: §A.6 · p. 25
  • For a balanced binary tree, each internal node's larger child has at most twice as many leaves as its smaller child.The proof also uses that every candidate pair is counted once, at its closest common ancestor, when summing over the tree.Source: §A.6 · p. 26

A.7 Proof of Theorem 4.10

For the star-shaped single-peaked domain, membership is characterized by the center candidate's rank, and distance is determined by how far below second place that candidate lies. The section also presents an analysis of maximal Condorcet domains with seven candidates.

A.7 Proof of Theorem 4.10

  • The star-shaped single-peaked domain contains exactly the votes ranking the center candidate first or second.The distance from a vote v to the domain is max(v[c] − 2,0), where v[c] is the center candidate's position.Source: §A.7 · p. 26
  • With m candidates, (m − 1)! votes place the center candidate at any given position.The proof uses this count in its calculation of outer diversity.Source: §A.7 · p. 26
  • Figure 4 analyzes all maximal Condorcet domains for seven candidates, identifying the full class of seven-candidate maximal Condorcet domains as the subject of the figure.Source: Figure 4 · p. 27

B Condorcet Domains with Seven Candidates

For seven candidates, the authors sample 1% of more than 172 million maximal nonisomorphic Condorcet domains and find conclusions similar to those for six candidates.

B Condorcet Domains with Seven Candidates

C Outer Diversity of Euclidean Domains

The section defines Euclidean preference domains and examines how candidate-location geometry and concentration relate to their outer diversity. In both circular and square subareas, center concentration generally increases mean outer diversity relative to uniform sampling, but the trend is non-monotonic.

C Outer Diversity of Euclidean Domains

D Microscope Visualizations of the Domains

The microscope visualizations compare Condorcet domains by size and outer diversity, embedding distinct votes by swap distance and coloring them by top-ranked candidate. They also depict never-middle domains and SP/T domains.

D Microscope Visualizations of the Domains

Loading 2610.00720v1…