A Fast Graph Neural Network-Based Method for Winner Determination in Multi-Unit Combinatorial Auctions

Mengyuan Lee, Seyyedali Hosseinalipour, Christopher Greg Brinton, Guanding Yu, Huaiyu Dai

Research output: Contribution to journalArticlepeer-review

Abstract

The combinatorial auction (CA) is an efficient mechanism for resource allocation in different fields, including cloud computing. However, the winner determination problem (WDP) is NP-complete to solve and inapproximable. Existing works for WDPs are generally based on mathematical optimization techniques and few works consider the multi-unit WDP where each item may have multiple units. Given that the multi-unit WDP is more complicated but prevalent in cloud computing, we propose leveraging machine learning (ML) techniques to develop a novel low-complexity algorithm for solving this problem with negligible revenue loss. Specifically, we model the multi-unit WDP as an augmented bipartite bid-item graph and use a graph neural network (GNN) with half-convolution operations to learn the probability of each bid belonging to the optimal allocation. To improve the sample generation efficiency, we propose two different sample generation processes. We also develop two novel graph-based post-processing algorithms to transform the outputs of the GNN into feasible solutions. Through simulations on both synthetic instances and a specific virtual machine (VM) allocation problem in a cloud computing platform, we validate that our proposed method can approach optimal performance with low complexity and has good generalization ability in terms of problem size and user-type distribution.

Original languageEnglish (US)
JournalIEEE Transactions on Cloud Computing
DOIs
StateAccepted/In press - 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications

Keywords

  • Machine learning
  • cloud computing
  • graph neural network
  • multi-unit combinatorial auction
  • resource allocation
  • winner determination problem

Fingerprint Dive into the research topics of 'A Fast Graph Neural Network-Based Method for Winner Determination in Multi-Unit Combinatorial Auctions'. Together they form a unique fingerprint.

Cite this