TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 19.11.2015


Page Content

to Navigation

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.


Jiehua Chen
TEL 512


Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe