Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games

DOI10.1016/J.MATHSOCSCI.2021.12.002MaRDI QIDQ2070558zbMATH OpenOpenAlexFDO

Authors Masato Tanaka, Tomomi Matsui

Publication date 24 January 2022

Published in Mathematical Social Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.11180

zbMATH Keywords

least corelinear programmingweighted voting games

Mathematics Subject Classification ID

Linear programming (90C05) Cooperative games (91A12) Applications of game theory (91A80) Voting theory (91B12)

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 $mboxO(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.

Recommendations

• Computing the nucleolus of weighted voting games
• Computing the nucleolus of weighted voting games in pseudo-polynomial time
• The least core, nucleolus, and kernel of homogeneous weighted majority games
• Individual weighted excess and least square values
• On the computational complexity of weighted voting games

Cites work

• A CLASS OF MAJORITY GAMES
• A new index of power for simple n-person games
• A new polynomial-time algorithm for linear programming
• Computing the nucleolus of weighted voting games
• Dimension of the Lisbon voting rules in the EU council: a challenge and new world record
• Feature Article—The Ellipsoid Method: A Survey
• Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1766750 (Why is no real title available?)
• scientific article; zbMATH DE number 3257031 (Why is no real title available?)
• NP-completeness for calculating power indices of weighted majority games
• NP-completeness of some problems concerning voting games
• On minimum sum representations for weighted voting games
• On the Complexity of Cooperative Solution Concepts
• On the computational complexity of weighted voting games
• On the existence of a minimum integer representation for weighted voting systems
• Polynomial algorithms in linear programming
• The Nucleolus of a Characteristic Function Game
• The nucleolus of large majority games
• The Treaty of Nice and qualified majority voting
• Voting power in the European Union enlargement
• Weighted games without a unique minimal representation in integers

This page was built for publication: Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2070558)