Processing games with restricted capacities

This paper analyzes processing problems and related cooperative games. In a processing problem there is a finite set of jobs, each requiring a specific amount of effort to be completed, whose costs depend linearly on their completion times. The main feature of the model is a capacity restriction, i.e., there is a maximum amount of effort per time unit available for handling jobs. There are no other restrictions whatsoever on the processing schedule.Assigning to each job a player and letting each player have an individual capacity for handling jobs, each coalition of cooperating players in fact faces a processing problem with the coalitional capacity being the sum of the individual capacities of the members. The corresponding processing game summarizes the minimal joint costs for every coalition. It turns out that processing games are totally balanced. The proof of this statement is constructive and provides a core element in polynomial time.     

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 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.     

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.      

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.     

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.     

Cost allocation games with information costs

We propose a simple model which embeds cost allocation games into a richer structure to take into account that information on costs can be itself costly. The model is an outgrowth of experience on cost allocation for consortia of municipalities dealing with garbage collection.The authors thank an anonymous referee for having pointed out a mistake in the previous version of Lemma 1     

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.     

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.     

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.     

Coalitional games: Monotonicity and core

We characterize a monotonic core solution defined on the class of veto balanced games. We also discuss what restricted versions of monotonicity are possible when selecting core allocations. We introduce a family of monotonic core solutions for veto balanced games and we show that, in general, the per capita nucleolus is not monotonic.     

Convex multi-choice games: Characterizations and monotonic allocation schemes

This paper focuses on new characterizations of convex multi-choice games using the notions of exactness and superadditivity. Furthermore, level-increase monotonic allocation schemes (limas) on the class of convex multi-choice games are introduced and studied. It turns out that each element of the Weber set of such a game is extendable to a limas, and the (total) Shapley value for multi-choice games generates a limas for each convex multi-choice game.     

Operations research games: A survey

This paper surveys the research area of cooperative games associated with several types of operations research problems in which various decision makers (players) are involved. Cooperating players not only face a joint optimisation problem in trying, e.g., to minimise total joint costs, but also face an additional allocation problem in how to distribute these joint costs back to the individual players. This interplay between optimisation and allocation is the main subject of the area of operations research games. It is surveyed on the basis of a distinction between the nature of the underlying optimisation problem: connection, routing, scheduling, production and inventory.     

A core of voting games with improved foresight

This paper considers voting situations in which the vote takes place iteratively. If a coalition replaces the status quo a with a contestant b, then b becomes the new status quo, and the vote goes on until a candidate is reached that no winning coalition is willing to replace. It is well known that the core, that is, the set of undominated alternatives, may be empty. To alleviate this problem, Rubinstein [Rubinstein, A., 1980. Stability of decision systems under majority rule. Journal of Economic Theory 23, 150–159] assumes that voters look forward one vote before deciding to replace an alternative by a new one. They will not do so if the new status quo is going to be replaced by a third that is less interesting than the first. The stability set, that is, the set of undominated alternatives under this behavior, is always non-empty when preferences are strict. However, this is not necessarily the case when voters’ indifference is allowed. Le Breton and Salles [Le Breton, M., Salles, M., 1990. The stability set of voting games: Classification and generecity results. International Journal of Game Theory 19, 111–127], Li [Li, S., 1993. Stability of voting games. Social Choice and Welfare 10, 51–56] and Martin [Martin, M., 1998. Quota games and stability set of order d. Economic Letters 59, 145–151] extend the sophistication of the voters by having them look d votes forward along the iterative process. For d sufficiently large, the resulting set of undominated alternatives is always non-empty even if indifference is allowed. We show that it may be unduly large. Next, by assuming that other voters along a chain of votes are also rational, that is, they also look forward to make sure that the votes taking place later on will not lead to a worst issue for them, we are able to reduce the size of this set while insuring its non-emptiness. Finally, we show that a vote with sufficient foresight satisfies a no-regret property, contrarily to the classical core and the stability set.     

Cooperative facility location games

The location of facilities in order to provide service for customers is a well-studied problem in the operations research literature. In the basic model, there is a predefined cost for opening a facility and also for connecting a customer to a facility, the goal being to minimize the total cost. Often, both in the case of public facilities (such as libraries, municipal swimming pools, fire stations, … ) and private facilities (such as distribution centers, switching stations, … ), we may want to find a ‘fair’ allocation of the total cost to the customers—this is known as the cost allocation problem. A central question in cooperative game theory is whether the total cost can be allocated to the customers such that no coalition of customers has any incentive to build their own facility or to ask a competitor to service them. We establish strong connections between fair cost allocations and linear programming relaxations for several variants of the facility location problem. In particular, we show that a fair cost allocation exists if and only if there is no integrality gap for a corresponding linear programming relaxation; this was only known for the simplest unconstrained variant of the facility location problem. Moreover, we introduce a subtle variant of randomized rounding and derive new proofs for the existence of fair cost allocations for several classes of instances. We also show that it is in general NP-complete to decide whether a fair cost allocation exists and whether a given allocation is fair.     

On balanced games with infinitely many players: Revisiting Schmeidler's result

We consider transferable utility cooperative games with infinitely many players and the core understood in the space of bounded additive set functions. We show that, if a game is bounded below, then its core is non-empty if and only if the game is balanced. This finding generalizes Schmeidler (1967) “On Balanced Games with Infinitely Many Players”, where the game is assumed to be non-negative. We also generalize Schmeidler's (1967) result to the case of restricted cooperation too.     

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.