Computing the nucleolus of weighted voting games in pseudo-polynomial time

DOI10.1007/S10107-021-01693-4MaRDI QIDQ2089798zbMATH OpenOpenAlexFDO

Authors Kanstantsin Pashkovich

Publication date 24 October 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

allocationslinear programmingnucleolusweighted voting games

Mathematics Subject Classification ID

Linear programming (90C05) Cooperative games (91A12) Algorithmic game theory and complexity (91A68)

Abstract: We provide an algorithm for computing the nucleolus for an instance of a weighted voting game in pseudo-polynomial time. This resolves an open question posed by Elkind. et.al. 2007.

Recommendations

• Computing the nucleolus of weighted voting games
• A general framework for computing the nucleolus via dynamic programming
• On the computational complexity of weighted voting games

Cites work

• A note on the nucleolus and the kernel of the assignment game
• Computing the nucleolus of min-cost spanning tree games is NP-hard.
• Computing the nucleolus of weighted voting games
• Erratum: ``PRIMES is in P
• Finding nucleolus of flow game
• Game theoretic analysis of a bankruptcy problem from the Talmud
• Geometric algorithms and combinatorial optimization
• Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts
• Matching Games: The Least Core and the Nucleolus
• On the computational complexity of weighted voting games
• On the nucleolus of neighbor games
• On the nucleolus of shortest path games
• The Nucleolus of a Characteristic Function Game

Cited in

(6)

• Simple games versus weighted voting games: bounding the critical threshold value
• Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games
• On the computational complexity of weighted voting games
• Computing the nucleolus of weighted voting games
• False-Name Manipulation in Weighted Voting Games Is Hard for Probabilistic Polynomial Time
• A polynomial time algorithm for computing the nucleolus for a class of disjunctive games with a permission structure

This page was built for publication: Computing the nucleolus of weighted voting games in pseudo-polynomial time

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