The minimum sum representation as an index of voting power

We propose a new power index based on the minimum sum representation (MSR) of a weighted voting game. The MSR offers a redesign of a voting game, such that voting power as measured by the MSR index becomes proportional to voting weight. The MSR index is a coherent measure of power that is ordinally equivalent to the Banzhaf, Shapley–Shubik and Johnston indices. We provide a characterization for a bicameral meet as a weighted game or a complete game, and show that the MSR index is immune to the bicameral meet paradox. We discuss the computation of the MSR index using a linear integer program and the inverse MSR problem of designing a weighted voting game with a given distribution of power.     

The Banzhaf power index for ternary bicooperative games

In this paper we analyze ternary bicooperative games, which are a refinement of the concept of a ternary voting game introduced by Felsenthal and Machover. Furthermore, majority voting rules based on the difference of votes are simple bicooperative games. First, we define the concepts of the defender and detractor swings for a player. Next, we introduce the Banzhaf power index and the normalized Banzhaf power index. The main result of the paper is an axiomatization of the Banzhaf power index for the class of ternary bicooperative games. Moreover, we study ternary bicooperative games with two lists of weights and compute the Banzhaf power index using generating functions.     

Measuring the interactions among variables of functions over the unit hypercube

By considering a least squares approximation of a given square integrable function f:n[0,1]→R by a multilinear polynomial of a specified degree, we define an index which measures the overall interaction among variables of f. This definition extends the concept of Banzhaf interaction index introduced in cooperative game theory. Our approach is partly inspired from multilinear regression analysis, where interactions among the independent variables are taken into consideration. We show that this interaction index has appealing properties which naturally generalize several properties of the Banzhaf interaction index. In particular, we interpret this index as an expected value of the difference quotients of f or, under certain natural conditions on f, as an expected value of the derivatives of f. Finally, we discuss a few applications of the interaction index in aggregation function theory.     

模糊合作博弈局中人参与水平间相互作用度量

本文基于经典合作博弈局中人间相互作用现象的有关度量方法,针对具有模糊联盟的合作博弈问题,给出了模糊联盟中各局中人参与水平间相互作用的度量方法,定义了水平间相互独立性概念,建立了反映局中人各参与水平间相互作用平均程度的两指标:Shapley相互作用指标及Banzhaf相互作用指标.同时对于具有k-单调性的模糊合作博弈局中人参与水平间的边缘相互作用的有关性质作了进一步研究,得出了一些新的结论.     

联合国安理会改革的势力分析

建立了联合国安理会加权投票系统模型,给出了联合国安理会加权投票系统的Shapley势力指数和Banzhaf势力指数,计算了联合国安理会各种改革方案下各理事国的势力指数。最后对联合国安理会各种改革方案下各理事国的势力指数的变化情况进行了比较分析。     

具有图结构和联盟结构的Banzhaf值及应用

Banzhaf值是经典可转移效用合作对策中一个著名的分配规则,可以用来评估参与者在对策中的不同作用。本文将Banzhaf值推广到具有联盟结构和图结构的TU-对策中,首先提出并定义了具有联盟结构和图结构的Banzhaf值(简称PL-Banzhaf值),证明了PL-Banzhaf值满足公平性、平衡贡献性和分割分支总贡献性,并给出了该值的两种公理性刻画。其次,讨论了PL-Banzhaf值在跨国天然气管道案例中的应用,并和其他分配规则进行了比较分析。     

The Banzhaf power index for political games

The Banzhaf index of a voting game is a measure of a priori power of the voters. The model on which the index is based treats the voters symmetrically, i.e. the ideology, outlook, etc., of the voters influencing their voting behavior is ignored. Here we present a nonsymmetric generalization of the Banzhaf index in which the ideology of the voters affecting their voting behavior is taken into account. A model of ideologies and issues is presented. The conditions under which our model gives the Shapley-Shubik index (another index of a priori power of the voters) are given. Finally several examples are presented and some qualitative results are given for straight majority and pure bargaining games.     

On the inverse power index problem

