Games with a permission structure - A survey on generalizations and applications

In the field of cooperative games with restricted cooperation, various restrictions on coalition formation are studied. The most studied restrictions are those that arise from restricted communication and hierarchies. This survey discusses several models of hierarchy restrictions and their relation with communication restrictions. In the literature, there are results on game properties, Harsanyi dividends, core stability, and various solutions that generalize existing solutions for TU-games. In this survey, we mainly focus on axiomatizations of the Shapley value in different models of games with a hierarchically structured player set, and their applications. Not only do these axiomatizations provide insight in the Shapley value for these models, but also by considering the types of axioms that characterize the Shapley value, we learn more about different network structures. A central model of games with hierarchies is that of games with a permission structure where players in a cooperative transferable utility game are part of a permission structure in the sense that there are players that need permission from other players before they are allowed to cooperate. This permission structure is represented by a directed graph. Generalizations of this model are, for example, games on antimatroids, and games with a local permission structure. Besides discussing these generalizations, we briefly discuss some applications, in particular auction games and hierarchically structured firms.     

一类具有限制联盟结构的合作对策的两阶段Shapley值

讨论一类具有限制联盟结构的合作对策,其中局中人通过优先联盟整体参与大联盟的合作,同时优先联盟内部有合取权限结构限制,利用两阶段Shapley值的分配思想并考虑到权限结构对优先联盟内合作的限制,给出了此类合作对策的解。 该解可看做具有联盟结构的合作对策的两阶段Shapley值的推广。 证明了该解满足的公理化条件,并验证了这些条件的独立性。     

A polynomial time algorithm for computing the nucleolus for a class of disjunctive games with a permission structure

Recently, applications of cooperative game theory to economic allocation problems have gained popularity. In many such allocation problems there is some hierarchical ordering of the players. In this paper we consider a class of games with a permission structure describing situations in which players in a cooperative TU-game are hierarchically ordered in the sense that there are players that need permission from other players before they are allowed to cooperate. The corresponding restricted game takes account of the limited cooperation possibilities by assigning to every coalition the worth of its largest feasible subset. In this paper we provide a polynomial time algorithm for computing the nucleolus of the restricted games corresponding to a class of games with a permission structure which economic applications include auction games, dual airport games, dual polluted river games and information market games.     

An algorithm for computing the nucleolus of disjunctive non-negative additive games with an acyclic permission structure

A cooperative game with a permission structure describes a situation in which players in a cooperative TU-game are hierarchically ordered in the sense that there are players that need permission from other players before they are allowed to cooperate. In this paper we consider non-negative additive games with an acyclic permission structure. For such a game we provide a polynomial time algorithm for computing the nucleolus of the induced restricted game. The algorithm is applied to a market situation where sellers can sell objects to buyers through a directed network of intermediaries.     

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.     

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.     

Harsanyi power solutions for graph-restricted games

We consider cooperative transferable utility games, or simply TU-games, with limited communication structure in which players can cooperate if and only if they are connected in the communication graph. Solutions for such graph games can be obtained by applying standard solutions to a modified or restricted game that takes account of the cooperation restrictions. We discuss Harsanyi solutions which distribute dividends such that the dividend shares of players in a coalition are based on power measures for nodes in corresponding communication graphs. We provide axiomatic characterizations of the Harsanyi power solutions on the class of cycle-free graph games and on the class of all graph games. Special attention is given to the Harsanyi degree solution which equals the Shapley value on the class of complete graph games and equals the position value on the class of cycle-free graph games. The Myerson value is the Harsanyi power solution that is based on the equal power measure. Finally, various applications are discussed.     

Axiomatizations of the Shapley value for games on augmenting systems

This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of unallowable coalitions. Games restricted by a communication graph were introduced by Myerson and Owen. In their model, the feasible coalitions are those that induce connected subgraphs. Another type of model is introduced in Gilles, Owen and van den Brink. In their model, the possibilities of coalition formation are determined by the positions of the players in a so-called permission structure. Faigle proposed another model for cooperative games defined on lattice structures. We introduce a combinatorial structure called augmenting system which is a generalization of the antimatroid structure and the system of connected subgraphs of a graph. In this framework, the Shapley value of games on augmenting systems is introduced and two axiomatizations of this value are showed.     

An axiomatization of the disjunctive permission value for games with a permission structure

Players that participate in acooperative game with transferable utilities are assumed to be part of apermission structure being a hierarchical organization in which there are players that need permission from other players before they can cooperate. Thus a permission structure limits the possibilities of coalition formation. Various assumptions can be made about how a permission structure affects the cooperation possibilities. In this paper we consider thedisjunctive approach in which it is assumed that each player needs permission from at least one of his predecessors before he can act. We provide an axiomatic characterization of thedisjunctive permission value being theShapley value of a modified game in which we take account of the limited cooperation possibilities.     

An axiomatic characterization of the Owen–Shapley spatial power index

We present an axiomatic characterization of the Owen–Shapley spatial power index for the case where issues are elements of two-dimensional space. This characterization employs a version of the transfer condition, which enables us to unravel a spatial game into spatial games connected to unanimity games. The other axioms include two conditions concerned particularly with the spatial positions of the players, besides spatial versions of anonymity and dummy. The last condition says that dummy players can be left out in a specific way without changing the power of the other players. We show that this condition can be weakened to requiring dummies to have zero power if we add a condition of positional continuity. We also show that the axioms in our characterization(s) are logically independent.     

The Myerson Value and Superfluous Supports in Union Stable Systems

