Extending Myerson's Optimal Auctions to Correlated Bidders via Neural Network Interpolation

Mingyu Guo; Jiayuan Liu; Vincent Conitzer

cs.GTOct 16, 2026

Extending Myerson's Optimal Auctions to Correlated Bidders via Neural Network Interpolation

Authors: Mingyu Guo, Jiayuan Liu, Vincent Conitzer

Organizations: Adelaide University, Adelaide, Australia · Carnegie Mellon University, Pittsburgh, USA

Abstract

We aim to design revenue-maximizing single-item auctions that are deterministic, strategy-proof, and ex post individually rational --- the quintessential fundamental model for optimal mechanism design. While Myerson's seminal work solved this model for independent bidders, straightforward extensions to correlated settings often result in non-monotonic, and therefore non-strategy-proof allocations. Critically, optimal allocation design for correlated bidders is NP-hard to approximate, rendering theoretical optimality guarantees in this domain computationally intractable. We establish a new standard of empirical rigor for this theoretically hard model by proposing an empirical pipeline. We synthesize neural interpolation of Myerson's greedy allocation based on marginal profits (the correlated variant of virtual valuation), formal neural verification to enforce exact strategy-proofness, and a constructive repair procedure. Empirically, our method is highly effective, consistently achieves near-optimal revenue across a wide range of distributions, including synthetic, adversarial, and real-world (consumer, financial, and industrial) datasets. Compared to existing manual and neural baselines, our approach shows substantial improvement, often reducing the revenue gap by an order of magnitude. Our study is also the first to introduce (unattainable) greedy revenue as a rigorous upper bound for empirical benchmarking, providing a definitive quantitative performance measure where true optima remain theoretically elusive. We demonstrate the generality of our approach by extending it to multi-unit auctions with unit demand and integrating our verification techniques into RegretNet to achieve exact strategy-proofness.

Figures & tables

Panel of Figure 1 — Figure 1: Illustration of a 2-bidder setting where axes represent two bids in $[0,1]$ . Blue and red regions denote wins for bidder 1 and 2, respectively. (a) monotone allocation: A strategy-proof allocation where a winner necessarily remains the winner after a unilateral bid increase. (b) greedy allocation (based on marginal profits): Non-monotone allocation that gives the revenue upper bound — red and blue points enclosed in opposing regions represent monotonicity violations that preclude strategy-proofness. (c) (monotone) interpolation: A tiny neural network mimics the macro-trends of (b) while “glossing over” fine-grained violations due to its limited expressive capacity. This interpolation is formally verified to be monotone, thereby ensuring exact strategy-proofness. (d) revenue fix (leading to final allocation): The result after applying the revenue fix in Section 3 , which determines the exact shape of the “no-sale” (white) region to maximize expected revenue without altering the strategy-proofness established in the previous stage.

\begin{bmatrix}11&24&7&20&3\\ 4&12&25&8&16\\ 17&5&13&21&9\\ 10&18&1&14&22\\ 23&6&19&2&15\end{bmatrix}\\

Table 2

Distrib.	Greedy	AMD	Myer.	2nd	RNet	MP	VV	IVV
$G5_{0}$	$0.4353$	$0.4368$	$0.4191$	$0.4197$	$0.4307$	0.4368	$0.4355$	$0.4329$
$G5_{1}$	$0.4047$	$0.4041$	$0.3939$	$0.3929$	$0.4021$	0.4037	$0.4032$	$0.4032$
$G5_{2}$	$0.3979$	$0.3967$	$0.3771$	$0.3823$	$0.3869$	0.3959	$0.3946$	$0.3955$
$G5_{3}$	$0.4629$	$0.4625$	$0.4533$	$0.4546$	$0.4522$	$\textbf{0.4628}^{*}$	$0.4612$	$0.4616$
$G5_{4}$	$0.4681$	$0.4665$	$0.4476$	$0.4472$	$0.4639$	$\textbf{0.4674}^{*}$	$0.4673$	$0.4671$
$G5_{5}$	$0.4204$	$0.4187$	$0.4075$	$0.4057$	$0.4062$	0.4151	$0.4148$	$0.4150$

