Computing the nucleolus of weighted voting games in pseudo-polynomial time
成果类型：
Article
署名作者：
Pashkovich, Kanstantsin
署名单位：
University of Ottawa
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-021-01693-4
发表日期：
2022
页码：
1123-1133
关键词：
摘要：
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).
来源URL：