Weighted voting games are frequently used in decision making. Each voter has a weight and a proposal is accepted if the weight sum of the supporting voters exceeds a quota. One line of research is the efficient computation of so-called power indices measuring the influence of a voter. We treat the inverse problem: Given an influence vector and a power index, determine a weighted voting game such that the distribution of influence among the voters is as close as possible to the given target value. We present exact algorithms and computational results for the Shapley–Shubik and the (normalized) Banzhaf power index.     

Weighted Banzhaf values

The family of weighted Banzhaf values for cooperativen-person TU-games is studied. First we introduce the weighted Banzhaf value for an exogenously given vector of positive weights of the players. Then we give an axiomatic characterization of the class of all possible weighted Banzhaf values.     

Weighted and roughly weighted simple games

In this paper we give necessary and sufficient conditions for a simple game to have rough weights. We define two functions f(n) and g(n) that measure the deviation of a simple game from a weighted majority game and roughly weighted majority game, respectively. We formulate known results in terms of lower and upper bounds for these functions and improve those bounds. We also investigate rough weightedness of simple games with a small number of players.     

Multilinear extensions and values for multichoice games

We define multilinear extensions for multichoice games and relate them to probabilistic values and semivalues. We apply multilinear extensions to show that the Banzhaf value for a compound multichoice game is not the product of the Banzhaf values of the component games, in contrast to the behavior in simple games. Following Owen (Manag Sci 18:64–79, 1972), we integrate the multilinear extension over a simplex to construct a version of the Shapley value for multichoice games. We compare this new Shapley value to other extensions of the Shapley value to multichoice games. We also show how the probabilistic value (resp. semivalue, Banzhaf value, Shapley value) of a multichoice game is equal to the probabilistic value (resp. semivalue, Banzhaf value, Shapley value) of an appropriately defined TU decomposition game. Finally, we explain how semivalues, probabilistic values, the Banzhaf value, and this Shapley value may be viewed as the probability that a player makes a difference to the outcome of a simple multichoice game.     

超网络中心性度量的υ-Position值方法

利用合作博弈理论的分配规则如Shapley值、Banzhaf值等来度量政治、经济和社会网络中节点的中心性或者重要性是识别网络中关键节点的一类重要方法。考虑到在超网络中代表各类组织的超边在网络中发挥的作用不同,本文研究了超网络博弈上一类广义Position值的分配规则,被称为υ-position值。它可以作为网络中度值测度的一类推广,以此来度量网络中参与者的中心性和相对重要性。其次,证明了超网络结构上类Shapley-position值可由分支超边指数和局部平衡超边贡献两个性质所唯一刻画。最后, 举例分析了υ-position值在超网络中心性测度中的应用。     

Inferior players in simple games

Power indices like those of Shapley and Shubik (1954) or Banzhaf (1965) measure the distribution of power in simple games. This paper points at a deficiency shared by all established indices: players who are inferior in the sense of having to accept (almost) no share of the spoils in return for being part of a winning coalition are assigned substantial amounts of power. A strengthened version of the dummy axiom based on a formalized notion of inferior players is a possible remedy. The axiom is illustrated first in a deterministic and then a probabilistic setting. With three axioms from the Banzhaf index, it uniquely characterizes the Strict Power Index (SPI). The SPI is shown to be a special instance of a more general family of power indices based on the inferior player axiom. Received: December 1999/Final version: June 2001     

The Banzhaf index in complete and incomplete shareholding structures: A new algorithm

In this global world, many firms present a complex shareholding structure with indirect participation, such that it may become difficult to assess a firm’s controllers. Furthermore, if there are numerous dominant shareholders, the control can be shared between them. Determining who has the most influence is often a difficult task. To measure this influence, game theory allows the modeling of voting games and the computing of the Banzhaf index. This paper firstly offers a new algorithm to compute this index in all structures and then suggests some modelisations of the floating shareholder. Then, our model is applied to a real case study: the French group Lafarge. This exemplary case demonstrates how the float’s structure and hidden coalition can impact the power relationship between dominant shareholders.     

Banzhaf index for multiple voting systems. An application to the European Union

