A general procedure to compute mixed modified semivalues for cooperative games with structure of coalition blocks

Semivalues are solution concepts for cooperative games that assign to each player a weighted sum of his/her marginal contributions to the coalitions, where the weights only depend on the coalition size. The Shapley value and the Banzhaf value are semivalues. Mixed modified semivalues are solutions for cooperative games when we consider a priori coalition blocks in the player set. For all these solutions, a computational procedure is offered in this paper.     

The Shapley value for arbitrary families of coalitions

We address the problem of finding a suitable definition of a value similar to that of Shapley’s, when the games are defined on a subfamily of coalitions with no structure. We present two frameworks: one based on the familiar efficiency, linearity and null player axioms, and the other on linearity and the behavior on unanimity games. We give several properties and examples in each case, and give necessary and sufficient conditions on the family of coalitions for the approaches to coincide.     

The axiomatic approach to three values in games with coalition structure

We present a unified framework for a broad class of values in transferable utility games with coalition structure, including the Owen coalitional value and two weighted versions with weights given by the size of the coalitions. We provide three axiomatic characterizations using the properties of Efficiency, Linearity, Independence of Null Coalitions, and Coordination, with two versions of Balanced Contributions inside a Coalition and Weighted Sharing in Unanimity Games, respectively.     

The collective value: a new solution for games with coalition structures

In this study, we provide a new solution for cooperative games with coalition structures. The collective value of a player is defined as the sum of the equal division of the pure surplus obtained by his coalition from the coalitional bargaining and of his Shapley value for the internal coalition. The weighted Shapley value applied to a game played by coalitions with coalition-size weights is assigned to each coalition, reflecting the size asymmetries among coalitions. We show that the collective value matches exogenous interpretations of coalition structures and provide an axiomatic foundation of this value. A noncooperative mechanism that implements the collective value is also presented.     

边赋权图对策Myerson值的和分解

2003年,Gómez等在考虑社会网络中心性度量时,引入了对称对策上Myerson值的和分解概念,本文将这一概念推广到边赋权图对策上,给出了相应于边赋权图对策的组内Myerson值和组间Myerson值。其中边的权表示这条边的两个端点之间的直接通讯容量,组内Myerson值衡量了每个参与者来自它所在联盟的收益,而组间Myerson值评估了参与者作为其他参与者中介所获取的收益。本文侧重分析了边赋权图对策的组内Myerson值和组间Myerson值的权稳定性和广义稳定性, 并给出了这两类值的刻画。     

Axiomatic characterizations under players nullification

Many axiomatic characterizations of values for cooperative games invoke axioms which evaluate the consequences of removing an arbitrary player. Balanced contributions (Myerson, 1980) and balanced cycle contributions (Kamijo and Kongo, 2010) are two well-known examples of such axioms. We revisit these characterizations by nullifying a player instead of deleting her/him from a game. The nullification (Béal et al., 2014a) of a player is obtained by transforming a game into a new one in which this player is a null player, i.e. the worth of the coalitions containing this player is now identical to that of the same coalition without this player. The degree with which our results are close to the original results in the literature is connected to the fact that the targeted value satisfies the null player out axiom (Derks and Haller, 1999). We also revisit the potential approach (Hart and Mas-Colell, 1989) similarly.     

Representation of finite games as network congestion games

Weighted network congestion games are a natural model for interactions involving finitely many non-identical users of network resources, such as road segments or communication links. However, in spite of their special form, these games are not fundamentally special: every finite game can be represented as a weighted network congestion game. The same is true for the class of (unweighted) network congestion games with player-specific costs, in which the players differ in their cost functions rather than their weights. The intersection of the two classes consists of the unweighted network congestion games. These games are special: a finite game can be represented in this form if and only if it is an exact potential game.     

A class of non-normalized power indices for simple games

