Topics in Hardness of Approximation and Social Choice Theory
Marcus Isaksson · Chalmers Research (Chalmers University of Technology) · 2010
Tools from Fourier analysis of Boolean functions have commonly been used to prove results both in hardness of approximation in computer science and in the study of voting schemes in social choice theory. In this thesis we consider various topics in both these contexts.In hardness of approximation we study the asymptotic approximation curve of MAX-CSP's for predicates given by linear threshold functions and prove upper and lower bounds for this curve for majority-like threshold functions.We also relate the hardness of MAX-q-CUT to a conjecture in Gaussian isoperimetry and the plurality is stablest conjecture in social choice. In particular the Frieze-Jerrum semidefinite programming based algorithm for MAX-q-CUT achieves the optimal approximation factor assuming the unique games conjecture if plurality is indeed stablest. In social choice theory we show a quantitative version of the Gibbard-Satterthwaite Theorem, showing that for election schemes in elections with more than 2 candidates, situations in which a voter has an incentive tomanipulate by not voting according to his true preference are common enough that they cannot completely be masked behind computational hardness. We also prove a generalization of a Gaussian isoperimetricresult by Borell and show that it implies that the majority function is optimal in Condorcet voting in the sense that it maximizes the probability that there is a single candidate which the society prefers over all other candidates.