Cloud computing techniques for winner determination in computational social choice

Abstract

This work deals with the development of cloud-computing algorithms for problems of winner determination in computational social choice. In winner determination in computational social choice we are concerned with determining the winner(s) of an election. In the considered elections the votes are given as preference profiles, i.e. a ranking of candidates, by a voter or by an automated process. For example, such scenarios include preference data generated by online services, e.g. streaming services of music or movies, or online shops. In such systems the user has to choose among many candidates and this action is interpreted as a vote, i.e. the users express their preferences. Such online services result in very large elections, but the developed algorithms for methods in computational social choice are usually designed for much smaller settings. To make it possible to apply the methods of computational social choice to such large elections it is necessary to adapt new technologies. Such new technologies have been devised in other areas dealing with huge data sets and include parallel computation and cloud computing techniques. For developing algorithms suited for parallel computation in cloud computing environments the programming paradigms MapReduce and Pregel have been proposed. This work aims at developing algorithms for winner determination by using these programming paradigms. In this thesis, first some problems of winner determination in computational social choice are analysed regarding to their parallelizability. Known complexity results are summarized and extended by new results. Based on this investigation new cloud computing algorithms for several methods in computational social choice are proposed. The algorithms are analysed with regard to common performance measures and are further evaluated by an experimental study. The resulting source code is available as open-source.