Pseudo Polynomial Size LP Formulation for Calculating the Least Core Value of Weighted Voting Games

Abstract

In this paper, we propose a pseudo polynomial size LP formulation for finding a payoff vector in the least core of a weighted voting game. The numbers of variables and constraints in our formulation are both bounded by $\mbox{O}(n W_+)$, where $n$ is the number of players and $W_{+}$ is the total sum of (integer) voting weights. When we employ our formulation, a commercial LP solver calculates a payoff vector in the least core of practical weighted voting games in a few seconds. We also extend our approach to vector weighted voting games.

14 pages, 1 figure

References in corpus (1)

• Dimension of the Lisbon voting rules in the EU Council: a challenge and new world record