Shapley Shubik Assignment Submission

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

Lloyd Shapley was one of the founding giants of game theory. He shared the 2012 Nobel Prize in Economics for his seminal work with the late David Gale on stable matching – situations in which there are no two agents who would prefer one another over their current counterparts. But he could have won a Nobel for any of a number of his papers that initiated whole literatures.

In addition to being one of the very first to formulate and study the core of a game, which was intimately related to his work on matching, he invented the Shapley value for evaluating games with side payments, which he and Martin Shubik showed could also be used in studying voting and political processes. He and John Milnor initiated the study of games with a continuum of players (‘oceanic games’), a subject that he later explored in depth with Robert Aumann; his paper on ‘stochastic games’ initiated the study of Markov decision processes as well as Markov games; and he contributed deep insights about learning in games and the structure of markets.

At a time when game theory was viewed as addressing two fairly distinct kinds of situations – cooperative games (in which models focus on what coalitions could accomplish if they agree) and non-cooperative games (which focus on individual players’ strategic choices) – Shapley made fundamental contributions to both.

Lloyd Shapley was born on 2 June 1923 to Martha and Harlow Shapley – his father was a famous astronomer. In 1943 Lloyd was drafted into the Army, where he served from 1943-45 and won the Bronze Star for breaking a Soviet weather code. After the war he completed his undergraduate studies at Harvard and, after briefly returning to the RAND Corporation, entered the math PhD programme at Princeton in 1949, where he shared a dormitory suite with Martin Shubik and John Nash, and where he also met David Gale and Herbert Scarf. Shapley’s dissertation advisor was Albert Tucker, and his dissertation was on “Additive and Non-additive Set Functions”.

After getting his PhD in 1953, he spent the bulk of his career at RAND, then moved to UCLA in 1981, where he was an emeritus professor when the early morning call came from Stockholm. He was 92 when he passed away on 12 March 2016.

Key contributions of Shapley

One of Shapley’s earliest contributions (1953a) was to formulate and study the function that is today known as the Shapley value, for games modelled as cooperative games in coalitional function form with side payments. Such a game is modelled by a set N = {1,…n} of players, and a function v that assigns a real number to each coalition S, that is, to each subset of N, such that v(S) represents the amount (of money or of utility) that coalition S is able to transfer among its members in any way that they all agree to.

A closely related paper with Martin Shubik (1954) specialised the approach to games modelling political decisions. In such a ‘simple game’, v(S) equals either 0 or 1, to express the idea that the coalition is either a losing coalition without enough votes to enforce any outcome, or a winning coalition able to enforce every outcome. Modelling political processes even in this simple way illuminates some deep ideas; for example, a coalition S that is not a winning coalition may nevertheless be a ‘blocking coalition’ if every winning coalition must include some members of the coalition S. Shapley and Shubik modelled an individual’s abstract political power as a weighted sum of the number of coalitions such that this individual’s membership in the coalition would transform it from a losing coalition to a winning one.

The Shapley value of a general game with side payments, intended to summarise how valuable it is to play the game from each position, was similarly a weighted sum, over all coalitions, of a player i’s marginal contribution v(S) – v(S-{i}). An edited volume called The Shapley Value (Roth 1988) was published in honor of Lloyd’s 65th birthday, to represent the very substantial literature that had grown up around deriving, interpreting, and applying the Shapley value over a wide range of situations.

Lloyd and John Milnor (who was an undergraduate at Princeton when Shapley was a grad student) initiated the study of ‘oceanic games’, in which price-taking behaviour was analysed by modelling players as a non-atomic continuum of individually insignificant players (1961). Lloyd and Robert Aumann later explored such models together in their masterful 1974 volume Values of Non-Atomic Games (which I once found shelved in the physics section of the Stanford bookstore). That work was part of a grand unification of ideas from game theory with classical ideas from economics, and Aumann and Shapley used the model of a game with a continuum of players to study conditions that could be interpreted as ‘perfect competition’ in which the Shapley value of a market game coincided with the market’s competitive equilibrium outcomes.

Shapley (1953b) is often cited as was one of the first formulations of the core of a game as an independent solution concept – the set of outcomes such that no coalition of players can do better on their own. He explored the notion of ‘balanced games’ to characterise those that always have non-empty cores (Shapley 1967). Shapley and Shubik (1969) showed that the games with side payments that can be formulated as exchange economies with continuous and concave utility functions are precisely those that are ‘totally balanced’ – that is, those for which the subgame formed by each subset of players is a balanced game.

His 1962 paper with Gale looked at the core in a simple model of matching such as the ‘marriage problem’ in which there are two kinds of agents, each of whom wishes to be matched to one agent of the other kind. They formulated two-sided matching models and the deferred acceptance algorithm, which today have practical application in many labour market and school choice clearinghouses that match applicants to jobs or students to schools. (See also the 1971 paper with Shubik on a model of two-sided matching with side payments. The title of that paper was “The Assignment Game I: The Core”, and Lloyd once advised me never to title a paper that way unless I already had a follow-up paper – no number II ever followed that one.) Another paper, by Shapley and the late Herbert Scarf (1974), provided a model of exchange of indivisible goods without money that has provided conceptual foundations for organising kidney-exchange transplants among patient-donor pairs who cannot donate to one another directly.

Shapley’s work on games in strategic form (non-cooperative games) was equally fundamental. Some of that work in fact served to show how some of the same issues studied by cooperative game theory could also be studied with strategic models – see, for example, his 1976 paper on strategic market games (a topic he explored together with both Martin Shubik and Pradeep Dubey). And much of his work on non-cooperative games was conducted at the same time as his work on cooperative games.

His paper on stochastic games (1953c) introduced a model in which players’ choices jointly determine not only their payoffs but also the transition probabilities to a subsequent stage of the game. It was among the first formulations of a dynamic, multi-stage game, and has fostered a large and thriving literature.

Shapley and Dov Monderer (1996a) studied the class of ‘potential games’, for which there exists a potential function – that is, a function such that each player’s reactions to the choices of others increases his own payoff function if and only if it increases the potential function. These are games in which simple learning dynamics work very well in reaching equilibrium, since each player can seek to myopically maximise his own earnings while simultaneously increasing a kind of social objective function. This connection was made particularly clear by Shapley and Monderer’s related paper, published the same year (1996b), on fictitious play learning in games with identical interests.

Concluding remarks

No brief account can summarise Lloyd Shapley’s intellectual life and career, which was among the most fertile of the 20th century. He opened up vast areas to be explored by those who followed. To pick just an area in which I have worked, a few of his foundational ideas – the core, two-sided matching, and exchange in cycles of trade – have led to the study of matching markets, and to a thriving branch of practical market design, which is the engineering part of game theory.

References

Aumann, R J, and L S Shapley (1974), Values of Non-Atomic Games, Princeton University Press.

Gale, D, and L S Shapley (1962), ‘College Admissions and the Stability of Marriage’, The American Mathematical Monthly 69 (1): 9-15.

Milnor, J W, and L S Shapley (1961), ‘Values of Large Games, II: Oceanic Games’, RM-2649, The Rand Corporation, Santa Monica, CA.

Monderer, D, and L S Shapley (1996a), ‘Potential Games’, Games and Economic Behavior 14 (1): 124-43.

Monderer, D, and L S Shapley (1996b), ‘Fictitious Play Property for Games with Identical Interests’, Journal of Economic Theory 68 (1): 258-65.

Roth, A E (editor) (1988), The Shapley Value: Essays in Honor of Lloyd S. Shapley, Cambridge University Press.

Shapley, L S. (1953a), ‘A Value of n-Person Games’, Annals of Math Studies 28: 307-17.

Shapley, L S (1953b), ‘Open Questions’, in Report of an Informal Conference on the Theory of N-Person Games, Held at Princeton University, March 20-21, Kuhn (ed.) mimeo.

Shapley, L S (1953c), ‘Stochastic Games’, Proceedings of the National Academy of Sciences 39: 1095-1100.

Shapley, L S (1967), ‘On Balanced Sets and Cores’, Naval Research Logistics Quarterly 14: 453-60.

Shapley, L S (1976), ‘Noncooperative General Exchange’, in Theory and Measurement of Economic Externalities, A.Y. Lin (ed.), Academic Press, 155-75.

Shapley, L S, and H Scarf (1974), ‘On Cores and Indivisibility’, Journal of Mathematical Economics 1: 23-37.

Shapley, L S, and M Shubik (1954), ‘A Method for Evaluating the Distribution of Power in a Committee System’, American Political Science Review 48 (3): 787-92. 

Shapley, L S, and M Shubik (1969), ‘On Market Games’, Journal of Economic Theory, 1, 9-25.

Shapley, L S, and M Shubik (1971), ‘The Assignment Game I: The Core’, International Journal of Game Theory 1 (1): 111-30.

Topics: Frontiers of economic research

Tags: game theory, Shapley, Shapley value, matching models

One thought on “Shapley Shubik Assignment Submission

Leave a Reply

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