论文标题
shapley值的线性代表性游戏和伪多项式计算
Linearly representable games and pseudo-polynomial calculation of the Shapley value
论文作者
论文摘要
我们介绍了线性代表的游戏的概念。从广义上讲，这些是TU游戏，可以用与加权投票游戏，机场游戏或破产游戏等玩家的数量一样多的参数描述。我们表明，Shapley价值计算是线性代表的游戏的伪多项式。这是对文献中许多古典和最新结果的概括。当参数在玩家数量中是多项式时，我们的方法自然会变成严格的多项式算法。
We introduce the notion of linearly representable games. Broadly speaking, these are TU games that can be described by as many parameters as the number of players, like weighted voting games, airport games, or bankruptcy games. We show that the Shapley value calculation is pseudo-polynomial for linearly representable games. This is a generalization of many classical and recent results in the literature. Our method naturally turns into a strictly polynomial algorithm when the parameters are polynomial in the number of players.
