Nowadays, computer science is present in all spheres of life, thus making its techniques an option in supporting societal decision-making. Electronic elections are one example, but there is a far wider range of application.
From June 7 to 12, 2015, leading international computer scientists from different fields as well as economists and social and political scientists met at Schloss Dagstuhl – Leibniz Center for Informatics in northern Saarland, Germany, in order to discuss the state of the art as well as further challenges in the field of computational social choice.
The interdisciplinary field of computational social choice connects computer science to the theory of collective decisions, usually known as social choice theory, and promotes the exchange between both disciplines. An exemplary research question in social choice theory is how to define fair distribution of resources: Is it necessary for each person to have the same, or enough so that no one envies anyone else, or is it sufficient to ensure a certain minimum standard? Theories in collective decision-making such as this have recently been applied in computer science, for instance in the context of fair distribution of computation time on a supercomputer among scientists. Vice versa, traditional methods of computer science play a role in social choice theory, for instance regarding the development of fast algorithms for highly complex distribution patterns.
Foodbank Australia, an Australian aid organization that provides food for those in need, is concerned with the fair distribution of resources. Computer science professor Toby Walsh, Sydney, participated in the Dagstuhl Seminar „Computational Social Choice: Theory and Applications“ in June 2015. He talked about techniques he has developed that help Foodbank Australia to work more effectively, seeing that the requests for help rise by 10 per cent every year. Professor Walsh’s contribution promotes an even distribution of the donated food among different charity organizations. One of the most important innovations is the possibility to donate and distribute online. Food donations can be made via an app, which also determines ideal routes for collection and delivery by using the vehicles‘ route planner. Food donations are made virtually all day, and are allotted and distributed immediately, i.e. while the total amount of donated food is still unknown.
Not only the fair distribution of resources, but also matching problems are an issue in computational social choice. This problem arises, for example, in the context of kidney transplantation. There are numerous patients all over the world waiting for a matching donor kidney. Although there might be a donor willing to help, the transplant might be impossible due to blood type or tissue type incompatibility. In such cases, the patient may exchange the donated kidney for that of another patient in a similar situation provided a matching donor-recipient pair can be found. Frequently, an exchange is only possible if there are more than two pairs participating and if there is a chain or a circle of donor-recipient pairs: the donor of pair A gives a kidney to the recipient of pair B; the donor kidney of pair B is a match for the recipient of pair C, and the donor of pair C gives a kidney to the recipient of pair A.
Since early 2007, the British National Health Service Blood and Transplant authority has been operating a distribution pattern for living-donor kidney transplantation that has taken into account scientific results gained by computer science professor David Manlove, University of Glasgow. Professor Manlove, who also participated in the Dagstuhl Seminar on computational social choice, has developed an optimized method for finding matching donors and recipients. Thanks to this method, there have been 427 successful transplantations since 2008, in contrast to only eight transplantations in 2007. This illustrates how techniques and results in computer science can be put to use effectively in everyday life.
Techniques of social choice theory are also applied in elections. Annick Laruelle, Professor of economics at the University of the Basque Country, considers the question of how citizens may express their discontent regarding politicians by way of elections. Up to now, the only possibility is for citizens to abstain from voting or to cast an empty ballot. However, this form of election boycott is not taken into account. Professor Laruelle has developed a method with which each voter may cast one positive, negative or neutral vote per candidate. The candidate who gains the highest difference between positive and negative votes is elected. Giving citizens the opportunity to express their discontent might be a way to raise turnout, which is of tremendous importance. After all, voter participation is the beating heart of democracy.
The Dagstuhl Seminar not only dealt with applications, but also with theoretical concepts. In general, computational social choice is concerned with collective decision-making, whereby the aim is to reach solutions that are as „fair“ as possible. The first challenge is to determine whether there can be a solution at all, or to show under which conditions a solution can be found. Thus, there are many aspects to be taken into account regarding the problem and its solution. Especially the great variety of different aspects makes it necessary to consider interdisciplinary expertise.
The organizers of the Dagstuhl Seminar succeeded in bringing together scientists from different disciplines at Schloss Dagstuhl, thus promoting the field of computational social choice. The seminar participants finally agreed that many research questions in social choice theory come out of everyday life and are applied, for example, in industry or politics. In this context, theoretical studies are of great importance in order to facilitate real applications and to ensure their high quality. Vice versa, specific characteristics and fringe conditions of tangible applications introduce theoretical questions that have to be solved by foundational research.
The organizers of the Dagstuhl Seminar were:
- Craig Boutiller (Universität Toronto, CA)
- Britta Dorn (Universität Tübingen, DE)
- Nicolas Maudet (UPMC – Paris, FR)
- Vincent Merlin (Universität Caen, FR)
For further information about the Dagstuhl Seminar „Computational Social Choice: Theory and Applications“ including a list of participants, please see http://www.dagstuhl.de/15241
