Sökning: onr:"swepub:oai:gup.ub.gu.se/136789" >
The geometry of man...
-
Isaksson, Marcus,1978Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper, matematisk statistik,Department of Mathematical Sciences, Mathematical Statistics,University of Gothenburg,Chalmers tekniska högskola,Chalmers University of Technology
(författare)
The geometry of manipulation - A quantitative proof of the gibbard satterthwaite theorem
- Artikel/kapitelEngelska2010
Förlag, utgivningsår, omfång ...
Nummerbeteckningar
-
LIBRIS-ID:oai:gup.ub.gu.se/136789
-
ISBN:9780769542447
-
https://gup.ub.gu.se/publication/136789URI
-
https://doi.org/10.1109/FOCS.2010.37DOI
-
https://research.chalmers.se/publication/136789URI
Kompletterande språkuppgifter
Ingår i deldatabas
Klassifikation
-
Ämneskategori:ref swepub-contenttype
-
Ämneskategori:kon swepub-publicationtype
Anmärkningar
-
We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function f of q >= 4 alternatives and n voters will be manipulable with probability at least 10(-4)epsilon(2)n(-3)q(-30), where epsilon is the minimal statistical distance between f and the family of dictator functions. Our results extend those of [1], which were obtained for the case of 3 alternatives, and imply that the approach of masking manipulations behind computational hardness (as considered in [2], [3], [4], [5], [6]) cannot hide manipulations completely. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of 3 or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies.
Ämnesord och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Kindeler, G.The Hebrew University Of Jerusalem
(författare)
-
Mossel, E.Weizmann Institute of Science,University of California
(författare)
-
Göteborgs universitetInstitutionen för matematiska vetenskaper, matematisk statistik
(creator_code:org_t)
Sammanhörande titlar
-
Ingår i:2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010; Las Vegas, NV; 23 October 2010 through 26 October 2010:Article number 5671191, s. 319-3280272-54289780769542447
Internetlänk
Hitta via bibliotek
Till lärosätets databas