On extensions of the core and the anticore of transferable utility games

We consider several related set extensions of the core and the anticore of games with transferable utility. An efficient allocation is undominated if it cannot be improved, in a specific way, by sidepayments changing the allocation or the game. The set of all such allocations is called the undominated set, and we show that it consists of finitely many polytopes with a core-like structure. One of these polytopes is the $L_1$ -center, consisting of all efficient allocations that minimize the sum of the absolute values of the excesses. The excess Pareto optimal set contains the allocations that are Pareto optimal in the set obtained by ordering the sums of the absolute values of the excesses of coalitions and the absolute values of the excesses of their complements. The $L_1$ -center is contained in the excess Pareto optimal set, which in turn is contained in the undominated set. For three-person games all these sets coincide. These three sets also coincide with the core for balanced games and with the anticore for antibalanced games. We study properties of these sets and provide characterizations in terms of balanced collections of coalitions. We also propose a single-valued selection from the excess Pareto optimal set, the min-prenucleolus, which is defined as the prenucleolus of the minimum of a game and its dual.     

k-convexn-person games and their cores

For any natural numbersk andn, the subclass ofk-convexn-person games is introduced. In casek=n, the subclass consists of the convexn-person games. Ak-convexn-person game is characterized in several ways in terms of the core and certain marginal worth vectors. The marginal worth vectors of a game are described in terms of an upper bound for the core and the corresponding gap function. It is shown that thek-convexity of ann-person gamev is equivalent to

1. all marginal worth vectors ofv belong to the core ofv; or
2. the core ofv is the convex hull of the set consisting of all marginal worth vectors ofv; or
3. the extreme points of the core ofv are exactly the marginal worth vectors ofv.

Examples ofk-convexn-person games are also treated.     

The intermediate set and limiting superdifferential for coalitional games: between the core and the Weber set

We introduce the intermediate set as an interpolating solution concept between the core and the Weber set of a coalitional game. The new solution is defined as the limiting superdifferential of the Lovász extension and thus it completes the hierarchy of variational objects used to represent the core (Fréchet superdifferential) and the Weber set (Clarke superdifferential). It is shown that the intermediate set is a non-convex solution containing the Pareto optimal payoff vectors that depend on some chain of coalitions and marginal coalitional contributions with respect to the chain. A detailed comparison between the intermediate set and other set-valued solutions is provided. We compute the exact form of intermediate set for all games and provide its simplified characterization for the simple games and the glove game.     

On the restricted cores and the bounded core of games on distributive lattices

A game with precedence constraints is a TU game with restricted cooperation, where the set of feasible coalitions is a distributive lattice, hence generated by a partial order on the set of players. Its core may be unbounded, and the bounded core, which is the union of all bounded faces of the core, proves to be a useful solution concept in the framework of games with precedence constraints. Replacing the inequalities that define the core by equations for a collection of coalitions results in a face of the core. A collection of coalitions is called normal if its resulting face is bounded. The bounded core is the union of all faces corresponding to minimal normal collections. We show that two faces corresponding to distinct normal collections may be distinct. Moreover, we prove that for superadditive games and convex games only intersecting and nested minimal collection, respectively, are necessary. Finally, it is shown that the faces corresponding to pairwise distinct nested normal collections may be pairwise distinct, and we provide a means to generate all such collections.     

Weighted values and the core in NTU games

Monderer et al. (Int J Game Theory 21(1):27–39, 1992) proved that the core is included in the set of the weighted Shapley values in TU games. The purpose of this paper is to extend this result to NTU games. We first show that the core is included in the closure of the positively weighted egalitarian solutions introduced by Kalai and Samet (Econometrica 53(2):307–327, 1985). Next, we show that the weighted version of the Shapley NTU value by Shapley (La Decision, aggregation et dynamique des ordres de preference, Editions du Centre National de la Recherche Scientifique, Paris, pp 251–263, 1969) does not always include the core. These results indicate that, in view of the relationship to the core, the egalitarian solution is a more desirable extension of the weighted Shapley value to NTU games. As a byproduct of our approach, we also clarify the relationship between the core and marginal contributions in NTU games. We show that, if the attainable payoff for the grand coalition is represented as a closed-half space, then any element of the core is attainable as the expected value of marginal contributions.     

