Egalitarian solutions in the core

In this paper we define the Lorenz stable set, a subset of the core consisting of the allocations that are not Lorenz dominated by any other allocation of the core. We introduce the leximin stable allocation, which is derived from the application of the Rawlsian criterion on the core. We also define and axiomatize the egalitarian core, a set of core allocations for which no transfer from a rich player to a poor player is possible without violating the core restrictions. We find an inclusive relation of the leximin stable allocation and of the Lorenz stable set into the egalitarian core. Received: October 1999/Final version: July 2001     

A composite run-to-the-bank rule for multi-issue allocation situations

In this paper, we propose a new extension of the run-to-the-bank rule for bankruptcy situations to the class of multi-issue allocation situations. We show that this rule always yields a core element and that it satisfies self-duality. We characterise our rule by means of a new consistency property, issue-consistency.     

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.     

Cooperation in Markovian queueing models

In this paper we study some cooperative models in Markovian queues. We stress the case of several agents agreeing to maintain a common server for their populations in which a priority scheme with preemption has been established. In this situation we propose and characterize an allocation rule for the holding costs that provides core allocations.     

排序对策的一个新的收益分配准则

针对一个机器的排序问题,给出了排序问题中成本增加量的表达式,提出了收益分配的不小于成本增加量准则。针对一类特殊的排序问题,给出一个符合不小于成本增加量分配准则的解,并证明了它满足有效性,哑元性和单调性。结合一个算例,对本文的提出的方法进行了分析验证。     

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.     

Convex and exact games with non-transferable utility

We generalize exactness to games with non-transferable utility (NTU). A game is exact if for each coalition there is a core allocation on the boundary of its payoff set.     

Towards an axiomatization of the core-center

The core-center is an allocation rule introduced in González-Díaz and Sánchez-Rodríguez (González-Díaz, J., Sánchez-Rodríguez, E., 2007. A natural selection from the core of a TU game: The core-center. International Journal of Game Theory 36, 27–46. doi: 10.1007/s00182-007-0074-5) for the class of games with a non-empty core. In this paper we present a weighted additivity axiom, which we call trade-off property, and use it to obtain two characterizations of the core-center.     

Avoiding unfairness of Owen allocations in linear production processes

This paper deals with cooperation situations in linear production problems in which a set of goods are to be produced from a set of resources so that a certain benefit function is maximized, assuming that resources not used in the production plan have no value by themselves. The Owen set is a well-known solution rule for the class of linear production processes. Despite their stability properties, Owen allocations might give null payoff to players that are necessary for optimal production plans. This paper shows that, in general, the aforementioned drawback cannot be avoided allowing only allocations within the core of the cooperative game associated to the original linear production process, and therefore a new solution set named EOwen is introduced. For any player whose resources are needed in at least one optimal production plan, the EOwen set contains at least one allocation that assigns a strictly positive payoff to such player.     

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.     

A linear proportional effort allocation rule

This paper proposes a new class of allocation rules in network games. Like the solution theory in cooperative games of how the Harsanyi dividend of each coalition is distributed among a set of players, this new class of allocation rules focuses on the distribution of the dividend of each network. The dividend of each network is allocated in proportion to some measure of each player’s effort, which is called an effort function. With linearity of the allocation rules, an allocation rule is specified by the effort functions. These types of allocation rules are called linear proportional effort allocation rules. Two famous allocation rules, the Myerson value and the position value, belong to this class of allocation rules. In this study, we provide a unifying approach to define the two aforementioned values. Moreover, we provide an axiomatic analysis of this class of allocation rules, and axiomatize the Myerson value, the position value, and their non-symmetric generalizations in terms of effort functions. We propose a new allocation rule in network games that also belongs to this class of allocation rules.     

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.     

An algorithm for computing the stable coalition structures in tree-graph communication games

We construct an algorithm which provides in finite steps the stable coalition structure(s) of tree-graph communication games and an allocation of the core: the restricted marginal contribution allocation. This paper has been presented at the St. Petersburg Institute for Economics and Mathematics (Russian Academy of Sciences), University of Santiago de Compostela (International Workshop on Game Theory), Universidad Autónoma de Barcelona, and Universidad de Sevilla. This research has been supported partially by: DGICYT PB94-1372 and UPV 035.321-HB146/96     

