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

NUCLEOLUS; VOTING; DECISION making; GAMES; OPEN-ended questions

In cooperative games, players have a possibility to form different coalitions. This leads to the questions about ways to motivate all players to collaborate, i.e. to motivate the players to form the so-called grand coalition. One of such ways is captured by the concept of nucleolus, which dates back to Babylonian Talmud. Weighted voting games form a class of cooperative games, that are often used to model decision making processes in parliaments. In this paper, 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. (Ann Math Artif Intell 56(2), 109–131, 2007). [ABSTRACT FROM AUTHOR]

Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)