Deposit games with reinvestment

In a deposit game coalitions are formed by players combining their capital. The proceeds of their investments then have to be divided among those players. The current model extends earlier work on capital deposits by allowing reinvestment of returns. Two specific subclasses of deposit games are introduced. These subclasses provide insight in two extreme cases. It is seen that each term dependent deposit game possesses a core element. Capital dependent deposit games are also shown to have a core element and even a population monotonic allocation scheme if the revenue function exhibits increasing returns to scale. Furthermore, it is shown that all superadditive games are deposit games if one allows for debt.     

On the population monotonicity of independent set games

An independent set game is a cooperative game dealing with profit sharing in the maximum independent set problem. A population monotonic allocation scheme is a rule specifying how to share the profit of each coalition among its participants such that every participant is better off when the coalition expands. In this paper, we provide a necessary and sufficient characterization for independent set games admitting population monotonic allocation schemes. Moreover, our characterization can be verified efficiently.     

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.     

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.     

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.     

Robust dynamic cooperative games

Classical cooperative game theory is no longer a suitable tool for those situations where the values of coalitions are not known with certainty. We consider a dynamic context where at each point in time the coalitional values are unknown but bounded by a polyhedron. However, the average value of each coalition in the long run is known with certainty. We design “robust” allocation rules for this context, which are allocation rules that keep the coalition excess bounded while guaranteeing each player a certain average allocation (over time). We also present a joint replenishment application to motivate our model. We thank two anonymous referees for their valuable comments.     

The not-quite non-atomic game: Non-emptiness of the core in large production games

We show that, in cooperative production games, when the production functions are not concave, the core may well be empty. However, as the number of players increases (subject to some regularity conditions), the relative deficit obtained by using concavified functions decreases to zero. Furthermore, differentiability of the functions will cause the absolute deficit to go to zero.     

On the core of cost-revenue games: Minimum cost spanning tree games with revenues

In this paper, we analyze cost sharing problems arising from a general service by explicitly taking into account the generated revenues. To this cost-revenue sharing problem, we associate a cooperative game with transferable utility, called cost-revenue game. By considering cooperation among the agents using the general service, the value of a coalition is defined as the maximum net revenues that the coalition may obtain by means of cooperation. As a result, a coalition may profit from not allowing all its members to get the service that generates the revenues. We focus on the study of the core of cost-revenue games. Under the assumption that cooperation among the members of the grand coalition grants the use of the service under consideration to all its members, it is shown that a cost-revenue game has a nonempty core for any vector of revenues if, and only if, the dual game of the cost game has a large core. Using this result, we investigate minimum cost spanning tree games with revenues. We show that if every connection cost can take only two values (low or high cost), then, the corresponding minimum cost spanning tree game with revenues has a nonempty core. Furthermore, we provide an example of a minimum cost spanning tree game with revenues with an empty core where every connection cost can take only one of three values (low, medium, or high cost).     

Approximating the least core value and least core of cooperative games with supermodular costs

We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a 3-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time algorithm for computing a cost allocation in the 2-approximate least core of these games. This approximation framework extends naturally to submodular profit cooperative games. For scheduling games, a special class of supermodular cost cooperative games, we give a fully polynomial-time approximation scheme for computing the least core value. For matroid profit games, a special class of submodular profit cooperative games, we give exact polynomial-time algorithms for computing the least core value as well as a least core cost allocation.     

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     

Multi-choice clan games and their core

In this paper, we consider market situations with two corners. One corner consists of a group of powerful agents with yes-or-no choices and clan behavior. The other corner consists of non-powerful agents with multi-choices regarding the extent at which cooperation with the clan can be achieved. Multi-choice clan games arise from such market situations. The focus is on the analysis of the core of multi-choice clan games. Several characterizations of multi-choice clan games by the shape of the core are given, and the connection between the convexity of a multi-choice clan game and the stability of its core is studied.      

Extended cooperative networks games

We present here a pricing model which is an extension of the Cooperative Game concept and which includes a notion of Price-Dependent Demand. We present some existence results as well as some algorithms, and conclude by discussing a specific problem related to Network Pricing.     

On the bargaining set, kernel and core of superadditive games

We prove that for superadditive games a necessary and sufficient condition for the bargaining set to coincide with the core is that the monotonic cover of the excess game induced by a payoff be balanced for each imputation in the bargaining set. We present some new results obtained by verifying this condition for specific classes of games. For N-zero-monotonic games we show that the same condition required at each kernel element is also necessary and sufficient for the kernel to be contained in the core. We also give examples showing that to maintain these characterizations, the respective assumptions on the games cannot be lifted. Received: March 1998/Revised version: December 1998     

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.      

On characterization of the core of lane covering games via dual solutions

The lane covering game (LCG) is a cooperative game where players cooperate to reduce the cost of cycles that cover their required lanes on a network. We discuss the possibilities/impossibilities of a complete characterization of the core via dual solutions in LCGs played among a collection of shippers, each with a number of service requirements along some lanes, and show that such a complete characterization is possible if each shipper has at most one service requirement.     

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.     

Processing games with shared interest

This paper introduces processing problems with shared interest as an extension of processing situations with restricted capacities (Meertens, M., et al., Processing games with restricted capacities, 2004). Next to an individual capacity to handle jobs, each player now may have interest in the completion of more than one job, and the degrees of interest may vary among players. By cooperating the players can bundle their capacities and follow an optimal processing scheme to minimize total joint costs. The resulting cost allocation problem is analyzed by considering an associated cooperative cost game. An explicit core allocation of this game is provided.