On Recognising Nearly Single-Crossing Preferences

Florian Jaeckle, Dominik Peters, Edith Elkind

Abstract

If voters' preferences are one-dimensional, many hard problems in computational social choice become tractable. A preference profile can be classified as one-dimensional if it has the single-crossing property, which requires that the voters can be ordered from left to right so that their preferences are consistent with this order. In practice, preferences may exhibit some one-dimensional structure, despite not being single-crossing in the formal sense. Hence, we ask whether one can identify preference profiles that are close to being single-crossing. We consider three distance measures, which are based on partitioning voters or candidates or performing a small number of swaps in each vote. We prove that it can be efficiently decided if voters can be split into two single-crossing groups. Also, for every fixed k >
BibTeX
@inproceedings{jaeckle2018recognising,
  author = {Florian Jaeckle and Dominik Peters and Edith Elkind},
  title = {{On Recognising Nearly Single-Crossing Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11461},
}

Loading related content...

Figure