In the last semester of my bachelor's journey, I decided to take a course about algorithmic game theory. In the end, we did this fun, small project with Henry Fleischmann, where we managed to design a mechanism that addresses the gerrymandering1 problem, proving it has the desired properties. The following is a quick summary of our project.
We describe our model of the problem. Our goal is to design a fair rule to get a redistricting map based on a selected group of commissioners while being aware that
- There are three types of commissioners, i.e., independent commissioners, Democrats, and Republicans.
- Some groups of commissioners might collude together, trying to manipulate the outcome.
The usual model of a voting scheme is known as the social-choice function under the context of algorithmic game theory. The basic idea is to collect everyone's preferences profile and return a final result, and in our project, we want to design a social-choice function that collects commissioners' preferences for maps and returns one at the end.
As one might expect, defining fairness is not a trivial thing to do. In our example, we want to achieve at least the following.
Group Strategy Proof
The group strategyproofness is a generalized notion of strategyproofness, where even if a group of voters colludes to misreport their preferences, there's no way they can improve their utility (i.e., achieving their goal such as selecting a map that is biased to a particular party). In other words, even if a group of people can collude, being truthful is the best strategy.
We want to always select an unbiased map such that no particular party benefits. We refer to such an unbiased map as a neutral map. Notice that this is a desired property directly controlling the outcome of the voting rule to produce a fair outcome.
We see that by combining group strategyproofness and unbiased map property, there's no way to manipulate the mechanism.
Now we describe our technical contribution. Assuming that we have three maps, biased toward Democrats, Republicans, and neutral respectively. Then, by considering a simple positional-scoring rule with score on commissioners' preference on these three types of maps, we prove the following.
Theorem Supposes that the commission is composed of an equal number of Democrats and Republicans and at least one Independent commissioner, , or .2 Then, the positional-scoring voting rule with scores , respectively, is group strategy-proof and chooses a neutral map.
The equal number of Democrats and Republicans is referred to as the balanced case.3
- We assume that even an independent commissioner has his/her preference as a weak Democrat/Republican. This is a fair assumption since the preference of an independent commissioner is expected to be either "neutral mapDemocrats mapRepublicans map" (i.e., weak Democrats, ) or "neutral mapRepublicans mapDemocrats map" (i.e., weak Republicans, ).↩
- It's possible to relax the result to the unbalanced case with some adjustments to the scoring. See the paper for details.↩