On Detecting Nearly Structured Preference Profiles


  • Edith Elkind University of Oxford
  • Martin Lackner Vienna University of Technology




Algorithms, Computational Social Choice, Domain Restrictions, Preferences, Approximation Algorithms


Structured preference domains, such as, for example, the domains of single-peaked and single-crossing preferences, are known to admit efficient algorithms for many problems in computational social choice. Some of these algorithms extend to preferences that are close to having the respective structural property, i.e., can be made to enjoy this property by performing minor changes to voters' preferences, such as deleting a small number of voters or candidates. However, it has recently been shown that finding the optimal number of voters or candidates to delete in order to achieve the desired structural property is NP-hard for many such domains. In this paper, we show that these problems admit efficient approximation algorithms. Our results apply to all domains that can be characterized in terms of forbidden configurations; this includes, in particular, single-peaked and single-crossing elections. For a large range of scenarios, our approximation results are optimal under a plausible complexity-theoretic assumption. We also provide parameterized complexity results for this class of problems.




How to Cite

Elkind, E., & Lackner, M. (2014). On Detecting Nearly Structured Preference Profiles. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8823



AAAI Technical Track: Game Theory and Economic Paradigms