Table 1:

2

bidders:

\textsc{Gap}(\textsc{MP})=0.26\%

\textsc{Gap}(\textsc{RNet})=2.7\%

\textsc{Gap}(\textsc{2nd})=4.2\%

\textsc{Gap}(\textsc{Myer})=4.3\%

Distrib.	Greedy	M/2	RNet	MP	Greedy	M/2	RNet	MP
	$n=3$				$n=5$
$G5_{0}$	$0.5512$	$0.5346$	$0.5346$	0.5517	$0.6862$	$0.6700$	$0.6670$	0.6799
$G5_{1}$	$0.5647$	$0.5475$	$0.5509$	0.5651	$0.6901$	$0.6738$	$0.6713$	0.6846
$G5_{2}$	$0.5316$	$0.5137$	$0.5153$	0.5302	$0.6838$	$0.6709$	$0.6681$	0.6783
$G5_{3}$	$0.5476$	$0.5283$	$0.5290$	0.5450	$0.6894$	$0.6724$	$0.6684$	0.6838
$G5_{4}$	$0.5485$	$0.5306$	$0.5310$	0.5471	$0.6853$	$0.6692$	$0.6664$	0.6787

Table 2:

3

and

5

bidders: M/2 represents the better between Myerson and 2nd

n=3

\textsc{Gap}(\textsc{MP})=0.36\%

\textsc{Gap}(\textsc{RNet})=3.6\%

\textsc{Gap}(\textsc{2nd})=3.9\%

\textsc{Gap}(\textsc{Myer})=3.8\%

n=5

\textsc{Gap}(\textsc{MP})=0.87\%

\textsc{Gap}(\textsc{RNet})=2.8\%

\textsc{Gap}(\textsc{2nd})=2.4\%

\textsc{Gap}(\textsc{Myer})=2.4\%

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: Plots for grid distribution $[0.2,3.58,0.32,0.05,0.85]$ . The grid distribution family is formally defined in Section 5 . The example grid distribution here describes a random variable with range $[0,1]$ , which is divided into $5$ equally-sized sub-intervals. In $[0,\frac{1}{5}]$ , the probability density value is uniformly $0.2$ . In $[\frac{1}{5},\frac{2}{5}]$ , the probability density value is uniformly $3.58$ .

Distrib.	Greedy	AMD	Myer.	2nd	RNet	MP
$EA(G5_{0})$	$0.3935$	$0.3918$	$0.3857$	$0.3869$	$0.3875$	0.3905
	$\pm 0.001$		$\pm 0.0007$	$\pm 0.0008$	$\pm 0.0008$	$\pm 0.0008$
$EA(G5_{1})$	$0.4143$	$0.4111$	$0.4030$	$0.4010$	$0.4028$	0.4106
	$\pm 0.001$		$\pm 0.0008$	$\pm 0.0008$	$\pm 0.0008$	$\pm 0.0008$
$EA(G5_{2})$	$0.4311$	$0.4279$	$0.4137$	$0.4116$	$0.3836$	0.4220
	$\pm 0.001$		$\pm 0.0007$	$\pm 0.0007$	$\pm 0.001$	$\pm 0.0008$

Appendix

Table 3:

2

bidders, evolutionary computation generated adversarial distributions

Distrib.	Greedy	AMD	Myer.	2nd	RNet	MP
worst10	$0.4401$	$0.4379$	$0.3733$	$0.3919$	$0.4130$	$\textbf{0.4441}^{*}$
	$\pm 0.001$		$\pm 0.0009$	$\pm 0.0006$	$\pm 0.0007$	$\pm 0.003$
worst100	$0.4678$	$0.4565$	$0.3885$	$0.3805$	$0.4126$	$\textbf{0.4632}^{*}$
	$\pm 0.001$		$\pm 0.0007$	$\pm 0.0004$	$\pm 0.0006$	$\pm 0.003$

Appendix

Table 4:

2

bidders, mixed-integer-programming generated adversarial distributions

