4 March 2010, Computational Social Choice Seminar, Bart de Keijzer

Abstract

In many decision making settings, situations arise in which the participants must collectively make decisions, while not every participant is supposed to have an equal amount of influence on the outcome of the decision. Weighted voting games are often used to deal with these situations. The amount of influence that a player has in a weighted voting game can be measured by means of various power indices.

In this talk will discuss the problem of finding a weighted voting game in which the distribution of the influence among the players is as close as possible to a given target value. I will explain a method to exactly solve this problem. This method relies on a new efficient procedure for enumerating weighted voting games of a fixed number of players.

The enumeration algorithm we propose works by exploiting the properties of a specific partial order over the class of weighted voting games. The algorithm enumerates weighted voting games of a fixed number of players in time exponential in the number of players, and polynomial in the number of games output. As a consequence we obtain an exact anytime algorithm for designing weighted voting games.

The material I will cover in this talk is part of my MSc. Thesis, which can be found at http://repository.tudelft.nl/view/ir/uuid:b2dda5ac-b72f-4342-bcbf-89d6aa0a99ba/

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle.endriss at uva.nl).