Dominant strategy implementation of stable rules
AbstractMost 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.
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.
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.
Bibliographic InfoArticle provided by Elsevier in its journal Games and Economic Behavior.
Volume (Year): 75 (2012)
Issue (Month): 1 ()
Contact details of provider:
Web page: http://www.elsevier.com/locate/inca/622836
Deferred acceptance algorithm; Dominant strategy implementation; Stability; Weak nonbossiness; Multiple equilibria;
Find related papers by JEL classification:
- C62 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Existence and Stability Conditions of Equilibrium
- C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
- D78 - Microeconomics - - Analysis of Collective Decision-Making - - - Positive Analysis of Policy Formulation and Implementation
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.:
- 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.
- Tatsuyoshi Saijo & Tomas Sjostrom & Takehiko Yamato, 2005.
Economics Working Papers
0056, Institute for Advanced Study, School of Social Science.
- 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.
- Guillaume Haeringer & Flip Klijn, 2008.
"Constrained School Choice,"
294, Barcelona Graduate School of Economics.
- Caterina Calsamiglia & Guillaume Haeringer & Flip Klijn, 2010.
"Constrained School Choice: An Experimental Study,"
American Economic Review,
American Economic Association, vol. 100(4), pages 1860-74, September.
- 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.
- 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).
- Kojima, Fuhito, 2010. "Impossibility of stable and nonbossy matching mechanisms," Economics Letters, Elsevier, vol. 107(1), pages 69-70, April.
- Kumano, Taro & Watabe, Masahiro, 2011. "Untruthful dominant strategies for the deferred acceptance algorithm," Economics Letters, Elsevier, vol. 112(2), pages 135-137, August.
- 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).
- Alcalde, Jose & Barbera, Salvador, 1994. "Top Dominance and the Possibility of Strategy-Proof Stable Solutions to Matching Problems," Economic Theory, Springer, vol. 4(3), pages 417-35, May.
- 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.
- Tayfun Sonmez, 1999. "Strategy-Proofness and Essentially Single-Valued Cores," Econometrica, Econometric Society, vol. 67(3), pages 677-690, May.
- 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.
- John William Hatfield & Paul R. Milgrom, 2005.
"Matching with Contracts,"
American Economic Review,
American Economic Association, vol. 95(4), pages 913-935, September.
- Tayfun Sönmez & Tarik Kara, 1997. "Implementation of college admission rules (*)," Economic Theory, Springer, vol. 9(2), pages 197-218.
- 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.
- 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.
- 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.
- Kara, Tarik & Sonmez, Tayfun, 1996. "Nash Implementation of Matching Rules," Journal of Economic Theory, Elsevier, vol. 68(2), pages 425-439, February.
- 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.
- Alkan, Ahmet & Gale, David, 2003. "Stable schedule matching under revealed preference," Journal of Economic Theory, Elsevier, vol. 112(2), pages 289-306, October.
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.