Advanced Search
MyIDEAS: Login

Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms

Contents:

Author Info

  • Yeon-Koo Che

    ()
    (Columbia University - Department of Economics)

  • Fuhito Kojima

    ()
    (Cowles Foundation, Yale University)

Abstract

The random priority (random serial dictatorship) mechanism is a common method for assigning objects to individuals. The mechanism is easy to implement and strategy-proof. However this mechanism is inefficient, as the agents may be made all better off by another mechanism that increases their chances of obtaining more preferred objects. Such an ineciency is eliminated by the recent mechanism called probabilistic serial, but this mechanism is not strategy-proof. Thus, which mechanism to employ in practical applications has been an open question. This paper shows that these mechanisms become equivalent when the market becomes large. More specifically, given a set of object types, the random assignments in these mechanisms converge to each other as the number of copies of each object type approaches infinity. Thus, the inefficiency of the random priority mechanism becomes small in large markets. Our result gives some rationale for the common use of the random priority mechanism in practical problems such as student placement in public schools.

Download Info

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.
File URL: http://www.econ.columbia.edu/RePEc/pdf/DP0809-06.pdf
Our checks indicate that this address may not be valid because: 404 Not Found (http://www.econ.columbia.edu/RePEc/pdf/DP0809-06.pdf [301 Moved Permanently]--> http://econ.columbia.edu/RePEc/pdf/DP0809-06.pdf). If this is indeed the case, please notify (Discussion Paper Coordinator)
Download Restriction: no

Bibliographic Info

Paper provided by Columbia University, Department of Economics in its series Discussion Papers with number 0809-06.

as in new window
Length:
Date of creation: 2008
Date of revision:
Handle: RePEc:clu:wpaper:0809-06

Contact details of provider:
Postal: 1022 International Affairs Building, 420 West 118th Street, New York, NY 10027
Phone: (212) 854-3680
Fax: (212) 854-8059
Web page: http://www.econ.columbia.edu/
More information through EDIRC

Related research

Keywords:

Other versions of this item:

Find related papers by JEL classification:

This paper has been announced in the following NEP Reports:

References

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.:
as in new window
  1. Sönmez, Tayfun & Pathak, Parag A. & Abdulkadiroglu, Atila & Roth, Alvin, 2005. "The Boston Public School Match," Scholarly Articles 2562764, Harvard University Department of Economics.
  2. Moulin, Herve & Cres, Moulin, 2000. "Scheduling with Opting Out: Improving upon Random Priority," Working Papers 2000-03, Rice University, Department of Economics.
  3. Judd, Kenneth L., 1985. "The law of large numbers with a continuum of IID random variables," Journal of Economic Theory, Elsevier, vol. 35(1), pages 19-25, February.
  4. Sun, Yeneng, 2006. "The exact law of large numbers via Fubini extension and characterization of insurable risks," Journal of Economic Theory, Elsevier, vol. 126(1), pages 31-69, January.
  5. Martin W. Cripps & Jeroen M. Swinkels, 2006. "Efficiency of Large Double Auctions," Econometrica, Econometric Society, vol. 74(1), pages 47-92, 01.
  6. McLennan, Andrew, 2002. "Ordinal Efficiency and the Polyhedral Separating Hyperplane Theorem," Journal of Economic Theory, Elsevier, vol. 105(2), pages 435-449, August.
  7. Atila Abdulkadiroglu & Tayfun Sonmez, 1998. "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems," Econometrica, Econometric Society, vol. 66(3), pages 689-702, May.
  8. Bogomolnaia, Anna & Moulin, Herve, 2001. "A New Solution to the Random Assignment Problem," Journal of Economic Theory, Elsevier, vol. 100(2), pages 295-328, October.
  9. Abdulkadiroglu, Atila & Sonmez, Tayfun, 2003. "Ordinal efficiency and dominated sets of assignments," Journal of Economic Theory, Elsevier, vol. 112(1), pages 157-172, September.
  10. Hylland, Aanund & Zeckhauser, Richard, 1979. "The Efficient Allocation of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 87(2), pages 293-314, April.
  11. Yan Chen & Tayfun S�nmez, 2002. "Improving Efficiency of On-Campus Housing: An Experimental Study," American Economic Review, American Economic Association, vol. 92(5), pages 1669-1686, December.
  12. Balinski, Michel & Sonmez, Tayfun, 1999. "A Tale of Two Mechanisms: Student Placement," Journal of Economic Theory, Elsevier, vol. 84(1), pages 73-94, January.
  13. Jackson, Matthew O. & Manelli, Alejandro M., 1997. "Approximately Competitive Equilibria in Large Finite Economies," Journal of Economic Theory, Elsevier, vol. 77(2), pages 354-376, December.
  14. Jackson, Matthew O., 1992. "Incentive compatibility and competitive allocations," Economics Letters, Elsevier, vol. 40(3), pages 299-302, November.
Full references (including those not matched with items on IDEAS)

Citations

Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
as in new window

Cited by:
  1. Radzik, Tadeusz, 2013. "Is the solidarity value close to the equal split value?," Mathematical Social Sciences, Elsevier, vol. 65(3), pages 195-202.
  2. Eric Budish & Estelle Cantillon, 2012. "The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard," ULB Institutional Repository 2013/99376, ULB -- Universite Libre de Bruxelles.
  3. John William Hatfield & Fuhito Kojima & Yusuke Narita, 2012. "Promoting School Competition Through School Choice: A Market Design Approach," Discussion Papers 12-036, Stanford Institute for Economic Policy Research.
  4. Yoichi Kasajima, 2013. "Probabilistic assignment of indivisible goods with single-peaked preferences," Social Choice and Welfare, Springer, vol. 41(1), pages 203-215, June.
  5. Athanassoglou, Stergios, 2011. "Efficiency under a combination of ordinal and cardinal information on preferences," Journal of Mathematical Economics, Elsevier, vol. 47(2), pages 180-185, March.
  6. Kojima, Fuhito, 2009. "Random assignment of multiple indivisible objects," Mathematical Social Sciences, Elsevier, vol. 57(1), pages 134-142, January.

Lists

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

Statistics

Access and download statistics

Corrections

When requesting a correction, please mention this item's handle: RePEc:clu:wpaper:0809-06. 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: (Discussion Paper Coordinator).

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.