Algorithm Selection for Combinatorial Auctions

Description

In this research project at SCC, we are investigating a machine learning approach to select the best algorithm for solving an instance of a combinatorial auction [0], based on features of the problem instance. This approach is called algorithm selection [1] and is usually applied to NP-hard problems (like combinatorial auctions), where computing an optimal solution is intractable, and approximate algorithms perform significantly different across the input space.

This work is motivated by resource allocation in cloud computing, where a flexible and market-driven allocation modeled as a combinatorial auction can improve both provider revenue and client utility.

Your tasks would be to investigate and implement different auction algorithms, on which you can later apply various classification algorithms for feature-based algorithm selection.

You will have to work with existing C++ code for auction input generation and testing, as well as the scikit-learn [3] python toolset for machine learning.

Tasks

• research existing algorithms for allocation in combinatorial auctions
• implement different algorithms
• evaluate algorithms' performance under different scenarios
• evaluate classification approach on the implemented algorithm portfolio

Requirements

• good knowledge of C++ and Python
• some theoretical computer science background or machine learning knowledge would be a plus

References

[0] S. De Vries and R. V. Vohra. Combinatorial auctions: A survey. INFORMS Journal on computing, 2003. doi:10.1287/ijoc.15.3.284.16077.

[1] Kotthoff, Lars. "Algorithm selection for combinatorial search problems: A survey." AI Magazine 35.3 (2014): 48-60. [1]

[2] Leyton-Brown, Kevin, Eugene Nudelman, and Yoav Shoham. "Empirical hardness models: Methodology and a case study on combinatorial auctions." Journal of the ACM (JACM) 56.4 (2009): 22. doi:10.1145/1538902.1538906

[3] scikit-learn

Contact

Diana.Gudu@kit.edu