Single-Peaked Consistency for Weak Orders Is Easy

Zack Fitzsimmons
(Rochester Institute of Technology)

In economics and social choice single-peakedness is one of the most important and commonly studied models for preferences. It is well known that single-peaked consistency for total orders is in P. However in practice a preference profile is not always comprised of total orders. Often voters have indifference between some of the candidates. In a weak preference order indifference must be transitive. We show that single-peaked consistency for weak orders is in P for three different variants of single-peakedness for weak orders. Specifically, we consider Black's original definition of single-peakedness for weak orders, Black's definition of single-plateaued preferences, and the existential model recently introduced by Lackner. We accomplish our results by transforming each of these single-peaked consistency problems to the problem of determining if a 0-1 matrix has the consecutive ones property.

In R Ramanujam: Proceedings Fifteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2015), Carnegie Mellon University, Pittsburgh, USA, June 4-6, 2015, Electronic Proceedings in Theoretical Computer Science 215, pp. 127–140.
Published: 23rd June 2016.

ArXived at: http://dx.doi.org/10.4204/EPTCS.215.10 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org