Inverse power index problem: algorithms and complexity
View/ Open
Date
31/07/2021Author
Pavlou, Chrystalla
Metadata
Abstract
Weighted voting games are a family of cooperative games, typically used to model
voting situations where a number of agents (players) vote against or for a proposal.
In such games, a proposal is accepted if an appropriately weighted sum of the votes
exceeds a prespecified threshold. As the influence of a player over the voting outcome
is not in general proportional to her assigned weight, various power indices have been
proposed to measure each player’s influence. The inverse power index problem is the
problem of designing a weighted voting game that achieves a set of target influences
according to a predefined power index. In the first part of this thesis, we study the
computational complexity of the inverse problem when the power index belongs to the
class of semivalues. We prove that the inverse problem is computationally intractable
for a broad family of semivalues, including all regular semivalues. As a special case
of our general result, we establish computational hardness of the inverse problem for
the Banzhaf indices and the Shapley values, arguably the most popular power indices.
In the second part, we design efficient approximation algorithms for the inverse semi-value problem. We develop a unified methodology that leads to computationally efficient algorithms that solve the inverse semivalue problem to any desired accuracy. We
perform an extensive experimental evaluation of our algorithms on both synthetic and
real inputs. Our experiments show that our algorithms are scalable and achieve higher
accuracy compared to previous methods in the literature.