A note on the multiple partners assignment game

In the assignment game of Shapley and Shubik [Shapley, L.S., Shubik, M., 1972. The assignment game. I. The core, International journal of Game Theory 1, 11-130] agents are allowed to form one partnership at most. That paper proves that, in the context of firms and workers, given two stable payoffs for the firms there is a stable payoff which gives each firm the larger of the two amounts and also one which gives each of them the smaller amount. Analogous result applies to the workers. Sotomayor [Sotomayor, M., 1992. The multiple partners game. In: Majumdar, M. (Ed.), Dynamics and Equilibrium: Essays in Honor to D. Gale. Mcmillian, pp. 322-336] extends this analysis to the case where both types of agents may form more than one partnership and an agent`s payoff is multi-dimensional. Instead, this note concentrates in the total payoff of the agents. It is then proved the rather unexpected result that again the maximum of any pair of stable payoffs for the firms is stable but the minimum need not be, even if we restrict the multiplicity of partnerships to one of the sides. (C) 2009 Elsevier B.V. All rights reserved.

Adjusting prices in the multiple-partners assignment game

Starting with an initial price vector, prices are adjusted in order to eliminate the excess demand and at the same time to keep the transfers to the sellers as low as possible. In each step of the auction, to which set of sellers should those transfers be made is the key issue in the description of the algorithm. We assume additively separable utilities and introduce a novel distinction by considering multiple sellers owing multiple identical objects and multiple buyers with an exogenously defined quota, consuming more than one object but at most one unit of a seller`s good and having multi-dimensional payoffs. This distinction induces a necessarily more complicated construction of the over-demanded sets than the constructions of these sets for the other assignment games. For this approach, our mechanism yields the buyer-optimal competitive equilibrium payoff, which equals the buyer-optimal stable payoff. The symmetry of the model allows to getting the seller-optimal stable payoff and the seller-optimal competitive equilibrium payoff can then be also derived.

A generalized assignment game

The proposed game is a natural extension of the Shapley and Shubik Assignment Game to the case where each seller owns a set of different objets instead of only one indivisible object. We propose definitions of pairwise stability and group stability that are adapted to our framework. Existence of both pairwise and group stable outcomes is proved. We study the structure of the group stable set and we finally prove that the set of group stable payoffs forms a complete lattice with one optimal group stable payoff for each side of the market.

The Multiple-partners assignment game with heterogeneous sales and multi-unit demands: competitive equilibria

A multiple-partners assignment game with heterogeneous sales and multiunit demands consists of a set of sellers that own a given number of indivisible units of (potentially many different) goods and a set of buyers who value those units and want to buy at most an exogenously fixed number of units. We define a competitive equilibrium for this generalized assignment game and prove its existence by using only linear programming. In particular, we show how to compute equilibrium price vectors from the solutions of the dual linear program associated to the primal linear program defined to find optimal assignments. Using only linear programming tools, we also show (i) that the set of competitive equilibria (pairs of price vectors and assignments) has a Cartesian product structure: each equilibrium price vector is part of a competitive equilibrium with all optimal assignments, and vice versa; (ii) that the set of (restricted) equilibrium price vectors has a natural lattice structure; and (iii) how this structure is translated into the set of agents' utilities that are attainable at equilibrium.

On Cooperative solutions of a generalized assignment game: limit theorems to the set of competitive equilibria

We study two cooperative solutions of a market with indivisible goods modeled as a generalized assignment game: Set-wise stability and Core. We first establish that the Set-wise stable set is contained in the Core and it contains the non-empty set of competitive equilibrium payoffs. We then state and prove three limit results for replicated markets. First, the sequence of Cores of replicated markets converges to the set of competitive equilibrium payoffs when the number of replicas tends to infinity. Second, the Set-wise stable set of a two-fold replicated market already coincides with the set of competitive equilibrium payoffs. Third, for any number of replicas there is a market with a Core payoff that is not a competitive equilibrium payoff.

On the dimension of the core of the assignment game

The set of optimal matchings in the assignment matrix allows to define a reflexive and symmetric binary relation on each side of the market, the equal-partner binary relation. The number of equivalence classes of the transitive closure of the equal-partner binary relation determines the dimension of the core of the assignment game. This result provides an easy procedure to determine the dimension of the core directly from the entries of the assignment matrix and shows that the dimension of the core is not as much determined by the number of optimal matchings as by their relative position in the assignment matrix.

