Decision Sciences & Systems
Technical University of Munich

Dominik Peters (University of Oxford): Total Unimodularity and Single-Peakedness + Recognising Multidimensional Euclidean Preferences

Wednesday, 06 April 2016 11:00
(1) We report on ongoing work that uses totally unimodular mixed-integer programs to obtain polynomial-time algorithms for problems in committee selection when preferences are required to be single-peaked.
(2) Euclidean preferences are a widely studied preference model, in which decision makers and alternatives are embedded in d-dimensional Euclidean space. Decision makers prefer those alternatives closer to them. This model, also known as multidimensional unfolding, has applications in economics, psychometrics, marketing, and many other fields. We study the problem of deciding whether a given preference profile is d-Euclidean. For the one-dimensional case, polynomial-time algorithms are known. We show that, in contrast, for every other fixed dimension d > 1, the recognition problem is equivalent to the existential theory of the reals (ETR), and so in particular NP-hard. We further show that some Euclidean preference profiles require exponentially many bits in order to specify any Euclidean embedding, and prove that the domain of d-Euclidean preferences does not admit a finite forbidden minor characterisation for any d > 1. We also study dichotomous preferences and the behaviour of other metrics, and survey a variety of related work.

All Dates

  • Wednesday, 06 April 2016 11:00

Powered by iCagenda

Decision Sciences & Systems (DSS), Department of Informatics (I18), Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany
©2002-2017 DSS All Rights Reserved
Impressum, Privacy Policy, Copyright Information and Disclaimer