Dynamic weighted voting games
Dynamic weighted voting games
复制标题
动态加权投票游戏
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Yair Zick
中科院分区：
文献类型：
--
作者：
Edith Elkind;D. Pasechnik;Yair Zick
我们开创了动态合作对策的研究-特征函数随时间变化的合作对策。我们为这类博弈引入了两类算法问题：在时间t计算给定解概念，以及检验博弈的某一函数(例如，给定玩家的Shapley值或最小核的值)在时间间隔[t0，t1]内是否保持在给定界内。然后，我们研究了动态加权投票对策问题的复杂性，其中每个参与者的权重和配额都是时间的函数，这些函数是由整系数的低次多项式给出的。我们为这两种类型的问题提供了伪多项式算法，并提供了各种解决方案的概念。然后，我们使用我们的结果来调查未来50年欧洲联盟理事会权力分配的变化。
We initiate the study of dynamic cooperative games --- cooperative games where the characteristic function may change over time. We introduce two types of algorithmic problems for such games: computing a given solution concept at time t, and checking that a certain function of the game (e.g., the Shapley value of a given player or the value of the least core) remains within given bounds during time interval [t_0, t_1]. We then investigate the complexity of these problems for dynamic weighted voting games, where the weight of each player and the quota are functions of time that are given by low-degree polynomials with integer coefficients. We provide pseudopolynomial algorithms for problems of both types, for a variety of solution concepts. We then use our results to investigate the changes in power distribution in the Council of the European Union over the next 50 years.