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

arXiv: https://arxiv.org/abs/2009.13697 · HTML: https://mlsanity.com/paper/2009.13697/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2020.

## Built on by (most cited first, 6 of 6)

- [Device Sampling for Heterogeneous Federated Learning: Theory, Algorithms, and Implementation](https://mlsanity.com/paper/2101.00787/) (2021)
- [Graph Neural Networks Meet Wireless Communications: Motivation, Applications, and Future Directions](https://mlsanity.com/paper/2212.04047/) (2022)
- [Neural Airport Ground Handling](https://mlsanity.com/paper/2303.02442/) (2023)
- [Privacy-Preserving Decentralized Inference with Graph Neural Networks in Wireless Networks](https://mlsanity.com/paper/2208.06963/) (2022)
- [Traffic Engineering in Large-scale Networks with Generalizable Graph Neural Networks](https://mlsanity.com/paper/2503.24203/) (2025)
- [Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks](https://mlsanity.com/paper/2602.14772/) (2026)

## Abstract (arXiv)

The combinatorial auction (CA) is an efficient mechanism for resource allocation in different fields, including cloud computing. It can obtain high economic efficiency and user flexibility by allowing bidders to submit bids for combinations of different items instead of only for individual items. However, the problem of allocating items among the bidders to maximize the auctioneers" revenue, i.e., the winner determination problem (WDP), is NP-complete to solve and inapproximable. Existing works for WDPs are generally based on mathematical optimization techniques and most of them focus on the single-unit WDP, where each item only has one unit. On the contrary, few works consider the multi-unit WDP in which 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 and decrease the number of needed labeled instances, 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.