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.     

The nucleolus for cooperative games with arbitrary bounds of individual rationality

We consider cooperative games with a given bound for individual rationality. We introduce the nucleolus with respect to the set of preimputations satisfying the newly defined bounds of rationality. An axiomatization of this nucleolus is given.     

Network strength games: the core and the nucleolus

Mathematical Programming - The maximum number of edge-disjoint spanning trees in a network has been used as a measure of the strength of a network. It gives the number of disjoint ways that the...     

On the core and nucleolus of directed acyclic graph games

We introduce directed acyclic graph (DAG) games, a generalization of standard tree games, to study cost sharing on networks. This structure has not been previously analyzed from a cooperative game theoretic perspective. Every monotonic and subadditive cost game—including monotonic minimum cost spanning tree games—can be modeled as a DAG-game. We provide an efficiently verifiable condition satisfied by a large class of directed acyclic graphs that is sufficient for the balancedness of the associated DAG-game. We introduce a network canonization process and prove various structural results for the core of canonized DAG-games. In particular, we characterize classes of coalitions that have a constant payoff in the core. In addition, we identify a subset of the coalitions that is sufficient to determine the core. This result also guarantees that the nucleolus can be found in polynomial time for a large class of DAG-games.     

On dominance core and stable sets for cooperative ellipsoidal games

Abstract

The allocation problem of rewards or costs is a central question for individuals and organizations contemplating cooperation under uncertainty. The involvement of uncertainty in cooperative games is motivated by the real world where noise in observation and experimental design, incomplete information and further vagueness in preference structures and decision-making play an important role. The theory of cooperative ellipsoidal games provides a new game theoretical angle and suitable tools for answering this question. In this paper, some solution concepts using ellipsoids, namely the ellipsoidal imputation set, the ellipsoidal dominance core and the ellipsoidal stable sets for cooperative ellipsoidal games, are introduced and studied. The main results contained in the paper are the relations between the ellipsoidal core, the ellipsoidal dominance core and the ellipsoidal stable sets of such a game.     

On the core of cooperative queueing games

We consider a class of cooperative games for managing several canonical queueing systems. When cooperating parties invest optimally in common capacity or choose the optimal amount of demand to serve, cooperation leads to “single-attribute” games whose characteristic function is embedded in a one-dimensional function. We show that when and only when the latter function is elastic will all embedded games have a non-empty core, and the core contains a population monotonic allocation. We present sufficient conditions for this property to be satisfied. Our analysis reveals that in most Erlang B and Erlang C queueing systems, the games under our consideration have a non-empty core, but there are exceptions, which we illustrate through a counterexample.     

On cooperative games with large monotonic core

Cooperative games with large core were introduced by Sharkey (Int. J. Game Theory 11:175–182, 1982), and the concept of Population Monotonic Allocation Scheme was defined by Sprumont (Games Econ. Behav. 2:378–394, 1990). Inspired by these two concepts, Moulin (Int. J. Game Theory 19:219–232, 1990) introduced the notion of large monotonic core giving a characterization for three-player games. In this paper we prove that all games with large monotonic core are convex. We give an effective criterion to determine whether a game has a large monotonic core and, as a consequence, we obtain a characterization for the four-player case.     

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.     

The least square values and the shapley value for cooperative TU games

The main result proved in this paper is the fact that any Least Square Value is the Shapley value of a game obtained from the given game by rescaling. An Average per capita formula for Least Square Values, similar to the formula for the Shapley value (Dragan (1992)), will lead to this conclusion and allow a parallel computation for these values. The potential for the Least Square Values, a potential basis relative to Least Square Values and an approach similar to the one used for the Shapley value is allowing us to solve the Inverse problem for Least Square Values.     

The least square prenucleolus and the least square nucleolus. Two values for TU games based on the excess vector

