Personal tools
You are here: Home Events Lab Lunch: Ilias Diakonikolas - Inverse Problems for Power Indices in Weighted Voting Games

Lab Lunch: Ilias Diakonikolas - Inverse Problems for Power Indices in Weighted Voting Games

What
When Dec 04, 2012
from 01:00 PM to 02:00 PM
Where MF2
Add event to calendar vCal
iCal
Abstract: Suppose we must design a weighted voting scheme to be used by n voters to choose between two candidates. We want the i-th voter to have a certain prescribed amount of "influence" over the final outcome of the vote -- 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 weighted voting scheme that gives each voter the prescribed amount of influence? Of course, in order to even hope to answer such a question we need a well-defined notion of the influence of a voter in a weighted voting scheme. Many such measures of influence have been studied in the voting theory literature; such measures are sometimes called "power indices". 
 
In this talk we will consider two of the most popular power indices: the "Banzhaf indices" and the "Shapley-Shubik indices". These are two quite different natural ways of quantifying how much power each voter has over the outcome in a given weighted voting scheme. We will describe provably efficient algorithms that solve the inverse problem of designing a weighted voting scheme for each of these power indices.
 
No background in voting theory is required for the talk. 
 


Based on joint works with Anindya De (Berkeley), Vitaly Feldman (IBM) and Rocco Servedio (Columbia) 
that appeared in STOC'12 and ICALP'12.
Document Actions