Distrib.	Blue	Red	Green	Black
	$M\rightarrow M$	$\overline{M}\rightarrow\overline{M}$	$\overline{M}\rightarrow M$	$M\rightarrow\overline{M}$
$G5_{6}$ ( $n=5$ )	$0.6841\pm 0.0006$	$0.6551\pm 0.002$	$0.6847\pm 0.002$	$0.6844\pm 0.002$
worst10 ( $n=2$ )	$0.4347\pm 0.0009$	$0.4441\pm 0.003$	$0.4410\pm 0.003$	$0.4370\pm 0.003$
worst100 ( $n=2$ )	$0.4517\pm 0.0008$	$0.4632\pm 0.003$	$0.4516\pm 0.002$	$0.4544\pm 0.0008$

Appendix

Table 5: Summary of best revenue per category, where

100

trials are divided into

4

categories based on the monotonicity status at the end of stage-one and two:

M

=Monotonicity;

\overline{M}

=non-monotonicity;

M\rightarrow\overline{M}

means the stage-one result is monotone and the stage-two result is not monotone

Figure 3: While green and black reached slightly higher highs, the gap between blue and green/black is statistically insignificant considering the standard errors. In conclusion, counterexample-guided training and monotonicity fix are not needed for this distribution.

Figure 4: Red and green reached higher, so counterexample-guided training and monotonicity fix do help. We do need the whole suite of techniques to reach near-optimal revenue.

Figure 5: Red reached higher, so counterexample-guided training and monotonicity fix do help. We do need the whole suite of techniques to reach near-optimal revenue.

Distrib.	Greedy	MyerNet	MinMax	MyerNet+	MinMax+	Myer.	MP
$G5_{0}$	$0.6862$	$0.5754$	$0.5135$	$0.6630$	$0.6625$	$0.6695$	0.6799
	$\pm 0.0008$	$\pm 0.0005$	$\pm 0.0008$	$\pm 0.0006$	$\pm 0.0006$	$\pm 0.0006$	$\pm 0.0006$
$G5_{1}$	$0.6901$	$0.5746$	$0.4503$	$0.6681$	$0.6670$	$0.6737$	0.6846
	$\pm 0.0008$	$\pm 0.0005$	$\pm 0.0007$	$\pm 0.0006$	$\pm 0.0006$	$\pm 0.0006$	$\pm 0.0006$
$G5_{2}$	$0.6838$	$0.5216$	$0.5688$	$0.6642$	$0.6635$	$0.6709$	0.6783
	$\pm 0.0008$	$\pm 0.0006$	$\pm 0.0006$	$\pm 0.0006$	$\pm 0.0006$	$\pm 0.0006$	$\pm 0.0006$

Appendix

Table 6: Additional experiments for

5

bidders

\textsc{Gap}(\textsc{MP})=0.87\%

\textsc{Gap}(\textsc{Myer.})=2.4\%

(note:

\textsc{Gap}(\textsc{2nd})

is also

2.4\%

)

\textsc{Gap}(\textsc{MyerNet+})=3.3\%

\textsc{Gap}(\textsc{MyerNet})=19\%

\textsc{Gap}(\textsc{MinMax+})=3.4\%

\textsc{Gap}(\textsc{MinMax})=18\%

Distrib.	Greedy	m+1	MP	Greedy	m+1	MP	Greedy	m+1	MP
	$n=3$			$n=4$			$n=5$
$G5_{0}$	$0.7629$	$0.7251$	0.7624	$0.9387$	$0.8923$	0.9360	$1.0856$	$1.0428$	1.0757
	$\pm 0.002$	$\pm 0.001$	$\pm 0.001$	$\pm 0.002$	$\pm 0.001$	$\pm 0.001$	$\pm 0.002$	$\pm 0.001$	$\pm 0.001$
$G5_{1}$	$0.7896$	$0.7413$	0.7901	$0.9646$	$0.9172$	0.9608	$1.0973$	$1.0477$	1.0844
	$\pm 0.002$	$\pm 0.001$	$\pm 0.001$	$\pm 0.002$	$\pm 0.001$	$\pm 0.001$	$\pm 0.002$	$\pm 0.001$	$\pm 0.001$
$G5_{2}$	$0.7311$	$0.6900$	0.7311	$0.9380$	$0.8932$	0.9319	$1.0868$	$1.0394$	1.0755

Appendix

Table 7: Multi-unit auctions with unit demand with

2

items (i.e.,

m=2

) m+1 refers to the (m+1)-th price auction with the optimal reserve price,

\textsc{Gap}(\textsc{MP})=0.67\%

\textsc{Gap}(\textsc{m+1})=5.1\%

Distrib.	Greedy	2nd	MP
$f(x,y)=2x+y$	$0.5095\pm 0.001$	$0.5079\pm 0.0008$	$\textbf{0.5094}\pm 0.0008$
$f(x,y)=2x-y+1$	$0.4518\pm 0.001$	$0.4469\pm 0.0008$	$\textbf{0.4517}\pm 0.0008$
$f(x,y)=sin(x)+cos(y)+2$	$0.4216\pm 0.001$	$0.4211\pm 0.0008$	$\textbf{0.4215}\pm 0.0008$

Appendix

Table 8: Experiments on three continuous distributions

\textsc{Gap}(\textsc{MP})=0.02\%

\textsc{Gap}(\textsc{2nd})=0.5\%

Distrib.	Greedy	2nd	Myer.	MP
Consumer (eBay)	$0.5445\pm 0.0006$	$0.4211\pm 0.0001$	$0.3568\pm 0.0002$	$\textbf{0.5373}\pm 0.0006$
Financial (Ethereum)	$0.3040\pm 0.0007$	$0.2805\pm 0.0007$	$0.2598\pm 0.0008$	$\textbf{0.3022}\pm 0.0007$
Electric Market (PJM)	$0.2508\pm 0.0005$	$0.1578\pm 0.0001$	$0.1575\pm 0.0001$	$\textbf{0.2375}\pm 0.0004$

Appendix

Table 9: Experiments on Distributions Based on Real-World Datasets:

\textsc{Gap}(\textsc{MP})=2.0\%

\textsc{Gap}(\textsc{2nd})=22\%

\textsc{Gap}(\textsc{Myer.})=30\%

Distrib.	Greedy	AMD	Myer.	2nd	RNet	MP	VV	IVV
$G5_{0}$	$0.4353$	$0.4368$	$0.4191$	$0.4197$	$0.4307$	0.4368	$0.4355$	$0.4329$
	$\pm 0.001$		$\pm 0.0008$	$\pm 0.0009$	$\pm 0.0009$	$\pm 0.0009$	$\pm 0.0009$	$\pm 0.0009$
$G5_{1}$	$0.4047$	$0.4041$	$0.3939$	$0.3929$	$0.4021$	0.4037	$0.4032$	$0.4032$
	$\pm 0.001$		$\pm 0.0007$	$\pm 0.0006$	$\pm 0.0007$	$\pm 0.0007$	$\pm 0.0007$	$\pm 0.0007$
$G5_{2}$	$0.3979$	$0.3967$	$0.3771$	$0.3823$	$0.3869$	0.3959	$0.3946$	$0.3955$
	$\pm 0.001$		$\pm 0.0009$	$\pm 0.001$	$\pm 0.0009$	$\pm 0.001$	$\pm 0.001$	$\pm 0.001$

Appendix

Table 10:

2

bidders (with standard errors)

\textsc{Gap}(\textsc{MP})=0.26\%

\textsc{Gap}(\textsc{RNet})=2.7\%

\textsc{Gap}(\textsc{2nd})=4.2\%

\textsc{Gap}(\textsc{Myer})=4.3\%