In this paper, the set of feasible coalitions in a cooperative game is given by a union stable system. Well-known examples of such systems are communication situations and permission structures. Two games associated with a game on a union stable system are the restricted game (on the set of players in the game) and the conference game (on the set of supports of the system). We define two types of superfluous support property through these two games and provide new characterizations for the Myerson value. Finally, we analyze inheritance of properties between the restricted game and the conference game.     

A link between sequential semi-anonymous nonatomic games and their large finite counterparts

We show that obtainable equilibria of a multi-period nonatomic game can be used by players in its large finite counterparts to achieve near-equilibrium payoffs. Such equilibria in the form of random state-to-action rules are parsimonious in form and easy to execute, as they are both oblivious of past history and blind to other players’ present states. Our transient results can be extended to a stationary case, where the finite multi-period games are special discounted stochastic games. In both nonatomic and finite games, players’ states influence their payoffs along with actions they take; also, the random evolution of one particular player’s state is driven by all players’ states as well as actions. The finite games can model diverse situations such as dynamic price competition. But they are notoriously difficult to analyze. Our results thus suggest ways to tackle these problems approximately.     

The core and the Weber set of games on augmenting systems

This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of unallowable coalitions. Games restricted by a communication graph were introduced by Myerson and Owen. In their model, the feasible coalitions are those that induce connected subgraphs. Another type of model is introduced in Gilles, Owen and van den Brink. In their model, the possibilities of coalition formation are determined by the positions of the players in a so-called permission structure. Faigle proposed a general model for cooperative games defined on lattice structures. In this paper, the restrictions to the cooperation are given by a combinatorial structure called augmenting system which generalizes antimatroid structure and the system of connected subgraphs of a graph. In this framework, the core and the Weber set of games on augmenting systems are introduced and it is proved that monotone convex games have a non-empty core. Moreover, we obtain a characterization of the convexity of these games in terms of the core of the game and the Weber set of the extended game.     

The core of games on ordered structures and graphs

In cooperative games, the core is the most popular solution concept, and its properties are well known. In the classical setting of cooperative games, it is generally assumed that all coalitions can form, i.e., they are all feasible. In many situations, this assumption is too strong and one has to deal with some unfeasible coalitions. Defining a game on a subcollection of the power set of the set of players has many implications on the mathematical structure of the core, depending on the precise structure of the subcollection of feasible coalitions. Many authors have contributed to this topic, and we give a unified view of these different results.     

The core of games on ordered structures and graphs

In cooperative games, the core is the most popular solution concept, and its properties are well known. In the classical setting of cooperative games, it is generally assumed that all coalitions can form, i.e., they are all feasible. In many situations, this assumption is too strong and one has to deal with some unfeasible coalitions. Defining a game on a subcollection of the power set of the set of players has many implications on the mathematical structure of the core, depending on the precise structure of the subcollection of feasible coalitions. Many authors have contributed to this topic, and we give a unified view of these different results.     

基于图对策的收益分配

基于具有交流结构的合作对策,即图对策,对平均树解拓展形式的特征进行刻画,提出此解满足可加性公理。进一步地,分析了对于无圈图对策此解是分支有效的。并且当连通分支中两个局中人相关联的边删掉后,此连通分支的收益变化情况可用平均树解表示。这一性质是Shapley值和Myerson值所不具有的。最后,我们给出了模糊联盟图对策中模糊平均树解的可加性和分支有效性。     

An axiomatization of the Banzhaf value for cooperative games on antimatroids

Cooperative games on antimatroids are cooperative games in which coalition formation is restricted by a combinatorial structure which generalizes permission structures. These games group several well-known families of games which have important applications in economics and politics. The current paper establishes axioms that determine the restricted Banzhaf value for cooperative games on antimatroids. The set of given axioms generalizes the axiomatizations given for the Banzhaf permission values. We also give an axomatization of the restricted Banzhaf value for the smaller class of poset antimatroids. Finally, we apply the above results to auction situations.     

Power Measures and Solutions for Games Under Precedence Constraints

Games under precedence constraints model situations, where players in a cooperative transferable utility game belong to some hierarchical structure, which is represented by an acyclic digraph (partial order). In this paper, we introduce the class of precedence power solutions for games under precedence constraints. These solutions are obtained by allocating the dividends in the game proportional to some power measure for acyclic digraphs. We show that all these solutions satisfy the desirable axiom of irrelevant player independence, which establishes that the payoffs assigned to relevant players are not affected by the presence of irrelevant players. We axiomatize these precedence power solutions using irrelevant player independence and an axiom that uses a digraph power measure. We give special attention to the hierarchical solution, which applies the hierarchical measure. We argue how this solution is related to the known precedence Shapley value, which does not satisfy irrelevant player independence, and thus is not a precedence power solution. We also axiomatize the hierarchical measure as a digraph power measure.     

Bounded rationality, strategy simplification, and equilibrium

It is frequently suggested that predictions made by game theory could be improved by considering computational restrictions when modeling agents. Under the supposition that players in a game may desire to balance maximization of payoff with minimization of strategy complexity, Rubinstein and co-authors studied forms of Nash equilibrium where strategies are maximally simplified in that no strategy can be further simplified without sacrificing payoff. Inspired by this line of work, we introduce a notion of equilibrium whereby strategies are also maximally simplified, but with respect to a simplification procedure that is more careful in that a player will not simplify if the simplification incents other players to deviate. We study such equilibria in two-player machine games in which players choose finite automata that succinctly represent strategies for repeated games; in this context, we present techniques for establishing that an outcome is at equilibrium and present results on the structure of equilibria.