A survey on assignment markets

Marina  Núñez; Carles  Rafels

doi:10.3934/jdg.2015003

Article Contents

2015, Volume 2, Issue 3&4: 227-256. Doi: 10.3934/jdg.2015003

This issue Previous Article Endogenous budget constraints in the assignment game Next Article Paths to stability in the assignment problem

A survey on assignment markets

Marina Núñez^1, and
Carles Rafels^1,

1.
Departament de Matemàtica Econòmica, Financera i Actuarial, Universitat de Barcelona, Av. Diagonal, 690, 08034 Barcelona

Received: November 30, 2014

Revised: December 31, 2014

Published: June 2015

Abstract Related Papers Cited by

Abstract

The assignment game is a two-sided market, say buyers and sellers, where demand and supply are unitary and utility is transferable by means of prices. This survey is structured in three parts: a first part, from the introduction of the assignment game by Shapley and Shubik (1972) until the publication of the book of Roth and Sotomayor (1990), focused on the notion of core; the subsequent investigations that broaden the scope to other notions of solution for these markets; and its extensions to assignment markets with multiple sides or multiple partnership. These extended two-sided assignment markets, that allow for multiple partnership, better represent the situation in a labour market or an auction.

Keywords:

Mathematics Subject Classification: Primary: 91A12, 91A40; Secondary: 90B80.

Citation:

Related Papers

Cited by

References

