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

Assigning agents to a line

Contents:

Author Info

  • HOUGAARD, Jens L.

    (University of Copenhagen)

  • moreno-ternero, JUAN D.

    (Universidad Pablo de Olavide, Spain and Université catholique de Louvain, CORE, Belgium)

  • OSTERDAL, Lars P.

    (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 utilitarian 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 utilitarian. We then consider probabilistic assignment of agents to slots, and make use of the previous method to propose a utilitarian 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.

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://uclouvain.be/cps/ucl/doc/core/documents/coredp2013_15.pdf
Download Restriction: no

Bibliographic Info

Paper provided by Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) in its series CORE Discussion Papers with number 2013015.

as in new window
Length:
Date of creation: 06 May 2013
Date of revision:
Handle: RePEc:cor:louvco:2013015

Contact details of provider:
Postal: Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium)
Phone: 32(10)474321
Fax: +32 10474304
Email:
Web page: http://www.uclouvain.be/core
More information through EDIRC

Related research

Keywords: probabilistic assignment; random priority; utilitarianism; 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. 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).
  2. Kojima, Fuhito, 2009. "Random assignment of multiple indivisible objects," Mathematical Social Sciences, Elsevier, vol. 57(1), pages 134-142, January.
  3. 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.
  4. Kojima, Fuhito & Manea, Mihai, 2010. "Incentives in the probabilistic serial mechanism," Journal of Economic Theory, Elsevier, vol. 145(1), pages 106-123, January.
  5. Moulin, Herve & Bogomolnaia, Anna, 2001. "Random Matching under Dichotomous Preferences," Working Papers 2001-03, Rice University, Department of Economics.
  6. 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.
  7. Stergios Athanassoglou & Jay Sethuraman, 2011. "House allocation with fractional endowments," International Journal of Game Theory, Springer, vol. 40(3), pages 481-513, August.
  8. 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.
  9. 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.
  10. 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.
  11. Chambers, Christopher P., 2004. "Consistency in the probabilistic assignment model," Journal of Mathematical Economics, Elsevier, vol. 40(8), pages 953-962, December.
  12. Yoichi Kasajima, 2013. "Probabilistic assignment of indivisible goods with single-peaked preferences," Social Choice and Welfare, Springer, vol. 41(1), pages 203-215, June.
  13. Manea, Mihai, 2009. "Asymptotic ordinal inefficiency of random serial dictatorship," Theoretical Economics, Econometric Society, vol. 4(2), June.
  14. Kesten, Onur, 2009. "Why do popular mechanisms lack efficiency in random environments?," Journal of Economic Theory, Elsevier, vol. 144(5), pages 2209-2226, September.
  15. 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.
  16. Moulin, Herve & Cres, Moulin, 2000. "Scheduling with Opting Out: Improving upon Random Priority," Working Papers 2000-03, Rice University, Department of Economics.
  17. Manea, Mihai, 2008. "A constructive proof of the ordinal efficiency welfare theorem," Journal of Economic Theory, Elsevier, vol. 141(1), pages 276-281, July.
  18. Abdulkadiroglu, Atila & Sonmez, Tayfun, 2003. "Ordinal efficiency and dominated sets of assignments," Journal of Economic Theory, Elsevier, vol. 112(1), pages 157-172, September.
  19. Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2012. "Assigning agents to a line," Discussion Papers of Business and Economics 11/2012, Department of Business and Economics, University of Southern Denmark.
  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. 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.
  22. YIlmaz, Özgür, 2009. "Random assignment under weak preferences," Games and Economic Behavior, Elsevier, vol. 66(1), pages 546-558, May.
  23. 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.
  24. Gibbard, Allan, 1978. "Straightforwardness of Game Forms with Lotteries as Outcomes," Econometrica, Econometric Society, vol. 46(3), pages 595-614, May.
  25. Ü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.
  26. 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.
  27. Robert J. Dolan, 1978. "Incentive Mechanisms for Priority Queuing Problems," Bell Journal of Economics, The RAND Corporation, vol. 9(2), pages 421-436, Autumn.
  28. McLennan, Andrew, 2002. "Ordinal Efficiency and the Polyhedral Separating Hyperplane Theorem," Journal of Economic Theory, Elsevier, vol. 105(2), pages 435-449, August.
  29. 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.
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 Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2012. "Assigning agents to a line," Discussion Papers of Business and Economics 11/2012, Department of Business and Economics, University of Southern Denmark.
  2. CORNUEJOLS, Gérard & WOLSEY, Laurence & YILDIZ, Sercan, 2013. "Sufficiency of cut-generating functions," CORE Discussion Papers 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:cor:louvco:2013015. 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: (Alain GILLIS).

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.