Dynamic realization games in newsvendor inventory centralization

Consider a set N of n (> 1) stores with single-item and single-period nondeterministic demands like in a classic newsvendor setting with holding and penalty costs only. Assume a risk-pooling single-warehouse centralized inventory ordering option. Allocation of costs in the centralized inventory ordering corresponds to modelling it as a cooperative cost game whose players are the stores. It has been shown that when holding and penalty costs are identical for all subsets of stores, the game based on optimal expected costs has a non empty core (Hartman et al. 2000, Games Econ Behav 31:26–49; Muller et al. 2002, Games Econ Behav 38:118–126). In this paper we examine a related inventory centralization game based on demand realizations that has, in general, an empty core even with identical penalty and holding costs (Hartman and Dror 2005, IIE Trans Scheduling Logistics 37:93–107). We propose a repeated cost allocation scheme for dynamic realization games based on allocation processes introduced by Lehrer (2002a, Int J Game Theor 31:341–351). We prove that the cost subsequences of the dynamic realization game process, based on Lehrer’s rules, converge almost surely to either a least square value or the core of the expected game. We extend the above results to more general dynamic cost games and relax the independence hypothesis of the sequence of players’ demands at different stages.     

Computation of the random arrival rule for bankruptcy problems

Bankruptcy problems are a fundamental class of fair division problems in microeconomics. Among the various solution concepts proposed for the problem, the random arrival rule is one of the most prominent. In this paper, we conduct a computational analysis of the rule. It is shown that the allocation returned by the rule is #P-complete to compute. The general complexity result is complemented by a pseudo-polynomial-time dynamic programming algorithm for the random arrival rule.     

On Cost Allocation in Hub-Like Networks

We consider telecommunication network design in which each pair of nodes can communicate via a direct link and the communication flow can be delivered through any path in the network. The cost of flow through each link is discounted if and only if the amount of flow exceeds a certain threshold. This exploitation of economies of scale encourages the concentration of flows and use of relatively small number of links. We will call such networks hub-like networks. The cost of services delivered through a hub-like network is distributed among its users who may be individuals or organizations with possibly conflicting interests. The cooperation of these users is essential for the exploitation of economies of scale. Consequently, there is a need to find a fair distribution of the cost of providing the service among users of such network. In order to describe this cost allocation problem we formulate the associated cooperative game, to be referred to as the hub-like game. Special attention is paid to users' contribution to economies of scale. We then demonstrate that certain cost allocation solutions (the core and the nucleolus of the hub-like game), which provide users with the incentive to cooperate, can be efficiently characterized.     

Inventory games with permissible delay in payments

Meca et al. (2004) studied a class of inventory games which arise when a group of retailers who observe demand for a common item decide to cooperate and make joint orders with the EOQ policy. In this paper, we extend their model to the situation where retailer’s delay in payments is permitted by the supplier. We introduce the corresponding inventory game with permissible delay in payments, and prove that its core is nonempty. Then, a core allocation rule is proposed which can be reached through population monotonic allocation scheme. Under this allocation rule, the grand coalition is shown to be stable from a farsighted point of view.     

Sequencing games without initial order

In this note we study uncertainty sequencing situations, i.e., one-machine sequencing situations in which no initial order is specified. We associate cooperative games with these sequencing situations, study their core, and provide links with the classic sequencing games introduced by Curiel et al. (Eur J Oper Res 40:344–351, 1989). Moreover, we propose and characterize two simple cost allocation rules for uncertainty sequencing situations with equal processing times.     

A note on coalitional manipulation and centralized inventory management

In this note we deal with inventory games as defined in Meca et al. (Math. Methods Oper. Res. 57:483–491, 2003). In that context we introduce the property of immunity to coalitional manipulation, and demonstrate that the SOC-rule (Share the Ordering Cost) is the unique allocation rule for inventory games which satisfies this property. The authors acknowledge the financial support of Ministerio de Educación y Ciencia, FEDER and Xunta de Galicia through projects SEJ2005-07637-C02-02 and PGIDIT06PXIC207038PN.