Weights are attached to the coalitions of a finite set of players in order to reflect the fact that some coalitions are more likely to be formed than others. A new power index for simple games which depends only on these weights and the minimal winning coalitions of a game is introduced. Two axiomatic characterizations of this index are given. Symmetry, dummy player and quarrel properties of the index are treated. Two special forms of the index arising from certain assumptions about the weights are described.     

Dimension of complete simple games with minimum

Weighted majority games have the property that players are totally ordered by the desirability relation (introduced by Isbell in [J.R. Isbell, A class of majority games, Quarterly Journal of Mathematics, 7 (1956) 183–187]) because weights induce it. Games for which this relation is total are called complete simple games. Taylor and Zwicker proved in [A.D. Taylor, W.S. Zwicker, Weighted voting, multicameral representation, and power, Games and Economic Behavior 5 (1993) 170–181] that every simple game (or monotonic finite hypergraph) can be represented by an intersection of weighted majority games and consider the dimension of a game as the needed minimum number of them to get it. They provide the existence of non-complete simple games of every dimension and left open the problem for complete simple games.     

Quitting games – An example

Quitting games are multi-player sequential games in which, at every stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; each player i then receives a payoff r _S ⁱ, which depends on the set S of players that did choose to quit. If the game never ends, the payoff to each player is zero.? We exhibit a four-player quitting game, where the “simplest” equilibrium is periodic with period two. We argue that this implies that all known methods to prove existence of an equilibrium payoff in multi-player stochastic games are therefore bound to fail in general, and provide some geometric intuition for this phenomenon. Received: October 2001     

The Harsanyi paradox and the “right to talk” in bargaining among coalitions

We describe a coalitional value from a non-cooperative point of view, assuming coalitions are formed for the purpose of bargaining. The idea is that all the players have the same chances to make proposals. This means that players maintain their own “right to talk” when joining a coalition. The resulting value coincides with the weighted Shapley value in the game between coalitions, with weights given by the size of the coalitions. Moreover, the Harsanyi paradox (forming a coalition may be disadvantageous) disappears for convex games.     

基于平均树值的无圈图博弈有效解

本文对无圈图博弈进行了研究,考虑了大联盟收益不小于各分支收益之和的情况。通过引入剩余公平分配性质,也就是任意两个分支联盟的平均支付变化相等,给出了一个基于平均树值的无圈图博弈有效解。同时,结合有效性和分支公平性对该有效解进行了刻画。特别地,若无圈图博弈满足超可加性时,证明了该有效解一定是核中的元素,说明此时的解是稳定的。最后,通过一案例分析了该有效解的特点,即越大的分支分得的剩余越多,并且关键参与者,也就是具有较大度的参与者可获得相对多的支付。     

Semivalues as power indices

A restricted notion of semivalue as a power index, i.e. as a value on the lattice of simple games, is axiomatically introduced by using the symmetry, positivity and dummy player standard properties together with the transfer property. The main theorem, that parallels the existing statement for semivalues on general cooperative games, provides a combinatorial definition of each semivalue on simple games in terms of weighting coefficients, and shows the crucial role of the transfer property in this class of games. A similar characterization is also given that refers to unanimity coefficients, which describe the action of the semivalue on unanimity games. We then combine the notion of induced semivalue on lower cardinalities with regularity and obtain a series of characteristic properties of regular semivalues on simple games, that concern null and nonnull players, subgames, quotients, and weighted majority games.     

Three hierarchies of simple games parameterized by “resource” parameters

This paper contributes to the program of numerical characterization and classification of simple games outlined in the classic monograph of von Neumann and Morgenstern. We suggest three possible ways to classify simple games beyond the classes of weighted and roughly weighted games. To this end we introduce three hierarchies of games and prove some relationships between their classes. We prove that our hierarchies are true (i.e., infinite) hierarchies. In particular, they are strict in the sense that more of the key “resource” (which may, for example, be the size or structure of the “tie-breaking” region where the weights of the different coalitions are considered so close that we are allowed to specify either winningness or nonwinningness of the coalition) yields the flexibility to capture strictly more games.     

