IDEAS home Printed from
MyIDEAS: Log in (now much improved!) to save this paper

Assigning agents to a line

  • Jens L. Hougaard


    (Department of Food and Resource Economics, University of Copenhagen)

  • Juan D. Moreno-Ternero


    (Department of Economics, Universidad Pablo de Olavide; CORE, Université catholique de Louvain)

  • Lars P. Osterdal


    (Department of Business and Economics, University of Southern Denmark)

We consider the problem of assigning agents to slots on a line, where only one agent can be served at a slot and each agent prefers to be served as close as possible to his target. Our focus is on aggregate gap minimizing methods, i.e., those that minimize the total gap between targets and assigned slots. We first consider deterministic assignment of agents to slots, and provide a direct method for testing if a given deterministic assignment is aggregate gap minimizing. We then consider probabilistic assignment of agents to slots, and make use of the previous method to propose an aggregate gap minimizing modification of the classic random priority method to solve this class of problems. We also provide some logical relations in our setting among standard axioms in the literature on assignment problems, and explore the robustness of our results to several extensions of our setting.

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:
Download Restriction: no

Paper provided by Universidad Pablo de Olavide, Department of Economics in its series Working Papers with number 14.01.

in new window

Length: 29 pages
Date of creation: Mar 2014
Date of revision:
Handle: RePEc:pab:wpaper:14.01
Contact details of provider: Postal:
Carretera de Utrera km.1, 41013 Sevilla

Phone: + 34 954 34 8913
Fax: + 34 954 34 9339
Web page:

More information through EDIRC

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. Manea, Mihai, 2009. "Asymptotic ordinal inefficiency of random serial dictatorship," Theoretical Economics, Econometric Society, vol. 4(2), June.
  2. Yoichi Kasajima, 2013. "Probabilistic assignment of indivisible goods with single-peaked preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(1), pages 203-215, June.
  3. Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2014. "Assigning agents to a line," Games and Economic Behavior, Elsevier, vol. 87(C), pages 539-553.
  4. Salvador Barberà & Dolors Berga & Bernardo Moreno, 2009. "Individual versus group strategy-proofness: when do they coincide?," UFAE and IAE Working Papers 761.09, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
  5. McLennan, Andrew, 2002. "Ordinal Efficiency and the Polyhedral Separating Hyperplane Theorem," Journal of Economic Theory, Elsevier, vol. 105(2), pages 435-449, August.
  6. Zhou, Lin, 1990. "On a conjecture by gale about one-sided matching problems," Journal of Economic Theory, Elsevier, vol. 52(1), pages 123-135, October.
  7. Kojima, Fuhito, 2009. "Random assignment of multiple indivisible objects," Mathematical Social Sciences, Elsevier, vol. 57(1), pages 134-142, January.
  8. Anna Bogomolnaia & Herve Moulin, 2004. "Random Matching Under Dichotomous Preferences," Econometrica, Econometric Society, vol. 72(1), pages 257-279, 01.
  9. 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.
  10. Hervé Crès & Hervé Moulin, 1998. "Scheduling with Opting Out: Improving Upon Random Priority," Working Papers hal-00601584, HAL.
  11. Yeon-Koo Che & Fuhito Kojima, 2010. "Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms," Econometrica, Econometric Society, vol. 78(5), pages 1625-1672, 09.
  12. Kesten, Onur, 2009. "Why do popular mechanisms lack efficiency in random environments?," Journal of Economic Theory, Elsevier, vol. 144(5), pages 2209-2226, September.
  13. Budish, Eric & Cantillon, Estelle, 2010. "The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard," CEPR Discussion Papers 7641, C.E.P.R. Discussion Papers.
  14. Chambers, Christopher P., 2004. "Consistency in the probabilistic assignment model," Journal of Mathematical Economics, Elsevier, vol. 40(8), pages 953-962, December.
  15. Alkan, Ahmet & Demange, Gabrielle & Gale, David, 1991. "Fair Allocation of Indivisible Goods and Criteria of Justice," Econometrica, Econometric Society, vol. 59(4), pages 1023-39, July.
  16. Sprumont, Yves, 1991. "The Division Problem with Single-Peaked Preferences: A Characterization of the Uniform Allocation Rule," Econometrica, Econometric Society, vol. 59(2), pages 509-19, March.
  17. YIlmaz, Özgür, 2009. "Random assignment under weak preferences," Games and Economic Behavior, Elsevier, vol. 66(1), pages 546-558, May.
  18. Stergios Athanassoglou & Jay Sethuraman, 2011. "House allocation with fractional endowments," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(3), pages 481-513, August.
  19. Manea, Mihai, 2008. "A constructive proof of the ordinal efficiency welfare theorem," Journal of Economic Theory, Elsevier, vol. 141(1), pages 276-281, July.
  20. Ju, Biung-Ghi & Miyagawa, Eiichi & Sakai, Toyotaka, 2007. "Non-manipulable division rules in claim problems and generalizations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 1-26, January.
  21. Gibbard, Allan, 1978. "Straightforwardness of Game Forms with Lotteries as Outcomes," Econometrica, Econometric Society, vol. 46(3), pages 595-614, May.
  22. Katta, Akshay-Kumar & Sethuraman, Jay, 2006. "A solution to the random assignment problem on the full preference domain," Journal of Economic Theory, Elsevier, vol. 131(1), pages 231-250, November.
  23. Robert J. Dolan, 1978. "Incentive Mechanisms for Priority Queuing Problems," Bell Journal of Economics, The RAND Corporation, vol. 9(2), pages 421-436, Autumn.
  24. Onur Kesten & Morimitsu Kurino & M. Utku Ünver, 2010. "Fair and Efficient Assignment via the Probabilistic Serial Mechanism," Boston College Working Papers in Economics 742, Boston College Department of Economics, revised 30 May 2011.
  25. Bogomolnaia, Anna & Heo, Eun Jeong, 2012. "Probabilistic assignment of objects: Characterizing the serial rule," Journal of Economic Theory, Elsevier, vol. 147(5), pages 2072-2082.
  26. Abdulkadiroglu, Atila & Sonmez, Tayfun, 2003. "Ordinal efficiency and dominated sets of assignments," Journal of Economic Theory, Elsevier, vol. 112(1), pages 157-172, September.
  27. Ünver, M. Utku & Kesten, Onur & Kurino, Morimitsu & Hashimoto, Tadashi & Hirata, Daisuke, 2014. "Two axiomatic approaches to the probabilistic serial mechanism," Theoretical Economics, Econometric Society, vol. 9(1), January.
  28. Kojima, Fuhito & Manea, Mihai, 2010. "Incentives in the probabilistic serial mechanism," Journal of Economic Theory, Elsevier, vol. 145(1), pages 106-123, January.
  29. 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.
  30. 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.
Full references (including those not matched with items on IDEAS)

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

When requesting a correction, please mention this item's handle: RePEc:pab:wpaper:14.01. 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: (Publicación Digital - UPO)

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.

This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.