Algorithmics and Computational Complexity Research GroupTalk 19.11.2015

# On the One-Dimensional Euclidean Domain

Jiehua Chen (TU Berlin)

Consider a preference profile where each voter has a ranking over a number of alternatives. We say that this profile is one-dimensional Euclidean if there is an embedding of the alternatives and the voters into the real numbers such that every voter ranks alternatives that are embedded closer to him higher than alternatives which are embedded further away.

One-dimensional Euclidean profiles are necessarily single-peaked and single-crossing; single-peakedness describes a natural order of the alternatives, and single-crossingness describes a natural order of the voters.

While it is known that both the single-peaked domain and the single-crossing domain can be characterized by finitely many obstructions, we show that this is not the case for the one-dimensional Euclidean domain. In this talk, we demonstrate that for any number $k\ge 4$, we can construct a preference profile with $2k$ voters and $4k$ alternatives which is not one-dimensional Euclidean, but the deletion of an arbitrary voter from it yields a one-dimensional Euclidean profile.

Date
Speaker
Location
Language
19.11.2015
16:15
Jiehua Chen
TEL 512
English

Back to the research colloquium site.