CS Paper Radar

Differentiable Combinatorial Auction Design: Optimizing Revenue-Welfare-Fairness Frontiers With Graph Attention Networks

Mai Pham, Vikrant Vaze, Peter Chin

cs.GT ·submitted 2026-10-22 22:35 UTC · v1

Abstract

Designing optimal auctions for allocating public infrastructure-such as airport slots and energy resources-is challenging due to interdependent resources and complex side-constraints. While the Vickrey-Clarke-Groves (VCG) auction guarantees maximum welfare, it cannot maximize revenue or accommodate the multi-objective trade-offs inherent in public infrastructure systems. We propose a differentiable, constraint-aware framework for combinatorial auction design that enables end-to-end learning of fractionally feasible, approximately strategy-proof mechanisms. Our primary contribution is a combinatorial constraint enforcement technique that ensures fractional feasibility by construction, bypassing the need for penalty-based approximations. We introduce CAGraph, a novel graph-based architecture designed to capture dependencies between items and bidders, alongside CANet and CAFormer as deep learning baselines, for combinatorial settings. We also provide a Matching Pursuit-inspired decomposition that maps fractional allocations to feasible discrete allocations and empirically evaluates the resulting discretization gap. In synthetic benchmarks and an airport slot-divestiture case study, respectively, the learned mechanisms achieve up to 73.5% and 180% higher expected revenue than VCG, under small empirical regret. Finally, we visualize the Pareto frontiers for revenue, welfare, and fairness, providing regulators with a decision-support tool to design infrastructure auctions that balance profitability, efficiency and equity.

Closest papers

Nearest neighbours by meaning across the whole index.

EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference

cs.LG math.OC ·2026-10-24 ·Niki Triantafyllou, Maria M. Papathanasiou
top venue similarity 0.63
Abstract · Accepted at NeurIPS 2026

Learning-based approaches to combinatorial optimization often predict solutions directly or use predictions to restrict search, while expressive energy-based models typically rely on approximate inference. We introduce EnerGNN, a framework that learns energy functions over complete binary configurations and minimizes them under explicit hard constraints through mixed integer programming (MIP). EnerGNN combines a graph neural network encoder with an optimization-compatible readout and a nonlinear energy head, enabling exact constrained inference over the learned energy. An optimality-aware contrastive loss trains the energy to reflect solution quality and constraint violations. Across Quadratic Knapsack, Combinatorial Auctions, and a personalized cell therapy supply chain problem, EnerGNN achieves near-optimal solutions with 100% feasibility. On the supply chain problem, it achieves a 0.05% mean primal gap and a 17.4$\times$ speedup over the monolithic MIP. The learned energy also generalizes to larger instances and supports zero-shot constraint injection, adapting to changing constraints without retraining while preserving feasibility.

0.41

CONSTRAINER: Promptable Graph-Structured Optimization via Constraint Conditioning

cs.LG ·2026-11-07 ·Zeeshan Memon, Mingke Tian, Xinyuan Song, Hongwei Jin, Kibaek Kim +1 more
similarity 0.61
Abstract

Neural methods for graph-structured optimization have achieved strong performance within individual problem classes, but are typically trained for fixed formulations, limiting reuse across related problem variants. Recent progress in foundation models has motivated shared neural backbones trained across multiple graph-structured optimization tasks; however, existing approaches primarily share instance-level representations while treating feasibility constraints implicitly. A key source of shared structure across constrained optimization problems is the constraint set itself, which often exhibits substantial overlap across tasks. We propose CONSTRAINER, a constraint-conditioned framework for graph-structured optimization that treats constraints as structured inputs. Constraint specifications are parsed into operator graphs and encoded using a graph neural network to produce invariant constraint embeddings, which condition a shared backbone model for solution prediction. We evaluate our approach on power grid optimization and mixed-integer linear programming problems, where it shows improved solution optimality and enables efficient transfer learning and generalization compared to baseline methods.

0.07

A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions

cs.GT cs.DS ·2026-10-24 ·Qiuyu Chen, Baao Xie
similarity 0.56
Abstract

