IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v163y2008i1p49-6210.1007-s10479-008-0335-0.html
   My bibliography  Save this article

Multiagent resource allocation in k-additive domains: preference representation and complexity

Author

Listed:
  • Yann Chevaleyre
  • Ulle Endriss
  • Sylvia Estivie
  • Nicolas Maudet

Abstract

We study a framework for multiagent resource allocation where autonomous software agents negotiate over the allocation of bundles of indivisible resources. Connections to well-known combinatorial optimisation problems, including the winner determination problem in combinatorial auctions, shed light on the computational complexity of the framework. We give particular consideration to scenarios where the preferences of agents are modelled in terms of k-additive utility functions, i.e. scenarios where synergies between different resources are restricted to bundles of at most k items. Copyright The Author(s) 2008

Suggested Citation

  • Yann Chevaleyre & Ulle Endriss & Sylvia Estivie & Nicolas Maudet, 2008. "Multiagent resource allocation in k-additive domains: preference representation and complexity," Annals of Operations Research, Springer, vol. 163(1), pages 49-62, October.
    • Handle: RePEc:spr:annopr:v:163:y:2008:i:1:p:49-62:10.1007/s10479-008-0335-0
    DOI: 10.1007/s10479-008-0335-0
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-008-0335-0
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-008-0335-0?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Keeney,Ralph L. & Raiffa,Howard, 1993. "Decisions with Multiple Objectives," Cambridge Books, Cambridge University Press, number 9780521438834.
    2. Michael H. Rothkopf & Aleksandar Pekev{c} & Ronald M. Harstad, 1998. "Computationally Manageable Combinational Auctions," Management Science, INFORMS, vol. 44(8), pages 1131-1147, August.
    3. K. J. Arrow & A. K. Sen & K. Suzumura (ed.), 2002. "Handbook of Social Choice and Welfare," Handbook of Social Choice and Welfare, Elsevier, edition 1, volume 1, number 1.
    4. Peter Cramton & Yoav Shoham & Richard Steinberg (ed.), 2006. "Combinatorial Auctions," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262033429, December.
    5. repec:dau:papers:123456789/5748 is not listed on IDEAS
    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


    Cited by:

    1. Takanori Maehara & Kazuo Murota, 2015. "Valuated matroid-based algorithm for submodular welfare problem," Annals of Operations Research, Springer, vol. 229(1), pages 565-590, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Nhan-Tam Nguyen & Dorothea Baumeister & Jörg Rothe, 2018. "Strategy-proofness of scoring allocation correspondences for indivisible goods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(1), pages 101-122, January.
    2. repec:dau:papers:123456789/5665 is not listed on IDEAS
    3. Vohra, Rakesh V., 2015. "Combinatorial Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    4. Pallab Sanyal, 2016. "Characteristics and Economic Consequences of Jump Bids in Combinatorial Auctions," Information Systems Research, INFORMS, vol. 27(2), pages 347-364, June.
    5. Ioannis Petrakis & Georg Ziegler & Martin Bichler, 2013. "Ascending Combinatorial Auctions with Allocation Constraints: On Game Theoretical and Computational Properties of Generic Pricing Rules," Information Systems Research, INFORMS, vol. 24(3), pages 768-786, September.
    6. Gediminas Adomavicius & Alok Gupta & Mochen Yang, 2022. "Bidder Support in Multi-item Multi-unit Continuous Combinatorial Auctions: A Unifying Theoretical Framework," Information Systems Research, INFORMS, vol. 33(4), pages 1174-1195, December.
    7. Thomas Kittsteiner & Marion Ott & Richard Steinberg, 2022. "Competing Combinatorial Auctions," Information Systems Research, INFORMS, vol. 33(4), pages 1130-1137, December.
    8. Petr Fiala, 2016. "Supply chain coordination with auctions," Journal of Business Economics, Springer, vol. 86(1), pages 155-171, January.
    9. KARRI PASANEN & MIKKO KURTTILA & JOUNI PYKÄlÄINEN & JYRKI KANGAS & PEKKA LESKINEN, 2005. "Mesta — Non-Industrial Private Forest Owners' Decision-Support Environment For The Evaluation Of Alternative Forest Plans Over The Internet," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 4(04), pages 601-620.
    10. Lombardi, Michele & Yoshihara, Naoki, 2016. "Partially-honest Nash Implementation with Non-connected Honesty Standards," Discussion Paper Series 633, Institute of Economic Research, Hitotsubashi University.
    11. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    12. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    13. Ehlers, Lars & Hafalir, Isa E. & Yenmez, M. Bumin & Yildirim, Muhammed A., 2014. "School choice with controlled choice constraints: Hard bounds versus soft bounds," Journal of Economic Theory, Elsevier, vol. 153(C), pages 648-683.
    14. Leo Katz & Alvaro Sandroni, 2020. "Limits on power and rationality," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(2), pages 507-521, March.
    15. Thibault Gajdos & John Weymark, 2005. "Multidimensional generalized Gini indices," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 26(3), pages 471-496, October.
    16. Jeremy Bulow & Jonathan Levin & Paul Milgrom, 2009. "Winning Play in Spectrum Auctions," NBER Working Papers 14765, National Bureau of Economic Research, Inc.
    17. List, Christian & Polak, Ben, 2010. "Introduction to judgment aggregation," Journal of Economic Theory, Elsevier, vol. 145(2), pages 441-466, March.
    18. Gerd Gigerenzer, 1997. "Bounded Rationality: Models of Fast and Frugal Inference," Swiss Journal of Economics and Statistics (SJES), Swiss Society of Economics and Statistics (SSES), vol. 133(II), pages 201-218, June.
    19. Lamprirni Zarpala & Dimitris Voliotis, 2022. "A core-selecting auction for portfolio's packages," Papers 2206.11516, arXiv.org, revised Feb 2024.
    20. Shuang Liu & Kirsten Maclean & Cathy Robinson, 2019. "A cost-effective framework to prioritise stakeholder participation options," EURO Journal on Decision Processes, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 221-241, November.
    21. Khaled, Oumaima & Minoux, Michel & Mousseau, Vincent & Michel, Stéphane & Ceugniet, Xavier, 2018. "A multi-criteria repair/recovery framework for the tail assignment problem in airlines," Journal of Air Transport Management, Elsevier, vol. 68(C), pages 137-151.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:163:y:2008:i:1:p:49-62:10.1007/s10479-008-0335-0. See general information about how to correct material in RePEc.

    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 CitEc recognized a bibliographic reference but did not link an item in RePEc 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.