[1]	R. P. Arribillaga, J. Massó and A. Neme, On the structure of cooperative and competitive solutions of a generalized assignment game, Journal of Applied Mathematics, (2014), Art. ID 190614, 20 pp.doi: 10.1155/2014/190614.
[2]	L. M. Ausubel and P. Milgrom, Ascending auctions with package bidding, Frontiers of Theoretical Economics, 1 (2002), 44pp(Republished in BePress Advances in Theoretical Economics).doi: 10.2202/1534-5955.1019.
[3]	L. M. Ausubel and P. Milgrom, The lovely but lonely Vickrey auction, In Combinatorial Auctions (ed. P. Cramton, R. Steinberg and Y. Shoham), MIT Press, 2005.
[4]	L. M. Ausubel and P. Milgrom, Ascending Proxy Auctions, In Combinatorial Auctions (ed. P. Cramton, R. Steinberg and Y. Shoham), MIT Press, 2005.
[5]	M. L. Balinski and D. Gale, On the core of the assignment game, In Functional Analysis, Optimization and Mathematical Economics (ed. L.J. Leifman), Oxford University (1990), 274-289.
[6]	S. Bikhchandani and J. M. Ostroy, The package assignment model, Journal of Economic Theory, 107 (2002), 377-406.doi: 10.1006/jeth.2001.2957.
[7]	G. Birkhoff, Tres observaciones sobre el álgebra lineal, Revista Universidad Nacional de Tucuman, Series A, 5 (1946), 147-151.
[8]	R. van den Brink and M. Pintér, On axiomatizations of the Shapley value for assignment games, Journal of Mathematical Economics, 60 (2015), 110-114.doi: 10.1016/j.jmateco.2015.06.016.
[9]	E. Camiña, A generalized assignment game, Mathematical Social Sciences, 52 (2006), 152-161.doi: 10.1016/j.mathsocsci.2006.06.003.
[10]	V. P. Crawford and E. M. Knoer, Job matching with heterogeneous firms and workers, Econometrica, 49 (1981), 437-450.doi: 10.2307/1913320.
[11]	M. Davis and M. Maschler, The kernel of a cooperative game, Naval Research Logistics Quarterly 12 (1965), 223-259.doi: 10.1002/nav.3800120303.
[12]	G. Demange, Strategyproofness in the Assignment Market Game, Laboratoire d'Econometrie de l'Ecole Polytechnique, Paris, Mimeo, 1982.
[13]	G. Demange and D. Gale, The strategy structure of two-sided matching markets, Econometrica, 53 (1985), 873-888.doi: 10.2307/1912658.
[14]	G. Demange, D. Gale and M. Sotomayor, Multi-item auctions, Journal of Political Economy, 94 (1986), 863-872.doi: 10.1086/261411.
[15]	T. S. H. Driessen, A note on the inclusion of the kernel in the core of the bilateral assignment game, International Journal of Game Theory, 27 (1998), 301-303.doi: 10.1007/s001820050073.
[16]	A. Fagebaume, D. Gale and M. Sotomayor, A note on the multiple-partners assignment game, Journal of Mathematical Economics, 46 (2010), 388-392.doi: 10.1016/j.jmateco.2009.06.014.
[17]	D. Gale, The Theory of Linear Economic Models, McGraw-Hill, New York, 1960.
[18]	D. Gale and L. S. Shapley, College Admission and the Stability of Marriage, American Mathematical Monthly, 69 (1962), 9-15.doi: 10.2307/2312726.
[19]	H. Hamers, F. Klijn, T. Solymosi, S. Tijs and J. P. Villar, Assignment games satisfy the CoMa-property, Games and Economic Behavior, 38 (2002), 231-239.
[20]	M. Hoffmann and P. Sudhölter, The Shapley value of exact assignment games, International Journal of Game Theory 35 (2007), 557-568.doi: 10.1007/s00182-006-0068-8.
[21]	J. M. Izquierdo, M. Núñez and C. Rafels, A simple procedure to obtain the extreme core allocations of an assignment market, International Journal of Game Theory, 36 (2007), 17-26.doi: 10.1007/s00182-007-0091-4.
[22]	D. Jaume, J. Massó and A. Neme, The multiple-partners assignment game with heterogeneous sales and multi-unit demands: competitive equilibria, Mathematical Methods of Operations Research, 76 (2012), 161-187.doi: 10.1007/s00186-012-0395-4.
[23]	M. Kaneko, On the core and competitive equilibria of a market with indivisible goods, Naval Research Logistics Quarterly, 23 (1976), 321-337.doi: 10.1002/nav.3800230214.
[24]	M. Kaneko, The central assignment game and the assignment markets, Journal of Mathematical Economics, 10 (1982), 205-232.doi: 10.1016/0304-4068(82)90038-6.
[25]	M. Kaneko and M. Wooders, Cores of partitioning games, Mathematical Social Sciences, 3 (1982), 313-327.doi: 10.1016/0165-4896(82)90015-4.
[26]	T. C. Koopmans and M. Beckmann, Assignment Problems and the Location of Economic Activities, Econometrica, 25 (1957), 53-76.doi: 10.2307/1907742.
[27]	H. B. Leonard, Elicitation of honest preferences for the assignment of individuals to positions, Journal of Political Economy, 91 (1983), 461-479.doi: 10.1086/261158.
[28]	F. Llerena and M. Núñez, A geometric characterization of the nucleolus of the assignment game, Economics Bulletin 31 (2011), 3275-3285.
[29]	F. Llerena, M. Núñez and C. Rafels, An axiomatization of the nucleolus of the assignment game, International Journal of Game Theory, 44 (2015), 1-15.doi: 10.1007/s00182-014-0416-z.
[30]	W. F. Lucas, A game with no solution, Bulletin of the American Mathematical Society, 74 (1968), 237-239.doi: 10.1090/S0002-9904-1968-11901-9.
[31]	W. F. Lucas, Core theory for multiple-sided assignment games, Duke Mathematical Journal, 81 (1995), 55-65.doi: 10.1215/S0012-7094-95-08106-X.
[32]	F. J. Martínez de Albéniz, M. Núñez and C. Rafels, Assignment markets with the same core, Games and Economic Behavior, 73 (2011), 553-563.doi: 10.1016/j.geb.2011.02.011.
[33]	F. J. Martínez de Albéniz, C. Rafels and N. Ybern, On the nucleolus of 2x2 assignment games, Economics Bulletin 3 (2013), 2938-2947.
[34]	F. J. Martínez de Albéniz, C. Rafels and N. Ybern, A procedure to compute the nucleolus of the assignment game, Operations Research Letters 41 (2013), 675-678.
[35]	F. J. Martínez de Albéniz and C. Rafels, Cooperative assignment games with the inverse Monge property, Discrete Applied Mathematics, 162 (2014), 42-50.doi: 10.1016/j.dam.2013.08.027.
[36]	M. Maschler, B. Peleg and L. S. Shapley, Geometric properties of the kernel, nucleolus and related solution concepts, Mathematics of Operations Research, 4 (1979), 303-338.doi: 10.1287/moor.4.4.303.
[37]	J. Massó and A. Neme, On cooperative solutions of a generalized assignment game: Limit theorems to the set of competitive equilibria, Journal of Economic Theory, 154 (2014), 187-215.doi: 10.1016/j.jet.2014.09.016.
[38]	J. P. Mo, Entry and structures of interest groups in assignment games, Journal of Economic Theory, 46 (1988), 66-96.doi: 10.1016/0022-0531(88)90150-0.
[39]	M. Núñez, A note on the nucleolus and the kernel of the assignment game, International Journal of Game Theory, 33 (2004), 55-65.doi: 10.1007/s001820400184.
[40]	M. Núñez and C. Rafels, Buyer-seller exactness in the assignment game, International Journal of Game Theory, 31 (2002), 423-436.doi: 10.1007/s001820300128.
[41]	M. Núñez and C. Rafels, The assignment game: the $\tau$-value, International Journal of Game Theory, 31 (2002), 411-422.doi: 10.1007/s001820300127.
[42]	M. Núñez and C. Rafels, Characterization of the extreme core allocations of the assignment game, Games and Economic Behavior, 44 (2003), 311-331.doi: 10.1016/S0899-8256(03)00054-X.
[43]	M. Núñez and C. Rafels, On the dimension of the core of the assignment game, Games and Economic Behavior, 64 (2008), 290-302.doi: 10.1016/j.geb.2008.01.004.
[44]	M. Núñez and C. Rafels, A glove-market partitioned matrix related to the assignment game, Games and Economic Behavior, 67 (2009), 598-610.doi: 10.1016/j.geb.2009.03.014.
[45]	M. Núñez and C. Rafels, Von Neumann-Morgenstern solutions in the assignment market, Journal of Economic Theory, 148 (2013), 1282-1291.doi: 10.1016/j.jet.2012.10.002.
[46]	M. Núñez and T. Solymosi, Lexicographic allocations and extreme core payoffs: The case of assignment games, Corvinus Economics Working Papers, CEWP 15/2014 (2014).
[47]	G. Owen, The Assignment Game: The Reduced Game, Annales d'Économie et de Statistique, (1992), 71-79.
[48]	B. Peleg, On the reduced game property and its converse, International Journal of Game Theory, 15 (1986), 187-200.doi: 10.1007/BF01769258.
[49]	D. Pérez-Castrillo and M. Sotomayor, A simple selling and buying procedure, Journal of Economic Theory, 103 (2002), 461-474.doi: 10.1006/jeth.2000.2783.
[50]	D. Pérez-Castrillo and M. Sotomayor, On the manipulability of competitive equilibrium rules in many-to-many buyer-seller markets, Working paper, 2014.
[51]	T. Quint, Characterization of cores of assignment games, International Journal of Game Theory, 19 (1991), 413-420.doi: 10.1007/BF01766430.
[52]	T. Quint, The core of an m-sided assignment game, Games and Economic Behavior, 3 (1991), 487-503.doi: 10.1016/0899-8256(91)90017-9.
[53]	S. C. Rochford, Symmetrically Pairwise-Bargained Allocations in an Assignment Market, Journal of Economic Theory, 34 (1984), 262-281.doi: 10.1016/0022-0531(84)90144-3.
[54]	A. E. Roth and M. Sotomayor, Interior points in the core of two-sided matching problems, Journal of Economic Theory, 45 (1988), 85-101.doi: 10.1016/0022-0531(88)90255-4.
[55]	A. E. Roth and M. Sotomayor, Two-sided Matching, Econometric Society Monograph 18, Cambridge University Press, 1990.doi: 10.1017/CCOL052139015X.
[56]	J. Sánchez-Soriano, M. A. López and I. García-Jurado, On the core of transportation games, Mathematical Social Sciences, 41 (2001), 215-225.doi: 10.1016/S0165-4896(00)00057-3.
[57]	J. Sánchez-Soriano, The pairwise egalitarian solution, European Journal of Operations Research, 150 (2003), 220-231.doi: 10.1016/S0377-2217(02)00503-9.
[58]	J. Sánchez-Soriano, Pairwise solutions and the core of transportation games, European Journal of Operations Research, 175 (2006), 101-110.doi: 10.1016/j.ejor.2005.04.033.
[59]	H. Sasaki, Consistency and monotonicity in assignment problems, International Journal of Game Theory, 24 (1995), 373-397.doi: 10.1007/BF01243039.
[60]	D. Schmeidler, The nucleolus of a characteristic function game, SIAM Journal of Applied Mathematics, 17 (1969), 1163-1170.doi: 10.1137/0117107.
[61]	L. S. Shapley, A Value for n-person Games. In Contributions to the Theory of Games, Volume 2 (eds. H.W.Khun and A.W. Tucker), Princeton University Press, (1953), 307-317.
[62]	L. S. Shapley, Complements and substitutes in the optimal assignment problem, Naval Research Logistics Quarterly, 9 (1962), 45-48.
[63]	L. S. Shapley and M. Shubik, The Assignment Game I: The Core, International Journal of Game Theory, 1 (1972), 111-130.
[64]	K. Sherstyuk, Multisided matching games with complementarities, International Journal of Game Theory, 28 (1999), 489-509.doi: 10.1007/s001820050121.
[65]	M. Shubik, Game Theory in the Social Sciences, Volume II, Cambridge, MIT Press, 1984.
[66]	T. Solymosi and T. E. S. Raghavan, An algorithm for finding the nucleolus of assignment games, International Journal of Game Theory, 23 (1994), 119-143.doi: 10.1007/BF01240179.
[67]	T. Solymosi and T. E. S. Raghavan, Assignment games with stable core, International Journal of Game Theory, 30 (2001), 177-185.doi: 10.1007/s001820100072.
[68]	M. Sotomayor, The multiple partners game, In Equilibrium and dynamics: Essays in Honor to David Game, (ed. M. Majumdar), 31 (1992), 269-283.
[69]	M. Sotomayor, The lattice structure of the set of stable outcomes of the multiple partners game, International Journal of Game Theory, 28 (1999), 567-583.doi: 10.1007/s001820050126.
[70]	M. Sotomayor, A labor market with heterogeneous firms and workers, International Journal of Game Theory, 31 (2002), 269-283.doi: 10.1007/s001820200116.
[71]	M. Sotomayor, Connecting the cooperative and the competitive structures of the multiple-partners assignment game, Journal of Economic Theory, 134 (2007), 155-174.doi: 10.1016/j.jet.2006.02.005.
[72]	M. Sotomayor, Adjusting prices in the multiple-partners assignment game, International Journal of Game Theory, 38 (2009), 575-600.doi: 10.1007/s00182-009-0171-8.
[73]	M. Sotomayor, Labor time shared in the assignment game generating new cooperative and competitive structures, Department of Economics FEA/USP, Working paper, 2013.
[74]	H. W. Stuart, The supplier-firm-buyer game and its m-sided generalization, Mathematical Social Sciences, 34 (1997), 21-27.doi: 10.1016/S0165-4896(96)00830-X.
[75]	O. Tejada, A note on competitive prices in multilateral assignment markets, Economics Bulletin, 30 (2010), 658-662.
[76]	O. Tejada, Analysis of the core of multisided Böhm-Bawerk assignment markets, TOP, 21 (2013), 189-205.doi: 10.1007/s11750-010-0170-8.
[77]	O. Tejada and M. Núñez, The nucleolus and the core-center of multi-sided Böhm-Bawerk assignment markets, Mathematical Methods of Operations Research, 75 (2012), 199-220.doi: 10.1007/s00186-012-0381-x.
[78]	O. Tejada and C. Rafels, Symmetrically multilateral-bargained allocations in multi-sided assignment markets, International Journal of Game Theory, 39 (2010), 249-258.doi: 10.1007/s00182-009-0204-3.
[79]	G. L. Thompson, Auctions and market games, in Game Theory and Mathematical Economics in honour of Oskar Morgenstern (ed. R. Aumann) Bibliographisches Institute AG, Zurich, (1980), 181-196.
[80]	M. Toda, Consistency and its converse in assignment games, International Journal of Mathematics, Game Theory and Algebra, 13 (2003), 1-14.
[81]	M. Toda, Axiomatization of the core of assignment games, Games and Economic Behavior, 53 (2005), 248-261.doi: 10.1016/j.geb.2004.09.006.
[82]	W. Vickrey, Counterspeculation, auctions and competitive sealed tenders, Journal of Finance, 16 (1961), 8-37.doi: 10.2307/2977633.
[83]	J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, 1944 (3rd. edition, 1953).
[84]	J. von Neumann, A certain zero-sum two-person game equivalent to the optimal assignment problem, in Contributions to the theory of games, (eds. H.W.Khun and A.W. Tucker), Princeton University Press, 2 (1953), 5-12.