Voting power on a graph connected political space with an application to decision-making in the Council of the European Union
研究了图限制投票博弈中Banzhaf和Shapley权力指数的计算问题，提出一种针对线团图的高效算法，并应用于欧盟理事会投票分析，发现结合投票权重和网络位置的权力指数能预测政治结果。
Abstract We analyze the problem of computing the Banzhaf and Shapley power indices for graph restricted voting games, defined in a particular class of graphs, that we called line-clique. A line-clique graph is a model of a uni-dimensional political space in which voters with the same bliss point are the connected vertices of a clique and then other arcs connect nodes of consecutive cliques. The interest to this model comes from its correspondence to the spatial voting game: a model that has been proposed and used by political analysts to understand nations’ behavior and the political outcome of the bargaining process within the EU Council. Broadly speaking, the computation of a power index of a graph restricted game is strongly #P-complete, as it includes the enumeration of all winning coalitions. Nevertheless, we show that in this special class of graph coalitions can be enumerated by dynamic programming, resulting in a pseudo-polynomial algorithm and proving that the problem only weakly #P-complete. After implementing our new algorithms and finding that they are very fast in practice, we analyze the voting behavior in the EU Council, as for this application previous research compiled a large data set concerning nations’ political positions and political outcomes. We will test whether voting power has an effect on the political outcome, more precisely, whether nations that are favored by their weight and position can influence the political outcome to their advantages. Using linear regressions, we will see that unrestricted power indices are not capable of any predictive property, but graph restricted indices are. The statistic evidence shows that the combination of voting weight and network position is a source of power that affects the political outcome to the advantage of a country.