Skip to main content

Inverse Problems for Power Indices in Weighted Voting Games

Ilias Diakonikolas ( University of Edinburgh )

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 pre-specified 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 well-defined 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 "Shapley-Shubik 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.)

Speaker bio

Ilias Diakonikolas is a Lecturer in the School of Informatics at the University of Edinburgh. He holds a diploma in electrical and computer engineering from the National Technical University of Athens (2004), and a Ph.D. in computer science from Columbia University (2010) where he was advised by Mihalis Yannakakis. He received a best thesis award for his doctoral dissertation and an honorable mention in the 2009 George Nicholson competition from the INFORMS society. Before moving to Edinburgh he spent a couple of years (2010-2012) as the Simons postdoctoral fellow in theoretical computer science at UC Berkeley. His research interests lie in theoretical computer science with a focus on algorithms, learning and game theory.

Share this: