Linear values for interior operator games

Interior operator games were introduced by Bilbao et al. (2005) as additive games restricted by antimatroids. In that paper several interesting cooperative games were shown as examples of interior operator games. The antimatroid is a known combinatorial structure which represents, in the game theory context, a dependence system among the players. The aim of this paper is to study a family of values which are linear functions and satisfy reasonable conditions for interior operator games. Two classes of these values are considered assuming particular properties.     

Partially ordered cooperative games: extended core and Shapley value

In this paper we analyze cooperative games whose characteristic function takes values in a partially ordered linear space. Thus, the classical solution concepts in cooperative game theory have to be revisited and redefined: the core concept, Shapley–Bondareva theorem and the Shapley value are extended for this class of games. The classes of standard, vector-valued and stochastic cooperative games among others are particular cases of this general theory. The research of the authors is partially supported by Spanish DGICYT grant numbers MTM2004-0909, HA2003-0121, HI2003-0189, MTM2007-67433-C02-01, P06-FQM-01366.     

On the core and nucleolus of minimum cost spanning tree games

We develop two efficient procedures for generating cost allocation vectors in the core of a minimum cost spanning tree (m.c.s.t.) game. The first procedure requires O(n ²) elementary operations to obtain each additional point in the core, wheren is the number of users. The efficiency of the second procedure, which is a natural strengthening of the first procedure, stems from the special structure of minimum excess coalitions in the core of an m.c.s.t. game. This special structure is later used (i) to ease the computational difficulty in computing the nucleolus of an m.c.s.t. game, and (ii) to provide a geometric characterization for the nucleolus of an m.c.s.t. game. This geometric characterization implies that in an m.c.s.t. game the nucleolus is the unique point in the intersection of the core and the kernel. We further develop an efficient procedure for generating fair cost allocations which, in some instances, coincide with the nucleolus. Finally, we show that by employing Sterns' transfer scheme we can generate a sequence of cost vectors which converges to the nucleolus. Part of this research was done while the author was visiting the Department of Operations Research at Stanford University. This research was partially supported by Natural Sciences and Engineering Research Council Canada Grant A-4181.     

Adaptive allocation rules for hypergraph games

Cooperative games with hypergraph structure, or hypergraph games, assume that all players in a hyperlink or conference have to be present before communication. Contrary to this situation, assuming that whenever players leave a conference the remaining players can still communicate with each other, adaptive allocation rules for hypergraph games, being alternative extensions of the Myerson value and the position value respectively, are introduced in this paper. Axiomatic characterizations are also provided by considering players' absence.     

On three Shapley-like solutions for cooperative games with random payoffs

Three solution concepts for cooperative games with random payoffs are introduced. These are the marginal value, the dividend value and the selector value. Inspiration for their definitions comes from several equivalent formulations of the Shapley value for cooperative TU games. An example shows that the equivalence is not preserved since these solutions can all be different for cooperative games with random payoffs. Properties are studied and a characterization on a subclass of games is provided.2000 Mathematics Subject Classification Number: 91A12.The authors thank two anonymous referees and an associate editor for their helpful comments.This author acknowledges financial support from the Netherlands Organization for Scientific Research (NWO) through project 613-304-059.Received: October 2000     

The fuzzy core in games with fuzzy coalitions

In this paper, the fuzzy core of games with fuzzy coalition is proposed, which can be regarded as the generalization of crisp core. The fuzzy core is based on the assumption that the total worth of a fuzzy coalition will be allocated to the players whose participation rate is larger than zero. The nonempty condition of the fuzzy core is given based on the fuzzy convexity. Three kinds of special fuzzy cores in games with fuzzy coalition are studied, and the explicit fuzzy core represented by the crisp core is also given. Because the fuzzy Shapley value had been proposed as a kind of solution for the fuzzy games, the relationship between fuzzy core and the fuzzy Shapley function is also shown. Surprisingly, the relationship between fuzzy core and the fuzzy Shapley value does coincide, as in the classical case.     

The nucleon of cooperative games and an algorithm for matching games

Thenucleon is introduced as a new allocation concept for non-negative cooperativen-person transferable utility games. The nucleon may be viewed as the multiplicative analogue of Schmeidler’s nucleolus. It is shown that the nucleon of (not necessarily bipartite) matching games can be computed in polynomial time.     

Interaction indices for games on combinatorial structures with forbidden coalitions

The notion of interaction among a set of players has been defined on the Boolean lattice and Cartesian products of lattices. The aim of this paper is to extend this concept to combinatorial structures with forbidden coalitions. The set of feasible coalitions is supposed to fulfil some general conditions. This general representation encompasses convex geometries, antimatroids, augmenting systems and distributive lattices. Two axiomatic characterizations are obtained. They both assume that the Shapley value is already defined on the combinatorial structures. The first one is restricted to pairs of players and is based on a generalization of a recursivity axiom that uniquely specifies the interaction index from the Shapley value when all coalitions are permitted. This unique correspondence cannot be maintained when some coalitions are forbidden. From this, a weak recursivity axiom is defined. We show that this axiom together with linearity and dummy player are sufficient to specify the interaction index. The second axiomatic characterization is obtained from the linearity, dummy player and partnership axioms. An interpretation of the interaction index in the context of surplus sharing is also proposed. Finally, our interaction index is instantiated to the case of games under precedence constraints.     