An axiomatization of the nucleolus of the assignment game

[cat] En el domini dels jocs bilaterals d’assignació, es presenta una axiomàtica del nucleolus com l´unica solució que compleix les propietats de consistència respecte del joc derivat definit per Owen (1992) i monotonia de les queixes dels sectors respecte de la seva cardinalitat. Com a conseqüència obtenim una caracterització geomètrica del nucleolus mitjançant una propietat de bisecció més forta que la que satisfan els punts del kernel (Maschler et al, 1979).

The assignment game: core bounds for mixed-pair coalitions

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the coreof the game. These games will be called buyer¿seller exact games and satisfy the condition that each mixed¿pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyerseller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer¿seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed¿pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a ¿45o¿lattice¿ by means of the core of an assignment game can now be answered

The extreme core allocations of the assignment game

Although assignment games are hardly ever convex, in this paper a characterization of their set or extreme points of the core is provided, which is also valid for the class of convex games. For each ordering in the player set, a payoff vector is defined where each player receives his marginal contribution to a certain reduced game played by his predecessors. We prove that the whole set of reduced marginal worth vectors, which for convex games coincide with the usual marginal worth vectors, is the set of extreme points of the core of the assignment game

The extreme core allocations of the assignment game

Although assignment games are hardly ever convex, in this paper a characterization of their set or extreme points of the core is provided, which is also valid for the class of convex games. For each ordering in the player set, a payoff vector is defined where each player receives his marginal contribution to a certain reduced game played by his predecessors. We prove that the whole set of reduced marginal worth vectors, which for convex games coincide with the usual marginal worth vectors, is the set of extreme points of the core of the assignment game

On the dimension of the core of the assignment game

The set of optimal matchings in the assignment matrix allows to define a reflexive and symmetric binary relation on each side of the market, the equal-partner binary relation. The number of equivalence classes of the transitive closure of the equal-partner binary relation determines the dimension of the core of the assignment game. This result provides an easy procedure to determine the dimension of the core directly from the entries of the assignment matrix and shows that the dimension of the core is not as much determined by the number of optimal matchings as by their relative position in the assignment matrix.

An axiomatization of the nucleolus of the assignment game

[cat] En el domini dels jocs bilaterals d’assignació, es presenta una axiomàtica del nucleolus com l´unica solució que compleix les propietats de consistència respecte del joc derivat definit per Owen (1992) i monotonia de les queixes dels sectors respecte de la seva cardinalitat. Com a conseqüència obtenim una caracterització geomètrica del nucleolus mitjançant una propietat de bisecció més forta que la que satisfan els punts del kernel (Maschler et al, 1979).

The assignment game: core bounds for mixed-pair coalitions

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the coreof the game. These games will be called buyer¿seller exact games and satisfy the condition that each mixed¿pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyerseller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer¿seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed¿pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a ¿45o¿lattice¿ by means of the core of an assignment game can now be answered

A geometric chracterization of the nucleolus of the assignment game

Maschler et al. (1979) caracteritzen geomètricament la intersecció del kernel i del core en els jocs cooperatius, demostrant que les distribucions que pertanyen a ambdós conjunts es troben en el punt mig d’un cert rang de negociació entre parelles de jugadors. En el cas dels jocs d’assignació, aquesta caracterització vol dir que el kernel només conté aquells elements del core on el màxim que un jugador pot transferir a una parella òptima és igual al màxim que aquesta parella li pot transferir, sense sortir-se’n del core. En aquest treball demostrem que el nucleolus d’un joc d’assignació queda caracteritzat si requerim que aquesta propietat de bisecció es compleixi no només per parelles, sinó també per coalicions entre sectors aparellades òptimament.

A geometric chracterization of the nucleolus of the assignment game

Maschler et al. (1979) caracteritzen geomètricament la intersecció del kernel i del core en els jocs cooperatius, demostrant que les distribucions que pertanyen a ambdós conjunts es troben en el punt mig d’un cert rang de negociació entre parelles de jugadors. En el cas dels jocs d’assignació, aquesta caracterització vol dir que el kernel només conté aquells elements del core on el màxim que un jugador pot transferir a una parella òptima és igual al màxim que aquesta parella li pot transferir, sense sortir-se’n del core. En aquest treball demostrem que el nucleolus d’un joc d’assignació queda caracteritzat si requerim que aquesta propietat de bisecció es compleixi no només per parelles, sinó també per coalicions entre sectors aparellades òptimament.