Shapley Shubik Assignment Definition

1Instituto de Matemática Aplicada San Luis (UNSL-CONICET), Ejército de los Andes 950, 5700 San Luis, Argentina
2Departament d'Economia i d'Història Econòmica, Universitat Autònoma de Barcelona and Barcelona GSE, Edifici B, Bellaterra, 08193 Barcelona, Spain

Received 5 December 2013; Revised 14 February 2014; Accepted 15 February 2014; Published 30 April 2014

Copyright © 2014 R. Pablo Arribillaga et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

We study cooperative and competitive solutions for a many-to-many generalization of Shapley and Shubik’s (1971) assignment game. We consider the Core, three other notions of group stability, and two alternative definitions of competitive equilibrium. We show that (i) each group stable set is closely related to the Core of certain games defined using a proper notion of blocking and (ii) each group stable set contains the set of payoff vectors associated with the two definitions of competitive equilibrium. We also show that all six solutions maintain a strictly nested structure. Moreover, each solution can be identified with a set of matrices of (discriminated) prices which indicate how gains from trade are distributed among buyers and sellers. In all cases such matrices arise as solutions of a system of linear inequalities. Hence, all six solutions have the same properties from a structural and computational point of view.

1. Introduction

Gale and Shapley [1] introduce ordinal two-sided matching models to study assignment problems between two disjoint sets of agents. In the marriage model, where matchings are one-to-one, each agent has to be matched to at most an agent on the opposite set. It is assumed that each agent has strict ordinal preferences over the set of agents that he does not belong to plus the prospect of remaining unmatched. These models are ordinal and money does not play any role; in particular, money cannot be used to compensate an agent in the case he has to be matched to an agent at the bottom of the agent’s preference list. Ordinal models have been enormously useful and extensively used in economics to study situations where the assignment problem has only one issue: who is matched to whom.1 In these models and given a preference profile (a preference for each agent), a matching is stable if it is individually rational (no agent is assigned to a partner that is worse than to remain unmatched) and pairwise stable (there is no pair of agents that are not matched to each other but they would prefer to be so rather than to be matched to the partner proposed by the matching, or to one of them if the agent is a college). Gale and Shapley [1] show that, for every preference profile, the set of stable matchings is nonempty and it coincides with the Core of the associated cooperative game with nontransferable utility (and hence, coalitions with two or more agents from the same set of agents do not have additional blocking power).2

However, there are many assignment problems (solved by markets) where money plays a significant role, for instance, through salaries or prices. Hence, in those cases agents’ preferences may be cardinal. But then, to describe a solution of the problem (in particular, to unsure its stability) it is not sufficient to specify the matching between the two sides of the market because it is also required to describe how each pair of assigned agents shares the gains of being matched to each other. Shapley and Shubik [2] propose the assignment game as an appropriated tool to study one-to-one matching problems with money (i.e., with transferable utility). The prototypical and most simple example of an assignment game is a market with sellers and buyers in which each seller owns one indivisible unit of a good and each buyer wants to buy at most one unit of one good. This setting differs from the marriage model of Gale and Shapley [1] by the fact that there exists money used as a means of exchange. In addition money is also used to determine buyers’ valuations (or maximal willingness to pay) of each unit of the available goods and sellers’ reservation prices (or minimal amounts at which they are willing to sell the unit of the good they own). Shapley and Shubik [2] show that the assignment game has, among others, the following properties. (i) There exists at least one competitive equilibrium price vector, with a price for each of the goods and an assignment between buyers and sellers such that, at those prices, each buyer is assigned to the seller that owns the good (namely, the buyer buys the unit of the good that the seller has and pays its price) that gives him the maximal net valuation (the difference between his valuation and the price of the good). (ii) The set of competitive equilibrium payoffs coincides with the Core of the cooperative game with transferable utility induced by the assignment game. (iii) The Core coincides with the set of individually rational and pairwise stable payoff vectors. In this model, a solution is not only an assignment (who buys to whom, or equivalently, who sells to whom) but it is also a description of how each assigned pair of agents splits the gains generated by their trade.3

Sotomayor [3–8], Camiña [9], Milgrom [10], Fagebaume et al. [11], Jaume et al. [12], and Massó and Neme [13] are some of the papers that extend the one-to-one Shapley and Shubik [2] assignment game by allowing that buyers can buy different goods and/or that sellers can own and sell units of different goods to different buyers. Most of those papers show that some of the properties of the one-to-one model also hold for the generalized versions. In addition, most of the previously cited papers propose and study cooperative solution concepts that are natural in the many-to-one or many-to-many contexts. The Core is the most studied solution concept. Given a payoff vector and an associated assignment (the payoffs are obtained after distributing among players the net gains generated from each trade specified by the assignment) a coalition Core-blocks the payoff vector if all its agents, by breaking all their trades with all agents outside the coalition, may improve upon their payoffs by reorganizing new trades, performed only among themselves. The Core is the set of payoff vectors that are not Core-blocked by any coalition.

However, in this setting there are other alternative notions of group stability. They differ on the type of transactions that agents in a blocking coalition are allowed to perform with agents outside. That is, the notions depend on how sale contracts have been specified and, hence, on how they can be broken. The Core concept assumes that agents in a blocking coalition can only trade among themselves, without being able to keep any trade with agents outside the blocking coalition; thus, when a coalition of agents Core-blocks a proposed payoff vector, they have to break all contracts with agents outside the coalition. In the group stability notion defined in Massó and Neme [13] it is assumed that sale contracts are unit-by-unit. A trade of a unit of a good between a buyer and a seller is performed independently of the other traded units of the same good as well as of the traded units of the other goods. An agent of a blocking coalition can reduce (but not increase) the trade, with members outside the coalition, of a given good in the number of units that he wishes, but without being forced for this reason to reduce neither the number of traded units of the same good nor the number of units of the other goods. In this paper we consider the other two alternative notions of group stability. They are more appropriated for those cases where sale contracts are written good-by-good or globally. In the good-by-good case, the sale contract between a buyer and a seller includes all traded units of only one good, and it is independent of their trade on the other goods. Thus, when an agent belongs to a blocking coalition and the other does not, either they keep the trade of all units of the good specified in the sale contract or they completely eliminate the trade of this good. In the global case, the sale contract between a buyer and a seller includes all trades on all goods and, thus, when an agent belongs to a blocking coalition and the other does not, either they keep all trades or they have to be eliminated altogether.

Jaume et al. [12], when defining competitive equilibrium for this generalized assignment game, consider that given a price vector (a price for each of the goods) agents demand and supply those units of the goods that maximize their total payoff without taking into account the aggregate feasibility constraints. The supply or demand of each agent only depends on the price vector and his individual feasibility constraints. The fact that, at a given price vector, all supply and demand plans are mutually compatible is an equilibrium question, rather than a restriction on the individual maximization problems. On the other hand, the competitive equilibrium notion studied by Sotomayor [6–8] in related models assumes that individual demands and supplies have to be feasible for the market. Namely, when obtaining their optimal demands and supplies, it is assumed that agents cannot demand or supply more than the available amounts present in the market.

The most important results of this paper are the following. First, we show that each one of the sets of payoffs corresponding to the three group stability notions can be directly identified with the union of Cores of particular cooperative games with transferable utility, where the blocking power of coalitions is inherited from the corresponding nature of the sale contracts between buyers and sellers (unit-by-unit, good-by-good, or global). Second and using this identification, we show that the three notions of group stability are supported by a Cartesian product structure between a given set of matrices of prices and the set of optimal assignments; all payoff vectors in any of the sets corresponding to the three group stability notions are fully identified by a set of matrices of prices; all payoff vectors in any of the sets corresponding to the three group stability notions are completely identified with the solutions of a system of bounded linear inequalities. Third, we show that each of the two competitive equilibrium notions can be directly identified with the union of Cores of certain cooperative games with transferable utility. This result allows us to obtain for the two competitive equilibrium concepts the same conclusions that we have already obtained for the three group stability notions. Hence, cooperative as well as competitive solutions have all the same properties from a structural and computational point of view. Furthermore, all studied solutions maintain a strictly nested relationship.

In short, the paper contributes to the study of markets with indivisible goods. In particular, it shows that the two competitive equilibrium notions are immune with respect to the secession of subgroups of agents. It also identifies some structural properties that hold for competitive equilibrium solutions as well as for different notions of group stability.

The paper is organized as follows. In the next section we present the model introduced in Jaume et al. [12]. In Section 3 we define three notions of group stability and study the equivalence of each of these notions with the Cores of their corresponding cooperative games with transferable utility. We show that the three group stability sets of payoffs have a Cartesian product structure and that they can be identified as the solutions of a system of linear inequalities. In Section 4 we perform a similar analysis for the two notions of competitive equilibria. In Section 5 we compare the three notions of group stability with the two notions of competitive equilibria. The Appendices include the proofs of three results omitted in the main text.

2. Preliminaries

A generalized assignment game (a market) consists of three finite and disjoint sets: the set of buyers, the set of goods, and the set of sellers. We denote a generic buyer by , a generic good by , and a generic seller by . Buyers have a constant marginal valuation of each good. Let be the monetary valuation that buyer assigns to each unit of good ; namely, is the maximum price that buyer is willing to pay for each unit of good . Denote by the matrix of valuations. We assume that buyer can buy at most units in total, where is the set of nonnegative integers. The strictly positive integer should be interpreted as a capacity constraint due to limits on 's ability for storage, transport, and so forth. Denote by the vector of maximal demands. Each seller has indivisible units of each good . Denote by the matrix of capacities. We assume that there is a strict amount of each good; namely, Let be the monetary valuation that seller assigns to each unit of good ; that is, is the reservation (or minimum) price that seller is willing to accept for each unit of good . Denote by the matrix of reservation prices.

A market is a 7-tuple satisfying condition (1). Shapley and Shubik’s [2] (one-to-one) assignment game is a special case of a market where each buyer can buy at most one unit, there is only one unit of each good, and each seller only owns one unit of one of the goods; that is, , for all , , and, for all , if and if .

Let be a market. An assignment for market is a three-dimensional integer matrix (i.e., a 3rd-order tensor) describing a collection of deliveries of units of the goods from sellers to buyers. Each should be interpreted as “buyer receives units of good from seller .” We often omit the sets to which the subscripts belong to and write, for instance, and instead of and , respectively.

The assignment is feasible for market if each buyer buys at most units and each seller sells at most units of each good . We are only interested in feasible assignments, namely, in the set For further reference, we denote this set of feasible assignments for market by (or simply by ).

The total gain from trade of market at assignment is

Definition 1. A feasible assignment is optimal for market if, for any feasible assignment , .

Example 2 below contains an instance of a market with a unique optimal assignment.

Example 2. Let be a market where

Please, wait while we are validating your browser

0 comments

Leave a Reply

Your email address will not be published. Required fields are marked *