I found the following in a book about voting systems, and it is claiming that in this particular situation there always is a Condorcet winner: "Suppose there is an odd number of voters and all voter's preferences are single peaked (ie if we identify the candidates with points on an axis and we represent by a function g the preference of a given voter then g must be either strictly increasing, decreasing, or first increasing and then decreasing, with strict preferences between the candidates), then let i be a voter whose preferred candidate is C, where C is the median or the middlemost of the preferred candidates of all voters, i is called the median-voter. Then C is the Condorcet winner". I understand why C would be a Condorcet winner but I don't understand why such a "median-candidate" C has to exist, and how do we find it? The example was taken from the book "Majority Judgement" by Laraki and Balinski, section 3.3. Thank you.
-
Each voter has a peak, by assumption, and there are an odd number of voters, hence an odd number of peaks Thus the collection of peaks actually realizes it's median. – lulu Nov 30 '17 at 11:39
-
To stress: this is just a consequence of the definition of "median". Odd collections of numbers always realize their median (it's the middle one in the list after you sort the numbers in order). Even collections generally do not (the median is the average of the two middle numbers, hence is not on the list unless the two middle numbers happen to coincide). – lulu Nov 30 '17 at 11:44
1 Answers
In order to understand why median-candidate has to exist, first you have to understand what exactly is meant by "voter's preferences are single peaked" (remember that it is not the same as 1D election).
How do we find Condorcet winner?
Suppose that we have $9$ candidates: $a,b,c,d,e,f,g,i$. Now we can put them on 1D interval. Let's say that $a$ is the most left one and $i$ is the most right one. Then, due to single peaked elections property, we know that if candidate $d$ beats $c$ (i.e. most voters prefer $d$ over $c$) then $d$ beats also $b$ and $a$. Analogously if $d$ beats $e$ than he also beats $f,g,h$ and $i$. Therefore, in order to find a Condorcet winner (without comparing all of the candidates) we can use log-search. We start by comparing two most middle candidates. If the left one win, we compare two most middle candidates of the left half of all candidates, if the right one win, then we compare two most middle candidates of the right half of all candidates and so on. If there are $N$ candidates, then at most in $log(N)$ steps we will find the Condorcet winner.
Btw. the same reasoning will work for 1D elections because single-peaked elections are more general than 1D elections.
- 270