Multi-Dimensional Single-Peaked Consistency and Its Approximations

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 \emph{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 \emph{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.