pith. sign in

arxiv: 1906.09671 · v1 · pith:5OSUPXMNnew · submitted 2019-06-23 · 💻 cs.GT · econ.TH

Single-crossing Implementation

Nathann Cohenn , Edith Elkind , Foram Lakhani This is my paper

Pith reviewed 2026-05-25 17:17 UTC · model grok-4.3

classification 💻 cs.GT econ.TH
keywords single-crossing electionsnearly single-crossinggraph mappingcomputational social choicevoting complexityobstacles in preferences
0
0 comments X

The pith

Mapping elections to graphs encodes the obstacles to single-crossing.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a mapping from elections to graphs so that features blocking single-crossing become visible as graph structures. Single-crossing elections have useful traits like transitive majority relations and admit efficient solutions to otherwise hard problems. Understanding the minimal modifications needed to reach single-crossing is therefore valuable. The graph encoding turns this task into one that can draw on existing graph algorithms and complexity results.

Core claim

We propose a mapping between elections and graphs that provides a convenient encoding of such obstacles. This mapping enables us to use the toolbox of graph theory in order to analyze the complexity of detecting nearly single-crossing elections, i.e., elections that can be made single-crossing by a small number of modifications.

What carries the argument

The mapping from elections to graphs that encodes obstacles to the single-crossing property.

If this is right

  • The complexity of identifying minimal modifications to achieve single-crossing can be studied through corresponding graph problems.
  • Graph-theoretic tools become applicable to questions about nearly single-crossing elections.
  • Detection of near-single-crossing elections reduces to graph problems whose complexity is better understood.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This method may help classify the computational difficulty of related preference domain restrictions.
  • Extensions could apply the same encoding to measure distance to other structured preference profiles.

Load-bearing premise

The mapping accurately and completely encodes the obstacles that prevent an election from being single-crossing.

What would settle it

A specific election where the graph representation fails to identify an actual obstacle to single-crossing or miscalculates the number of modifications needed.

Figures

Figures reproduced from arXiv: 1906.09671 by Edith Elkind, Foram Lakhani, Nathann Cohenn.

Figure 1
Figure 1. Figure 1: A bipartite graph that is not 3-implementable. in min{|V|, |E|}. We first define a class of single-crossing elections that can be used to implement an arbitrary graph. Definition 5. A single-crossing election E = (C, V ) with V = (v1, . . . , vn) is fully single-crossing if for every pair of candidates a, b ∈ C with a ≻1 b there is an i ∈ [n − 1] such that a ≻i b, b ≻i+1 a, and voter i + 1 ranks b just abo… view at source ↗
read the original abstract

An election over a finite set of candidates is called single-crossing if, as we sweep through the list of voters from left to right, the relative order of every pair of candidates changes at most once. Such elections have many attractive properties: e.g., their majority relation is transitive and they admit efficient algorithms for problems that are NP-hard in general. If a given election is not single-crossing, it is important to understand what are the obstacles that prevent it from having this property. In this paper, we propose a mapping between elections and graphs that provides us with a convenient encoding of such obstacles. This mapping enables us to use the toolbox of graph theory in order to analyze the complexity of detecting nearly single-crossing elections, i.e., elections that can be made single-crossing by a small number of modifications.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proposes a mapping from elections to graphs that encodes the obstacles preventing an election from being single-crossing. This encoding is claimed to be polynomial-time computable and to preserve semantics such that minimum modifications restoring single-crossing in the election correspond to minimum graph edits; the mapping thereby reduces the complexity analysis of nearly single-crossing elections to standard graph problems.

Significance. If the equivalence holds, the construction supplies a direct, reusable bridge between single-crossing social-choice problems and the graph-algorithm toolbox, which could yield both new hardness results and polynomial-time algorithms for modification problems that remain NP-hard in the unrestricted domain. The paper correctly notes the attractive algorithmic properties of exact single-crossing elections (transitive majority relation, efficient solution of otherwise hard problems).

minor comments (3)
  1. [§3] §3 (Mapping definition): the precise vertex/edge labels and the exact correspondence between a single-crossing violation and a forbidden induced subgraph should be stated with a small worked example so that readers can verify the claimed equivalence without reconstructing the proof.
  2. [Theorems 1 and 2] Theorems 1 and 2: the running-time analysis of the reduction should explicitly bound the size of the constructed graph in terms of the number of candidates and voters.
  3. [Figure 1] Figure 1: the caption should indicate whether the depicted graph is the image of a single-crossing or a non-single-crossing election.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work and for recommending minor revision. The referee accurately captures the paper's contribution: a polynomial-time mapping from elections to graphs that encodes single-crossing obstacles and reduces near-single-crossing detection to standard graph-edit problems. We appreciate the recognition of the algorithmic implications for social-choice problems.

Circularity Check

0 steps flagged

No significant circularity; definitional mapping with independent correctness claim

full rationale

The paper proposes a direct, polynomial-time mapping from elections to graphs that encodes obstacles to the single-crossing property, then uses this to reduce complexity questions about nearly single-crossing elections to standard graph problems. Correctness is established by exhibiting equivalence between election modifications and graph edits. No equations, fitted parameters, self-citations, or ansatzes appear in the provided text; the construction does not reduce to its own inputs by definition or rename a known result. The derivation is therefore self-contained and relies on external graph-theoretic tools rather than internal circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are described in the abstract.

