Empirical Hardness for Mixed Auctions | SpringerLink
Skip to main content
Springer Nature Link
Log in

Empirical Hardness for Mixed Auctions

  • Conference paper
Current Topics in Artificial Intelligence (CAEPIA 2009)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 5988))

Included in the following conference series:

Abstract

Mixed Multi-Unit Combinatorial Auctions (MMUCAs) offer a high potential to be employed for the automated assembly of supply chains of agents. However, little is known about the factors making a winner determination problem (WDP) instance hard to solve. In this paper we empirically study the hardness of MMUCAs: (i) to build a model that predicts the time required to solve a WDP instance (because time can be an important constraint during an auction-based negotiation); and (ii) to assess the factors that make a WDP instance hard to solve.

Funded by projects IEA (TIN2006-15662-C02-01), AT (CSD2007-0022), EVE (TIN2009-14702-C02-01, TIN2009-14702-C02-02).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Cerquides, J., Endriss, U., Giovannucci, A., Rodríguez-Aguilar, J.A.: Bidding languages and winner determination for mixed multi-unit combinatorial auctions. In: IJCAI, pp. 1221–1226 (2007)

    Google Scholar 

  2. Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2006)

    MATH  Google Scholar 

  3. Valeria Fionda, G.G.: Charting the tractability frontier of mixed multi-unit combinatorial auctions. In: Proceedings of IJCAI 2009, pp. 134–139 (2009)

    Google Scholar 

  4. Leyton-Brown, K., Nudelman, E., Shoham, Y.: Empirical hardness models for combinatorial auctions. In: Cramton, et al. (eds.) [2], ch. 19, pp. 479–504

    Google Scholar 

  5. Giovannucci, A., Vinyals, M., Rodríguez-Aguilar, J.A., Cerquides, J.: Computationally-efficient winner determination for mixed multi-unit combinatorial auctions. In: Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multi-agent Systems, pp. 1071–1078 (2008)

    Google Scholar 

  6. Giovannucci, A., Cerquides, J., Rodriguez-Aguilar, J.A.: Proving the correctness of the CCIP solver for MMUCA, Tech. rep., IIIA-CSIC (2007)

    Google Scholar 

  7. Vinyals, M., Giovannucci, A., Cerquides, J., Meseguer, P., Rodriguez-Aguilar, J.A.: A test suite for the evaluation of mixed multi-unit combinatorial auctions. Journal of Algorithms 63, 130–150 (2008)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IIIA, Artificial Intelligence Research Institute CSIC, Spanish National Research Council, Spain

    Pablo Almajano & Juan A. Rodriguez-Aguilar

  2. UB, WAI, Dep. Matemàtica Aplicada i Anàlisi, Universitat de Barcelona, Spain

    Jesús Cerquides

Authors
  1. Pablo Almajano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jesús Cerquides
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Juan A. Rodriguez-Aguilar
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. IIIA - CSIC, Campus UAB s/n, 08193, Bellaterra, Spain

    Pedro Meseguer

  2. Dpto. Lenguajes y Ciencias de la Computación, Universidad de Málaga, Campus de Teatinos, 29071, Málaga, Spain

    Lawrence Mandow

  3. Dpto. Lenguajes y Sistemas Informáticos, ETS Ingeniería Informática, University of Seville, Av. Reina Mercedes S/N, 41012, Sevilla, Spain

    Rafael M. Gasca

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Almajano, P., Cerquides, J., Rodriguez-Aguilar, J.A. (2010). Empirical Hardness for Mixed Auctions. In: Meseguer, P., Mandow, L., Gasca, R.M. (eds) Current Topics in Artificial Intelligence. CAEPIA 2009. Lecture Notes in Computer Science(), vol 5988. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14264-2_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-14264-2_17

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-14263-5

  • Online ISBN: 978-3-642-14264-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation