Optimal Auctions through Deep Learning∗
Paul Dütting1 , Zhe Feng2 , Harikrishna Narasimhan2 , and David C. Parkes2

arXiv:1706.03459v2 [cs.GT] 19 Mar 2018

1

Department of Mathematics, London School of Economics
p.d.duetting@lse.ac.uk
2
John A. Paulson School of Engineering and Applied Sciences, Harvard University
zhe feng,hnarasimhan,parkes@g.harvard.edu
March 13, 2018†

Abstract
Designing an auction that maximizes expected revenue is an intricate task. Despite major
efforts, only the single-item case is fully understood (Myerson, 1981). In this work, we initiate the exploration of the use of tools from deep learning for the automated design of optimal
auctions. The design objective is revenue optimal, dominant-strategy incentive compatible auctions. We show that multi-layer neural networks can learn almost-optimal auctions for essentially
all settings for which there are known analytical solutions (including results due to Myerson,
Manelli-Vincent, Pavlov, Daskalakis et al., and Yao). Moreover, this can be done without appealing to characterization results, and even if the only feedback during training is revenue and
regret. We are also able to design essentially optimal auctions for poorly understood problems,
as well as obtain state-of-the-art results for combinatorial settings that have been studied in
the framework of automated mechanism design. We further show how characterization results,
even rather implicit ones such as Rochet’s characterization through induced utilities and their
gradients, can be leveraged to provide a tool to improve our theoretical understanding of the
structure of optimal auctions.

1

Introduction

Optimal auction design is one of the cornerstones of economic theory. The basic question is that of
designing a protocol for selling one or more items so as to maximize expected revenue, when buyers
have independent private values. This question was answered by Myerson [41] for the case where
there is a single item for sale. Myerson’s work has sparked a flurry of work, first in Economics
and more recently in Computer Science, attacking the question when there is more than one item
for sale. While this literature succeeded in obtaining comparably clean analytical results for a
number of special cases (including results due to Manelli and Vincent [36], Pavlov [44], Haghpanah
and Hartline [26], Giannakopoulos and Koutsoupias [24], Daskalakis et al. [18], and Yao [56]) the
∗
We would like to thank Yang Cai, Vincent Conitzer, Constantinos Daskalakis, Alexander Rush, participants
in the Economics and Computation Reunion at Simons Institute, a Dagstuhl seminar, an LSE seminar, as well as
anonymous reviewers on an earlier version of this paper for their helpful feedback.
†
The first version of this paper was posted on arXiv on June 12, 2017. Preliminary versions were presented at
the 3rd Workshop on Algorithmic Game Theory and Data Science and the NIPS’17 Workshop on Learning in the
Presence of Strategic Behavior.

1

general case with an arbitrary number of items and an arbitrary number of buyers has defied a
thorough understanding despite major efforts and several recent breakthrough results. The focus
of this most recent wave of results has been on characterizations of the optimal Bayesian incentive
compatible (BIC) mechanism for the special case where item valuations are independent [9, 8, 10],
and on dominant-strategy incentive compatible mechanisms (DSIC) with provable approximation
guarantees [27, 2, 55, 11, 12].
In this paper, motivated by the recent renaissance of multi-layer, feed-forward neural networks
[34, 50, 39], including their ability to automatically pick up the relevant features in the underlying
data [4] and recent theoretical results on the ability of neural networks to find globally optimal
solutions for non-concave/non-convex objective functions [31], we show how to cast the problem of
designing an (essentially) revenue-optimal, dominant-strategy incentive compatible mechanism as a
supervised machine learning problem, and explore several ways of solving this problem using standard pipelines for multi-layer, feed-forward neural networks. Whereas the target of optimization
in recent work on computational approaches to optimal auction design has been interim representations of auction rules, and thus necessarily situated in the context of BIC auction design,
we combine the representational structure of deep nets with the use of regret during training to
advance the design of DSIC auctions (and thus, achieving a more robust equilibrium concept).

1.1

The Optimal Auction Design Problem

In the standard independent private values model (see, e.g., [32]) there are n bidders N and
m items M . Each bidder i has a valuation function vi : 2M → R+ drawn independently from
some distribution Fi overQ
possible valuation functions Vi . We write v = (v1 , . . . , vn ) for a profile
of valuations, and V = N
i=1 Vi for the possible valuation profiles. The auctioneer knows the
distributions F = (F1 , . . . , Fn ), but does not know the bidders’ realized valuation functions v.
The auctioneer runs a mechanism M = (g, p) consisting of a collection of (possibly randomized)
allocation rules gi : V → 2M and payment rules pi : V → R≥0 . The auction collects bids b =
(b1 , . . . , bn ) ∈ V , and then computes an allocation g(b) and payments p(b).
Bidders act strategically, and seek to maximize their utility ui (vi , b) = vi (gi (b)) − pi (b). Let
v−i denote
Q the valuation profile v = (v1 , . . . , vn ) without element vi , similarly for b−i , and let
V−i = j6=i Vj denote the possible valuation profiles of bidders other than bidder i. A mechanism
is dominant strategy incentive compatibility (DSIC), if ui (vi , (vi , b−i )) ≥ ui (vi , (bi , b−i )) for every
bidder i, every valuation vi ∈ Vi , every bid bi ∈ Vi , and all bids b−i ∈ V−i from others. That is,
the bidder’s utility is maximized by reporting truthfully no matter what the other bidders do. A
mechanism is (ex post) individually rational (IR) if ui (vi , (vi , b−i )) ≥ 0 for every bidder i, every
valuation vi , and every bid profile b−i of the bidders other than i.
In a DSIC and IR mechanism M, it is in
Pthe best interest of each bidder to report truthfully,
and so the revenue on valuation profile v is i pi (v). Optimal auction design seeks to identify the
DSIC and IR mechanism that maximizes expected revenue. It thus seeks to solve the following
constrained optimization problem:
"
#
X
max Ev∼F
pi (v)
s.t. (g, p) ∈ DSIC, (g, p) ∈ IR
(1)
g,p

i

where DSIC and IR denote the set of DSIC and IR mechanisms. We refer the reader to a recent
survey by Daskalakis [16] in regard to analytical solutions to this problem, and its relaxation where
the DSIC constraint is replaced with the weaker BIC constraint, as well as for an overview of the
many new challenges that arise in settings with multiple items.
2

1.2

Adopting the Lens of Machine Learning

To see the potential connection between machine learning and the design of revenue-maximizing
mechanisms, consider the following. In machine learning, in particular supervised learning (see,
e.g., [37]), we want to find a function from inputs (covariates) to outputs (the learning target)
that has good generalization error, for example minimizing the expected loss on input-output pairs
sampled from the same distribution as the training data. For parametric models, we solve:
min E(x,y)∼FXY [L(x, y; f w )] ,
w

(2)

where w are model parameters, say w ∈ Rd for d ≥ 1, (x, y) is an input-output pair sampled
i.i.d. from some distribution FXY , say x ∈ Rk for k ≥ 1 and y ∈ R, and f w : Rk 7→ R is a
parameterized function. The objective is to minimize the expected loss, for loss function L(x, y; f w ).
Given training data sampled from FXY , a typical approach to solve (2) is to use an optimization
method such as stochastic gradient descent to minimize the loss on the training data, perhaps along
with regularization, to prefer simple solutions over complex solutions that might over-fit the data.
Comparing formulations (1) and (2), suggests the following mapping from machine learning to
optimal auction design, where (g w , pw ) is a parameterized allocation and payment rule:
Covariates
Target value
Hypothesis
Loss function
Constraints (new)

x −→ v
not needed
f w −→ (g w , pw ) P
L(x, y; f w ) −→ − i∈N pw
i (v)
DSIC and IR

This way, the learning formulation (assuming that we can get it to handle the new constraints,
and assuming the parameterized family of rules is rich enough) provides an equivalent way of
maximizing expected revenue subject to DSIC and IR. The loss function is the negated revenue,
and thus minimizing expected loss is equivalent to maximizing expected revenue.1

1.3

Our Approach

We consider two basic approaches for solving the constrained supervised learning problem derived
above, which differ in the way they incorporate the constraints.
Fully Agnostic Approach The first—and more general—approach that we explore does not
depend on characterizations of DSIC and IR allocation and payment rules. It therefore bears the
biggest promise for being capable of handling cases for which analytical approaches to optimal
design get stuck. We incorporate constraints through the expected ex post regret of bidders, and
move the resulting constraints into the objective by augmenting the objective with a Lagrangian
term that captures violations of the constraints. Our network architectures for this approach—
which we refer to as RegretNet —are fully connected multi-layer, feed-forward neural networks. The
input to the network are the buyer valuations, and we will interpret part of the output as encoding
the allocation decision and part as incorporating the payments. We thus obtain a differentiable,
parameterized mechanism (g w , pw ) that depends on parameters w. The machine learning problem
1
Related connections between statistical machine learning and automated economic design have also been observed,
although not quite at this level of generality; e.g., Procaccia et al. [45] (no incentive considerations), Dütting et al.
[21] (payment rules only), Narasimhan et al. [42] (for a specific, parametric class) and Narasimhan and Parkes [43]
(via agent-independent price functions).

3