The nucleolus and the prenucleolus are solution concepts for TU games based on the excess vector that can be associated to any payoff vector. Here we explore some solution concepts resulting from a payoff vector selection based also on the excess vector but by means of an assessment of their relative fairness different from that given by the lexicographical order. We take the departure consisting of choosing the payoff vector which minimizes the variance of the resulting excesses of the coalitions. This procedure yields two interesting solution concepts, both a prenucleolus-like and a nucleolus-like notion, depending on which set is chosen to set up the minimizing problem: the set of efficient payoff vectors or the set of inputations. These solution concepts, which, paralleling the prenucleolus and the nucleolus, we call least square prenucleolus and least square nucleolus, are easy to calculate and exhibit nice properties. Different axiomatic characterizations of the former are established, some of them by means of consistency for a reasonable reduced game concept.     

Monotonicity of the core and value in dynamic cooperative games

We examine behavior of the core and value of certain classes of cooperative games in which a dynamic aspect is introduced. New players are added to the games while the underlying structure is held constant. This is done by considering games that satisfy properties like convexity, or games that are derived from optimization problems in which a player's addition can be defined naturally. For such games we give conditions regarding monotonicity of the core and value.     

A cooperative game of information trading: The core,the nucleolus and the kernel

A certain trade of the information about a technological innovation between the initial owner of the information andn identical producers is studied by means of a cooperative game theoretic approach. The information trading situation is modelled as a cooperative (n+1)-person game with side payments. The symmetrical strong -cores (including the core), the nucleolus and the kernel of the cooperative game model are determined. Interpretations of these game theoretic solutions and their implications for the information trading problem are given.     

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.     

The asymptotic core,nucleolus and Shapley value of smooth market games with symmetric large players

We examine the asymptotic nucleolus of a smooth and symmetric oligopoly with an atomless sector in a transferable utility (TU) market game. We provide sufficient conditions for the asymptotic core and the nucleolus to coincide with the unique TU competitive payoff distribution. This equivalence results from nucleolus of a finite TU market game belonging to its core, the core equivalence in a symmetric oligopoly with identical atoms and single-valuedness of the core in the limiting smooth game. In some cases (but not always), the asymptotic Shapley value is more favourable for the large traders than the nucleolus, in contrast to the monopoly case (Einy et al. in J Econ Theory 89(2):186–206, 1999), where the nucleolus allocation is larger than the Shapley value for the atom.     

The selectope for cooperative games

The selectope of a cooperative transferable utility game is the convex hull of the payoff vectors obtained by assigning the Harsanyi dividends of the coalitions to members determined by so-called selectors. The selectope is studied from a set-theoretic point of view, as superset of the core and of the Weber set; and from a value-theoretic point of view, as containing weighted Shapley values, random order values, and sharing values. Received May 1997/Revised version September 1999     

On the core of multiple longest traveling salesman games

In this paper we introduce multiple longest traveling salesman (MLTS) games. An MLTS game arises from a network in which a salesman has to visit each node (player) precisely once, except to his home location, in such an order that maximizes the total reward. First it is shown that the value of a coalition of an MLTS game is determined by taking the maximum of suitable combinations of one and two person coalitions. Secondly it is shown that MLTS games with five or less players have a nonempty core. However, a six player MLTS game may have an empty core. For the special instance in which the reward between a pair of nodes is equal to 0 or 1, we provide relations between the structure of the core and the underlying network.     

An algorithm for finding the nucleolus of assignment games

Assignment games with side payments are models of certain two-sided markets. It is known that prices which competitively balance supply and demand correspond to elements in the core. The nucleolus, lying in the lexicographic center of the nonempty core, has the additional property that it satisfies each coalition as much as possible. The corresponding prices favor neither the sellers nor the buyers, hence provide some stability for the market. An algorithm is presented that determines the nucleolus of an assignment game. It generates a finite number of payoff vectors, monotone increasing on one side, and decreasing on the other. The decomposition of the payoff space and the lattice-type structure of the feasible set are utilized in associating a directed graph. Finding the next payoff is translated into determining the lengths of longest paths to the nodes, if the graph is acyclic, or otherwise, detecting the cycle(s). In an (m,n)-person assignment game withm = min(m,n) the nucleolus is found in at most 1/2·m(m + 3) steps, each one requiring at mostO(m·n) elementary operations.