Multi-Dimensional Single-Peaked Consistency and Its Approximations Xin Sui Alex Francois-Nienaber Craig Boutilier
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 both single-dimensional and multi-dimensional approximations to explain preference pro?les drawn from several real-world elections. We develop a simple branch-andbound algorithm that ?nds multi-dimensional, singlepeaked axes that best ?t a given pro?le, 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 onedimensional space, but are nearly single-peaked in two dimensions. Our algorithms are reasonably ef?cient in practice, and also show excellent anytime performance.