![[2602.14772] Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.14772] Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks
Summary
This paper explores the use of graph neural networks (GNNs) for predicting algorithm performance in combinatorial auctions, focusing on instance-dependent algorithm selection to improve efficiency in solving NP-hard problems.
Why It Matters
Understanding how to effectively select algorithms based on instance hardness can significantly enhance the performance of combinatorial auction solutions. This research addresses a critical gap in machine learning applications for optimization, potentially leading to more efficient resource allocation in various fields.
Key Takeaways
- The study introduces a method for predicting when greedy algorithms fail in combinatorial auctions.
- A 20-dimensional feature vector is used to classify instance hardness with high accuracy.
- Hybrid approaches combining GNNs and traditional solvers can reduce optimality gaps significantly.
- The research highlights the limitations of GNNs compared to classical methods like Gurobi.
- Instance-dependent algorithm selection is proposed as a more viable approach than replacing existing solvers.
Computer Science > Machine Learning arXiv:2602.14772 (cs) [Submitted on 16 Feb 2026] Title:Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks Authors:Sungwoo Kang View a PDF of the paper titled Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks, by Sungwoo Kang View PDF HTML (experimental) Abstract:The Winner Determination Problem (WDP) in combinatorial auctions is NP-hard, and no existing method reliably predicts which instances will defeat fast greedy heuristics. The ML-for-combinatorial-optimization community has focused on learning to \emph{replace} solvers, yet recent evidence shows that graph neural networks (GNNs) rarely outperform well-tuned classical methods on standard benchmarks. We pursue a different objective: learning to predict \emph{when} a given instance is hard for greedy allocation, enabling instance-dependent algorithm selection. We design a 20-dimensional structural feature vector and train a lightweight MLP hardness classifier that predicts the greedy optimality gap with mean absolute error 0.033, Pearson correlation 0.937, and binary classification accuracy 94.7\% across three random seeds. For instances identified as hard -- those exhibiting ``whale-fish'' trap structure where greedy provably fails -- we deploy a heterogeneous GNN specialist that achieves ${\approx}0\%$ optimality gap on all six adversarial co...