Dominant strategy implementation of stable rules
Most priority-based assignment problems are solved using the deferred acceptance algorithm. Kojima (2010) shows that stability and nonbossiness are incompatible. We show that the deferred acceptance algorithm satisfies a weaker notion of nonbossiness for every substitutable priority structure. We also discuss the multiplicity of dominant strategy equilibria of the preference revelation game induced by the deferred acceptance algorithm. We show that even untruthful dominant strategy equilibria lead to the truthful equilibrium outcome. In other words, the deferred acceptance algorithm is dominant strategy implementable.
If 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.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
References listed on IDEAS
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.:
- Caterina Calsamiglia & Guillaume Haeringer & Flip Klijn, 2008.
"Constrained School Choice: An Experimental Study,"
365, Barcelona Graduate School of Economics.
- Caterina Calsamiglia & Guillaume Haeringer & Flip Klijn, 2008. "Constrained School Choice: An Experimental Study," UFAE and IAE Working Papers 757.08, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
- Guillaume Haeringer & Caterina Calsamiglia & Flip Klijn, 2009. "Constrained School Choice: An Experimental Study," Working Papers 2009.29, Fondazione Eni Enrico Mattei.
- Ahmet Alkan, 2001. "original papers : On preferences over subsets and the lattice structure of stable matchings," Review of Economic Design, Springer, vol. 6(1), pages 99-111.
- Alkan, Ahmet & Gale, David, 2003. "Stable schedule matching under revealed preference," Journal of Economic Theory, Elsevier, vol. 112(2), pages 289-306, October.
- Hideki Mizukami & Takuma Wakayama, 2006.
"Dominant Strategy Implementation in Economic Environments,"
ISER Discussion Paper
0669, Institute of Social and Economic Research, Osaka University.
- Mizukami, Hideki & Wakayama, Takuma, 2007. "Dominant strategy implementation in economic environments," Games and Economic Behavior, Elsevier, vol. 60(2), pages 307-325, August.
- Paul Milgrom, 2003.
"Matching with Contracts,"
03003, Stanford University, Department of Economics.
- Tatsuyoshi Saijo & Tomas Sjostrom & Takehiko Yamato, 2005.
Economics Working Papers
0056, Institute for Advanced Study, School of Social Science.
- Kojima, Fuhito, 2010. "Impossibility of stable and nonbossy matching mechanisms," Economics Letters, Elsevier, vol. 107(1), pages 69-70, April.
- Kara, Tarik & Sonmez, Tayfun, 1996. "Nash Implementation of Matching Rules," Journal of Economic Theory, Elsevier, vol. 68(2), pages 425-439, February.
- Guillaume Haeringer & Flip Klijn, 2008.
"Constrained School Choice,"
294, Barcelona Graduate School of Economics.
- Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth, 2009.
"Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match,"
American Economic Review,
American Economic Association, vol. 99(5), pages 1954-78, December.
- Abdulkadiroglu, Atila & Pathak, Parag Abishek & Roth, Alvin E., 2009. "Strategy-Proofness Versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match," Scholarly Articles 11077572, Harvard University Department of Economics.
- Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
- Atila Abdulkadiroğlu, 2005. "College admissions with affirmative action," International Journal of Game Theory, Springer, vol. 33(4), pages 535-549, November.
- Aytek Erdil & Haluk Ergin, 2008.
"What's the Matter with Tie-Breaking? Improving Efficiency in School Choice,"
American Economic Review,
American Economic Association, vol. 98(3), pages 669-89, June.
- Aytek Erdil & Haluk Ergin, 2007. "What`s the Matter with Tie-breaking? Improving Efficiency in School Choice," Economics Series Working Papers 349, University of Oxford, Department of Economics.
- Kumano, Taro & Watabe, Masahiro, 2011. "Untruthful dominant strategies for the deferred acceptance algorithm," Economics Letters, Elsevier, vol. 112(2), pages 135-137, August.
- Alcalde, Jose & Barbera, Salvador, 1994.
"Top Dominance and the Possibility of Strategy-Proof Stable Solutions to Matching Problems,"
Springer, vol. 4(3), pages 417-35, May.
- Alcalde, J. & Barberà, S., 1992. "Top Dominance and the Possibility of Strategy-Proof Stable Solutions to Matching Problems," UFAE and IAE Working Papers 196.92, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
- Dasgupta, Partha S & Hammond, Peter J & Maskin, Eric S, 1979. "The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility," Review of Economic Studies, Wiley Blackwell, vol. 46(2), pages 185-216, April.
- Tayfun Sonmez, 1999. "Strategy-Proofness and Essentially Single-Valued Cores," Econometrica, Econometric Society, vol. 67(3), pages 677-690, May.
- Tayfun Sönmez & Tarik Kara, 1997. "Implementation of college admission rules (*)," Economic Theory, Springer, vol. 9(2), pages 197-218.
- Repullo, Rafael, 1985. "Implementation in Dominant Strategies under Complete and Incomplete Information," Review of Economic Studies, Wiley Blackwell, vol. 52(2), pages 223-29, April.
- Satterthwaite, Mark A & Sonnenschein, Hugo, 1981. "Strategy-Proof Allocation Mechanisms at Differentiable Points," Review of Economic Studies, Wiley Blackwell, vol. 48(4), pages 587-97, October.
When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:75:y:2012:i:1:p:428-434. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
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.