Stabilization and stability for the spherically symmetric Navier–Stokes–Poisson system

We consider global behaviour of viscous compressible flows with spherical symmetry driven by gravitation and an outer pressure, outside a hard core. For a general state function $p=p\left(\rho \right)$, we present global-in-time bounds for solutions with arbitrarily large data. For non-decreasing $p$, the $\omega$-limit set for the density $\rho$ is studied. For increasing $p$, uniqueness and static stability of the stationary solutions (including variational aspects) are investigated. Moreover, stabilization rate bounds toward the statically stable solutions are given and their nonlinear dynamical stability is shown.     

A solidarity value forn-person transferable utility games

In this paper, we introduce axiomatically a new value for cooperative TU games satisfying the efficiency, additivity, and symmetry axioms of Shapley (1953) and some new postulate connected with the average marginal contributions of the members of coalitions which can form. Our solution is referred to as the solidarity value. The reason is that its interpretation can be based on the assumption that if a coalition, sayS, forms, then the players who contribute toS more than the average marginal contribution of a member ofS support in some sense their weaker partners inS. Sometimes, it happens that the solidarity value belongs to the core of a game while the Shapley value does not.This research was supported by the KBN Grant 664/2/91 No. 211589101.     

A general procedure to compute mixed modified semivalues for cooperative games with structure of coalition blocks

Semivalues are solution concepts for cooperative games that assign to each player a weighted sum of his/her marginal contributions to the coalitions, where the weights only depend on the coalition size. The Shapley value and the Banzhaf value are semivalues. Mixed modified semivalues are solutions for cooperative games when we consider a priori coalition blocks in the player set. For all these solutions, a computational procedure is offered in this paper.     

Single-payoff farsighted stable sets in strategic games with dominant punishment strategies

We investigate farsighted stable sets in a class of strategic games with dominant punishment strategies. In this class of games, each player has a strategy that uniformly minimizes the other players’ payoffs for any given strategies chosen by these other players. We particularly investigate a special class of farsighted stable sets, each of which consists of strategy profiles yielding a single payoff vector. We call such a farsighted stable set as a single-payoff farsighted stable set. We propose a concept called an inclusive set that completely characterizes single-payoff farsighted stable sets in strategic games with dominant punishment strategies. We also show that the set of payoff vectors yielded by single-payoff farsighted stable sets is closely related to the strict \(\alpha \)-core in a strategic game. Furthermore, we apply the results to strategic games where each player has two strategies and strategic games associated with some market models.     

The Folk theorem for dominance solutions

The known variants of the Folk theorem characterize the sets of equilibria for repeated games. The present paper considers dominance solutions of finitely repeated games and discounted supergames with perturbed payoff functions. The paper shows that for a normal form game the set of dominance solution payoff vectors of the T-fold repetitions converges to the set of feasible and individually rational payoffs as T tends to infinity and the perturbation value tends to 0. A similar theorem is proved for supergames as the discount factor tends to 1. Received: May 1994/final version: September 1997     

Multi-dimensional vector assignment problems

We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by $m$ disjoint sets, each of which contains the same number $n$ of $p$-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an $m$-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the $m$ sets of vectors into $n$   $m$-tuples so that no two vectors from the same set are in the same $m$-tuple and so that the sum of the costs of the $m$-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed $m$. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case $m=3$ and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension $p$.     

Restricted component additive games

Curiel, Potters, Prasad, Tijs and Veltman (1993) introduced component additive games which are cooperative TU games that arise by imposing an order on the player set. Further, they introduced the -rule which allocates a core element to each component additive game.In this paper we consider the class of restricted component additive games that arise by restricting the attention to head-tail coalitions. The extreme points of the corresponding restricted core are characterized. Further, it is shown that the -rule is the barycenter of the corresponding restricted core and that the -rule coincides with the nucleolus of this restricted game.     

The general nucleolus and the reduced game property