A simple “market value” bargaining model for weighted voting games: characterization and limit theorems

We offer a bargaining model for weighted voting games that is a close relative of the nucleolus and the kernel. We look for a set of weights that preserves winning coalitions that has the property of minimizing the difference between the weight of the smallest and the weight of the largest Minimum Winning Coalition. We claim that such a set of weights provides an a priori measure of a weighted voter’s bribeworthiness or market value. After introducing our model, we provide a characterization result for this model and show its links to other bargaining model approaches in the literature. Then we offer some limit results showing that, with certain reasonable conditions on the distributions of weights, as the size of the voting body increases, the values of bribeworthiness we calculate will approach both the weights themselves and the Banzhaf scores for the weighted voting game. We also show that, even for relatively small groups using weighted voting, such as the membership of the European Council of Ministers (and its predecessors) 1958–2003, similarities among the usual a priori power scores, bribeworthiness/market value, and the weights themselves, will be quite strong.     

An axiomatization of the Shapley value using a fairness property

In this paper we provide an axiomatization of the Shapley value for TU-games using a fairness property. This property states that if to a game we add another game in which two players are symmetric then their payoffs change by the same amount. We show that the Shapley value is characterized by this fairness property, efficiency and the null player property. These three axioms also characterize the Shapley value on the class of simple games. Revised August 2001     

An alternative characterization of the weighted Banzhaf value

We provide a new characterization of the weighted Banzhaf value derived from some postulates in a recent paper by Radzik, Nowak and Driessen [7]. Our approach owes much to the work by Lehrer [4] on the classical Banzhaf value based on the idea of amalgamation of pairs of players and an induction construction of the value. Compared with the approach in [7] we consider two new postulates: a weighted version of Lehrer’s “2-efficiency axiom” [4] and a generalized “null player out” property studied in terms of symmetric games by Derks and Haller [2]. Received: December 1997/final version: October 1999     

Some properties for probabilistic and multinomial (probabilistic) values on cooperative games

We investigate the conditions for the coefficients of probabilistic and multinomial values of cooperative games necessary and/or sufficient in order to satisfy some properties, including marginal contributions, balanced contributions, desirability relation and null player exclusion property. Moreover, a similar analysis is conducted for transfer property of probabilistic power indices on the domain of simple games.     

The Shapley value for cooperative games under precedence constraints

Cooperative games are considered where only those coalitions of players are feasible that respect a given precedence structure on the set of players. Strengthening the classical symmetry axiom, we obtain three axioms that give rise to a unique Shapley value in this model. The Shapley value is seen to reflect the expected marginal contribution of a player to a feasible random coalition, which allows us to evaluate the Shapley value nondeterministically. We show that every exact algorithm for the Shapley value requires an exponential number of operations already in the classical case and that even restriction to simple games is #P-hard in general. Furthermore, we outline how the multi-choice cooperative games of Hsiao and Raghavan can be treated in our context, which leads to a Shapley value that does not depend on pre-assigned weights. Finally, the relationship between the Shapley value and the permission value of Gilles, Owen and van den Brink is discussed. Both refer to formally similar models of cooperative games but reflect complementary interpretations of the precedence constraints and thus give rise to fundamentally different solution concepts.     

Egalitarian allocation and players of certain type

In cooperative game theory the Shapley value is different from the egalitarian value, the latter of which allocates payoffs equally. The null player property and the nullifying player property assign zero payoff to each null player and each nullifying player, respectively. It is known that if the null player property for characterizing the Shapley value is replaced by the nullifying player property, then the egalitarian value is determined uniquely. We propose several properties to replace the nullifying player property to characterize the egalitarian value. Roughly speaking, the results in this note hint that equal division for players of certain types may lead to the egalitarian allocation.