Position auctions require assigning advertisers to positions and determining their display order. Under cascade behavior, earlier clicks prevent users from reaching later placements, coupling the click probabilities of selected advertisements. Existing methods achieve constant-factor welfare approximation and monotone logarithmic-factor approximation separately, leaving open whether both guarantees can be attained simultaneously. The difficulty is that welfare-preserving rounding need not maintain the monotonicity of individual click-through rates required for truthful bidding. We resolve this problem by developing a polynomial-time randomized mechanism that achieves a factor-6 welfare approximation and truthfulness in expectation for arbitrary public advertiser-position click probabilities. The mechanism optimizes a reach-weighted linear relaxation and converts its solution into feasible ordered allocations through matching decomposition, probability-bounded grouping, and calibrated attenuation. This construction compensates for cascade dependence and ensures that each advertiser's expected click-through rate equals exactly one sixth of its fractional click coordinate. The resulting identity transfers the monotonicity of the fractional allocation to the implemented mechanism, enabling exact incentive-compatible payments while preserving the welfare guarantee. The allocation lottery and payments are computable in polynomial bit time, with exact sampling in expected polynomial time.

0.21

On Sparse Graph Limits for Neural Combinatorial Optimization

cs.LG math.CO ·2026-10-31 ·Thien Le, Melanie Weber
theory similarity 0.56
Abstract

Graph neural networks are often trained on small graphs and deployed on larger ones, raising the question of which graph information must be preserved for combinatorial optimization values to transfer across sizes. We establish size-transfer guarantees for normalized graph optimization values using finite collections of energy features. For affine objectives, including MAX-CUT, coloring defect, and independent-set density, differences in task value are controlled by discrepancies in normalized scalar energy probes on all bounded-degree graphs. For general Lipschitz objectives, such as those with balance penalties, an additional representation error appears; this error vanishes on hyperfinite graph families but can remain bounded away from zero on expanders. Thus, at fixed degree bound, state space, Lipschitz constant, and target accuracy, a finite energy representation independent of graph size suffices universally for affine tasks and asymptotically for general Lipschitz tasks on hyperfinite families. These results yield prediction guarantees under explicit conditions on encoder accuracy, readout stability, and representation coverage, together with statistical generalization bounds. Theoretically, we prove Shapley-Folkman bounds with sharp parameter dependence, including a dimension-free $\ell_2$ regime, and realize the resulting energy features with a fixed-weight message-passing network using random node initialization on bounded-treewidth graphs. Experiments with exact solvers and trained models test the resulting transfer guarantees.

0.25

Recursive Pricing and Incumbent Subtree Column Generation for Solving Optimal Classification Trees

cs.LG math.OC ·2026-11-08 ·Tengmu Hu, Chen Chen, Theodore T. Allen
benchmark similarity 0.56
Abstract · 48 pages, 6 figures, 10 tables

Solving optimal classification tree (OCT) problems is computationally challenging because branching, routing, and leaf-assignment decisions must be optimized jointly. We develop an incumbent subtree column generation algorithm (ISCG-OCT) that exploits the recursive structure of classification trees. We first introduce a mixed set-packing and set-partitioning formulation (MSSF). We then construct a restricted master problem whose columns represent feasible subtree patterns. Unlike conventional dual-based column generation, our incumbent-centered pricing evaluates objective improvements relative to the current solution. We establish a recursive decomposition in which fixing a branching decision separates the remaining pricing problem into independent subtree subproblems, enabling exact dynamic programming. We also develop threshold-based variants that trade optimality guarantees for computational efficiency. Computational experiments on 27 benchmark datasets demonstrate competitive training and testing accuracy and substantial reductions in solution time on many instances. When initialized with a CART solution, ISCG-OCT can certify global optimality faster than warm-started mixed-integer programming solvers on selected instances. These results demonstrate how recursive pricing and structured subtree optimization can improve the computational efficiency of exact classification tree methods.

0.28

Constrained Graph Diffusion for Mixed Integer Optimization