The nucleolus of a TU game is a solution concept whose main attraction is that it always resides in any nonempty -core. In this paper we generalize the nucleolus to an arbitrary pair (,F), where is a topological space andF is a finite set of real continuous functions whose domain is . For such pairs we also introduce the least core concept. We then characterize the nucleolus forclasses of such pairs by means of a set of axioms, one of which requires that it resides in the least core. It turns out that different classes require different axiomatic characterizations.One of the classes consists of TU-games in which several coalitions may be nonpermissible and, moreover, the space of imputations is required to be a certain generalized core. We call these gamestruncated games. For the class of truncated games, one of the axioms is a new kind ofreduced game property, in which consistency is achieved even if some coalitions leave the game, being promised the nucleolus payoffs. Finally, we extend Kohlberg's characterization of the nucleolus to the class of truncated games.     

Descent methods for convex essentially smooth minimization

Consider the problem of minimizing a convex essentially smooth function over a polyhedral set. For the special case where the cost function is strictly convex, we propose a feasible descent method for this problem that chooses the descent directions from a finite set of vectors. When the polyhedral set is the nonnegative orthant or the entire space, this method reduces to a coordinate descent method which, when applied to certain dual of linearly constrained convex programs with strictly convex essentially smooth costs, contains as special cases a number of well-known dual methods for quadratic and entropy (either –logx orx logx) optimization. Moreover, convergence of these dual methods can be inferred from a general convergence result for the feasible descent method. When the cost function is not strictly convex, we propose an extension of the feasible descent method which makes descent along the elementary vectors of a certain subspace associated with the polyhedral set. The elementary vectors are not stored, but generated using the dual rectification algorithm of Rockafellar. By introducing an -complementary slackness mechanism, we show that this extended method terminates finitely with a solution whose cost is within an order of of the optimal cost. Because it uses the dual rectification algorithm, this method can exploit the combinatorial structure of the polyhedral set and is well suited for problems with a special (e.g., network) structure.This work was partially supported by the US Army Research Office Contract No. DAAL03-86-K-0171 and by the National Science Foundation Grant No. ECS-85-19058.     

Strongly essential coalitions and the nucleolus of peer group games

Most of the known efficient algorithms designed to compute the nucleolus for special classes of balanced games are based on two facts: (i) in any balanced game, the coalitions which actually determine the nucleolus are essential; and (ii) all essential coalitions in any of the games in the class belong to a prespecified collection of size polynomial in the number of players. We consider a subclass of essential coalitions, called strongly essential coalitions, and show that in any game, the collection of strongly essential coalitions contains all the coalitions which actually determine the core, and in case the core is not empty, the nucleolus and the kernelcore. As an application, we consider peer group games, and show that they admit at most 2n−1 strongly essential coalitions, whereas the number of essential coalitions could be as much as 2ⁿ⁻¹. We propose an algorithm that computes the nucleolus of an n-player peer group game in time directly from the data of the underlying peer group situation.Research supported in part by OTKA grant T030945. The authors thank a referee and the editor for their suggestions on how to improve the presentation     

The core of games on ordered structures and graphs

In cooperative games, the core is the most popular solution concept, and its properties are well known. In the classical setting of cooperative games, it is generally assumed that all coalitions can form, i.e., they are all feasible. In many situations, this assumption is too strong and one has to deal with some unfeasible coalitions. Defining a game on a subcollection of the power set of the set of players has many implications on the mathematical structure of the core, depending on the precise structure of the subcollection of feasible coalitions. Many authors have contributed to this topic, and we give a unified view of these different results.     

The core of games on ordered structures and graphs

In cooperative games, the core is the most popular solution concept, and its properties are well known. In the classical setting of cooperative games, it is generally assumed that all coalitions can form, i.e., they are all feasible. In many situations, this assumption is too strong and one has to deal with some unfeasible coalitions. Defining a game on a subcollection of the power set of the set of players has many implications on the mathematical structure of the core, depending on the precise structure of the subcollection of feasible coalitions. Many authors have contributed to this topic, and we give a unified view of these different results.     

Coalition formation with local public goods and group-size effect

Many public goods that are provided by coalitions have a group-size effect. Namely, people prefer to consume a public good in a larger coalition. This paper studies local public goods games with anonymous and separable group-size effect. The core is nonempty when coalition feasible sets are monotonic and players’ preferences over public goods satisfy a condition called cardinal connectedness. Moreover, a core allocation consists of connected coalitions.