of interest is then to optimize the network parameters to minimize the expected loss, i.e. the
expected negative revenue, subject to the expected ex post regret for each bidder being 0. This
optimization problem is solved using the Augmented Lagrangian solver. The mechanisms that we
obtain through this approach have near-zero regret and are essentially DSIC and IR.
Characterization-Based Approach The second approach that we consider achieves DSIC by
hard-coding known characterization results into the network architecture. This approach is less
general as a result of its appeal to characterization results. But it holds promise as a tool to guide
our theoretical understanding of the structure of optimal auctions. As a case in point, we leverage
a characterization due to Rochet [47] for single bidder, multi-item auctions. According to this
characterization, an auction for additive values on items is DSIC if and only if its induced utility u is
1-Lipschitz with respect to the `1 -norm, non-decreasing, and convex. An analogous characterization
exists for a buyer with unit-demand valuations. Our network architecture (RochetNet) exploits
this characterization result, not by directly learning the optimal allocation rule and payment rule,
but rather by learning the induced utility function.2
The main novelty of this work is in modelling a mechanism as an end-to-end neural network,
and in devising ways to handle constraints for DSIC and IR in the learning problem.

1.4

Experiments

We explore, experimentally, whether our approaches can recover known optimal designs for singleand multi-item settings, as well as new designs for settings where such results are not known.
Results for fully agnostic approach We first show that RegretNet successfully learns mechanisms for single-item settings whose revenue is very close to Myerson’s auction, with vanishingly
small ex post regret and ex post IR violations. We present similar results for the mechanism of
Manelli and Vincent [36] and the mechanism of Daskalakis et al. [18] for a single bidder with independent preferences over two items, and the mechanism of Haghpanah and Hartline [26] for a
single additive bidder with joint preferences over two items. Here RegretNet identifies a mechanism,
which achieves essentially optimal revenue with vanishingly small regret and small ex post IR violation. Moreover, the learned allocation and pricing decisions match with surprising accuracy those
of the theoretically optimal mechanism. RegretNet is also able to recover the optimal mechanisms
of Pavlov [44] for a single bidder with independent unit-demand preferences over two items, as well
as the mechanism of Yao [56] for two bidders and two items, when the item valuations are drawn
identically from a uniform distribution with support size two.
We also consider various settings for which— to the best of our knowledge —optimal mechanisms are not known. These include a generalization of the Manelli and Vincent setting to 10
items, a generalization of the Yao setting to a distribution of support size three, settings with two
bidders with independent additive preferences over two items, and two bidders with combinatorial
preferences over two items, and a larger setting with 3 additive bidders and 10 items. For the
first two settings we show that RegretNet learns new mechanisms that beat reasonable baseline
2

As another illustration of how characterization results can be leveraged, we develop an architecture for singleitem settings. This network, referred to as MyersonNet, mimics Myerson’s characterization for single-item auctions
[41], and learns monotone transforms of bidder values. We present this approach in Appendix D and evaluate it in
Appendix E.1.

4

mechanisms such as a per-item Myerson auctions and Myerson on the grand bundle. For the combinatorial settings, we show that RegretNet outperforms or matches state-of-the art computational
mechanisms for these setting due to Sandholm and Likhodedov [48].
Results for characterization-based approach Our second set of results demonstrate the use
of RochetNet to recover the optimal mechanisms for the single bidder, two item settings described
above. Plots of the learned allocation rules reveal that the learned mechanisms match almost
precisely the theoretically optimal ones, although we have not encoded the specific (allocation)
structure of the optimal mechanisms explicitly into the network. As a demonstration of its utility
as a theoretical tool, we provide support for a conjecture of Daskalakis et al. [18] on the structure of
optimal auction for a single additive bidder, two item setting with independent uniform valuations.
Source Code We will release open-source code for all our neural network implementations over
the next few months.

1.5

Related Work

Our work fits within the broader agenda of automated mechanism design of Conitzer and Sandholm
[14, 15], albeit our emphasis on using supervised learning and neural networks as a tool for solving
the underlying optimization problem presents a significant departure from the traditional tools
considered in this literature.
There is a growing literature that uses tools from machine learning to optimize certain aspects of
auction design, such as work by Lahaie [33], Dütting et al. [21], Mohri and Medina [38], Narasimhan
et al. [42], Brero et al. [7], and Tang [51].
There have also been sample complexity results for the design of optimal single-item auctions
[13, 40, 30, 19, 1], single bidder, multi-item auctions [20], combinatorial auctions [3], and allocation
mechanisms (both with and without money) [43].
Several other research groups have recently picked up deep nets and inference tools and applied
them in an Econ context. These include Hartford et al. [29] and Fudenberg and Liang [23] who use
neural networks to predict behavior of human participants in strategic scenarios, Thompson et al.
[52] who provide an automated equilibrium analysis of mechanisms, Hartford et al. [28] and Louizos
et al. [35] who use deep nets for causal inference, and Raghu et al. [46] who use deep reinforcement
learning for solving combinatorial games.
There are two follow-up works to the present paper. Feng et al. [22] extend our approach to the
design of revenue-maximizing auctions for budget constrained bidders. Golowich et al. [25] extend
our approach to a mechanism design setting without money.

2

The RegretNet Framework

In this section, we develop the RegretNet framework for learning auctions that are essentially
optimal and essentially DSIC. This framework is very general, and can be applied where there are
no characterization results for DSIC auctions. We model an auction as a fully-connected neural
network and impose explicit constraints for DSIC and IR in the training problem.

2.1

Formulating Constraints for DSIC and IR

To enforce DSIC and IR we define a bidder’s ex post regret for truthful bidding. Fixing the bids
of others, this is the maximum increase in a bidder’s utility, considering all possible non-truthful
5

sof tmax
z11

b11
..
.

(1)

h1

h2

(1)

. . . h2

..
.

..
.

h1

(R)

b11

..
.

..
.
zn1

b1m
..
.
bn1
..
.

(1)

hJ1

(R)

..
.

..
.
z1m

bn1

..
.

..
.
znm

bnm

c1

(T )

relu

p1

c2

(1)

. . . c2

(T )

relu

p2

..
.

..
.

..
.

b1m

(R)

hJR

(1)

c1

(1)

cJ 0

1

bnm

(T )

cJ 0

T

relu

pn

sof tmax

(a) Allocation network g

(b) Payment network p

Figure 1: RegretNet for additive valuations: The allocation and payment networks for n bidders and m
items.

bids. The expected ex post regret for bidder i, given model parameters w, is


w
0
w
rgt i (w) = Ev∼F max
u
(v
;
(v
,
v
))
−
u
(v
;
(v
,
v
))
,
i
−i
i
i
−i
i
i
i
0
vi ∈Vi

(3)

We assume that F has full support on the space of valuation profiles V . Hence the mechanism is
strategy-proof if and only if rgt i (w) = 0, ∀i ∈ N . We define the expected violation of individual
rationality for bidder i as:


irp i (w) = Ev∼F max{0, −uw
(4)
i (vi ; v))} .
The machine learning problem of interest is to minimize the expected loss, i.e., the expected
negated revenue subject to the expected ex post regret and the expected IR violation being 0 for
each bidder:
h X
i
min Ev∼F −
pw
(v)
(5)
i
w

w

i∈N
w

w

w

s.t. [IC] rgt i (g , p ) = 0,
[IR] irp i (g , p ) = 0,

∀i ∈ N
∀i ∈ N

The neural network architecture for modeling a mechanism is described below for bidders with
additive valuations, with unit-demand valuations, and general combinatorial valuations.

2.2

Network Architecture for Additive Valuations

A bidder has additive valuations if the bidder’s valueP
for a bundle of items S ⊆ M is the sum of
her value for the individual items in S, i.e. vi (S) = j∈S vi (j). In this case, the bidders report
only their valuations for individual items.
The network architecture for additive bidders is shown in Figure 1. The network consists of
two logically distinct components: the allocation network g w : Rnm → [0, 1]nm and the payment
network pw : Rnm → Rn≥0 . The input layer of the networks consists of bids bij representing the
valuation of bidder i for item j. There are multiple “hidden layers” (denoted h(r) and c(t) in the
figure) and an output layer. The allocation network outputs for each item, the probability that
it is allocated to each bidder. The payment network outputs the payment for each bidder. Each
6

unit in a hidden layer and each unit in an output layer may be a non-linear activation function,
applied to a weighted sum of outputs from the previous layer. These weights form the parameters
of the network. We use w to denote the complete vector of parameters, for both the payment and
allocation parts of the network.
The allocation rule is modeled with R fully-connected hidden layers (we use R = 2 and 100 units
in each layer in our experiments), each with sigmoidal activations, and a fully-connected output
layer. For a given bid profile b, illustrated here as providing a number for each bidder for each of
m items, the network outputs a vector of allocation probabilities P
z1j = g1j (b), . . . , znj = gnj (b), for
each item j ∈ [m], through a softmax activation function, with ni=1 zij ≤ 1 (for n bidders). A
formal description of the allocation rule is given below:
(1)

= σ(αj · b), ∀j = 1, . . . , J1

(k)

= σ(αj · h(k−1) ), ∀k = 2, . . . , R, j = 1, . . . , Jk

sij

= αij

hj
hj

(1)

(k)

(R+1)

· h(R) , ∀i = 1, . . . , n + 1, j = 1, . . . , m

w
gij
(b) = softmax i (s1j , . . . , snj , sn+1,j ) ∀i = 1, . . . , n, j = 1, . . . , m,
(1)

(k)

(R+1)

where weights αj ∈ Rnm , αj ∈ RJk−1 , for k = 2, . . . , R, and j = 1, . . . , Jk , and weights αij
∈
RJR , for i = 1, . . . , n, and j = 1, . . . , m. The sigmoid activation function is σ(z) =P
1/(1 + e−z ). The
skj , where
softmax activation function for item j is softmax i (s1j , . . . , snj , sn+1,j ) = esij / n+1
k=1 e
sn+1,j is a dummy input that corresponds to the item not being allocated to any bidder. Bundling
of items is possible because the output units allocating items to the same bidder can be correlated.
The payment rule is modeled using a feed-forward neural network with T fully-connected hidden
layers (we use T = 2 and 100 units in each layer in our experiments), each with sigmoidal activations,
and a fully-connected output layer. The output layer uses ReLU activation units to define a payment
for each bidder. The output pi that corresponds to bidder i is the amount the bidder should pay
in expectation, for this particular bid profile. It is always feasible to convert it into an equivalent,
lottery in payments, such that a bidder’s payment is no greater than her value for all outcomes
in the support of the distribution on allocations implied by the softmax units of the allocation
network. A formal description of the payment rule is given below:
(1)

= σ(βj · b), ∀j = 1, . . . , J10

(k)

= σ(βj

cj
cj

(1)

(k)

(T +1)

si = βi

· c(k−1) ), ∀k = 2, . . . , T, j = 1, . . . , Jk0
· c(T ) , ∀i = 1, . . . , n

pw
i (b) = relu(si ), ∀i = 1, . . . , n,
(1)

where relu(z) = max{z, 0} ensures that the payments are non-negative, and weights βj
(k)

∈ Rnm ,

0

∈ RJk−1 , for k = 2, . . . , T + 1, and j = 1, . . . , Jk0 .
In the special case where there is only one bidder, the allocation network needs to only output
a probability for each item, denoting whether the item is allocated to the bidder. The network uses
sigmoidal activation output for each item instead of a softmax function (Figure 12 in Appendix A).

βj

2.3

Network Architecture for Unit-demand Valuations

A bidder has unit-demand valuations when the bidder’s value for a bundle of items S ⊆ M is the
maximum value she assigns to any one item in the bundle, i.e. vi (S) = maxj∈S vi (j). The allocation

7

b11
..
.

(1)
h1

(R)
h1

sof tmax

s11

s1m

..
.

..
.

...

sn1

b1m
(1)

..
.
bn1
..
.
bnm

sof tmax

. . . h2

..
.

..
.

(1)

s̄

..
.
zn1 = min{s̄n1 , s̄0n1 }

snm

(R)

h2

hJ1

z11 = min{s̄11 , s̄011 }

..
.
s011

...

s0n1

.. sof tmax s̄
.
. . . s0nm

(R)

hJR

s01m

0

z1m = min{s̄1m , s̄01m }
..
.
znm = min{s̄nm , s̄0nm }

sof tmax

Figure 2: RegretNet for unit-demand valuations: The allocation network for n bidders andP
m items. The
n+1
payment network is the same as that for additive bidders in Figure 1(b). Here s̄ij = esij / k=1 eskj and
P
0
0
n+1
s̄0ij = esij / k=1 eskj .

network for unit-demand bidders is the feed-forward network shown in Figure 2, while the payment
network is the same as the one for additive valuations (see Figure 1(b)).
For revenue maximization in this setting, it is sufficient to consider allocation rules that assign
at most one item to each bidder. In the case of randomized
P allocation rules, this would require that
the total allocation for each bidderPis at most 1, i.e. j zij ≤ 1, ∀i ∈ [n]. We would also require
that no item is over-allocated, i.e. i zij ≤ 1, ∀j ∈ [m]. Hence, we design allocation networks for
which the matrix of out probabilities [zij ]ni,j=1 is doubly stochastic.3
In particular, we have the allocation network compute two sets of scores sij ’s and s0ij ’s, with
the first set of scores normalized along the rows, and the second set of scores normalized along the
columns. Both normalizations can be performed by passing these scores through softmax functions.
The allocation for bidder i and item j is then computed as the minimum of the corresponding
normalized scores, i.e.
(
)
0
esij
esij
.
zij = min Pn+1 s , Pm+1 s0
kj
jk
k=1 e
k=1 e
Here indices n + 1 and m + 1 denote dummy inputs that correspond to an item not being allocated
to any bidder, and a bidder not being allocated any item respectively. It is easy to see that the
min operation ensures that the row sums and column sums for the resulting allocation matrix do
not exceed 1.
P
When there is only one bidder, we only need one constraint to be satisfied:
j z1,j ≤ 1. This
can be enforced by generating a score sj for each item j, and computingPthe probability of the
sk (Figure 13 in
item being allocated to the bidder using a softmax function: z1,j = esj / m+1
k=1 e
Appendix A).

2.4

Network Architecture for Combinatorial Valuations

We also consider bidders with general, combinatorial valuations (albeit developed in this present
work for only a small number of items). In this case, each bidder i reports a bid bi,S for every bundle
of items S ⊆ M (except the empty bundle, for which her valuation is taken as zero). The allocation
network has an output zi,S ∈ [0, 1] for each bidder i and bundle S, denoting the probability that
the bidder is allocated the bundle.
3

By the Birkhoff-von Neumann theorem, a randomized allocation represented by a doubly-stochastic matrix can
be decomposed into a lottery over deterministic one-to-one assignments [6, 53].

8

item1
sof tmax bidder1
sof tmax
min

z1,{1}

min

z1,{2}

min

z1,{1,2}

min

z2,{1,2}

min

z2,{1}

min

z2,{2}

b1,{1}
(1)

h1

h2

(1)

. . . h2

b2,{1}

..
.

..
.

b2,{2}

hJ1

b1,{2}

h1

(R)

b1,{1,2}

(1)

(R)

(R)

hJR

b2,{1,2}
bidder2
item2 sof tmax
sof tmax

Figure 3: RegretNet for combinatorial valuations: The allocation network for two bidders and two
items. The payment network resembles that for additive bidders in Figure 1(b), but takes bids
bi,{1} , bi,{2} , bi,{1,2} , i ∈ {1, 2} as input.

To prevent the items from being over-allocated, we require that the probability that an item
appears in a bundle allocated to some bidder is at most 1 and that the total allocation to a bidder
does not exceed 1, i.e.
X X
X
zi,S ≤ 1, ∀j ∈ M and
zi,S ≤ 1, ∀i ∈ N.
i∈N S⊆M :j∈S

S⊆M

To satisfy these constraints, we will have the allocation network compute a total of m+n groups
of scores. There is a group of bidder-wise scores si,S , ∀S ⊆ M for each bidder i ∈ N , and a group
(j)
of item-wise scores si,S , ∀i ∈ N, S ⊆ M for each item j ∈ M . Each group of scores is normalized
using a softmax function:
s̄i,S

esi,S
= P si,S
Se

(j)

and

(j)
s̄i,S

=P

esi,S
(j)

si,S
i,S e

.

The allocation for bidder i and bundle S ⊆ M is the minimum among the normalized bidder(j)
wise score s̄i,S for i and the normalized item-wise scores s̄i,S for each j ∈ S. In other words:
(j)

zi,S = min{s̄i,S , s̄i,S : j ∈ S}.
It is easy to see that as a result of the min operation and the score normalizations, the final
allocation satisfies both sets of constraints:
X X
X X
X
X
(j)
zi,S ≤
s̄i,S ≤ 1, ∀j ∈ M and
zi,S ≤
s̄i,S ≤ 1, ∀i ∈ N.
i∈N S⊆M :j∈S

i∈N S⊆M :j∈S

S⊆M

S⊂M

Figure 3 shows the network architecture for a setting with 2 bidders and 2 items. For ease of
exposition, we ignore the empty bundle in our discussion.4 For each bidder i ∈ {1, 2}, the network
4

In our experiments, the null assignment is made possible by including a dummy node in the softmax computation.

9

computes three scores si,{1} , si,{2} , and si,{1,2} , one for each bundle that she can be assigned, and
normalizes them using a softmax function. The network also computes four scores for item 1:
s11,{1} , s12,{1} , s11,{1,2} , and s12,{1,2} , one for each assignment where item 1 is present, and similarly,
four scores for item 2: s21,{2} , s22,{2} , s21,{1,2} , and s22,{1,2} . Each set of scores is then normalized by
separate softmax functions. The final allocation for each bidder i is computed as:

zi,{1} = min s̄i,{1} , s̄1i,{1} ,

zi,{2} = min s̄i,{2} , s̄2i,{2} , and

zi,{1,2} = min s̄i,{1,2} , s̄1i,{1,2} , s̄2i,{1,2} .

2.5

Augmented Lagrangian Solver

We optimize the parameters of the neural network, subject to regret and IR constraints, using the
augmented Lagrangian method. In practice, the loss, regret and IR penalty involved in formulating (5) are estimated from a sample S = {v (1) , . . . , v (L) } drawn i.i.d. from F . In place of expected
loss, we adopt the empirical loss
b w , pw ) = − 1
L(g
L

L X
n
X

(`)
pw
i (v ).