pith-pipeline@v0.9.0 · 5659 in / 904 out tokens · 46639 ms · 2026-05-25T17:17:08.544580+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 1 internal anchor

  1. [1]

    k-Majority Digraphs and the Hardness of Voting with a Constant Number of Voters

    [Bachmeier et al., 2017] G. Bachmeier, F. Brandt, C. Geist, P . Harrenstein, K. Kardel, D. Peters, and H. G. Seedig. k-majority digraphs and the hardness of voting with a constant number of voters. Technical report, arXiv 1704.06304,

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  2. [2]

    [Berge, 1961] C. Berge. F¨ arbung von Graphen, deren s¨ amtliche bzw. deren ungerade Kreise starr sind. Wis- senschaftliche Zeitschrift, page 114,

    work page 1961

  3. [3]

    Bollob´ as and P

    [Bollob´ as and Erd¨ os, 1976] B. Bollob´ as and P . Erd¨ os. Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society , 80(3):419–427,

    work page 1976

  4. [4]

    Bredereck, J

    [Bredereck et al., 2013] R. Bredereck, J. Chen, and G. Woeginger. A characterization of the single-crossing domain. Social Choice and W elfare, 41(4):989–998,

    work page 2013

  5. [5]

    Bredereck, J

    [Bredereck et al., 2016] R. Bredereck, J. Chen, and G. J. Woeginger. Are there any nicely structured preference pro- files nearby? Mathematical Social Sciences , 79:61–73,

    work page 2016

  6. [6]

    Chudnovsky, N

    [Chudnovsky et al., 2006] M. Chudnovsky, N. Robertson, P . Seymour, and R. Thomas. The strong perfect graph the- orem. Annals of Mathematics , 164:51–229,

    work page 2006

  7. [7]

    Cornaz, L

    [Cornaz et al., 2013] D. Cornaz, L. Galand, and O. Span- jaard. Kemeny elections with bounded single-peaked or single-crossing width. In Proceedings of the 23rd Inter- national Joint Conference on Artificial Intelligence , pages 76–82,

    work page 2013

  8. [8]

    [Diestel, 2012] R. Diestel. Graph Theory. Springer,

    work page 2012

  9. [9]

    Elkind and M

    [Elkind and Lackner, 2014 ] E. Elkind and M. Lackner. On detecting nearly structured preference profiles. In Pro- ceedings of the 28th AAAI Conference on Artificial Intelli- gence, pages 661–667,

    work page 2014

  10. [10]

    Elkind, M

    [Elkind et al., 2017] E. Elkind, M. Lackner, and D. Peters. Structured preferences. In U. Endriss, editor, Trends in Computational Social Choice, chapter 10, pages 187–207. AI Access,

    work page 2017

  11. [11]

    Erdos and L

    [Erdos and Moser, 1964 ] P . Erdos and L. Moser. On the rep- resentation of directed graphs as unions of orderings. Pub- lications of the Mathematical Institute of the Hungarian Academy of Science , 9:125–132,

    work page 1964

  12. [12]

    Erd¨ os and G

    [Erd¨ os and Szekeres, 1935] P . Erd¨ os and G. Szekeres. A combinatorial problem in geometry. Compositio mathe- matica, 2:463–470,

    work page 1935

  13. [13]

    [Garey and Johnson, 1979 ] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W . H. Freeman,

    work page 1979

  14. [14]

    [Golumbic, 1980] M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs . Academic Press [Har- court Brace Jovanovich, Publishers], New Y ork-London- Toronto, Ont.,

    work page 1980

  15. [15]

    [Jaeckle et al., 2018] F

    With a foreword by Claude Berge, Computer Science and Applied Mathematics. [Jaeckle et al., 2018] F. Jaeckle, D. Peters, and E. Elkind. On recognising nearly single-crossing preferences. In Pro- ceedings of the 32nd AAAI Conference on Artificial Intel- ligence, pages 1079–1086, February

    work page 2018

  16. [16]

    Lakhani, D

    [Lakhani et al., 2019] F. Lakhani, D. Peters, and E.Elkind. Correlating preferences and attributes: nearly single- crossing profiles. In Proceedings of the 28th International Joint Conference on Artificial Intelligence ,

    work page 2019

  17. [17]

    Lakshmivarahan, S

    [Lakshmivarahan et al., 1984] S. Lakshmivarahan, S. K. Dhall, and L. L. Miller. Parallel sorting algorithms. In Advances in Computers, volume 23, pages 295–354. Else- vier,

    work page 1984

  18. [18]

    [McGarvey, 1953] D. C. McGarvey. A theorem on the con- struction of voting paradoxes. Econometrica, 21(4):608– 610,

    work page 1953

  19. [19]

    Mirrlees

    [Mirrlees, 1971] J. Mirrlees. An exploration in the theory of optimal income taxation. Review of Economic Studies , 38:175–208,

    work page 1971

  20. [20]

    [Mirsky, 1971] L. Mirsky. A dual of Dilworth’s decompo- sition theorem. The American Mathematical Monthly , 78(8):876–877,

    work page 1971

  21. [21]

    [Roberts, 1977] K. W . S. Roberts. V oting over income tax schedules. Journal of Public Economics , 8(3):329–340,

    work page 1977

  22. [22]

    Simon and P

    [Simon and Trunz, 1994 ] K. Simon and P . Trunz. A cleanup on transitive orientation. In Orders, algorithms, and ap- plications (Lyon,

    work page 1994

  23. [23]

    Skowron, L

    [Skowron et al., 2015] P . Skowron, L. Y u, P . Faliszewski, and E. Elkind. The complexity of fully proportional repre- sentation for single-crossing electorates. Theoretical Com- puter Science, 569:43–57,

    work page 2015

  24. [24]

    [Stearns, 1959] R. Stearns. The voting problem. The Ameri- can Mathematical Monthly , 66(9):761–763, 1959

    work page 1959