Fourier Analysis for Social Choice
Frank Feys
Abstract:
Social choice theory studies mathematically the processes involved when groups of people make choices. There are a number of beautiful and astonishing qualitative results in this area, for example Arrow's Theorem about the non-existence of ideal voting schemes, and the Gibbard-Satterthwaite Theorem about the manipulation of elections. These classical theorems have had tremendous impact on the field of social choice.
Recently, there has been a sequence of stronger, quantitative versions of such theorems, due to Gil Kalai, Ehud Friedgut, Elchanan Mossel, and others. These results depend on the theory of Fourier analysis on the Boolean cube.
In this thesis, we seek to connect the at first seemingly disparate realms of social choice and Fourier analysis on the Boolean cube.
The first goal of this thesis is to study the aforementioned strengthened theorems. The second goal is to make them more accessible to researchers working in social choice. On our way to these results, we build up the theory of Boolean analysis, introducing pivotal notions such as influence and noise. Such concepts are of interest in their own right, as we will try to show by proving classical results such as the KKL Theorem and Friedgut's Theorem. The third goal, then, is to convince the reader that Fourier analysis on the Boolean cube is a worthwhile technique to consider for researchers in social choice. A common theme throughout the thesis is the impartial culture assumption: the contentious mathematical assumption that voters vote independently and randomly of one another. In the last chapter, the final goal is achieved: inspired by Daniel Kahneman's work on cognitive biases, a new, simple, model to simulate the various biases that show up in small meetings involving sequential voting is introduced.
Keywords: Social Choice, Arrow's Theorem, Gibbard-Satterthwaite Theorem, Fourier Analysis, Voting, Elections