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.     

Solution concepts ofk-convexn-person games

For any positive integersk andn, the subclass ofk-convexn-person games is considered. In casek=n, we are dealing with convexn-person games. Three characterizations ofk-convexn-person games, formulated in terms of the core and certain adapted marginal worth vectors, are given. Further it is shown that fork-convexn-person games the intersection of the (pre)kernel with the core consists of a unique point (namely the nucleolus), but that the (pre)kernel may contain points outside the core. For certain 1-convex and 2-convexn-person games the part of the bargaining set outside the core is even disconnected with the core. The Shapley value of ank-convexn-person game can be expressed in terms of the extreme points of the core and a correction-vector whenever the game satisfies a certain symmetric condition. Finally, theτ-value of ank-convexn-person game is given.     

A simple procedure to obtain the extreme core allocations of an assignment market

Given an assignment market, we introduce a set of vectors, one for each possible ordering on the player set, which we name the max-payoff vectors. Each one of these vectors is obtained recursively only making use of the assignment matrix. Those max-payoff vectors that are efficient turn out to give the extreme core allocations of the market. When the assignment game has a large core, all the max-payoff vectors are extreme core allocations.     

Highway games on weakly cyclic graphs

A highway problem is determined by a connected graph which provides all potential entry and exit vertices and all possible edges that can be constructed between vertices, a cost function on the edges of the graph and a set of players, each in need of constructing a connection between a specific entry and exit vertex. Mosquera (2007) introduce highway problems and the corresponding cooperative cost games called highway games to address the problem of fair allocation of the construction costs in case the underlying graph is a tree. In this paper, we study the concavity and the balancedness of highway games on weakly cyclic graphs. A graph G is called highway-game concave if for each highway problem in which G is the underlying graph the corresponding highway game is concave. We show that a graph is highway-game concave if and only if it is weakly triangular. Moreover, we prove that highway games on weakly cyclic graphs are balanced.     

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.     

Analysis of the core of multisided Böhm-Bawerk assignment markets

We introduce the class of multisided Böhm-Bawerk assignment games which generalizes the well-known two-sided Böhm-Bawerk assignment games to markets with an arbitrary number of sectors. We reach the core and the corresponding extreme allocations of any multisided Böhm-Bawerk assignment game by means of an associated convex game defined on the set of sectors instead of the set of sellers and buyers. We also study when the core of a multisided Böhm-Bawerk assignment game is stable in the sense of von Neumann–Morgenstern.     

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.     

A unifying model for matrix-based pairing situations

We present a unifying framework for transferable utility coalitional games that are derived from a non-negative matrix in which every entry represents the value obtained by combining the corresponding row and column. We assume that every row and every column is associated with a player, and that every player is associated with at most one row and at most one column. The instances arising from this framework are called pairing games, and they encompass assignment games and permutation games as two polar cases. We show that the core of a pairing game is always non-empty by proving that the set of pairing games coincides with the set of permutation games. Then we exploit the wide range of situations comprised in our framework to investigate the relationship between pairing games that have different player sets, but are defined by the same underlying matrix. We show that the core and the set of extreme core allocations are immune to the merging of a row player with a column player. Moreover, the core is also immune to the reverse manipulation, i.e., to the splitting of a player into a row player and a column player. Other common solution concepts fail to be either merging-proof or splitting-proof in general.     

An axiomatic approach to egalitarianism in TU-games

A core concept is a solution concept on the class of balanced games that exclusively selects core allocations. We show that every continuous core concept that satisfies both the equal treatment property and a new property called independence of irrelevant core allocations (IIC) necessarily selects egalitarian allocations. IIC requires that, if the core concept selects a certain core allocation for a given game, and this allocation is still a core allocation for a new game with a core that is contained in the core of the first game, then the core concept also chooses this allocation as the solution to the new game. When we replace the continuity requirement by a weak version of additivity we obtain an axiomatization of the egalitarian solution concept that assigns to each balanced game the core allocation minimizing the Euclidean distance to the equal share allocation.     

A note on a core catcher of a cooperative game

In Driessen (1986) it is shown that for games satisfying a certain condition the core of the game is included in the convex hull of the set of certain marginal worth vectors of the game, while it is conjectured that the inclusion holds without any condition on the game. In this note it is proved that the inclusion holds for all games.

---

Zusammenfassung In Driessen (1986) wurde für Spiele, die eine gewisse Bedingung erfüllen, gezeigt, da\ der Kern des Spieles in der konvexen Hülle von gewissen Vektoren der Marginalwerte liegt. Es wurde vermutet, da\ diese Inklusion ohne weitere Bedingung an das Spiel gilt. In dieser Note wird nun gezeigt, da\ die Inklusion für alle Spiele gilt.

     

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.     

