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,"
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).
- Caterina Calsamiglia & Guillaume Haeringer & Flip Klijn, 2008. "Constrained School Choice: An Experimental Study," Working Papers 365, Barcelona Graduate School of Economics.
- Guillaume Haeringer & Caterina Calsamiglia & Flip Klijn, 2009. "Constrained School Choice: An Experimental Study," Working Papers 2009.29, Fondazione Eni Enrico Mattei.
- repec:oup:restud:v:52:y:1985:i:2:p:223-29 is not listed on IDEAS
- Kojima, Fuhito, 2010. "Impossibility of stable and nonbossy matching mechanisms," Economics Letters, Elsevier, vol. 107(1), pages 69-70, April.
- Sjostrom, Tomas & Yamato, Takehiko & Saijo, Tatsuyoshi, 2007.
Econometric Society, vol. 2(3), September.
- Tatsuyoshi Saijo & Tomas Sjöström & Takehiko Yamato, 2004. "Secure Implementation," Levine's Bibliography 122247000000000615, UCLA Department of Economics.
- Tatsuyoshi Saijo & Tomas Sjostrom & Takehiko Yamato, 2005. "Secure Implementation," Economics Working Papers 0056, Institute for Advanced Study, School of Social Science.
- 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).
- Guillaume Haeringer & Flip Klijn, 2008.
"Constrained School Choice,"
294, Barcelona Graduate School of Economics.
- Atila Abdulkadiroğlu, 2005. "College admissions with affirmative action," International Journal of Game Theory, Springer, vol. 33(4), pages 535-549, November.
- Mizukami, Hideki & Wakayama, Takuma, 2007.
"Dominant strategy implementation in economic environments,"
Games and Economic Behavior,
Elsevier, vol. 60(2), pages 307-325, August.
- Hideki Mizukami & Takuma Wakayama, 2006. "Dominant Strategy Implementation in Economic Environments," ISER Discussion Paper 0669, Institute of Social and Economic Research, Osaka University.
- Abdulkadiroglu, Atila & Pathak, Parag Abishek & Roth, Alvin E., 2009.
"Strategy-Proofness Versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match,"
11077572, Harvard University Department 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.
- 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.
- Tayfun Sönmez & Tarik Kara, 1997. "Implementation of college admission rules (*)," Economic Theory, Springer, vol. 9(2), pages 197-218.
- repec:oup:restud:v:48:y:1981:i:4:p:587-97 is not listed on IDEAS
- Tayfun Sonmez, 1999. "Strategy-Proofness and Essentially Single-Valued Cores," Econometrica, Econometric Society, vol. 67(3), pages 677-690, May.
- Paul Milgrom, 2003.
"Matching with Contracts,"
03003, Stanford University, Department of Economics.
- repec:oup:restud:v:46:y:1979:i:2:p:185-216 is not listed on IDEAS
- Alkan, Ahmet & Gale, David, 2003. "Stable schedule matching under revealed preference," Journal of Economic Theory, Elsevier, vol. 112(2), pages 289-306, October.
- Kara, Tarik & Sonmez, Tayfun, 1996. "Nash Implementation of Matching Rules," Journal of Economic Theory, Elsevier, vol. 68(2), pages 425-439, February.
- Kumano, Taro & Watabe, Masahiro, 2011. "Untruthful dominant strategies for the deferred acceptance algorithm," Economics Letters, Elsevier, vol. 112(2), pages 135-137, August.
- 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.
- 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.
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.