Distrib.	Greedy	Myer.	2nd	RNet	MP
$G5_{0}$	$0.5512$ $\pm 0.001$	$0.5346$ $\pm 0.0007$	$0.5338$ $\pm 0.0008$	$0.5346$ $\pm 0.0007$	0.5517 $\pm 0.0007$
$G5_{1}$	$0.5647$ $\pm 0.0009$	$0.5467$ $\pm 0.0007$	$0.5475$ $\pm 0.0007$	$0.5509$ $\pm 0.0007$	0.5651 $\pm 0.0007$
$G5_{2}$	$0.5316$ $\pm 0.001$	$0.5137$ $\pm 0.0007$	$0.5118$ $\pm 0.0008$	$0.5153$ $\pm 0.0008$	0.5302 $\pm 0.0008$
$G5_{3}$	$0.5476$ $\pm 0.001$	$0.5283$ $\pm 0.0007$	$0.5282$ $\pm 0.0007$	$0.5290$ $\pm 0.0007$	0.5450 $\pm 0.0007$
$G5_{4}$	$0.5485$ $\pm 0.0009$	$0.5297$ $\pm 0.0007$	$0.5306$ $\pm 0.0007$	$0.5310$ $\pm 0.0007$	0.5471 $\pm 0.0007$
$G5_{5}$	$0.5477$ $\pm 0.001$	$0.5237$ $\pm 0.0007$	$0.5231$ $\pm 0.0007$	$0.5255$ $\pm 0.0007$	0.5443 $\pm 0.0008$

Appendix

Table 11:

3

bidders (with standard errors)

\textsc{Gap}(\textsc{MP})=0.36\%

\textsc{Gap}(\textsc{RNet})=3.6\%

\textsc{Gap}(\textsc{2nd})=3.9\%

\textsc{Gap}(\textsc{Myer})=3.8\%

Distrib.	Greedy	Myer.	2nd	RNet	MP
$G5_{0}$	$0.6270$ $\pm 0.0009$	$0.6086$ $\pm 0.0007$	$0.6082$ $\pm 0.0007$	$0.6072$ $\pm 0.0006$	0.6242 $\pm 0.0007$
$G5_{1}$	$0.6417$ $\pm 0.0009$	$0.6215$ $\pm 0.0006$	$0.6205$ $\pm 0.0007$	$0.6192$ $\pm 0.0006$	0.6379 $\pm 0.0007$
$G5_{2}$	$0.6250$ $\pm 0.0009$	$0.6096$ $\pm 0.0007$	$0.6101$ $\pm 0.0007$	$0.6072$ $\pm 0.0006$	0.6205 $\pm 0.0007$
$G5_{3}$	$0.6266$ $\pm 0.0009$	$0.6054$ $\pm 0.0006$	$0.6055$ $\pm 0.0006$	$0.6034$ $\pm 0.0006$	0.6220 $\pm 0.0007$
$G5_{4}$	$0.6296$ $\pm 0.0009$	$0.6084$ $\pm 0.0006$	$0.6077$ $\pm 0.0007$	$0.6076$ $\pm 0.0006$	0.6233 $\pm 0.0007$
$G5_{5}$	$0.6213$ $\pm 0.0009$	$0.6029$ $\pm 0.0007$	$0.6028$ $\pm 0.0007$	$0.6020$ $\pm 0.0006$	0.6158 $\pm 0.0007$

Appendix

Table 12:

4

bidders (with standard errors)

\textsc{Gap}(\textsc{MP})=0.78\%

\textsc{Gap}(\textsc{RNet})=3.5\%

\textsc{Gap}(\textsc{2nd})=3.2\%

\textsc{Gap}(\textsc{Myer})=3.2\%

