Dear all,
The next Computational Social Choice Seminar at the ILLC will take place next week on Tuesday at 16:00 and will be delivered by Frank Feys (TU Delft), who will talk about a new proof of Arrow's Theorem based on a fixed-point argument. I'm including the abstract below.
As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.
All the best, Ulle
-------------------------------------------------------------------------
Speaker: Frank Feys (Delft) Title: Arrow's Theorem through a Fixpoint Argument Date: Tuesday 25 June 2019 Time: 16:00 Location: Room F2.19, Science Park 107, Amsterdam
Abstract: Social choice theory studies mathematically the processes involved when groups of people make choices. The classical result that has inspired much of the research in this area is Arrow's impossibility theorem about the non-existence of ideal election systems. Arrow's original proof proceeded by showing the existence of a "decisive" voter. In this talk, we present a proof of Arrow’s theorem that uses a fixpoint argument. Specifically, we use Banach’s fixpoint theorem, which states that a contractive map on a complete metric space has a unique fixpoint. To this end, we first define a metric parametrized by a probability distribution on profiles: we let the distance between two voting rules be the probability under the given distribution that the outcome of the election is different. The use of a distribution has the benefit that it allows for profiles to be considered concurrently. Inspired by the technical notion of influence from Boolean analysis, we then define a notion that we call "force" of a voter, which is the probability that the outcome of the election coincides with that voter’s preference. We use this notion to define a map (a process that transforms voting rules) which is shown to be a contraction with the set of dictators as unique fixpoint. Our proof does not require us to manipulate specific profiles, like most other previous proofs of Arrow’s theorem, but offers an analytic perspective in terms of fixpoints and convergence rather than a combinatoric one. Conceptually, our approach shows that dictatorships can be seen as "stable points" (fixpoints) of a certain process. This talk is based on joint work with Helle Hvid Hansen.