Multi-Dimensional Single-Peaked Consistency and Its Approximations

Sui, Xin; Francois-Nienaber, Alex; Boutilier, Craig

Multi-Dimensional Single-Peaked Consistency and Its Approximations

Xin Sui, Alex Francois-Nienaber, Craig Boutilier

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 375-381.

Abstract

Single-peakedness is one of the most commonly used domain restrictions in social choice. However, the extent to which agent preferences are single-peaked in practice, and the extent to which recent proposals for approximate single-peakedness can further help explain voter preferences, is unclear. In this article, we assess the ability of both single-dimensional and multi-dimensional approximations to explain preference profiles drawn from several real-world elections. We develop a simple branch-and-bound algorithm that finds multi-dimensional, single-peaked axes that best fit a given profile, and which works with several forms of approximation. Empirical results on two election data sets show that preferences in these elections are far from single-peaked in any one-dimensional space, but are nearly single-peaked in two dimensions. Our algorithms are reasonably efficient in practice, and also show excellent anytime performance.

Xin Sui, Alex Francois-Nienaber, and Craig Boutilier. 2013. Multi-Dimensional Single-Peaked Consistency and Its Approximations. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 375–381. https://ijcai.org/proceedings/2013/63

@inproceedings{ijcai2013p63,
  title     = {Multi-Dimensional Single-Peaked Consistency and Its Approximations},
  author    = {Sui, Xin and Francois-Nienaber, Alex and Boutilier, Craig},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {375--381},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/63},
}

TY  - CPAPER
TI  - Multi-Dimensional Single-Peaked Consistency and Its Approximations
AU  - Sui, Xin
AU  - Francois-Nienaber, Alex
AU  - Boutilier, Craig
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 375
EP  - 381
UR  - https://ijcai.org/proceedings/2013/63
ER  -