(6)

`=1 i=1

To estimate the regret, we use additional samples of valuation profiles S` drawn i.i.d. from F
for each profile v (`) in S, and compute the maximum utility gain over these alternate profiles:
L

X

(`) (`)
w (`)
0 (`)
c i (g w , pw ) = 1
rgt
max
u
v
;
v
,
v
− uw
i
i
i (vi ; v ).
i
−i
v 0 ∈S`
L

(7)

`=1

The IR penalty is estimated as:
L

o
n
X
(`) (`) 
c i (g w , pw ) = 1
.
max 0, −uw
irp
i vi ; v
L

(8)

`=1

For large samples S and S` (for each `), a mechanism with very low empirical regret and very low
empirical IR penalty will have very low regret and very low IR penalty, with high probability.
The training problem becomes:
b w , pw )
min L(g

(9)

w

c i (g w , pw ) = 0,
s.t. rgt
c i (g w , pw ) = 0,
irp

∀i ∈ N
∀i ∈ N.

The augmented Lagrangian solver formulates a sequence of unconstrained optimization problems,
where the DSIC and IR constraints are enforced through a weighted term in the objective. More
specifically, the solver works with the Lagrangian function, augmented with a quadratic penalty
term for violating the constraints:
X

b w , pw ) +
c i (g w , pw ) + ρ rgt(g
c w , pw ) 2
Cρ (w; λrgt , λirp ) = L(g
λrgt,i rgt
2
i∈N
X

c i (g w , pw ) + ρ irp(g
c w , pw ) 2 ,
(10)
+
λirp,i irp
2
i∈N

10

P
c w , pw ) = i rgt
c i (g w , pw ),
where λrgt ∈ Rn and λirp ∈ Rn are vectors of Lagrange multipliers, rgt(g
P
c w , pw ) =
c w w
irp(g
i irp i (g , p ), and ρ > 0 is a fixed parameter that controls the weight on the
quadratic penalty. The solver operates across multiple iterations, and performs the following updates in each iteration t:
wt+1 ∈ argminw Cρ (w; λtrgt , λtirp )

(11)

t
t+1
c
λt+1
),
rgt,i = λrgt,i + ρ rgt i (w

∀i ∈ N,

(12)

t
t+1
c
λt+1
),
irp,i = λirp,i + ρ irp i (w

∀i ∈ N,

(13)

where the inner optimization in (11) is performed using stochastic gradient descent. In particular,
the gradient is pushed through the loss function as well as an empirical measure of regret.
With a suitably large penalty parameter ρ, the method of augmented Lagrangian is guaranteed
to converge to a (locally) optimal solution to the original problem [54] (also see Appendix B). Our
experience has been that even for small values of ρ and enough iterations, the solver converges
to auction designs that yield near-optimal revenue while closely satisfying the regret and IR constraints. Since in practice, a solver is run for finite number of iterations and the training sample is
finite in size, the result of training may be a mechanism with a small regret and IR violations. We
find in our experiments that the regret can indeed be driven down to negligible values, resulting in
mechanisms that are essentially DSIC and IR.

3

Experimental Results for RegretNet

In this section, we present experimental results that demonstrate that RegretNet can be used to
recover almost-optimal mechanisms for a variety of distributions, as well as to find new mechanisms
for settings where there is no known analytical solution. We focus on settings with multiple items;
our results for the single-item case can be found in Appendix E.2

3.1

Experimental Setup and Evaluation

Setup We use the TensorFlow deep learning library for implementing the neural network learning
algorithms. We use the ADAM solver with a learning rate of 0.001 and mini-batch size of 64 to
solve the optimization problem (11) within the augmented Lagrangian method. The experiments
were run on a compute cluster with NVDIA GPU cores.
Evaluation We generate training and test sets from various value distributions, optimize the
model parameters on the training set, and evaluate the revenue on the test set.
P We also evaluate the
c i (f, p), and the
regret, averaged across all bidders and test valuation profiles, Regret = n1 ni=1 rgt
P
c i (f, p)
IR penalty, averaged across all bidders and test valuation profiles, IR penalty = n1 ni=1 irp
(see (7) and (8)). We use a sufficient number of valuation profiles and deviating bids in the training
set to ensure that the learned auction mechanism does not “overfit” the training set, and yields
similar values of revenue, IR penalty and regret on the test set. The number of deviating bids was
100, and the specific sample sizes are provided in the following sections.

3.2

Multi-item Setting with Single Additive Bidder

We evaluate RegretNet for designing multi-item mechanisms with a single bidder. The allocation
and payment networks each use two hidden layers with 100 nodes (R = T = 2 in Figure 12). We
consider the following settings:
11

Distribution
Additive Uniform 1: v1 , v2 ∼ U [0, 1]
Additive Uniform II: v1 ∼ [4, 16], v2 ∼ U [4, 7]
Additive Uniform III: v1 , v2 drawn uniformly from a unit triangle
Unit-demand Uniform 1: v1 , v2 ∼ U [0, 1]
Unit-demand Uniform II: v1 , v2 ∼ U [2, 3]

Opt
irp
0.550
9.718
0.374
0.384
2.132

rev
0.550
9.725
0.370
0.394
2.128

RegretNet
rgt
irp
0.001
0.0
0.006
0.0
0.002
0.0
0.001
0.0006
0.0005
0.0

RochetNet
rev
0.549
9.672
0.381
0.382
2.129

Table 1: Revenue of auctions for single additive bidder, two items obtained with RegretNet and RochetNet.

(a)

(b)

Figure 4: Allocation rule learned by RegretNet for (a) the single additive bidder, two items setting with
item values v1 , v2 ∼ U [0, 1], and for (b) the single additive bidder, two items setting with values v1 ∼ U [4, 16]
and v2 ∼ U [4, 7]. The optimal mechanisms due to Manelli and Vincent [36] for (a) and Daskalakis et al. [18]
for (b) are described by the regions separated by the dashed orange lines. The numbers in orange are the
probability the item is allocated in a region.

(a) Additive Uniform I : single additive bidder with preferences over two items, where the item
values v1 , v2 ∼ U [0, 1],
(b) Additive Uniform II : single additive bidder with preferences over two non-identically distributed
items, where v1 ∼ U [4, 16] and v2 ∼ U [4, 7].
(c) Additive Uniform III : single additive bidder with preferences over two items, where (v1 , v2 ) are
drawn jointly and uniformly from a unit triangle with vertices (0, 0), (0, 1) and (1, 0).
(d) Unit-demand Uniform I : single unit-demand bidder with preferences over two items, where the
item values v1 , v2 ∼ U [0, 1],
(e) Unit-demand Uniform II : single unit-demand bidder with preferences over two items, where
the item values v1 , v2 ∼ U [2, 3],
(f) Additive Uniform IV : single additive bidder with preferences over ten items, where each vi ∼
U [0, 1].
For the first distribution, we show that our approach is able to almost exactly recover the optimal
mechanism of Manelli and Vincent [36]. For the second distribution, we show that the approach
12

(a)

(b)

Figure 5: Allocation rule learned by RegretNet for (a) the single additive bidder, two items setting with
values v1 , v2 drawn jointly, uniformly from a triangle with vertices (0, 0), (0, 1) and (1, 0), (optimal mechanism
by Haghpanah and Hartline [26]), and for (b) the single unit-demand bidder, two items setting with item
values v1 , v2 ∼ U [2, 3] (optimal mechanism by Pavlov [44]).
Distribution
Additive Uniform IV

Item-wise Myerson
rev
2.495

Bundled Myerson
rev
3.429

rev
3.484

RegretNet
rgt
irp
0.006 0.002

RochetNet
rev
3.431

Table 2: Revenue of auctions for single additive bidder, 10 items obtained with RegretNet and RochetNet.

almost exactly recovers the optimal mechanism of Daskalakis et al. [18]. For the third distribution,
we show that the approach almost exactly recovers the optimal mechanism of Haghpanah and
Hartline [26]. For the forth and fifth distributions, we show that the approach almost exactly
recovers the optimal mechanisms of Pavlov [44]. To our knowledge, an analytical solution for the
optimal mechanism for the sixth distribution is not available [16]. Here our approach finds a new
mechanism that has higher revenue than both a Myerson auction on each item and a Myerson on
the entire bundle.
The training and test set each contains 5,000 valuations and 10,000 valuation respectively. The
results are summarized in Table 1. Even without the aid of characterization results, RegretNet is
able to identify mechanisms that have revenue close to the optimal revenue, and with low regret
and IR violations. We also compare the learned allocation rules with the optimal rule in Figures 4,
5, and 6. Not only is RegretNet able to achieve near-optimal revenue, but is also able to learn
allocation rules that closely resemble the optimal rule.
The results for the ten item distribution are shown in Table 2, where we can see that RegretNet
identifies a new mechanism that yields higher revenue than the baselines, while incurring very small
regret. This demonstrates the power of RegretNet in designing new mechanisms.

13

Figure 6: Allocation rule learned by RegretNet for the single unit-demand bidder, two items setting with
item values v1 ∼ U [0, 1] and v2 ∼ U [0, 1]. The optimal mechanism of Pavlov [44] is described by the regions
separated by the dashed orange lines.
Distribution
Discrete Uniform I
Discrete Uniform II

Opt
rev
1.560
—

rev
1.552
1.868

RegretNet
rgt
irp
0.005 0.008
0.009 0.001

Item-wise
Myerson rev
1.494
1.818

Bundle-wise
Myerson rev
1.435
1.697

Table 3: Revenue and regret for the two additive bidders, two items setting, obtained with RegretNet for
the discrete uniform distributions.

3.3

Multi-item Setting with Multiple Bidders

We also apply RegretNet to settings for which there are no characterization results. We consider
settings with the following valuation distributions:
(a) Discrete Uniform I : two additive bidders and two items, where the bidders draw their value for
each item from identical uniform distributions over two values {0.5, 1.0}.
(b) Discrete Uniform II : two additive bidders and two items, where the bidders draw their value
for each item from identical uniform distributions over two values {0.5, 1.0, 1.5}.
(c) Continuous Uniform: two additive bidders and two items, where the bidders draw their value
for each item from identical uniform distributions over [0, 1]
(d) Combinatorial Uniform: two bidders and two items, with v1,1 , v1,2 , v2,1 , v2,2 ∼ U [1, 2], v1,{1,2} =
v1,1 + v1,2 + C and v2,{1,2} = v2,1 + v2,2 + C, where C ∼ U [−1, 1].
(e) Combinatorial Asymmetric Uniform: two bidders and two items, with v1,1 , v1,2 ∼ U [1, 2],
v2,1 , v2,2 ∼ U [1, 5], v1,{1,2} = v1,1 + v1,2 + C and v2,{1,2} = v2,1 + v2,2 + C, where C ∼ U [−1, 1].
(f) Unit-demand Uniform III : two unit-demand bidders and two items, where the bidders draw
their value for each item from identical uniform distributions over [0, 1].
(g) Additive Uniform V : three additive bidders and ten items, where the bidders draw their value
for each item from identical uniform distributions over [0, 1].
Even for these simple distributions, this setting is analytically difficult to solve. The optimal
mechanism for this setting is only known for the first distribution [56]. For the second discrete
distribution (b), we compare the trained mechanism against a Myerson auction on each item and
a Myerson auction on the entire bundle of items. For the distributions (c), (d) and (e), Sandholm
and Likhodedov [48] provide mechanisms optimized over specialized families of weighted affine
maximizer mechanisms. We compare the trained mechanism with the optimal mechanisms obtained
in their work, namely those from the VVCA and AMAbsym families.
In all the above settings, we generated training and test sets with 5000 valuations and 10,000
valuations respectively. Due to their small valuation spaces, we use smaller allocation and payment

14

Distribution
Continuous Uniform
Combinatorial Uniform
Comb. Asym. Uniform

rev
0.941
2.812
4.277

RegretNet
rgt
irp
0.011
0.006
0.006 0.0008
0.006 0.0001

Optimal VVCA
rev
0.861
2.743
4.208

Optimal AMAbsym
rev
0.862
2.761
3.734

Table 4: Revenue and regret for the two bidders, two items settings, obtained with RegretNet for the
continuous uniform, combinatorial uniform and combinatorial asymmetric uniform distributions.
Distribution
Unit-demand Uniform III
Additive Uniform V

rev
0.769
5.574

RegretNet
rgt
irp
0.006
0.0
0.026 0.029

Baseline
rev
0.180 (Ascending auction)
5.307 (Item-wise Myerson)

Table 5: Revenue and regret for two unit-demand bidders, two items setting and the three additive bidders,
ten items setting obtained by RegretNet. For the ascending auction, the prices were raised in units of 0.3
(which was empirically found to be optimal through a grid search).

networks for the two discrete distributions, with two hidden layers of 10 nodes each. For the others,
we use allocation and payment networks with two hidden layers of 100 nodes each.
The results are summarized in Table 3 for the discrete distributions and in Table 4 for the
continuous distribution. For the first distribution, RegretNet recovers the optimal mechanism,
yielding revenue close to the optimal and incurring a small regret and IR penalty. For the second
distribution, RegretNet is able to find a new mechanism that yields higher revenue than both
the baselines, while incurring very small regret and IR violations. For the third distribution,
RegretNet finds a new mechanism that is better than the results in Sandholm and Likhodedov [48],
while incurring a small regret and IR penalty. This shows that RegretNet is able to discover new
mechanisms in settings for which there are no useful characterizations of the optimal mechanism.
Figure 7 illustrates the test revenue and regret of the trained mechanism, when applied to the
first discrete distribution, as function of the number of solver iterations. The solver adaptively tunes
the relative weight (Lagrange multiplier) on the regret and IR penalty, focusing on the revenue in
the initial iterations and on regret and IR penalty in later iterations.
We also report the progress in the average absolute error P
between
the learned allocation rule g
L Pn Pm
1
∗
∗ (v (`) )|.
and Yao’s [56] optimal allocation rule g on the test set: Lmn `=1 i=1 j=1 |gij (v (`) ) − gij
Not only does the learned mechanism converge to the optimal revenue with a negligible regret, but
the structure of the learned allocation rule also closely approximates to the optimal allocation rule
in terms of the allocation error.
Table 5 contains the results for the Unit-demand Uniform III setting, with 2 unit-demand bidder
and 2 items, and the Additive Uniform V setting, with 3 additive bidders and 10 items. RegretNet
learns new mechanisms with higher revenues compared to an ascending auction in the first case and
to the item-wise Myerson mechanism (which here is equivalent to VCG with optimized reserves)
in the second case. For the former, we also show in Figure 7 the test regret as a function of solver
iterations for different sizes of misreport samples. As seen, even with larger number of misreport
samples, the regret is still small, implying that the learned mechanism is essentially DSIC.

4

The RochetNet Framework

In this section, we show how to leverage characterization results to develop essentially optimal
designs that are, moreover, exactly DSIC and IR. We focus on the setting of a single bidder with
15

0.25

Optimal Mechanism
RegretNet

1.8

Test regret

Test revenue

2.0

1.6
1.4
1.2
0

1

2

3

No. of iterations

4

0.20
0.15
0.10
0.05
0.00

5
1e5

1

100

0.3

10

1

10

2

2

3

No. of iterations

4

5
1e5

100 deviating samples
200 deviating samples
400 deviating samples
800 deviating samples

0.4
Test regret

Test allocation error

0.5

0

0.2
0

1

2
3
No. of iterations

4

5
1e5

0.0

0.5

1.0 1.5 2.0
No. of iterations

2.5

3.0
1e6

Figure 7: Plots 1–3: Test revenue, regret, and allocation error (against the optimal rule of Yao [56]) of
RegretNet as a function of number of solver iterations for the two additive bidders, two items setting with
the Discrete Uniform I distribution. Plot 4: Test regret of RegretNet as a function of solver iterations for
different misreport sample sizes for the two unit-demand bidders, two items setting.

preferences over multiple items, where there is no analytical solution to the problem even with
additive values and more than six items [16]. In fact, we only have an implicit characterization
of the optimal DSIC mechanism for this setting. Here we use neural networks to search over a
specific class of fully-DSIC mechanisms that are known to contain the optimal auction. We think
this specialized approach will be of interest as a tool with which to study and test conjectures
about the structure of optimal auctions in poorly-understood settings. In the Appendix D, we also
develop the specialized MyersonNet architecture for the single-item setting.5

4.1

The Network Architecture

We start with the case where the bidder’s preferences are additive. We make use of the characterization for Rochet [47] for a single bidder problem in terms of the bidder’s induced utility and its
gradient.6 The utility function u : Rm
≥0 → R induced by a mechanism (g, p) for a single bidder is:
u(v) =

m
X

gj (v) vj − p(v).

(14)

j=1

This is the bidder’s utility for bidding truthfully when her valuation is v. We say that the utility
function is monotonically non-decreasing if u(v) ≤ u(v 0 ) whenever vj ≤ vj0 , ∀j ∈ M . The following
theorem explains the connection between a DSIC mechanism and its induced utility function:
Theorem 4.1 (Rochet [47]). A utility function u : Rm
≥0 → R is induced by a DSIC mechanism iff
u is 1-Lipschitz w.r.t. the `1 -norm, non-decreasing, and convex. Moreover, for such a utility func5
Myerson characterized the structure of the optimal auction via monotone virtual value transformations. We
develop a neural network that mimics this characterization, by modelling the monotone transforms as neural networks
[49]. We show that MyersonNet can recover the optimal auction for a variety of valuation distributions.
6
Daskalakis et al. [17] and Daskalakis et al. [18] also make use of Rochet’s characterization in their duality-based
characterizations for the single-bidder multi item problem.

16

h1
b1

0

b2

h4

h2
max
..
.

u(b)

u(b)

h3

..
.

h2
u(b) = 0

h1

bm
hJ

b

(a)

(b)

Figure 8: RochetNet: (a) Neural network representation of a non-negative, monotone, convex induced
utility function; here hj (b) = wj · b + βj . (b) An example of a utility function represented by RochetNet
for m = 1.

tion u, ∇u(v) exists almost everywhere in Rm
≥0 , and wherever it exists, ∇u(v) gives the allocation
probabilities for valuation v, and ∇u(v) · v − u(v) is the corresponding payment.
Further, for a mechanism to be IR, its induced utility function must be non-negative, i.e.
u(v) ≥ 0, ∀v ∈ Rm
≥0 . To find the optimal mechanism, we need to search over all non-negative utility
functions that satisfy the conditions in Theorem 4.2, and pick the one that maximizes expected
revenue. This can be done by modeling the utility function as a neural network, and formulating
the above optimization as a neural network learning problem. The associated mechanism can then
be recovered from the gradient of the learned neural network.
To model a non-negative, monotone, convex, Lipschitz utility function, we use a max of J linear
functions with non-negative coefficients, and 0:


uα,β (v) = max max {wj · v + βj }, 0 ,
(15)
j∈[J]

where each wjk = 1/(1 + e−αjk ), for αjk ∈ R, j ∈ [J], k ∈ M , and βj ∈ R. By bounding the
hyperplane coefficients to [0, 1], we guarantee that the function is 1-Lipschitz.
Theorem 4.2. For any α ∈ RmJ and β ∈ RJ , the function uα,β is non-negative, monotonically
non-decreasing, convex and 1-Lipschitz w.r.t. the `1 -norm.
See Appendix C for the proof.
The utility function, represented as a single layer neural network, is illustrated in Figure 8(a),
where each hj (b) = wj · b + βj . Figure 8(b) shows an example of a utility function represented by
RochetNet for m = 1. By using a large number of hyperplanes, one can use this neural network
architecture to search over a sufficiently rich class of monotone, convex 1-Lipschitz utility functions.
Once trained, the mechanism (g, p) can be derived from the gradient of the utility function, with
the allocation rule given by:
g(b) = ∇uα,β (b),
(16)
and the payment rule is given by the difference between the expected value to the bidder from the
allocation and the bidder’s utility:
p(b) = ∇uα,β (b) · b − uα,β (b).

(17)

Here the utility gradient can be computed as: ∇j uα,β (b) = wj ∗ , for j ∗ ∈ argmaxj∈[J] {wj ·b + βj }.
We seek to minimize the negated, expected revenue:


−Ev∼F ∇uα,β (v) · v − uα,β (v) .
(18)
17

To ensure that the objective is a continuous function of the parameters α and β (so that the
parameters can be optimized efficiently), the gradient term is computed approximately by using a
softmax operation in place of the argmax. The loss function that we use is given by the negated
revenue with approximate gradients:


e α,β (v) · v − uα,β (v) ,
(19)
L(α, β) = −Ev∼F ∇u
where
e k uα,β (v) =
∇

X

wjk sof tmaxj w1 · v + β1 , . . . , wJ · v + βJ



(20)

j∈[J]

We seek to optimize the parameters of the neural network α ∈ RmJ , β ∈ RJ to minimize loss L
Given a sample S = {v (1) , . . . , v (L) } drawn from F , we optimize an empirical version of the loss.
Our approach easily extends to a bidder with unit-demand valuations. In this case, the sum
of the allocation probabilities cannot exceed 1.
This is enforced by restricting the coefficients for
Pm
each hyperplane to sum up to at most 1, i.e. k=1 wjk ≤ 1, ∀j ∈ [J]. It can be verified that even
with this restriction, the induced utility function continuous to be monotone, convex and Lipschitz,
ensuring that the resulting mechanism is DSIC.7
A possible interpretation of the RochetNet architecture is that the network maintains a menu
of (randomized) allocations and prices, and chooses the option from the menu that maximizes the
bidder’s utility based on the bidder’s bid. Each linear function hj (b) = wj · b + βj in RochetNet
corresponds to an option on the menu, with the allocation probabilities and payments encoded
through the parameters wj and βj respectively.

4.2

Experimental Results for RochetNet

We first consider the same distributions used to evaluate RegretNet in Section 3. We model the
induced utility function as a max network over 200 linear functions. The results provided in Table 1
(Section 3) show that the revenue of the trained mechanisms are close to the optimal revenue. Table
2 shows the results for the single bidder, 10 item distribution, where the revenue from RochetNet
is similar to or better than the baselines.
In Figure 9(a), we show the allocation rule learned by RochetNet for the Unit-demand Uniform
II setting, involving a single bidder with unit-demand preferences over two items. Notice that unlike
RegretNet, which could not recover the null allocation region at bottom left of the allocation plot
(see Figure 5(a)), RochetNet is able to recover the optimal mechanism accurately. The allocation
rules learned by RochetNet for the other distributions are shown in Figure 10. Generally, RochetNet
is able to yield sharper decision boundaries than RegretNet, and match the optimal mechanism
more closely. This is because for the valuation distributions considered, the optimal mechanism
can be described by a finite menu of allocations and payments, and RochetNet effectively recovers
the optimal menu of options for these distributions.
Finally, we use RochetNet to test a conjecture of Daskalakis et al. [17] for a single additive bidder,
two item settings where the item valuations are drawn independently from uniform distributions.
The authors conjecture that the optimal mechanism for these settings will assign zero utility to
a subset of valuations that have a pentagonal shape. We applied RochetNet to various valuation
distributions of the above form (including Additive Uniform I and II), and find that the learned
mechanisms have allocation plots where the zero utility regions do indeed have a (full or degenerate)
pentagonal shape. For example, in Figure 9(b), we show the allocation plots for a mechanism
7

The original characterization of Rochet [47] applies to general, convex outcome spaces (which—as one can verify—
is indeed the case here).

18

(a)

(b)

Figure 9: (a) Allocation rule learned by RochetNet for the single unit-demand bidder, two items setting
with item values v1 ∼ U [2, 3] and v2 ∼ U [2, 3]. The bottom-left region where the optimal mechanism of
Pavlov [44] makes no allocation is recovered here, but is not present in Figure 5. (b) Allocation rule learned
by RochetNet for the single additive bidder, two items setting with values v1 ∼ U [0, 4] and v2 ∼ U [0, 3]. The
subset of valuations (v1 , v2 ) where the bidder receives neither item forms a pentagonal shape.

learned by RochetNet for a setting with valuations v1 ∼ U [0, 4] and v2 ∼ U [0, 3]. Notice that there
is a pentagonal region where the bidder receives neither item, thus lending evidence in support of
Daskalakis et al.’s conjecture. This demonstrates the use of RochetNet as a tool for gaining insights
into the structure of optimal auctions.

5

Conclusion

Our work shows that tools from machine learning can re-discover theoretical results such as Myerson [41]’s optimal single-item auction, the Manelli and Vincent [36], Pavlov [44], Haghpanah and
Hartline [26] and Daskalakis et al. [18] mechanisms for a single bidder and two items, Yao [56] and
Sandholm and Likhodedov [48] for multiple bidders and two items, and provides some evidence for
the helpfulness of techniques from deep learning beyond these settings.
We believe that this is the starting point of a very fruitful research agenda of machine-aided
mechanism design, which could lead to new theoretical insight as well as new, practical mechanisms.
It would be interesting, for example, to see if our framework can be used to obtain additional insights
into the structure of optimal DSIC mechanisms. A particularly promising direction are auction
settings with n > 1 bidders and two items, where Yao [56] provides a partial characterization.
More generally, the power of deep learning is that it can, through representation learning, find
good or close-to-optimal designs in complex settings for which clean analytical characterizations
are unlikely. The framework can, in principle, be extended to the design of mechanisms for settings
with correlated values, to problems without money [25] or with budget constraints [22], as well as
to embrace additional desiderata such as envy-free and stable outcomes.
19

(a)

(b)

(c)

Figure 10: (a) Allocation rule learned by RochetNet for the single additive bidder, two items setting with
item values v1 , v2 ∼ U [0, 1]. The numbers in orange are the probability the item is allocated in a region. The
optimal mechanism of Manelli and Vincent [36] is described by the regions separated by the dashed orange
lines. (b) Allocation rule learned by RochetNet for the single additive bidder, two items setting with values
v1 ∼ U [4, 16] and v2 ∼ U [4, 7]. The optimal mechanism of Daskalakis et al. [18] is described by the regions
separated by the dashed orange lines. (c) Allocation rule learned by RochetNet for the single additive bidder,
two items setting with values v1 , v2 drawn jointly, uniformly from a triangle with vertices (0, 0), (0, 1) and
(1, 0). The optimal mechanism of Haghpanah and Hartline [26] is described by the regions separated by the
dashed orange lines.

It would also be interesting to see to which other notions of incentive compatibility—such
as (weak or strong) group-strategyproofness or obvious strategyproofness—our framework can be
extended.

References
[1] M. Albert, V. Conitzer, and P. Stone. 2017. Mechanism Design with Unknown Correlated
Distributions: Can We Learn Optimal Mechanisms?. In Proceedings of the 16th Conference on
Autonomous Agents and MultiAgent Systems. 69–77.
[2] M. Babaioff, N. Immorlica, B. Lucier, and S. M. Weinberg. 2014. A Simple and Approximately
Optimal Mechanism for an Additive Buyer. In Proceedings of the 55th IEEE Symposium on
Foundations of Computer Science. 21–30.
20

[3] M-F. Balcan, T. Sandholm, and E. Vitercik. 2016. Sample Complexity of Automated Mechanism Design. In Proceedings of the 29th Conference on Neural Information Processing Systems.
2083–2091.
[4] Y. Bengio, A. Courville, and P. Vincent. 2013. Representation learning: A review and new
perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence 35, 8 (2013),
1798–1828.
[5] D. P. Bertsekas. 2014. Constrained optimization and Lagrange multiplier methods. Academic
press.
[6] G. Birkhoff. 1946. Tres observaciones sobre el algebra lineal. Universidad Nacional de Tucumán, Revista A 5 (1946), 147–151.
[7] G. Brero, B. Lubin, and S. Seuken. 2017. Probably Approximately Efficient Combinatorial
Auctions via Machine Learning. In Proceedings of the 21st AAAI Conference on Artificial
Intelligence. 397–405.
[8] Y. Cai, C. Daskalakis, and M. S. Weinberg. 2012. Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. In Proceedings of the 53rd IEEE Symposium
on Foundations of Computer Science. 130–139.
[9] Y. Cai, C. Daskalakis, and S. M. Weinberg. 2012. An algorithmic characterization of multidimensional mechanisms. In Proceedings of the 44th ACM Symposium on Theory of Computing.
459–478.
[10] Y. Cai, C. Daskalakis, and S. M. Weinberg. 2013. Understanding Incentives: Mechanism Design
Becomes Algorithm Design. In Proceedings of the 54th IEEE Symposium on Foundations of
Computer Science. 618–627.
[11] Y. Cai and M. Zhao. 2017. Simple Mechanisms for Subadditive Buyers via Duality. In Proceedings of the 49th ACM Symposium on Theory of Computing. 170–183.
[12] S. Chawla, J. D. Hartline, D. L. Malec, and B. Sivan. 2010. Multi-parameter mechanism
design and sequential posted pricing. In Proceedings of the 42th ACM Symposium on Theory
of Computing. 311–320.
[13] R. Cole and T. Roughgarden. 2014. The sample complexity of revenue maximization. In
Proceedings of the 46th ACM Symposium on Theory of Computing. 243–252.
[14] V. Conitzer and T. Sandholm. 2002. Complexity of Mechanism Design. In Proceedings of the
18th Conference on Uncertainty in Artificial Intelligence. 103–110.
[15] V. Conitzer and T. Sandholm. 2004. Self-interested automated mechanism design and implications for optimal combinatorial auctions. In Proceedings of the 5th ACM Conference on
Electronic Commerce. 132–141.
[16] C. Daskalakis. 2015. Multi-item auctions defying intuition? SIGecom Exchanges 14, 1 (2015),
41–75.
[17] C. Daskalakis, A. Deckelbaum, and C. Tzamos. 2013. Mechanism design via optimal transport.
In Proceedings of the 14th ACM Conference on Electronic Commerce. 269–286.

21

[18] C. Daskalakis, A. Deckelbaum, and C. Tzamos. 2017. Strong Duality for a Multiple-Good
Monopolist. Econometrica 85 (2017), 735–767. Issue 3.
[19] N. R. Devanur, Z. Huang, and C.-A. Psomas. 2016. The sample complexity of auctions with
side information. In Proceedings of the 48th ACM Symposium on Theory of Computing. 426–
439.
[20] S. Dughmi, L. Han, and N. Nisan. 2014. Sampling and Representation Complexity of Revenue
Maximization. In Proceedings of the 10th Conference on Web and Internet Economics. 277–
291.
[21] P. Dütting, F. Fischer, P. Jirapinyo, J. Lai, B. Lubin, and D. C. Parkes. 2014. Payment Rules
through Discriminant-Based Classifiers. ACM Transactions on Economics and Computation
3, 1 (2014), 5.
[22] Z. Feng, H. Narasimhan, and D. C. Parkes. 2018. Deep Learning for Revenue-Optimal Auctions
with budgets. In Proceedings of the 17th International Conference on Autonomous Agents and
Multiagent Systems. To appear.
[23] D. Fudenberg and A. Liang. 2018. Predicting and Understanding Initial Play. (2018). Available
at SSRN: https://ssrn.com/abstract=3076682.
[24] Y. Giannakopoulos and E. Koutsoupias. 2015. Selling Two Goods Optimally. In Proceedings
of the 42nd International Colloquium on Automata, Languages, and Programming. 650–662.
[25] N. Golowich, H. Narasimhan, and D. C. Parkes. 2018. Deep Learning for Multi-Facility Location Mechanism Design. Technical report, Harvard SEAS (2018). Available upon request.
[26] N. Haghpanah and J. Hartline. 2015. Multi-dimensional Virtual Values and Second-degree
Price Discrimination. CoRR abs/1404.1341 (2015).
[27] S. Hart and N. Nisan. 2017. Approximate revenue maximization with multiple items. Journal
of Economic Theory 172 (2017), 313–347.
[28] J. S. Hartford, G. Lewis, K. Leyton-Brown, and M. Taddy. 2017. Deep IV: A Flexible Approach
for Counterfactual Prediction. In Proceedings of the 34th International Conference on Machine
Learning. 1414–1423.
[29] Jason S Hartford, James R Wright, and Kevin Leyton-Brown. 2016. Deep learning for predicting human strategic behavior. In Proceedings of the 29th Conference on Neural Information
Processing Systems. 2424–2432.
[30] Z. Huang, Y. Mansour, and T. Roughgarden. 2015. Making the Most of Your Samples. In
Proceedings of the 16th ACM Conference on Economics and Computation. 45–60.
[31] K. Kawaguchi. 2016. Deep Learning without Poor Local Minima. In Proceedings of the 30th
Conference on Neural Information Processing Systems. 586–594.
[32] V. Krishna. 2009. Auction Theory (2nd ed.). Academic Press.
[33] Sébastien Lahaie. 2011. A Kernel-Based Iterative Combinatorial Auction. In Proceedings of
the 25th AAAI Conference on Artificial Intelligence. 695–700.
[34] Y. LeCun, Y. Bengio, and G. Hinton. 2015. Deep learning. Nature 521, 7553 (2015), 436–444.
22

[35] C. Louizos, U. Shalit, J. M. Mooij, D. Sontag, R. S. Zemel, and M. Welling. 2017. Causal
Effect Inference with Deep Latent-Variable Models. In Proceedings of the 30th Conference on
Neural Information Processing Systems. 6449–6459.
[36] A. Manelli and D. Vincent. 2006. Bundling as an optimal selling mechanism for a multiple-good
monopolist. Journal of Economic Theory 127, 1 (2006), 1–35.
[37] T. M. Mitchell. 1997. Machine learning. McGraw-Hill.
[38] M. Mohri and A. M. Medina. 2016. Learning Algorithms for Second-Price Auctions with
Reserve. Journal of Machine Learning Research 17 (2016), 74:1–74:25.
[39] M. Moravčı́k, M. Schmid, N. Burch, V. Lisý, D. Morrill, N. Bard, T. Davis, K. Waugh, M.
Johanson, and M. Bowling. 2017. DeepStack: Expert-level artificial intelligence in heads-up
no-limit poker. Science (2017).
[40] J. Morgenstern and T. Roughgarden. 2015. On the Pseudo-Dimension of Nearly Optimal
Auctions. In Proceedings of the 28th Conference on Neural Information Processing Systems.
136–144.
[41] R. Myerson. 1981. Optimal Auction Design. Mathematics of Operations Research 6 (1981),
58–73.
[42] H. Narasimhan, S. Agarwal, and D. C. Parkes. 2016. Automated Mechanism Design without
Money via Machine Learning. In Proceedings of the 25th International Joint Conference on
Artificial Intelligence. 433–439.
[43] H. Narasimhan and D. C. Parkes. 2016. A General Statistical Framework for Designing
Strategy-proof Assignment Mechanisms. In Proceedings of the Conference on Uncertainty in
Artificial Intelligence.
[44] G. Pavlov. 2011. Optimal Mechanism for Selling Two Goods. B.E. Journal of Theoretical
Economics 11 (2011), 1–35. Issue 1.
[45] A. D. Procaccia, A. Zohar, Y. Peleg, and J. S. Rosenschein. 2009. Artificial Intelligence 173
(2009), 1133–1149.
[46] M. Raghu, A. Irpan, J. Andreas, R. Kleinberg, Q. V. Le, and J. M. Kleinberg. 2017. Can
Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games? CoRR abs/1711.02301
(2017).
[47] J.-C. Rochet. 1987. A Necessary and Sufficient Condition for Rationalizability in a Quasilinear
Context. Journal of Mathematical Economics 16 (1987), 191–200.
[48] T. Sandholm and A. Likhodedov. 2015. Automated Design of Revenue-Maximizing Combinatorial Auctions. Operations Research 63, 5 (2015), 1000–1025.
[49] J. Sill. 1998. Monotonic networks. In Proceedings of the 12th Conference on Neural Information
Processing Systems. 661–667.
[50] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser,
I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. P. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis.
23

2016. Mastering the game of Go with deep neural networks and tree search. Nature 529, 7587
(2016), 484–489.
[51] P. Tang. 2017. Reinforcement mechanism design. In Proceedings of the 26th International Joint
Conference on Artificial Intelligence. 5146–5150.
[52] D. Thompson, N. Newman, and K. Leyton-Brown. 2017. The Positronic Economist: A Computational System for Analyzing Economic Mechanisms. In Proceedings of the 31st AAAI
Conference on Artificial Intelligence. 720–727.
[53] J. von Neumann. 1953. A certain zero-sum two-person game equivalent to an optimal assignment problem. Annals of Mathematical Studies 28 (1953), 5–12.
[54] S. Wright and J. Nocedal. 1999. Numerical optimization. Springer (1999).
[55] A. C-C. Yao. 2015. An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications.
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms. 92–109.
[56] A. C-C. Yao. 2017. Dominant-Strategy versus Bayesian Multi-item Auctions: Maximum Revenue Determination and Comparison. In Proceedings of the 18th ACM Conference on Economics and Computation. 3–20.

A

RegretNet Architecture

We show the RegretNet architecture for a single-item auction in Figure 11, for a single bidder with
additive preferences over multiple items in Figure 12, and for a single bidder with unit-demand
preferences over multiple items in Figure 13.
sof tmax
b1

(1)
h1

b2

h2

. . . h2

..
.

..
.

(1)

..
.
bm

(1)

hJ1

(R)
h1

z1

b1

c1

(R)

z2

b2

..
.

(R)

hJR

..
.
zn

bn

(a) Allocation network g

(1)

c1

c2

(1)

. . . c2

..
.
(1)

cJ 0

1

(T )

relu

p1

(T )

relu

p2

..
.

..
.

(T )

cJ 0

T

relu

pn

(b) Payment network p

Figure 11: RegretNet: The allocation and payment networks for a setting with n bidders and a single item.

B

Augmented Lagrangian Method for Constrained Optimization

We give a brief description of the Augmented Lagrangian method for solving constrained optimization problems [5]. We use this method for solving neural network training problems involving
equality constraints.

24

(1)

h1

(1)

b1

h1

b2

h2
..
.

bm

..
.
(1)

hJ1

(R)

σ

z1

b1

c1

. . . h2

(R)

σ

z2

b2

c2

..
.

..
.

(R)

σ

hJR

..
.
zm

(1)

c1

(T )

(1)

. . . c2

..
.
(1)

cJ 0

bm

1

(a) Allocation network g

(T )

relu

p1

..
.
(T )

cJ 0

T

(b) Payment network p

Figure 12: RegretNet: The allocation and payment networks for a setting with a single bidder and m
items.
sof tmax
b1

(1)
h1

b2

h2

. . . h2

..
.

..
.

(1)

..
.

z1

(R)

z2
..
.

(R)

(1)

bm

(R)
h1

zm

hJR

hJ1

Figure 13: RegretNet: The allocation network for a setting with a single unit-demand bidder and
P m items.
The allocation probabilities for z1 , . . . , zm are computed using a softmax function to ensure that j=1 zj ≤ 1.

Consider the following optimization problem with s equality constraints:
min C(w)

(21)

w∈Rd

s.t.

gj (w) = 0, ∀j = 1, . . . , s.

The augmented Lagrangian method formulates an unconstrained objective, involving the Lagrangian for the above problem, augmented with additional quadratic penalty terms that penalize
violations in the equality constaints:
Cρ (w, λ) = C(w) +

s
X
j=1

s

ρX
(gj (w))2 ,
λj gj (w) +
2
j=1

where λ = [λ1 , . . . , λs ] is a vector of Lagrange multipliers associated with the equality constraints,
and ρ > 0 is a parameter that controls the weight on the penalty terms for violating the constraints.
The method then performs the following sequence of updates:
wt+1 ∈ argminw∈Rd Cρ (w, λt )

(22)

λt+1
j

(23)

=

λtj

− ρ gj (w

t+1

).

One can set the penalty parameter ρ to a very large value (i.e. set a high cost for violating
the equality constraints), so that method converges to a (locally) optimal solution to the original
25

constrained problem (21). However, in practice, this can lead to numerical issues in applying the
solver updates. Alternatively, the theory shows that under some conditions on the iterates of the
solver, any value of ρ above a certain threshold will take the solver close to a locally optimal solution
to (21) (see e.g. Theorem 17.6 in [54]).
In our experiments, we apply the augmented Lagrangian method to solve neural network revenue
optimization problems, where we implement the inner optimization within the solver updates using
mini-batch stochastic subgradient descent. We find that even for small values of ρ, with sufficient
number of iterations, the solver converges to auction designs that yield near-optimal revenue while
closely satisfying the IR/regret constraints (see experimental results in Sections 3).
Finally, we point out that the described method can also be applied to optimization problems
with inequality constraints hj (w) ≤ 0 by formulating equivalent equality constraints of the form
max{0, hj (w)} = 0.

C

Proof for Theorem 2.3

Proof. The convexity of uα,β follows from the fact it is a ‘max’ of linear functions. We now show
that uα,β is monotonically non-decreasing. Let hj (v) = wj · v + βj . Since wj is non-negative in all
entries, for any vi ≤ vi0 , ∀i ∈ M , we have hj (v) ≤ hj (v 0 ). Then
uα,β (v) = max hj (v) = hj∗ (v) ≤ hj∗ (v 0 ) ≤ max hj (v 0 ) = uα,β (v 0 ),
j∈[J]

j∈[J]

where j∗ ∈ argminj∈[J] hj (v). It remains to be shown that uα,β is 1-Lipschitz. For any v, v 0 ∈ Rm
≥0 ,
|uα,β (v) − uα,β (v 0 )| = | max hj (v) − max hj (v 0 )| ≤ max |hj (v 0 ) − hj (v)|
j∈[J]

j∈[J]

j∈[J]

0

= max |wj · (v − v)| ≤ max kwj k∞ |v 0 − v|1 ≤ |vk0 − vk |1
j∈[J]

j∈[J]

where the last inequality holds because each component wjk = σ(αjk ) ≤ 1.

D

MyersonNet for Single-item Auctions

We consider a setting with a single item to be sold, i.e. m = 1, and each bidder holds a private
value vi ∈ R≥0 for the item. We consider a randomized mechanism (g, p) that maps a reported bid
n
profile b ∈ Rn≥0 to a vector of allocation probabilities
Pn g(b) ∈ R≥0 , where gi (b) ∈ R≥0 denotes the
probability that bidder i is allocated the item and i=1 gi (b) ≤ 1. We shall represent the payment
rule pi via a price conditioned on the item being allocated to bidder i, i.e. pi (b) = gi (b) ti (b) for
some conditional payment function ti : Rn≥0 → R≥0 . The expected revenue of the mechanism, when
bidders are truthful, is given by:
X

n
rev(g, p) = Ev∼F
gi (v) ti (v) .
(24)
i=1

The structure of the revenue-optimal auction is well understood for this setting.
Theorem D.1 (Myerson [41]). There exist a collection of monotonically increasing functions φ̄i :
Vi → R called the ironed virtual valuation functions such that the optimal BIC mechanism for
selling a single item is the DSIC mechanism that assigns the item to the buyer i with the highest
ironed virtual value φ̄i (vi ) assuming this quantity is positive and charges the winning bidder the
smallest bid that ensures that the bidder is winning.
26

From Myerson’s characterization, the optimal auction for regular distributions is deterministic
and can be described by a set of strictly monotone virtual value transformations φ̄1 , . . . , φ̄n :
R≥0 → R≥0 . The auction can be viewed as applying the monotone transformations to the input
bids b̄i = φ̄i (bi ), feeding the computed virtual values to a second price auction (SPA) with zero
0
reserve price (g 0 , p0 ), making an allocation according to g 0 (b̄), and charging a payment φ̄−1
i (pi (b̄))
for agent i. In fact, this auction is DSIC for any choice of the strictly monotone virtual value
functions:
Theorem D.2. For any set of strictly monotonically increasing functions φ̄1 , . . . , φ̄n : R≥0 → R≥0 ,
an auction defined by outcome rule gi = gi0 ◦ φ̄ and payment rule pi = φ̄−1
◦ p0i ◦ φ̄ is DSIC and
i
IR.
Thus designing the optimal DSIC auction for a regular distribution reduces to finding a set of
strictly monotone virtual value functions that, when composed with the second price auction with
zero reserve, yields maximum expected revenue. In the case of irregular distributions, the optimal
mechanism is characterized by ironed virtual value transformations, which need not be strictly
monotone or invertible. Hence the prescribed template of using strictly monotone transforms in
conjuction with a SPA with zero reserve may not exactly recover the optimal mechanism. We shall
see that the proposed approach can still be used to design mechanisms that yield revenue very close
to the optimal revenue in the irregular case. See Figure 14(a) for the overall design of the neural
network in this setting.
Modeling monotone transforms. We model each virtual value function φ̄i as a two-layer feedforward network with min and max operations over linear functions. For K groups of J linear
i ∈ R , k = 1, . . . , K, j = 1, . . . , J and intercepts
functions, with strictly positive slopes wkj
>0
i
βkj ∈ R, k = 1, . . . , K, j = 1, . . . , J, we define:
i
i
.
bi + βkj
φ̄i (bi ) = min max wkj
k∈[K] j∈[J]

Since each of the above linear function is strictly non-decreasing, so is φ̄i . In practice, we can set
i = eαikj for parameters αi ∈ [−B, B] in a bounded range. A graphical representation of
each wkj
kj
the neural network used for this transform is shown in Figure 14(b). For sufficiently large K and
J, this neural network can be used to approximate any continuous, bounded monotone function
(that satisfies a mild regularity condition) to an arbitrary degree of accuracy [49]. A particular
advantage of this representation is that the inverse transform φ̄−1 can be directly obtained from
the parameters for the forward transform:
i

−αkj
i
φ̄−1
(y − βkj
).
i (y) = max min e
k∈[K] j∈[J]

Modeling SPA with zero reserve. We also need to model a SPA with zero reserve (SPA-0)
within the neural network structure. A neural network is usually a continuous function of its
inputs, so that its parameters can be optimized efficiently. Since the allocation rule here is a
discrete mapping (from bidder bids to the winning bidder), for the purpose of training, we employ
a smooth approximation to the allocation rule using a neural network. Once we obtain the optimal
virtual value functions using the approximate allocation rule, we use them in conjunction with an
exact SPA with zero reserve, to construct the final mechanism.
The SPA-0 allocation rule g 0 allocates the item to the bidder with the highest virtual value,
if the virtual value is greater than 0, and leaves the item unallocated otherwise. This can be

27

SPA-0
b1

φ̄1

g0

(z1 , . . . , zn )

..
.
bn

φ̄−1
1
φ̄−1
n

max

..
.

..
.

hK,1
..
.
hK,J

max

bi

t1

..
.

p0

φ̄n

h1,1
..
.
h1,J

tn

(a)

min

b̄i

(b)

Figure 14: (a) MyersonNet: The network applies monotone transformations φ̄1 , . . . , φ̄n to the input
bids, passes the virtual values to the SPA-0 network in Figure 15, and applies the inverse tranformations
αikj
−1
i
φ̄−1
bi + βkj
.
1 , . . . , φ̄n to the payment outputs; (b) Monotone virtual value function φ̄i , where hkj (bi ) = e
sof tmax
b̄1

z1

b̄2

z2
..
.

b̄n
0

b̄1

max

t01

b̄2

max

t02

..
.

..
.
zn−1
zn

(a) Allocation rule g 0

..
.

b̄n

max

t0n−1

0

max

t0n

(b) Payment rule t0

Figure 15: SPA-0 network for (approximately) modeling a second price auction with zero reserve price.
The inputs are (virtual) bids b̄1 , . . . , b̄n and the output is a vector of assignment probabilities z1 , . . . , zn and
prices (conditioned on allocation) t01 , . . . , t0n .

approximated using a ‘softmax’ function on the virtual values b̄1 , . . . , b̄n and an additional dummy
input b̄n+1 = 0:
eκb̄i
, i ∈ N,
gi0 (b̄) = Pn+1
κb̄j
j=1 e

(25)

where κ > 0 is a constant fixed apriori, and determines the quality of the approximation. The
higher the value of κ, the better is the approximation, but the less smooth is the resulting allocation
function (and thus it becomes harder to optimize).
The SPA-0 payment to bidder i (conditioned on being allocated) is the maximum of the virtual
values from the other bidders, and zero:

t0i (b̄) = max max b̄j , 0 , i ∈ N.
(26)
j6=i

Let g α,β and tα,β denote the allocation and conditional payment rules for the overall mechanism
in Figure 14(a), where (α, β) are the parameters of the forward monotone transform. Given a
sample of valuation profiles S = {v (1) , . . . , v (L) } drawn i.i.d. from F , we optimize the parameters
using the (negative) revenue on S as the error function:
L

n

1 X X α,β (`) α,β (`)
rd
ev(f, p) =
gi (v ) ti (v ).
L
`=1 i=1

We solve this optimization problem using a mini-batch stochastic gradient descent solver.
28

(27)

Distribution

n

Symmetric Uniform: vi ∼ U [0, 1]
Asymmetric Uniform: vi ∼ U [0, i]
Exponential: vi ∼ Exp(3)
Irregular: vi ∼ Firregular

3
5
3
3

Opt
rev
0.531
2.314
2.749
2.368

SPA
rev
0.500
2.025
2.500
2.210

rev
0.535
2.391
2.721
2.349

RegretNet
rgt
irp
0.019 0.0004
0.010
0.003
0.011 0.0004
0.005
0.002

MyersonNet
rev
0.531
2.305
2.747
2.355

1.0

40

0.5

30
Myerson Transformation
Agent 1
Agent 2
Agent 3

0.5
1.0
0.2

0.4

v

0.6

0.8

20
10
0

1.0

0

(a) Symmetric Uniform
2

v

15

20

0.5

0
1

1.0
0.2

0.4

v1

0.6

0.8
4

1.0

Agent 4

2
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
v2

0

1

2

3

4
v

5

6

7

8

3
2
1
0
1
2
3
0.0

Agent 3

0.5

1.0

Agent 5

1.5
v3

2.0

2.5

3.0

4

2

2
5(v5)

4(v4)

Myerson Transformation
Agent 1
Agent 2
Agent 3

(c) Irregular

Agent 2

1

0.0

2(v2)

1(v1)

0.5

0.0

10

8
6
4
2
0
2
4

(b) Exponential

Agent 1

1.0

5

3(v3)

0.0

Myerson Transformation
Agent 1
Agent 2
Agent 3
(v)

0.0

(v)

(v)

Table 6: The revenue of the single-item auctions obtained with RegretNet.

0

0
2

2

4

4
0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0
v4

0

1

2

v5

3

4

5

(d) Asymmetric Uniform
Figure 16: Virtual value transformations learned by MyersonNet for each agent and of the optimal auction.
The zero intercepts of most of the learned transforms are close to that of the optimal transforms. In many
cases, the slopes of the learned transforms above the zero intercept are roughly a positive scalar multiple of
the optimal transform, with the scalar being almost the same across agents.

E
E.1

Experimental Results for Single-Item Auctions
Results for MyersonNet

We evaluate the MyersonNet for designing single-item auctions on three regular distributions: (a)
symmetric uniform distribution with 3 bidders and each vi ∼ U [0, 1], (b) asymmetric uniform
distribution with 5 bidders and each vi ∼ U [0, i], and (c) exponential distribution with 3 bidders
and each vi ∼ Exp(3). We study auctions with a small number of bidders because this is where
revenue-optimal auctions are meaningfully different from efficient auctions. The optimal auctions
for these distributions involve virtual value functions φ̄i that are strictly monotone. We also consider
an irregular distribution Firregular , where each vi is drawn from U [0, 3] with probability 3/4 and
from U [3, 8] with probability 1/4. In this case, the optimal auction uses ironed virtual value
functions that are not strictly monotone. The training set and test set each have 1000 valuation
profiles, sampled i.i.d. from the respective valuation distribution. We model each transform φ̄i in
the MyersonNet architecture using 5 sets of 10 linear functions, and set κ = 103 .
29

The results are summarized in Table 6. For comparison, we also report the revenue obtained
by the optimal Myerson auction and the second price auction (SPA) without reserve. The auctions
learned by the neural network yield revenue close to the optimal.
The monotone virtual value transform inferred by the neural network for each bidder is shown
in Figure 16. It can be verified that two auctions with virtual value transforms φ̄1 , . . . , φ̄n and
φ̄01 , . . . , φ̄0n are equivalent if for each bidder i, φ̄i and φ̄0i have the same zero intercept, and there exists
a scalar γ > 0 such that for each bidder i, φ̄i (x) = γ φ̄0i (x) for all x above the zero intercept. With
the symmetric uniform and exponential distributions, the learned transform for each bidder has
the same zero intercept as the optimal transform for the bidder. Also, the learned transforms have
very similar slopes above the zero intercept. This is also seen with most agents in the asymmetric
uniform setting, where the learned transform above the zero intercept has almost the same slope
as the optimal transform. This indicates that the learned auctions for these distributions closely
resemble the optimal auctions.
With the irregular distribution, the learned transform for each bidder has almost the same zero
intercept as the optimal transform, but the learned transforms above the zero intercept are not
all the same scalar multiple of the optimal transform. However notice that the learned transforms
closely mimic the ironed flat portion of the optimal transform (albeit with a small non-zero slope
because of the strictness imposed on the transforms by the network architecture). The slight
mismatch between the learned and optimal transforms possibly explains why the revenue of the
learned auction is not as close to the optimal revenue as that for the other distributions.

E.2

Results for RegretNet

We evaluate RegretNet on the same distributions used to evaluate MyersonNet. The results are
shown in Table 6. The RegretNet yields revenue close to optimal, while incurring a small regret
(< 0.02) and a small IR penalty. In the case of the symmetric uniform distribution, the network is
able to achieve a slightly higher revenue than the optimal auction because it has a non-zero regret
and IR violation.

30

