Two noncooperative games between a coalition and its surrounding in a class of n-person games with constant sum

A cooperative game engendered by a noncooperative n-person game (the master game) in which any subset of n players may form a coalition playing an antagonistic game against the residual players (the surrounding) that has a (Nash equilibrium) solution, is considered, along with another noncooperative game in which both a coalition and its surrounding try to maximize their gains that also possesses a Nash equilibrium solution. It is shown that if the master game is the one with constant sum, the sets of Nash equilibrium strategies in both above-mentioned noncooperative games (in which a coalition plays with (against) its surrounding) coincide.     

图上合作博弈和图的边密度

1977年, Myerson建立了以图作为合作结构的可转移效用博弈模型(也称图博弈), 并提出了一个分配规则, 也即"Myerson 值", 它推广了著名的Shapley值. 该模型假定每个连通集合(通过边直接或间接内部相连的参与者集合)才能形成可行的合作联盟而取得相应的收益, 而不考虑连通集合的具体结构. 引入图的局部边密度来度量每个连通集合中各成员之间联系的紧密程度, 即以该连通集合的导出子图的边密度来作为他们的收益系数, 并由此定义了具有边密度的Myerson值, 证明了具有边密度的Myerson值可以由"边密度分支有效性"和"公平性"来唯一确定.     

The Myerson value for directed graph games

A directed graph game consists of a cooperative game with transferable utility and a digraph which describes limited cooperation and the dominance relation among the players. Under the assumption that only coalitions of strongly connected players are able to fully cooperate, we introduce the digraph-restricted game in which a non-strongly connected coalition can only realize the sum of the worths of its strong components. The Myerson value for directed graph games is defined as the Shapley value of the digraph-restricted game. We establish axiomatic characterizations of the Myerson value for directed graph games by strong component efficiency and either fairness or bi-fairness.     

Potential functions for finding stable coalition structures

The existence of a Nash-stable coalition structure in cooperative games with the Aumann–Dreze value is investigated. Using the framework of potential functions, it is proved that such a coalition structure exists in any cooperative game. In addition, a similar result is established for some linear values of the game, in particular, the Banzhaf value. For a cooperative game with vector payments, a type of stability based on maximizing the guaranteed payoffs of all players is proposed.     

On the Convenience to Form Coalitions or Partnerships in Simple Games

A partnership in a cooperative game is a coalition that possesses an internal structure and, simultaneously, behaves as an individual member. Forming partnerships leads to a modification of the original game which differs from the quotient game that arises when one or more coalitions are actually formed. In this paper, the Shapley value is used to discuss the convenience to form either coalitions or partnerships. To this end, the difference between the additive Shapley value of the partnership in the partnership game and the Shapley alliance value of the coalition, and also between the corresponding value of the internal and external players, are analysed. Simple games are especially considered. Research partially supported by Grant BFM 2003-01314 of the Science and Technology Spanish Ministry and the European Regional Development Fund.     

The consistent Shapley value for hyperplane games

A new value is defined for n-person hyperplane games, i.e., non-sidepayment cooperative games, such that for each coalition, the Pareto optimal set is linear. This is a generalization of the Shapley value for side-payment games. It is shown that this value is consistent in the sense that the payoff in a given game is related to payoffs in reduced games (obtained by excluding some players) in such a way that corrections demanded by coalitions of a fixed size are cancelled out. Moreover, this is the only consistent value which satisfies Pareto optimality (for the grand coalition), symmetry and covariancy with respect to utility changes of scales. It can be reached by players who start from an arbitrary Pareto optimal payoff vector and make successive adjustments.     

Monotonicity and dummy free property for multi-choice cooperative games

Given a coalition of ann-person cooperative game in characteristic function form, we can associate a zero-one vector whose non-zero coordinates identify the players in the given coalition. The cooperative game with this identification is just a map on such vectors. By allowing each coordinate to take finitely many values we can define multi-choice cooperative games. In such multi-choice games we can also define Shapley value axiomatically. We show that this multi-choice Shapley value is dummy free of actions, dummy free of players, non-decreasing for non-decreasing multi-choice games, and strictly increasing for strictly increasing cooperative games. Some of these properties are closely related to some properties of independent exponentially distributed random variables. An advantage of multi-choice formulation is that it allows to model strategic behavior of players within the context of cooperation.Partially funded by the NSF grant DMS-9024408     

Consistent and covariant solutions for TU games

One of the important properties characterizing cooperative game solutions is consistency. This notion establishes connections between the solution vectors of a cooperative game and those of its reduced game. The last one is obtained from the initial game by removing one or more players and by giving them the payoffs according to a specific principle (e.g. a proposed payoff vector). Consistency of a solution means that the restriction of a solution payoff vector of the initial game to any coalition belongs to the solution set of the corresponding reduced game. There are several definitions of the reduced games (cf., e.g., the survey of T. Driessen [2]) based on some intuitively acceptable characteristics. In the paper some natural properties of reduced games are formulated, and general forms of the reduced games possessing some of them are given. The efficient, anonymous, covariant TU cooperative game solutions satisfying the consistency property with respect to any reduced game are described.The research was supported by the NWO grant 047-008-010 which is gratefully acknowledgedReceived: October 2001     

