This is a research paper I published in 2014 as my undergraduate thesis. The draft of paper was written in English. But because Tsinghua requires all students to write their graduation theses in Mandarin, I translated the paper to Mandarin.
Recently I dug out the English draft and revise it a little bit. You can find the English version of the paper here on arxiv: Sinya Lee. Maximization of relative social welfare on truthful cardinal voting schemes.
Also here are the reviews I received for the thesis. The reviews are in both English and Mandarin.
If you are interested in the technical details, you can read the paper directly. The remaining part of this article would be a “science journalist” style introduction to the topic of this paper for people without any background.
Gibbard’s Theorem
In 1950 Nobel laureate Kenneth Arrow discovered the Arrows’s impossibility theorem. The theorem is further developed into Gibbard’s theorem in 1973. The theorem says, for any voting system where voters provides their own preference rankings of candidates, any deterministic (without dice rolling) voting scheme must satisfy at least one of the following:
(1) There exist a dictator. All other voters’ preferences don’t count.
(2) There is only two options.
(3) Lying about your real preference (tactical voting) is profitable.
The statement seems a little bit scary at first glance. But actually it’s easy to understand. You can be confident that this theorem is correct by considering the presidential election of the US in 2016. If there is only two options, Hillary Clinton and Donald Trump (2✔), then we can have a democratic election (1✘) and for every voters, their best tactic is to vote for the candidate they prefer (3✘).
However, the election actually has more than two candidates (2✘). Besides the Republican candidate Donald Trump and Democrat candidate Hillary Clinton, there is Libertarian candidate Gary Johnson. As a libertarian, my preference is Gary Johnson > Hillary Clinton > Donald Trump. However, because I know Gary Johnson has no chance winning the presidency, to my best interest, I should lie about my real preference and vote for Hillary (3✔) in the democratic election (1✘). I might get Crooked Hillary, but at least I won’t be deported because of my country of birth, and I won’t have a tax hike because of the cities I live in.
The theorem is actually very interesting in real life. It kind of prove why we have a two party system in the United States. Because of the set up of the voting system, people would always lie to get the result they want, third party will always lose votes in such system. Actually in the history of America, major parties appeared and disappeared, and even swap positions. But there are always two major parties.
And the theorem is also related to the controversial ranked choice voting system in Maine during the 2018 midterm election several months ago. By the theorem, this system is still vulnerable to tactical voting. But at least popular third party candidates would have a better chance winning the election.
Cardinal Voting
The problem this paper discuss is the cardinal voting system, which means voters not only choose their preference ranking, but also give score ratings to each candidates. Our goal is to maximize the social welfare (sum of people’s rating on the winner) in a voting system.
The best voting system is simply picking the one with highest score. Unfortunately this scheme is vulnerable to tactical voting. My paper is to find the best non-dictatorial, truthful (invulnerable to tactical voting) system which maximize the social welfare. With some more assumptions, we found out that one of the best voting system is as follow:
Pick a random voter, then flip a coin. If it’s the head, choose that voter’s favorite candidate. If it’s the tail, choose a random winner from that voter’s m^(1/3) favorite candidates, where m is the number of total candidates.
This result is interesting. At first glance the result seems depressing since it proves that the best we can do is to pick a random dictator. But actually this random dictator system is very similar to the jury trial system in common law countries like United States and Hong Kong. Even though the result of a trial is determined by a very small group of people, but because the jurors are chosen randomly, it is still kind of a fair system on average.