Weighted shapley values for games in generalized characteristic function form

We study the family of weighted Shapley values for games in generalized characteristic function form. These values are defined and characterized.     

Weighted Shapley hierarchy levels values

A new class of values for cooperative games with level structure is introduced. We apply a multi-step proceeding to the weighted Shapley values. For characterization, two well-known axiomatizations of the weighted Shapley values are extended, the first one by efficiency and weighted balanced contributions and the second one by weighted standardness for two-player games and consistency. We get a new axiomatization of the Shapley levels value too.     

A value for multichoice games

A multichoice game is a generalization of a cooperative TU game in which each player has several activity levels. We study the solution for these games proposed by Van Den Nouweland et al. (1995) [Van Den Nouweland, A., Potters, J., Tijs, S., Zarzuelo, J.M., 1995. Cores and related solution concepts for multi-choice games. ZOR-Mathematical Methods of Operations Research 41, 289–311]. We show that this solution applied to the discrete cost sharing model coincides with the Aumann-Shapley method proposed by Moulin (1995) [Moulin, H., 1995. On additive methods to share joint costs. The Japanese Economic Review 46, 303–332]. Also, we show that the Aumann-Shapley value for continuum games can be obtained as the limit of multichoice values for admissible convergence sequences of multichoice games. Finally, we characterize this solution by using the axioms of balanced contributions and efficiency.     

The Shapley value,the Proper Shapley value,and sharing rules for cooperative ventures

In this note, we discuss two solutions for cooperative transferable utility games, namely the Shapley value and the Proper Shapley value. We characterize positive Proper Shapley values by affine invariance and by an axiom that requires proportional allocation of the surplus according to the individual singleton worths in generalized joint venture games. As a counterpart, we show that affine invariance and an axiom that requires equal allocation of the surplus in generalized joint venture games characterize the Shapley value.     

Bargaining sets and the core in partitioning games

Partitioning games are useful on two counts: first, in modeling situations with restricted cooperative possibilities between the agents; second, as a general framework for many unrestricted cooperative games generated by combinatorial optimization problems.We show that the family of partitioning games defined on a fixed basic collection is closed under the strategic equivalence of games, and also for taking the monotonic cover of games. Based on these properties we establish the coincidence of the Mas-Colell, the classical, the semireactive, and the reactive bargaining setswith the core for interesting balanced subclasses of partitioning games, including assignment games, tree-restricted superadditive games, and simple network games. Prepared during the author’s Bolyai János Research Fellowship. Also supported by OTKA grant T46194.     

Comment on “A new approach of cooperative interval games: The interval core and Shapley value revisited”

The interval Shapley-like value for cooperative interval games was introduced by Han et al. (2012).A theorem of characterization of the interval Shapley-like value was provided in that paper. We show that there is an error in the proof of that theorem. We indicate how to avoid this error and complete the proof.     

Sharing costs in highways: A game theoretic approach

This paper introduces a new class of games, highway games, which arise from situations where there is a common resource that agents will jointly use. That resource is an ordered set of several indivisible sections, where each section has an associated fixed cost and each agent requires some consecutive sections. We present an easy formula to calculate the Shapley value, and we present an efficient procedure to calculate the nucleolus for this class of games.     

Density estimation using game theory

In this note we show that the mathematical tools of cooperative game theory allow a successful approach to the statistical problem of estimating a density function. Specifically, any random sample of an absolutely continuous random variable determines a transferable utility game, the Shapley value of which proves to be an estimator of the density function of binned kernel and WARPing types, with good computational and statistical properties.Authors acknowledge the financial support of Spanish Ministry for Science and Technology and FEDER through projects BFM2002-03213 and BEC2002-04102-C02-02 and of Xunta de Galicia through projects PGIDT00PXI20104PR and PGIDT03PXIC20701PN. They also thank the comments of two anonymous referees.     

Minimum norm solutions for cooperative games

A solution f for cooperative games is a minimum norm solution, if the space of games has a norm such that f(v) minimizes the distance (induced by the norm) between the game v and the set of additive games. We show that each linear solution having the inessential game property is a minimum norm solution. Conversely, if the space of games has a norm, then the minimum norm solution w.r.t. this norm is linear and has the inessential game property. Both claims remain valid also if solutions are required to be efficient. A minimum norm solution, the least square solution, is given an axiomatic characterization.      

Simple games on closure spaces

LetN be a finite set. By a closure space we mean the family of the closed sets of a closure operator on 2 ^N satisfying the additional condition . A simple game on a closure space is a functionv: such that andv (N)=1. We assume simple games are monotonic. The coalitions are the closed sets of and the players are the elementsi∈N. We will give results concerning the structure of the core and the Weber set for this type of games. We show that a simple game is supermodular if and only if the game is a unanimity game and theCore ( ,v) is a stable set if and only if the gamev is a unanimity game. This work was supported by the project USE 97-191 of the University of Seville.