Multi-criteria simple games constitute an extension of the basic framework of voting systems and collective decision-making. The study of power index plays an important role in the theory of multi-criteria simple games. Thus, in this paper, we propose the extended Banzhaf index for these games, as the natural generalization of this index in conventional simple games. This approach allows us to compare various criteria simultaneously. An axiomatic characterization of this power index is established. The Banzhaf index is computed by taking into account the minimal winning coalitions of each class. Since this index depends on the number of ways in which each player can effect a swing, one of the main difficulties for finding this index is that it involves a large number of computations. We propose a combinatorial procedure, based on generating functions, to obtain the Banzhaf index more efficiently for weighted multi-criteria simple games. As an application, the distribution of voting power in the European Union is calculated.     

具有超图合作结构的赋权Position值

具有超图交流结构的可转移效用合作对策,也称为超图对策,它由一个三元组(N,v,H)所组成,其中(N,H)是一个可转移效用对策(简称TU-对策),而(N,H)是一个超图(超网络)。在超图对策中,除Myerson值(Myerson)外,Position值(Meessen)是另一个重要的分配规则。该模型要求把超图结构中每条超边Shapley的值平均分配给它所包含的点,而不考虑每个点的交流能力或合作水平。本文引入超图结构中点的度值来度量每条超边中每个点的交流能力或合作水平,并结合Haeringer提出用于推广Shapley值的权重系统,并由此定义了具有超图合作结构的赋权Position值。我们证明了具有超图合作结构的赋权Position值可以由“分支有效性”、“冗余超边性”、“超边可分解性”、“拟可加性”、“弱积极性”和“弱能转换”六个性质所唯一确定,并且发现参与者获得的支付随其度值的增加而增加,参与者分摊的成本随其度值的增加而降低。     

Achievable hierarchies in voting games with abstention

It is well known that he influence relation orders the voters the same way as the classical Banzhaf and Shapley–Shubik indices do when they are extended to the voting games with abstention (VGA) in the class of complete games. Moreover, all hierarchies for the influence relation are achievable in the class of complete VGA. The aim of this paper is twofold. Firstly, we show that all hierarchies are achievable in a subclass of weighted VGA, the class of weighted games for which a single weight is assigned to voters. Secondly, we conduct a partial study of achievable hierarchies within the subclass of H-complete games, that is, complete games under stronger versions of influence relation.     

The complexity of power indexes with graph restricted coalitions

Coalitions of weighted voting games can be restricted to be connected components of a graph. As a consequence, coalition formation, and therefore a player’s power, depends on the topology of the graph. We analyze the problems of computing the Banzhaf and the Shapley–Shubik power indexes for this class of voting games and prove that calculating them is #P-complete in the strong sense for general graphs. For trees, we provide pseudo-polynomial time algorithms and prove #P-completeness in the weak sense for both indexes.     

Axiomatizations of Banzhaf permission values for games with a permission structure

In games with a permission structure it is assumed that players in a cooperative transferable utility game are hierarchically ordered in the sense that there are players that need permission from other players before they are allowed to cooperate. We provide axiomatic characterizations of Banzhaf permission values being solutions that are obtained by applying the Banzhaf value to modified TU-games. In these characterizations we use power- and player split neutrality properties. These properties state that splitting a player’s authority and/or contribution over two players does not change the sum of their payoffs.     

Approximations of Lovász extensions and their induced interaction index

The Lovász extension of a pseudo-Boolean function f:{0,1}ⁿ→R is defined on each simplex of the standard triangulation of [0,1]ⁿ as the unique affine function that interpolates f at the n+1 vertices of the simplex. Its degree is that of the unique multilinear polynomial that expresses f. In this paper we investigate the least squares approximation problem of an arbitrary Lovász extension by Lovász extensions of (at most) a specified degree. We derive explicit expressions of these approximations. The corresponding approximation problem for pseudo-Boolean functions was investigated by Hammer and Holzman [Approximations of pseudo-Boolean functions; applications to game theory, Z. Oper. Res. 36(1) (1992) 3-21] and then solved explicitly by Grabisch et al. [Equivalent representations of set functions, Math. Oper. Res. 25(2) (2000) 157-178], giving rise to an alternative definition of Banzhaf interaction index. Similarly we introduce a new interaction index from approximations of and we present some of its properties. It turns out that its corresponding power index identifies with the power index introduced by Grabisch and Labreuche [How to improve acts: an alternative representation of the importance of criteria in MCDM, Internat. J. Uncertain. Fuzziness Knowledge-Based Syst. 9(2) (2001) 145-157].