CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

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

Marcus Isaksson (Institutionen för matematiska vetenskaper, matematisk statistik) ; G. Kindler ; E. Mossel
Combinatorica (0209-9683). Vol. 32 (2012), 2, p. 221-250.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: voting schemes

Denna post skapades 2012-07-02. Senast ändrad 2016-08-18.
CPL Pubid: 159857


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematisk statistik (2005-2016)



Chalmers infrastruktur