Distrib.	Greedy	Myer.	2nd	RNet	MP
$G5_{0}$	$0.6862$ $\pm 0.0008$	$0.6695$ $\pm 0.0006$	$0.6700$ $\pm 0.0006$	$0.6670$ $\pm 0.0006$	0.6799 $\pm 0.0006$
$G5_{1}$	$0.6901$ $\pm 0.0008$	$0.6737$ $\pm 0.0006$	$0.6738$ $\pm 0.0006$	$0.6713$ $\pm 0.0005$	0.6846 $\pm 0.0006$
$G5_{2}$	$0.6838$ $\pm 0.0008$	$0.6709$ $\pm 0.0006$	$0.6691$ $\pm 0.0006$	$0.6681$ $\pm 0.0005$	0.6783 $\pm 0.0006$
$G5_{3}$	$0.6894$ $\pm 0.0008$	$0.6724$ $\pm 0.0006$	$0.6721$ $\pm 0.0006$	$0.6684$ $\pm 0.0005$	0.6838 $\pm 0.0006$
$G5_{4}$	$0.6853$ $\pm 0.0008$	$0.6692$ $\pm 0.0006$	$0.6682$ $\pm 0.0006$	$0.6664$ $\pm 0.0006$	0.6787 $\pm 0.0006$
$G5_{5}$	$0.6850$ $\pm 0.0008$	$0.6717$ $\pm 0.0006$	$0.6720$ $\pm 0.0006$	$0.6685$ $\pm 0.0006$	0.6809 $\pm 0.0006$

Appendix

Table 13:

5

bidders (with standard errors)

\textsc{Gap}(\textsc{MP})=0.87\%

\textsc{Gap}(\textsc{RNet})=2.8\%

\textsc{Gap}(\textsc{2nd})=2.4\%

\textsc{Gap}(\textsc{Myer})=2.4\%

Mechanism Design

Mechanism design studies rules for allocating resources and shaping incentives when participants hold private information or act strategically.

See all 142 papers

Duality for Optimal Multi-Item, Multi-Bidder Auction Design: Revenue Certificates through Deep Learning
Jun 8, 2026Yanchen Jiang, David C. Parkes, Tonghan WangPrimal-Dual Optimization Game Theory
Harvard University, USA · College of AI, Tsinghua University, China
Strategyproof Deep Reinforcement Learning for Online Resource Allocation
Oct 27, 2026Fariba Dehghan, Sebastian Stein, Vahid Yazdanpanah +1Online Resource Allocation Mechanism Design
University of Southampton
A3M: Adaptive, Adversarial and Multi-Objective Learning for Strategic Bidding in Repeated Auctions
Jun 27, 2026Junhan Li, Yuxin Zhang, Haoran Wang +1Multi-Objective Reinforcement Learning Game Theory
Department of Computer Science Nanjing University

Jun 8, 2026J/K move · Enter open · S save

Duality for Optimal Multi-Item, Multi-Bidder Auction Design: Revenue Certificates through Deep Learning

Yanchen Jiang, David C. Parkes, Tonghan Wang

Harvard University, USA · College of AI, Tsinghua University, China

Primal-Dual Optimization Game Theory Constrained Optimization

Open paper AskPDF arXiv

Characterizing revenue-optimal auctions for multi-item, multi-bidder settings remains a fundamental open problem, with no known closed-form solution existing beyond restrictive binary-type instances. This has motivated interest in computational approaches to optimal auction design. In this paper, we introduce the first computational framework that directly tackles the dual problem for multi-item, multi-bidder auctions and dominant-strategy incentive compatibility (DSIC), generating certified revenue upper bounds. Our approach parametrizes Lagrange multipliers with a structurally guaranteed strict flow-conservation property using neural networks, enabling efficient optimization over feasible dual solutions via gradient descent. To bridge the gap between discrete computational methods and theoretical guarantees for continuous types, we develop a novel lifting technique that maps dual certificates from coarse discretizations to fine refinements. We prove that lifting gives valid revenue upper bounds for multi-item, multi-bidder auctions with continuous uniform valuations. Furthermore, we give a generalized lifting construction for arbitrary continuous distributions and demonstrate that these lifted duals converge to the revenue of the original continuous problem in the discrete limit. We validate this computational framework for the dual auction design problem by recovering known analytical mechanisms for canonical instances. For multi-item multi-bidder problems, our framework establishes a small gap between the optimal revenue and best-known DSIC mechanisms, providing computational certificates of near-optimality.

Abstract

Mechanism Design

Explore similar work

Duality for Optimal Multi-Item, Multi-Bidder Auction Design: Revenue Certificates through Deep Learning

Strategyproof Deep Reinforcement Learning for Online Resource Allocation

A3M: Adaptive, Adversarial and Multi-Objective Learning for Strategic Bidding in Repeated Auctions