Ballots: what is out there?

A team project for MA279, Fall 2013

Team members: Qianyu Deng, Sui Fang, Weichen Gai, Chenkai Wang, Bolun Zhang

Introduction (Chenkai Wang)

The main purpose of using ballots in an election is to record the opinions of electorates and their preferences of the candidates. The goal is to determine a winner from the candidates. Ballots come in many physical forms, such as a piece of paper or a digital document stored in a computer. The actual format of a ballot is called voting system or voting method. A voting system has several built-in rules in order to ensure fair voting during the election. Another functionality of a voting system is counting the voting from ballots to determine a final winner. So to specify a valid voting system, we have to describe two key ingredients: allowable votes, i.e., ballots and the algorithms of collecting votes. In this study, we will study how various voting systems are designed and reveal the mathematical reasons in designing these voting systems.

Fairness Criteria

In order to minimize biased opinions in a voting system, we use fairness criteria to measure the "fairness" of a particular voting system. A fairness criteria is a mathematical description of the rules a voting systems uses. In a formal mathematical treatment, we can define the mathematical meaning of the word "fairness" according to these criteria. Here we describe three important criteria and end with Arrow's impossibility theorem. First, we have the following definition.

Definition Let $ C $ be the finite set of candidates and $ N $ be the finite set of voters. Let $ L $ be the set of all total (linear) ordering on $ C $, i.e., it's the space of all possible ballots submitted by voters. Note since all underlying sets are finite, there is no difference between total ordering and well ordering. Each total ordering assigns a unique natural number $ 1\leq\mathrm{rank}(a)\leq|C| $ to all candidates $ a\in C $ since a finite well ordering is isomorphic to a unique finite ordinal number. A social welfare function is a function $ f:L^N\rightarrow L $. The domain of $ f $ is called the set of preference profiles. A generic element of $ L^N $ has the form $ \langle \leq_1, \leq_2,\cdots,\leq_N \rangle $, where $ \leq_i $ are total ordering on $ C $, i.e., one generic element (preference profile) represents a possible outcome of all voters. A social welfare function represents the process of choosing the winner from one generic preference profile, i.e., giving the final total ordering of the candidates. Let's denote $ f(\leq_1,\cdots,\leq_N) $ by the single symbol $ \leq $.

Unanimity

Definition Let $ a,b\in C $, if $ \forall i\in N(a<_ib) $, then $ a<b $. In words, if every voters prefer one candidate to another, this order should be preserved in the final decision.

Independence of Irrelevant Alternatives

Definition Let $ r,s\in L^N $ and $ a\in C $, if $ \mathrm{rank}_r(a)=\mathrm{rank}_s(a) $, then $ \mathrm{rank}_{f(r)}(a)=\mathrm{rank}_{f(s)}(a) $. In other words, if one candidate has the same ranks in two preference profiles, the rank should also be the same in two corresponding final decisions.

Non-dictatorship

Definition There is no $ i\in N $ such that if $ \langle\leq_1,\cdots,\leq_N\rangle\in L^N $, we have $ f(\leq_1,\cdots,\leq_N)=\leq_i $. In words, the final decision should be different from all elements in a preference profile.

Arrow's Impossibility Theorem

Theorem There is no social welfare function satisfies the criteria of unanimity, independence of Irrelevant Alternatives, and non-dictatorship for candidates of size greater than three.

Copeland Method (Sui Fang)

History

Copeland method is a Condorcet method to elect winners by using pairwise comparison that the order of candidates is ranked by the difference between the number of pairwise wins and the number of pairwise loses. Supporters argue that this method is fairly understandable and practical in our daily life. Moreover, it is easy for us to calculate data and get results. However, others believe that this method cannot deal with all cases. “When there is Condorcet winner, Copeland method usually meets ties.”—(Wiki) In addition, opponents think this method pay too much attention to the number of rounds’ victories and defeats instead of quantities of voters for candidates. Then I will use two examples from website to show how to apply this method and what problems are with this method.

How it works?