The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem - Mathematics > CombinatoricsReportar como inadecuado




The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We prove a quantitative version of the Gibbard-Satterthwaite theorem. We showthat a uniformly chosen voter profile for a neutral social choice function f of$q \ge 4$ alternatives and n voters will be manipulable with probability atleast $10^{-4} \eps^2 n^{-3} q^{-30}$, where $\eps$ is the minimal statisticaldistance between f and the family of dictator functions. Our results extendthose of FrKaNi:08, which were obtained for the case of 3 alternatives, andimply that the approach of masking manipulations behind computational hardnessas considered in BarthOrline:91, ConitzerS03b, ElkindL05, ProcacciaR06 andConitzerS06 cannot hide manipulations completely. Our proof is geometric. Morespecifically it extends the method of canonical paths to show that the measureof the profiles that lie on the interface of 3 or more outcomes is large. Tothe best of our knowledge our result is the first isoperimetric result toestablish interface of more than two bodies.



Autor: Marcus Isaksson, Guy Kindler, Elchanan Mossel

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados