transparent gif

 

Ej inloggad.

Göteborgs universitets publikationer

The geometry of manipulation - A quantitative proof of the Gibbard-Satterthwaite theorem

Författare och institution:
Marcus Isaksson (Institutionen för matematiska vetenskaper, matematisk statistik, Chalmers/GU); G. Kindler (-); E. Mossel (-)
Publicerad i:
Combinatorica, 32 ( 2 ) s. 221-250
ISSN:
0209-9683
Publikationstyp:
Artikel, refereegranskad vetenskaplig
Publiceringsår:
2012
Språk:
engelska
Fulltextlänk:
Sammanfattning (abstract):
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 a parts per thousand yen 4 alternatives and n voters will be manipulable with probability at least 10(-4)a(2) n (-3) q (-30), where a is the minimal statistical distance between f and the family of dictator functions. Our results extend those of [11], which were obtained for the case of 3 alternatives, and imply that the approach of masking manipulations behind computational hardness (as considered in [4,6,9,15,7]) 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.
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
NATURVETENSKAP ->
Matematik
Nyckelord:
voting schemes
Postens nummer:
159857
Posten skapad:
2012-07-02 11:52
Posten ändrad:
2016-08-18 13:24

Visa i Endnote-format

Göteborgs universitet • Tel. 031-786 0000
© Göteborgs universitet 2007