Advanced Search
MyIDEAS: Login to save this paper or follow this series

Assigning agents to a line

Contents:

Author Info

  • 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)

Abstract

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.

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.upo.es/serv/bib/wps/econ1401.pdf
Download Restriction: no

Bibliographic Info

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

as 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
Email:
Web page: http://www.upo.es/econ/
More information through EDIRC

Related research

Keywords: Probabilistic assignment; random priority; aggregate gap minimizing; sd-efficiency; bottleneck;

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

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: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.