On Recognising Nearly Single-Crossing Preferences

2018-02-08

Proceedings of the AAAI Conference on Artificial Intelligence, 32

Volume

Thirty-Second AAAI Conference on Artificial Intelligence 2018

AAAI Technical Track: Game Theory and Economic Paradigms

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.

10.1609/aaai.v32i1.11461