Szczegóły publikacji
Opis bibliograficzny
Recognizing 1-Euclidean preferences: an alternative approach / Edith Elkind, Piotr FALISZEWSKI // W: Algorithmic game theory : 7th international symposium, SAGT 2014 : Haifa, Israel, September 30–October 2, 2014 : proceedings / ed. Ron Lavi. — [Berlin, etc.] : Springer, 2014. — (Lecture Notes in Computer Science ; ISSN 0302-9743 ; LNCS 8768). — ISBN: 978-3-662-44802-1; e-ISBN: 978-3-662-44803-8. — S. 146–157. — Bibliogr. s. 157, Abstr.
Autorzy (2)
- Elkind Edith
- AGHFaliszewski Piotr
Dane bibliometryczne
| ID BaDAP | 85083 |
|---|---|
| Data dodania do BaDAP | 2014-11-17 |
| Rok publikacji | 2014 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | International Symposium on Algorithmic Game Theory 2014 |
| Czasopismo/seria | Lecture Notes in Computer Science |
Abstract
We consider the problem of detecting whether a given election is 1-Euclidean, i.e., whether voters and candidates can be mapped to points on the real line so that voters' preferences over the candidates are determined by the Euclidean distance. A recent paper by Knoblauch [14] shows that this problem admits a polynomial-time algorithm. Knoblauch's approach relies on the fact that a 1-Euclidean election is necessarily single-peaked, and makes use of the properties of the respective candidate order to find a mapping of voters and candidates to the real line. We propose an alternative polynomial-time algorithm for this problem, which is based on the observation that a 1-Euclidean election is necessarily singe-crossing, and we use the properties of the respective voter order to find the desired mapping.
