Inverse Problems for Power Indices in Weighted Voting Games
Ilias Diakonikolas ( University of Edinburgh )

16:30 3rd December 2013 ( week 8, Michaelmas Term 2013 )Lecture Theatre B
A classical problem in social choice theory is to design a voting mechanism such as the distribution of power of
the different players (voters) is equal to a prespecified target. For example, the voters may correspond to states with different
populations, or shareholders who hold different numbers of shares in a company. How can we design a voting mechanism
that gives each player the prescribed amount of power? To formalize this question, one needs a welldefined notion of
the power of a player. Several such notions (known as "power indices") have been studied. In this talk we will consider
the most popular ones: the "Banzhaf indices" and the "ShapleyShubik indices". We will describe the first efficient algorithms
that solve the inverse problem of designing a weighted voting scheme for each of these power indices.
(Based on joint works with Anindya De, Vitaly Feldman and Rocco Servedio. No prior knowledge of social choice theory will
be required for the talk.)