cs.LG ·2026-08-13 ·Vincenzo Di Vito, Yusuf Guven, Babak Badnava, Deepjyoti Deka, Kaarthik Sundar +1 more
similarity 0.56
Abstract

This paper proposes a novel learning-based approach to approximately solve instances of mixed-integer optimization problems. These problems are computationally challenging, as they require jointly determining discrete and continuous decisions while satisfying complex combinatorial constraints. problem-agnostic and can accommodate a broad class of mixed-integer optimization problems through suitable projection operators. We introduce Constrained Graph Diffusion (CGD), a learning-based framework that approximately solves recurring instances of such problems by learning a conditional distribution over their discrete decisions. CGD uses a graph-based diffusion model and incorporates constraint information directly into the reverse diffusion process, steering intermediate predictions toward the feasible region throughout generation. By operating on continuous relaxations of the discrete variables, CGD defines a differentiable constrained generation pathway up to terminal discrete recovery. Once the discrete decision is recovered and fixed, a numerical optimizer solves the remaining continuous problem, avoiding online combinatorial search over the binary variables while retaining numerical optimization for continuous completion. We evaluate CGD on AC-OPF with branch switching and discrete portfolio optimization, demonstrating substantial improvements in feasibility and solution quality over learning-based baselines while achieving speedups of up to $543\times$ over state-of-the-art MIP solvers on large instances.

0.04

Dynamic Auction Mechanisms in a Closed-Credit Economy: Sequential Slot Reallocation in Air Traffic Management

cs.GT cs.MA ·2026-10-15 ·Jihun Kim, Pan-Yang Su, Maria G. Mendoza, Victoria Marie Tuck, Chinmay Maheshwari +1 more
hot direction similarity 0.55
Abstract · 12 pages, 4 figures

Indivisible resources allocated in advance may need to be reallocated when capacity reductions make existing assignments infeasible, yet monetary compensation is often impractical or undesirable. We develop a sequential resource reallocation scheme using reusable artificial credits, where agents hold pre-existing resource rights and have heterogeneous marginal valuations over time blocks. Capacity reductions produce fractional endowments, which our closed-credit scheme resolves into indivisible final allocations. We model agents' intertemporal preferences through a predicted-value-to-go function and characterize conditions ensuring that their optimal demand is non-increasing in price. We propose an ascending-auction mechanism that partitions agents into subgroups and uses the minimum subgroup market-clearing price as a common transaction price. We show that the mechanism preserves non-myopic individual rationality and weak nontrader neutrality. Moreover, we establish Pareto efficiency under optimal-demand clearing in the unified market and bound the expected gain from misreporting by the probability that an agent changes the common price. Simulations of airport slot reallocation demonstrate reductions in total modeled delay and cancellation costs relative to a ground-delay baseline.

0.38

Settling PROPm and PROPavg in Graphical Resource Allocation

cs.GT ·2026-10-07 ·Bo Li, Ankang Sun, Ruijie Wang
publishedtheory similarity 0.55
Abstract · Full version of a paper to appear in WINE 2026. V2 includes an extended related work section

We study proportional fairness in graphical resource allocation, where agents are vertices, indivisible items are edges, and each item must be allocated to one of its two endpoints. It has been proved that PROP1 orientations always exist and PROPx orientations may not, but it has remained open whether the intermediate relaxations PROPm and PROPavg (both can be satisfied without graphical constraints) can always be satisfied. In this paper, we resolve this gap. We prove that PROPm orientations always exist for goods on multigraphs and can be computed efficiently. The guarantee extends to chores and a mixture of goods and chores. In sharp contrast, we show that PROPavg orientations need not exist, even for simple graphs with binary valuations, and that deciding their existence is NP-complete. We further quantify the efficiency loss of PROPm: for goods, the price of PROPm is exactly $2$, which is one of the few settings where a constant bound on the price of fairness can be obtained. We complement these results with hardness results for welfare optimization under PROPm and for the existence of orientations that are simultaneously PROPm and Pareto optimal.

0.25