Information market games

In this paper information markets with perfect patent protection and only one initial owner of the information are studied by means of cooperative game theory. To each information market of this type a cooperative game with sidepayments is constructed. These cooperative games are called information (market) games. The set of all information games with fixed player set is a cone in the set of all cooperative games with the same player set. Necessary and sufficient conditions are given in order that a cooperative game is an information game. The core of this kind of games is not empty and is also the minimal subsolution of the game. The core is the image of an (n-1)-dimensional hypercube under an affine transformation, (= hyperparallellopiped), the nucleolus and -value coincide with the center of the core. The Shapley value is computed and may lie inside or outside the core. The Shapley value coincides with the nucleolus and the -value if and only if the information game is convex. In this case the core is also a stable set.     

A convex representation of totally balanced games

We analyze the least increment function, a convex function of n variables associated to an n-person cooperative game. Another convex representation of cooperative games, the indirect function, has previously been studied. At every point the least increment function is greater than or equal to the indirect function, and both functions coincide in the case of convex games, but an example shows that they do not necessarily coincide if the game is totally balanced but not convex. We prove that the least increment function of a game contains all the information of the game if and only if the game is totally balanced. We also give necessary and sufficient conditions for a function to be the least increment function of a game as well as an expression for the core of a game in terms of its least increment function.     

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.     

Characterizations ofk-Convex Games

The paper deals with the class of k-convex n-person transferable utility games which has clear affinities to the well-known class of convex n-person TU-games. Five new characterizations of a k-convex n-person game are presented in terms of the following key notions:(1) the unanimity coordinates, as determined by the algebraic representation of the game with respect to the particular basis consisting of all n-person unanimity games; (2) the second order partial derivatives of Owen's multilinear extension of the game; (3) the coremembership of the adjusted marginal worth vectors of the game (taking into account even or odd orderings of players); (4) a min-modular decomposition of an appropriately chosen cover-game (the decomposition of which is based on the adjusted marginal worth vectors of the initial game); (5) the concavity of the Lovász extension of the associated cover-game     

A system-theoretic model for cooperation, interaction and allocation

A system-theoretic approach to cooperation, interaction and allocation is presented that simplifies, unifies and extends the results on classical cooperative games and their generalizations. In particular, a general Weber theory of linear values is obtained and a new theory for local cooperation and general interaction indices is established. The model is dynamic and based on the notion of states of cooperation that change under actions of agents. Careful distinction between “local” states of cooperation and general “system” states leads to a notion of entropy for arbitrary non-negative and efficient allocations and thus to a new information-theoretic criterion for fairness of allocation mechanisms. Shapley allocations, for instance, are exhibited as arising from random walks with maximal entropy. For a large class of cooperation systems, a characterization of game symmetries in terms of λ-values is given. A concept for cores and Weber sets is proposed and it is shown that a Weber set of a game with selection structure always contains the core.     

Shapley mappings and the cumulative value for n-person games with fuzzy coalitions

In this paper we prove existence and uniqueness of the so-called Shapley mapping, which is a solution concept for a class of n-person games with fuzzy coalitions whose elements are defined by the specific structure of their characteristic functions. The Shapley mapping, when it exists, associates to each fuzzy coalition in the game an allocation of the coalitional worth satisfying the efficiency, the symmetry, and the null-player conditions. It determines a “cumulative value” that is the “sum” of all coalitional allocations for whose computation we provide an explicit formula.     

Asymptotic equivalence between Cournot–Nash and Walras equilibria in exchange economies with atoms and an atomless part

In this paper, we consider an exchange economy à la Shitovitz (Econometrica 41:467–501, 1973), with atoms and an atomless set. We associate with it a strategic market game of the kind first proposed by Lloyd S. Shapley, known as the Shapley window model. We analyze the relationship between the set of the Cournot–Nash allocations of the strategic market game and the Walras allocations of the exchange economy with which it is associated. We show, with an example, that even when atoms are countably infinite, any Cournot–Nash allocation of the game is not a Walras allocation of the underlying exchange economy. Accordingly, in the original spirit of Cournot (Recherches sur les principes mathématiques de la théorie des richesses. Hachette, Paris, 1838), we partially replicate the mixed exchange economy by increasing the number of atoms, without affecting the atomless part, and ensuring that the measure space of agents remains finite. Our main theorem shows that any sequence of Cournot–Nash allocations of the strategic market games associated with the partial replications of the exchange economy has a limit point for each trader and that the assignment determined by these limit points is a Walrasian allocation of the original economy.