基于时隙ALOHA协议的数据传输二人随机博弈模型

在一个给定的拓扑网络中研究关于数据传输的二人随机博弈模型.两个局中人（源节点）试图通过一个公共节点向目的节点传输随机数据包,这些数据包被分为重要的数据包和不重要的数据包两类,假设每个局中人都有一个用于存储数据包的有限容量的缓冲器.通过构造数据传输的成本分摊和奖励体系,把这种动态的冲突控制过程建模为具有有限状态集合的随机博弈,研究局中人在这种随机博弈模型下的非合作以及合作行为.在非合作情形下,给出纳什均衡的求解算法;在合作情形下,选择Shapley值作为局中人支付总和的分配方案,并讨论其子博弈一致性,提出使得Shapley值为子博弈一致的分配补偿程序.     

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     

Players indifferent to cooperate and characterizations of the Shapley value

In this paper we provide new axiomatizations of the Shapley value for TU-games using axioms that are based on relational aspects in the interactions among players. Some of these relational aspects, in particular the economic or social interest of each player in cooperating with each other, can be found embedded in the characteristic function. We define a particular relation among the players that it is based on mutual indifference. The first new axiom expresses that the payoffs of two players who are not indifferent to each other are affected in the same way if they become enemies and do not cooperate with each other anymore. The second new axiom expresses that the payoff of a player is not affected if players to whom it is indifferent leave the game. We show that the Shapley value is characterized by these two axioms together with the well-known efficiency axiom. Further, we show that another axiomatization of the Shapley value is obtained if we replace the second axiom and efficiency by the axiom which applies the efficiency condition to every class of indifferent players. Finally, we extend the previous results to the case of weighted Shapley values.     

基于图对策的收益分配

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

Inheritance of properties in communication situations

In this paper we consider cooperative games in which the possibilities for cooperation between the players are restricted because communication between the players is restricted. The bilateral communication possibilities are modeled by means of a (communication) graph. We are interested in how the communication restrictions influence the game. In particular, we investigate what conditions on the communication graph guarantee that certain appealing properties of the original game are inherited by the graph-restricted game, the game that arises once the communication restrictions are taken into account. We study inheritance of the following properties: average convexity, inclusion of the Shapley value in the core, inclusion of the Shapley values of a game and all its subgames in the corresponding cores, existence of a population monotonic allocation scheme, and the property that the extended Shapley value is a population monotonic allocation scheme. Received May 1998/Revised version January 2000     

A new basis and the Shapley value

The purpose of this paper is to introduce a new basis of the set of all TU games. Shapley (1953) introduced the unanimity game in which cooperation of all players in a given coalition yields payoff. We introduce the commander game in which only one player in a given coalition yields payoff. The set of the commander games forms a basis and has two properties. First, when we express a game by a linear combination of the basis, the coefficients related to singletons coincide with the Shapley value. Second, the basis induces the null space of the Shapley value.     

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

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

The Shapley value for the probability game

The main goal of this paper is to introduce the probability game. On one hand, we analyze the Shapley value by providing an axiomatic characterization. We propose the so-called independent fairness property, meaning that for any two players, the player with larger individual value gets a larger portion of the total benefit. On the other, we use the Shapley value for studying the profitability of merging two agents.     

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.     

Values on regular games under Kirchhoff’s laws

The Shapley value is a central notion defining a rational way to share the total worth of a cooperative game among players. We address a general framework leading to applications to games with communication graphs, where the feasible coalitions form a poset whose all maximal chains have the same length. Considering a new way to define the symmetry among players, we propose an axiomatization of the Shapley value of these games. Borrowing ideas from electric networks theory, we show that our symmetry axiom and the efficiency axiom correspond to the two Kirchhoff’s laws in the circuit associated to the Hasse diagram of feasible coalitions.     

全对策的边际贡献值

全对策是定义在局中人集合的所有分划集上的一类特殊合作对策.本文在效用可转移情形下研究全对策的"值"问题.定义了全对策的边际贡献值,得出全对策的Shapley值,以及具有某些性质的值是边际贡献值,并给出两种边际贡献值的具体表达式,及其一些性质.     

Weighted allocation rules for standard fixed tree games

In this paper we consider standard fixed tree games, for which each vertex unequal to the root is inhabited by exactly one player. We present two weighted allocation rules, the weighted down-home allocation and the weighted neighbour-home allocation, both inspired by the painting story in Maschler et al. (1995) . We show, in a constructive way, that the core equals both the set of weighted down-home allocations and the set of weighted neighbour allocations. Since every weighted down-home allocation specifies a weighted Shapley value (Kalai and Samet (1988)) in a natural way, and vice versa, our results provide an alternative proof of the fact that the core of a standard fixed tree game equals the set of weighted Shapley values. The class of weighted neighbour allocations is a generalization of the nucleolus, in the sense that the latter is in this class as the special member where players have all equal weights.     

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 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.     

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     

The Shapley Valuation Function for Strategic Games in which Players Cooperate

In this note we use the Shapley value to define a valuation function. A valuation function associates with every non-empty coalition of players in a strategic game a vector of payoffs for the members of the coalition that provides these players’ valuations of cooperating in the coalition. The Shapley valuation function is defined using the lower-value based method to associate coalitional games with strategic games that was introduced in Carpente et al. (2005). We discuss axiomatic characterizations of the Shapley valuation function.     

Constrained core solutions for totally positive games with ordered players

In many applications of cooperative game theory to economic allocation problems, such as river-, polluted river- and sequencing games, the game is totally positive (i.e., all dividends are nonnegative), and there is some ordering on the set of the players. A totally positive game has a nonempty core. In this paper we introduce constrained core solutions for totally positive games with ordered players which assign to every such a game a subset of the core. These solutions are based on the distribution of dividends taking into account the hierarchical ordering of the players. The Harsanyi constrained core of a totally positive game with ordered players is a subset of the core of the game and contains the Shapley value. For special orderings it coincides with the core or the Shapley value. The selectope constrained core is defined for acyclic orderings and yields a subset of the Harsanyi constrained core. We provide a characterization for both solutions.     

单调集对策及合成对策的边缘值

本文给出了单调集对策及其合成对策的边缘值，它类似于我们所熟知的TU—对策的Shapley值及文献[6]．集对策的边缘值的意义在于允许局中人共享项目．这使得不能分割的项目在局中人之间的分配成为可能．我们给出了这种边缘值的一些性质，并讨论了合成集对策的核及其子对策的核之间的关系．     

A value for partially defined cooperative games

The Shapley value provides a method, which satisfies certain desirable axioms, of allocating benefits to the players of a cooperative game. When there aren players andn is large, the Shapley value requires a large amount of accounting because the number of coalitions grows exponentially withn. This paper proposes a modified value that shares some of the axiomatic properties of the Shapley value yet allows the consideration of games that are defined only for certain coalitions. Two different axiom systems are shown to determine the same modified value uniquely.     

On stochastic games

In this paper, we consider the stochastic games of Shapley, when the state and action spaces are all infinite. We prove that, under certain conditions, the stochastic game has a value and that both players have optimal strategies.Part of this research was supported by NSF grant. The authors are indebted to L. S. Shapley for the useful discussions on this and related topics. The authors thank the referee for pointing out an ambiguity in the formulation of Lemma 2.4 in an earlier draft of this article.