The Difference Indifference Makes in Strategy-Proof Allocation of Objects
AbstractWe study the problem of allocating objects among people. We consider cases where each object is initially owned by someone, no object is initially owned by anyone, and combinations of the two. The problems we look at are those where each person has a need for exactly one object and initially owns at most one object (also known as house allocation with existing tenants"). We split with most of the existing literature on this topic by dropping the assumption that people can always strictly rank the objects. We show that, without this assumption, problems in which either some or all of the objects are not initially owned are equivalent to problems where each object is initially owned by someone. Thus, it suffices to study problems of the latter type.We ask if there are efficient rules that provide incentives for each person not only to participate (rather than stay home with what he owns), but also to state his preferences honestly. Our main contribution is to show that the answer is positive. The intuitive "top trading cycles" algorithm provides the only such rule for environments where people are never indifferent (Ma 1994). We generalize this algorithm in a way that allows for indifference without compromising on efficiency and incentives."
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by UNIVERSIDAD DE LOS ANDES-CEDE in its series DOCUMENTOS CEDE with number 008746.
Date of creation: 03 Apr 2011
Date of revision:
Contact details of provider:
strategy-proofness; indivisible goods; indifference; housing market; house allocation; kidney exchange;
Other versions of this item:
- Jaramillo, Paula & Manjunath, Vikram, 2012. "The difference indifference makes in strategy-proof allocation of objects," Journal of Economic Theory, Elsevier, vol. 147(5), pages 1913-1946.
- C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
- C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
- D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations
- D78 - Microeconomics - - Analysis of Collective Decision-Making - - - Positive Analysis of Policy Formulation and Implementation
This paper has been announced in the following NEP Reports:
- NEP-ALL-2011-06-18 (All new papers)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Ehlers, Lars, 2002. "Coalitional Strategy-Proof House Allocation," Journal of Economic Theory, Elsevier, vol. 105(2), pages 298-317, August.
- Bird, Charles G., 1984. "Group incentive compatibility in a market with indivisible goods," Economics Letters, Elsevier, vol. 14(4), pages 309-313.
- Sönmez, Tayfun & Ünver, M. Utku, 2010. "House allocation with existing tenants: A characterization," Games and Economic Behavior, Elsevier, vol. 69(2), pages 425-445, July.
- Tayfun Sonmez, 1999. "Strategy-Proofness and Essentially Single-Valued Cores," Econometrica, Econometric Society, vol. 67(3), pages 677-690, May.
- Marek Pycia & M. Utku Ünver, 2009. "Incentive Compatible Allocation and Exchange of Discrete Resources," Boston College Working Papers in Economics 715, Boston College Department of Economics, revised 11 Mar 2014.
- Thomas Quint & Jun Wako, 2004. "On Houseswapping, the Strict Core, Segmentation, and Linear Programming," Yale School of Management Working Papers ysm373, Yale School of Management.
- Szilvia Papai, 2000. "Strategyproof Assignment by Hierarchical Exchange," Econometrica, Econometric Society, vol. 68(6), pages 1403-1434, November.
- Alcalde-Unzu, Jorge & Molis, Elena, 2011.
"Exchange of indivisible goods and indifferences: The Top Trading Absorbing Sets mechanisms,"
Games and Economic Behavior,
Elsevier, vol. 73(1), pages 1-16, September.
- ALCALDE-UNZU, Jorge & MOLIS, Elena, 2009. "Exchange of indivisible goods and indifferences: the Top Trading Absorbing Sets mechanisms," CORE Discussion Papers 2009062, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Miyagawa, Eiichi, 2002. "Strategy-Proofness and the Core in House Allocation Problems," Games and Economic Behavior, Elsevier, vol. 38(2), pages 347-361, February.
- Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
- Abdulkadiroglu, Atila & Sonmez, Tayfun, 1999. "House Allocation with Existing Tenants," Journal of Economic Theory, Elsevier, vol. 88(2), pages 233-260, October.
- Bogomolnaia, Anna & Deb, Rajat & Ehlers, Lars, 2005. "Strategy-proof assignment on the full preference domain," Journal of Economic Theory, Elsevier, vol. 123(2), pages 161-186, August.
- Roth, Alvin E., 1982. "Incentive compatibility in a market with indivisible goods," Economics Letters, Elsevier, vol. 9(2), pages 127-132.
- Kesten, Onur, 2006. "On two competing mechanisms for priority-based allocation problems," Journal of Economic Theory, Elsevier, vol. 127(1), pages 155-171, March.
- Ma, Jinpeng, 1994. "Strategy-Proofness and the Strict Core in a Market with Indivisibilities," International Journal of Game Theory, Springer, vol. 23(1), pages 75-83.
- Carbajal, Juan Carlos & McLennan, Andrew & Tourky, Rabee, 2013.
"Truthful implementation and preference aggregation in restricted domains,"
Journal of Economic Theory,
Elsevier, vol. 148(3), pages 1074-1101.
- Juan Carlos Carbajal & Andrew McLennan & Rabee Tourky, 2012. "Truthful Implementation and Preference Aggregation in Restricted Domains," Discussion Papers Series 459, School of Economics, University of Queensland, Australia.
- Antonio Nicolò & Carmelo Rodríguez-Álvarez, 2013. "Age based preferences in paired kidney exchange," Documentos de Trabajo del ICAE 2013-38, Universidad Complutense de Madrid, Facultad de Ciencias Económicas y Empresariales, Instituto Complutense de Análisis Económico.
- Salvador Barberà & Dolors Berga & Bernardo Moreno, 2011.
"Two Necessary Conditions for Strategy-Proofness: on What Domains are they also Sufficient?,"
598, Barcelona Graduate School of Economics.
- Barberà, Salvador & Berga, Dolors & Moreno, Bernardo, 2012. "Two necessary conditions for strategy-proofness: On what domains are they also sufficient?," Games and Economic Behavior, Elsevier, vol. 75(2), pages 490-509.
- Salvador Barberà & Dolors Berga & Bernardo Moreno, 2011. "Two Necessary Conditions for Strategy-Proofness: on What Domains are they also Sufficient?," UFAE and IAE Working Papers 892.11, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Universidad De Los Andes-Cede).
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.