On Recognising Nearly Single-Crossing Preferences

Authors

  • Florian Jaeckle University of Oxford
  • Dominik Peters University of Oxford
  • Edith Elkind University of Oxford

DOI:

https://doi.org/10.1609/aaai.v32i1.11461

Keywords:

social choice, structured preferences, preferences, single-crossing, single-peaked, recognition algorithm

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 >= 1 we can decide in polynomial time if a profile can be made single-crossing by performing at most k candidate swaps per vote. In contrast, for each k >= 3 it is NP-complete to decide whether candidates can be partitioned into k sets so that the restriction of the input profile to each set is single-crossing.

Downloads

Published

2018-04-25

How to Cite

Jaeckle, F., Peters, D., & Elkind, E. (2018). On Recognising Nearly Single-Crossing Preferences. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11461

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms