Elisa Celis and Nisheeth Vishnoi
Elections are the nervous system of a democracy and, hence, issues related to their transparency and fairness are central to healthy societies. However, the number of controversial elections has exploded since 2000, and the more recent ones involve the use of the Internet and algorithms — a good excuse for computer scientists to get involved in elections to save democracy!
Last year, the two of us and Lingxao Huang revisited the question of fairness in multi-winner elections. A multi-winner election is one where the objective is to select a committee from a set of candidates based on voter preferences. However, election systems for multi-winner elections have been shown to be biased against minorities by giving preference to committees that under-represent their already-small numbers. When the candidates have certain sensitive attributes (such as gender), and different types (e.g., male, female and non-binary) we may instead wish to impose additional requirement so that the winning committee is fair. We considered the problem of finding the committee with the maximum number of votes, subject to such additional fairness requirements.
But what does it mean to be fair?
Is a committee fair when types are equally represented? Or proportionally represented? These questions have received more than a century’s worth of attention in social choice theory and are deeply entangled with culture and politics. In short, fairness means different things in different contexts and rather than addressing a specific instance of this question, we asked ourselves — can we provide a framework in which a user can specify fairness constraints according to their needs and design algorithms that can compute the winning committee accordingly?
Because such a framework must handle general classes of constraints, the algorithmic task became more challenging than the usual unconstrained case. If you are interested in understanding our algorithmic and complexity results, they appear in our recent paper that was presented at IJCAI-ECAI this year.
Clearly, however, there are real merits to providing such generality — earlier this year, our paper caught the eye of members of a people’s movement from the Valais canton in Switzerland, who were in the process of rethinking elections in their region. They were happy to know that we had solved the exact problem they needed for a primary election and asked us if we would be willing to help them conduct their elections. We were, of course, thrilled!
After an intense collaboration for more than four months, 8 elections that used our framework concluded on September 9, 2018. For us, there were several eye-opening aspects of taking our algorithmic framework from theory to practice. Perhaps the most interesting one was coming up with an answer to:
Who decides what is fair?
In this case, it was the voters! Before voting on the committee, a vote to determine the fairness constraints was conducted in each of the eight districts. This vote was in mid-June and also checked if the voters agree to use our algorithmic framework. Since transparency was the key motivation, prior to this vote, we were invited to a press conference to educate the people about the whole process that resulted in coverage in newspapers Le Temps, Le Nouvelliste, TV channel Canal 9, and radio channels Rhone FM and Radio Chablais.
An image from the press conference in Sion on June 12, 2018. Elisa Celis (center), accompanied by members of Appel Citoyen.
In the end, the voters decided to place constraints on the gender balance, age demographics, and regions. While all districts approved these same three attributes, the specific constraints varied by district according to their demographics and pre-defined regions. This was a truly open and democratic way to determine the criteria by which the committee was to be balanced. The constraints not only ensured that the outcome would be fair (as defined by the voters) but also encouraged many more women to run for election than the party originally anticipated — in fact, in several districts there were more women than men contesting the election!
Computing the winning committees in Sion on September 9, 2018. From L to R: Lingxiao Huang, Vijay Keswani, Elisa Celis, Florian Evequoz, Bernadette Morand-Aymon.
Everything about these elections, from votes, candidates, constraints, and code, to the output, is open for all to verify. We have also made available a demo with pre-loaded constraints, candidate information, and votes for anyone to test and compute the results. To know more about the use of our algorithm in these elections, take a look at this video. A few links to the coverage of these elections can be found here: Canal 9, Le Temps, Le Nouvelliste.
We feel fortunate that we were given this unique opportunity to take tools from computer science to the heart of a democratic process. It was an unparalleled learning experience for all of us and something that we increasingly look forward to in the future.
You can also use our demo to design your own elections and play around with our algorithms. This demo was developed with the help of Abhibhav Garg and Vijay Keswani and has limited functionality. If you are interested in using our full framework and/or working with us, please feel free to contact us.
Algorithms, Nature, and Society 