| 1. |
- Isaksson, Marcus, 1978, et al.
(författare)
-
Maximally stable Gaussian partitions with discrete applications
- 2012
-
Ingår i: Israel Journal of Mathematics. - : Springer Science and Business Media LLC. - 0021-2172 .- 1565-8511. ; 189:1, s. 347-396
-
Tidskriftsartikel (refereegranskat)abstract
- Gaussian noise stability results have recently played an important role in proving results in hardness of approximation in computer science and in the study of voting schemes in social choice. We prove a new Gaussian noise stability result generalizing an isoperimetric result by Borell on the heat kernel and derive as applications: An optimality result for majority in the context of Condorcet voting. A proof of a conjecture on "cosmic coin tossing" for low influence functions. We also discuss a Gaussian noise stability conjecture which may be viewed as a generalization of the "Double Bubble" theorem and show that it implies: A proof of the "Plurality is Stablest Conjecture". That the Frieze-Jerrum SDP for MAX-q-CUT achieves the optimal approximation factor assuming the Unique Games Conjecture.
|
|
| 2. |
- Isaksson, Marcus, 1978, et al.
(författare)
-
The geometry of manipulation - A quantitative proof of the gibbard satterthwaite theorem
- 2010
-
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. - 0272-5428. - 9780769542447 ; :Article number 5671191, s. 319-328
-
Konferensbidrag (refereegranskat)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 >= 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.
|
|
| 3. |
- Isaksson, Marcus, 1978, et al.
(författare)
-
The geometry of manipulation - A quantitative proof of the Gibbard-Satterthwaite theorem
- 2012
-
Ingår i: Combinatorica. - : Springer Science and Business Media LLC. - 0209-9683 .- 1439-6912. ; 32:2, s. 221-250
-
Tidskriftsartikel (refereegranskat)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.
|
|
