Single-crossing Implementation

Nathann Cohenn, Edith Elkind and Foram Lakhani

Papers from arXiv.org

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.

Date: 2019-06
New Economics Papers: this item is included in nep-cdm
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/1906.09671 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:1906.09671

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().