The Owen value values friendship

This paper presents two new axiomatizations of the Owen value for games with coalition structures. Two associated games are defined and a consistency axiom is required. The construction of the associated games presupposes that coalitions behave in an aggressive manner towards players who are not members of the same unions and in a friendly manner towards players that do belong to their unions. The consistency axiom necessitates the definition of only one associated game which is not a reduced game. Received: February 1999/Revised version: January 2000     

基于Choquet积分形式的模糊联盟核心

在具有联盟结构的合作对策中,针对局中人以某种程度参与到合作中的情况,研究了模糊联盟结构的合作对策的收益分配问题。首先,定义了具有模糊联盟结构的合作对策及相关概念。其次,定义了Choquet积分形式的模糊联盟核心,提出了该核心与联盟核心之间的关系,对于强凸联盟对策,证明Choquet积分形式的模糊Owen值属于其所对应的模糊联盟核心。最后通过算例,对该分配模型的可行性进行分析。     

Convexity properties for interior operator games

Interior operator games arose by abstracting some properties of several types of cooperative games (for instance: peer group games, big boss games, clan games and information market games). This reason allow us to focus on different problems in the same way. We introduced these games in Bilbao et al. (Ann. Oper. Res. 137:141–160, 2005) by a set system with structure of antimatroid, that determines the feasible coalitions, and a non-negative vector, that represents a payoff distribution over the players. These games, in general, are not convex games. The main goal of this paper is to study under which conditions an interior operator game verifies other convexity properties: 1-convexity, k-convexity (k≥2 ) or semiconvexity. But, we will study these properties over structures more general than antimatroids: the interior operator structures. In every case, several characterizations in terms of the gap function and the initial vector are obtained. We also find the family of interior operator structures (particularly antimatroids) where every interior operator game satisfies one of these properties.     

The aspiration approach to predicting coalition formation and payoff distribution in sidepayment games

This paper presents the aspiration approach to coalition formation and payoff distribution in games with sidepayments. The approach is based on the idea that players set prices for their participation within coalitions. The solution space which is appropriate for price-setting players is different from that of the usual solution concepts and is called the space of aspirations. Solution concepts defined on the space of aspirations correspond to notions of how players bargain over their prices. Once the players choose a vector of prices, the coalitions which can afford to pay these prices are the coalitions which are predicted to form in the game.     

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.     

Preferred coalitions in cooperative differential games

There are many interesting situations which can be described by anN-person general-sum differential game. Such games are characterized by the fact that the strategy of each player depends upon reasonable assumptions about the strategies of the remaining players; and, thus, these games cannot be considered asN uncoupled optimal control problems. In such cases, we say that the game is not strictly competitive, but involves a mutual interest which makes it possible for all of the players to reduce their costs by cooperating with one another, provided the resulting agreement can be enforced. When cooperation is allowed and there are more than two players, there is always the question of whether all possible subcoalitions will be formed with equal ease. This work considers the situation in which a particular subcoalition is preferred. A theory of general-sum games with preferred coalitions is presented, together with constructive examples of alternative approaches which are unsatisfactory.     

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.     

On some families of cooperative fuzzy games

In a fuzzy cooperative game the players may choose to partially participate in a coalition. A fuzzy coalition consists of a group of participating players along with their participation level. The characteristic function of a fuzzy game specifies the worth of each such coalition. This paper introduces well-known properties of classical cooperative games to the theory of fuzzy games, and studies their interrelations. It deals with convex games, exact games, games with a large core, extendable games and games with a stable core.     

Cooperation in dividing the cake

This paper defines models of cooperation among players partitioning a completely divisible good (such as a cake or a piece of land). The novelty of our approach lies in the players’ ability to form coalitions before the actual division of the good with the aim to maximize the average utility of the coalition. A social welfare function which takes into account coalitions drives the division. In addition, we derive a cooperative game which measures the performance of each coalition. This game is compared with the game in which players start cooperating only after the good has been portioned and has been allocated among the players. We show that a modified version of the game played before the division outperforms the game played after the division.     

A sufficiency condition for coalitive pareto-optimal solutions

In ak-player, nonzero-sum differential game, there exists the possibility that a group of players will form a coalition and work together. If allk players form the coalition, the criterion usually chosen is Pareto optimality whereas, if the coalition consists of only one player, a minmax or Nash equilibrium solution is sought.In this paper, games with coalitions of more than one but less thank players are considered. Coalitive Pareto optimality is chosen as the criterion. Sufficient conditions are presented for coalitive Pareto-optimal solutions, and the results are illustrated with an example.     

Linear and symmetric allocation methods for partially defined cooperative games

A partially defined cooperative game is a coalition function form game in which some of the coalitional worths are not known. An application would be cost allocation of a joint project among so many players that the determination of all coalitional worths is prohibitive. This paper generalizes the concept of the Shapley value for cooperative games to the class of partially defined cooperative games. Several allocation method characterization theorems are given utilizing linearity, symmetry, formulation independence, subsidy freedom, and monotonicity properties. Whether a value exists or is unique depends crucially on the class of games under consideration. Received June 1996/Revised August 2001