Math Department (Thesis/2012-13)

# Extensions of Condorcet's Paradox of Voting

## Under the direction of: William Zwicker

Dear Students, I've found that it is very helpful for students to get a head start by doing some background reading before the official start of a thesis. If you will be working with me, please get in touch as soon as you know - in particular, at least 2 weeks before exams for Spring term 2012. Drop by my office (Bailey 200B) or send e-mail: zwickerw@union.edu.

A student working on this topic should have strong programming skills.

Imagine that $a, b,$ and $c$ are three candidates for president, and three voters $v1, v2, v3$ have the following preferences: $\begin{array}{ccc} v_{1} & v_{2}& v_{3} \\ a& c &b \\ b& a &c \\ c& b &a \\ \end{array}$

This means that $v1$'s favorite candidate is $a$, her second favorite is $b$, and her least favorite is $c$; $v2$'s favorite is $c$, etc.

Notice that two-thirds of the voters prefer $a$ to $b$, two-thirds prefer $b$ to $c$ and two-thirds prefer $c$ to $a$. This means that whichever candidate is elected, two-thirds of the voters can name a single alternative candidate whom they prefer. This simple but puzzling situation is Condorcet's paradox of voting - it lies at the heart of much of the mathematical theory of voting.

Now suppose we were electing a committee $C$ of candidates, and we want the committee to be "stable" in the sense that for each candidate $y$ outside $C$ there is at least one candidate $x$ inside $C$ who is preferred to $y$ by a majority of voters. Condorcet's paradox tells us that to be stable, a committee may need to have more than one member. So, do two-person stable committees always exist? Recently, a group of researchers from Paris and Singapore found a relatively simple example for which no stable two-person committee exists; their example has 15 voters and 15 candidates. Even more recently, two of us at Union found smaller examples, which are more complicated. Do stable committees of size 3 always exist? How can we understand the structure of these examples? There is a wealth of related questions we can explore.

1- or 2-term thesis

 Math Department web pages Created: 25 Apr 2007 Last modified: 02 May 2012 10:53:31 Comments to: math@union.edu