Assignment Problems with Complementarities
Paperzz.com, your paperzz.
© Copyright 2024 Paperzz
Browse Econ Literature
- Working papers
- Software components
- Book chapters
- JEL classification
More features
- Subscribe to new research
RePEc Biblio
Author registration.
- Economics Virtual Seminar Calendar NEW!
One-Sided Matching with Limited Complementarities
- Author & abstract
- 12 References
- 1 Citations
- Most related
- Related works & more
Corrections
(Krannert School of Management, Purdue University)
(Department of Economics, Northwestern University)
(Department of Economics, University of Pennsylvania)
Suggested Citation
Download full text from publisher, references listed on ideas.
Follow serials, authors, keywords & more
Public profiles for Economics researchers
Various research rankings in Economics
RePEc Genealogy
Who was a student of whom, using RePEc
Curated articles & papers on economics topics
Upload your paper to be listed on RePEc and IDEAS
New papers by email
Subscribe to new additions to RePEc
EconAcademics
Blog aggregator for economics research
Cases of plagiarism in Economics
About RePEc
Initiative for open bibliographies in Economics
News about RePEc
Questions about IDEAS and RePEc
RePEc volunteers
Participating archives
Publishers indexing in RePEc
Privacy statement
Found an error or omission?
Opportunities to help RePEc
Get papers listed
Have your research listed on RePEc
Open a RePEc archive
Have your institution's/publisher's output listed on RePEc
Get RePEc data
Use data assembled by RePEc
International Symposium on Algorithmic Game Theory
SAGT 2011: Algorithmic Game Theory pp 117–129 Cite as
Peer Effects and Stability in Matching Markets
- Elizabeth Bodine-Baron 17 ,
- Christina Lee 17 ,
- Anthony Chong 17 ,
- Babak Hassibi 17 &
- Adam Wierman 17
- Conference paper
1788 Accesses
129 Citations
Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 6982))
Many-to-one matching markets exist in numerous different forms, such as college admissions, matching medical interns to hospitals for residencies, assigning housing to college students, and the classic firms and workers market. In all these markets, externalities such as complementarities and peer effects severely complicate the preference ordering of each agent. Further, research has shown that externalities lead to serious problems for market stability and for developing efficient algorithms to find stable matchings. In this paper we make the observation that peer effects are often the result of underlying social connections, and we explore a formulation of the many-to-one matching market where peer effects are derived from an underlying social network. The key feature of our model is that it captures peer effects and complementarities using utility functions, rather than traditional preference ordering. With this model and considering a weaker notion of stability, namely two-sided exchange stability, we prove that stable matchings always exist and characterize the set of stable matchings in terms of social welfare. To characterize the efficiency of matching markets with externalities, we provide general bounds on how far the welfare of the worst-case stable matching can be from the welfare of the optimal matching, and find that the structure of the social network (e.g. how well clustered the network is) plays a large role.
This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CCF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747, and by Caltech’s Lee Center for Advanced Networking.
This is a preview of subscription content, log in via an institution .
Buying options
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Compact, lightweight edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
Tax calculation will be finalised at checkout
Purchases are for personal use only
Unable to display preview. Download preview PDF.
Alcalde, J.: Exchange-proofness or divorce-proofness? stability in one-sided matching markets. Rev. Econ. Design 1, 275–287 (1994)
Article Google Scholar
Anshelevich, E., Das, S., Naamad, Y.: Anarchy, stability, and utopia: Creating better matchings. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol. 5814, pp. 159–170. Springer, Heidelberg (2009)
Chapter Google Scholar
Baccara, M., Imrohoroglu, A., Wilson, A., Yariv, L.: A field study on matching with network externalities, Working paper (2009)
Google Scholar
Bajari, P., Fox, J.: Measuring the efficiency of an fcc spectrum auction. Working Paper 11671, National Bureau of Economic Research (2009)
Bodine-Baron, E., Lee, C., Chong, A., Hassibi, B.: A Wierman. Matching with friends: stability and peer effects in housing assignment, working paper, available on arxiv (2011)
Bogomolnaia, A., Jackson, M.: The stability of hedonic coalition structures. Games Econ. Behav. 38(2), 201–230 (2002)
Article MathSciNet MATH Google Scholar
Brânzei, S., Larson, K.: Coalitional affinity games and the stability gap. In: IJCAI, pp. 1319–1320 (2009)
Cechlarova, K., Manlove, D.: On the complexity of exchange-stable roommates. DAM 116(3), 279–287 (2002)
MathSciNet MATH Google Scholar
Cechlarova, K., Manlove, D.: The exchange-stable marriage problem. DAM 152(1-3), 109–122 (2005)
Dutta, B., Masso, J.: Stability of matchings when individuals have preferences over colleagues. J. Econ. Theory 75(2), 464–475 (1997)
Echenique, F., Yenmez, M.: A solution to matching with preferences over colleagues. Games Econ. Behav. 59(1), 46–71 (2007)
Fox, J.: Estimating matching games with transfers, Working paper (2010)
Gale, D., Shapley, L.S.: College admissions and the stability of marriage. AMM 69(1), 9–15 (1962)
Hafalir, I.E.: Stability of marriage with externalities. Int. J. Game Theory 37, 353–370 (2008)
Irving, R.: Stable matching problems with exchange restrictions. J. Comb. Opt. 16, 344–360 (2008)
Jackson, M.: Social and Economic Networks. Princeton University Press, Princeton (2008)
MATH Google Scholar
Kannan, R., Vempala, S., Vetta, A.: On clusterings: Good, bad and spectral. J. ACM 51(3), 497–515 (2004)
Klaus, B., Klijn, F.: Stable matchings and preferences of couples. J. Econ. Theory 121, 75–106 (2005)
Klaus, B., Klijn, F.: Paths to stability for matching markets with couples. Games Econ. Behav. 58, 154–171 (2007)
Kojima, F., Pathak, P.: Incentives and stability in large two-sided matching markets. Amer. Econ. Rev. 99(3), 608–627 (2009)
Ostrovsky, M.: Stability in supply chain networks. Amer. Econ. Rev. 98(3), 897–923 (2008)
Pycia, M.: Many-to-one matching with complementarities and peer effects, Working paper (2007)
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D.: Defining and identifying communities in networks. PNAS 101(9), 2658–2663 (2004)
Revilla, P.: Many-to-one matching when colleagues matter, Working paper (2004)
Ronn, E.: Np-complete stable matching problems. J. Alg. 11, 285–304 (1990)
Roth, A.E.: The evolution of the labor market for medical interns and residents: A case study in game theory. J. of Polit. Econ. 92, 991–1016 (1984)
Roth, A.E., Rothblum, U.G., Vande Vate, J.H.: Stable matchings, optimal assignments and linear programming. MOR 18(4), 803–828 (1993)
Roth, A.E., Sotomayor, M.: Two-sided matching: A study in game-theoretic modeling and analysis. Cambridge University Press, Cambridge (1990)
Book MATH Google Scholar
Roth, A.E., Vande Vate, J.H.: Random paths to stability in two-sided matching. Econometrica 58, 1475–1480 (1990)
Sasaki, H., Toda, M.: Two-sided matching problems with externalities. J. Econ. Theory 70(1), 93–108 (1996)
Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. of Pattern Analysis and Machine Intelligence 22(8), 888–905 (2000)
Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge (1994)
Download references
Author information
Authors and affiliations.
California Institute of Technology, Pasadena, CA, 91125, USA
Elizabeth Bodine-Baron, Christina Lee, Anthony Chong, Babak Hassibi & Adam Wierman
You can also search for this author in PubMed Google Scholar
Editor information
Editors and affiliations.
Dipartimento di Informatica ed Applicazioni Università di Salerno, 84084, Fisciano, SA, Italy
Giuseppe Persiano
Rights and permissions
Reprints and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper.
Bodine-Baron, E., Lee, C., Chong, A., Hassibi, B., Wierman, A. (2011). Peer Effects and Stability in Matching Markets. In: Persiano, G. (eds) Algorithmic Game Theory. SAGT 2011. Lecture Notes in Computer Science, vol 6982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24829-0_12
Download citation
DOI : https://doi.org/10.1007/978-3-642-24829-0_12
Publisher Name : Springer, Berlin, Heidelberg
Print ISBN : 978-3-642-24828-3
Online ISBN : 978-3-642-24829-0
eBook Packages : Computer Science Computer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Publish with us
Policies and ethics
- Find a journal
- Track your research
IMAGES
VIDEO
COMMENTS
The problem of allocating bundles of indivisible objects without transfers arises in many practical settings, including the assignment of courses to students, of siblings to schools, and of truckloads of food to food banks. In these settings, the complementarities in preferences are small compared with the size of the market.
The problem of allocating bundles of indivisible objects without transfers arises in many practical settings, including the assignment of courses to students, of siblings to schools, and of truckloads of food to food banks. In these settings, the complementarities in preferences are small compared with the size of the market. We exploit this to design mechanisms satisfying constrained ...
The problem of allocating bundles of indivisible objects without transfers arises in the assignment of courses to students, of computing resources like CPU time, memory and disk space to computing tasks and the truck loads of food to food banks. In these settings the complementarities in preferences are small compared with the size of the market.
The problem of allocating bundles of indivisible objects without transfers arises in many practical settings, including the assignment of courses to students, of siblings to schools, and of truckloads of food to food banks. In these settings, the complementarities in preferences are small compared with the size of the market.
The problem of allocating bundles of indivisible objects without transfers arises in many practical settings, including the assignment of courses to students, of siblings to schools, and of truckloads of food to food banks. In these settings, the complementarities in preferences are small compared with the size of the market.
For example, for the combinatorial assignment problem with limited complementarities, Nguyen et al. (2016) show that one can always decompose a feasible random assignment into a lottery over ...
Assignment problems have been widely studied by economists as well as those in opera-tions research (e.g., Koopmans and Beckmann, 1957; Gale, 1960; Roth and Sotomayor, 1990; Burkard, Dell'Amico and Martello, 2009). Adding statistical content to these problems in a manageable way is nontrivial. Doing so raises a number of interesting and ...
Assignment problems with complementarities. Thành Nguyen, Ahmad Peivandi and Rakesh Vohra. Journal of Economic Theory, 2016, vol. 165, issue C, 209-241 . Abstract: The problem of allocating bundles of indivisible objects without transfers arises in many practical settings, including the assignment of courses to students, of siblings to schools, and of truckloads of food to food banks.
Assignment Problems with Complementarities∗ Thành Nguyen†, Ahmad Peivandi‡, Rakesh Vohra§ November 2015 Abstract The problem of allocating bundles of indivisible objects without transfers arises in many practical settings, including the assignment of courses to students, of siblings to schools, and of truckloads of food to food banks.
Equivalent Assignment Problem c(x, y) 00312 01015 43330 00110 12204 cp(x, y) 3891510 41071614 913111910 813122013 175119 8 13 11 19 13 5 4 3 0 8 9 + 8 - 13 10 Reduced costs. For x # X, y # Y, define cp(x, y) = p(x) + c(x, y) - p(y). Observation 1. Finding a min cost perfect matching with reduced costs
This combinatorial assignment problem4 (or course-allocation problem) is one feature removed ... (Steinhaus, 1948) to accomodate environments with indivisibilities and complementarities. An allocation satis-es the maximin share guarantee if all agents obtain a bundle they weakly prefer to their maximin share. An allocation satis-es envy ...
additional complementarities due to goals such as maintaining diversity. It is clear that some form of stability is a key goal of this \housing assignment" problem. Notation for many-to-one matchings Using the language of the housing assignment problem, we de ne two nite and disjoint sets, H= fh 1;:::;h mg and S= fs 1;:::;s
Complementarities and Externalities Th anh Nguyen and Rakesh Vohray February 24, 2022 ... David Gale and Lloyd Shapley formulated the problem of nding a stable match- ... The third is establishing the existence of 'stable' fractional assignments. The connection to stability has been neglected, perhaps, because the study of NTU ...
Downloadable! The problem of allocating bundles of indivisible objects without transfers arises in the assignment of courses to students, of computing resources like CPU time, memory and disk space to computing tasks and the truck loads of food to food banks. In these settings the complementarities in preferences are small compared with the size of the market.
There are two basic challenges in adapting CEEI to the problem of combinatorial assignment 1. CEEI prices need not exist I Either indivisibilities or complementarities alone complicate existence. Our economy features both. 2. The fairness criteria at the heart of the argument for CEEI are either unde-ned or unrealistic in our environment
It is well known that if complementarities are present in such markets, a stable matching may not exist. We study large random matching markets with couples. We introduce a new matching algorithm and show that if the number of couples grows slower than the size of the market, a stable matching will be found with high probability. If however ...
California Institute of Technology, Pasadena, CA 91125, USA. {eabodine,chlee,anthony,hassibi,adamw}@caltech.edu. Abstract. Many-to-one matching markets exist in numerous different forms, such as college admissions, matching medical interns to hospitals for residencies, assigning housing to college students, and the classic and workers market.
Assignment Problems with Complementarities, Journal of Economic Theory, vol. 165, 209-241, 2016 (with Th anh Nguyen and Ahmad Peivandi). 10. Just Enough or All: Selling a Firm, American Economic Journal: Microeconomics, vol. 8 (3), 223-256, 2016 (with Mehmet Ekmekci and Nenad Kos ).
problems in macroeconomics and finance to pricing and product selection issues in industrial organization. At the heart of complementarity is the notion, due to Edgeworth, that the marginal value of an action or variable increases in the level of another action or variable. Complementarities have been a recurrent and somewhat contentious topic ...
This problem that comes with multiple biases is reminiscent of the Anna Karenina principle, which states that failure in just one factor out ... Treatment assignment was randomized and the group sizes are as follows: 82 in CON, 88 in SER, 90 in RTF, 91 in DUAL. 13. ... Our theoretical framework predicts that complementarities should become more ...
Complementation problems >> Notes. State the number of complementation groups (different gene loci) in each set of crosses, and which strains contain defective alleles for the same locus. (-) means failure to complement; (+) means complementation, restoration of function.
Jacobides et al. (2018) focus on the reasons why such alignment structures emerge, highlighting the role of modularity and, perhaps more importantly, the nature and strength of complementarities as defining features. 5 This view is shared by Baldwin, 2022, who claims that "for an ecosystem to be sustained, the complementarities among products ...
Study with Quizlet and memorize flashcards containing terms like Specialized task assignment, Broad task assignment, Benefits of specialized task assignment and more. ... (sales only looks for sales, even if the sale imposes large service costs) - foregone complementarities across tasks - coordination costs --> transferring informations between ...