Following Zhang and Grossi~(AAAI 2021), we study in more depth a variant of weighted voting games in which agents' weights are induced by a transitive support structure. This class of simple games is notably well suited to study the relative importance of agents in the liquid democracy framework. We first propose a pseudo-polynomial time algorithm to compute the Banzhaf and Shapley-Shubik indices for this class of game. Then, we study a bribery problem, in which one tries to maximize/minimize the voting power/weight of a given agent by changing the support structure under a budget constraint. We show that these problems are computationally hard and provide several parameterized complexity results.
翻译:紧随张和格罗西~(AAAI 2021)之后,我们更深入地研究加权投票游戏的变式,其中代理商的权重是由过渡性支持结构引起的。这一类简单游戏显然非常适合研究代理商在液态民主框架内的相对重要性。我们首先提出一种假的极化时间算法,用于计算这种类型的游戏的班扎夫指数和沙普利-舒比克指数。然后,我们研究一个贿赂问题,其中一个人试图通过改变预算限制下的支持结构,最大限度地/最大限度地减少某个代理商的投票权/权重。我们表明这些问题在计算上是困难的,并提供了几种参数化的复杂性结果。