Auction Learning as a Two-Player Game
Authors: Jad Rahme
Samy Jelassi
S. Matthew Weinberg
Venue: ICLR 2021 Poster (2021)
Keywords: Mechanism Design
Auction Theory
Game Theory
Deep Learning

Abstract: Designing an incentive compatible auction that maximizes expected revenue is a central problem in Auction Design. While theoretical approaches to the problem have hit some limits, a recent research direction initiated by Duetting et al. (2019) consists in building neural network architectures to find optimal auctions.  We propose two conceptual deviations from their approach which result in enhanced performance. First, we use recent results in theoretical auction design to introduce a time-independent Lagrangian.  This not only circumvents the need for an expensive hyper-parameter search (as in prior work), but also provides a single metric to compare the performance of two auctions (absent from prior work). Second, the optimization procedure in previous work uses an inner maximization loop to compute optimal misreports. We amortize this process through the introduction of an additional neural network. We demonstrate the effectiveness of our approach by learning competitive or strictly improved auctions compared to prior work. Both results together further imply a novel formulation of Auction Design as a two-player game with stationary utility functions.

Published as a conference paper at ICLR 2021
AUCTION LEARNING AS A TWO-PLAYER GAME
Jad Rahme", Samy Jelassi, Matthew Weinberg Princeton University Princeton, NJ 08540, USA (jrahme, sjelassi, smweinberg }@princeton.edu
ABSTRACT
Designing an incentive compatible auction that maximizes expected revenue a central problem in Auction Design. While theoretical approaches to the problem have hit some limits, a recent research direction initiated by Duetting et al. (2019) consists in building neural network architectures find optimal auctions. We propose two conceptual deviations from their approach which result in enhanced performance. First, we recent results in theoretical auction design introduce a time-independee Lagrangian. This not only circumvents the need for an expensive hyper-paramee apper-parameter search (as in prior work), but also provides single metric compare the performance of two auctions (absent from prior work). Second, optimization procedure previous work uses an inner maximization loop compute optimal misreports. We amortize this process through the introduction of an additional neural network. We demonstrate the effectiveness our approach by learning competitive strictly improved auctions compared to prior work. Both results together further imply a novel formulation of Auction Design as a two-player game with stationary utility functions.
INTRODUCTION
Efficiently designing truthful auctions is a core problem in Mathematical Economics. Concrete examples include the sponsored search auctions conducted by companies Google auctions on platforms as eBay. Following seminal work of Vickrey (Vickrey, 1961) and Myerson (Myerson, 1981), auctions are typically studied in the independent private valuations model: each bidder has valuation function over items, and their payoff depends only on the items they receive. Moreover, the auctioneer knows aggregate information about the population that each bidder comes from, modeled as distribution over valuation functions, but does not know precisely each bidder's valuation (outside of any information in this Bayesian prior). A major difficulty in designing auctions is that valuations are private and bidders need to be incentivized to report their valuations truthfully. The goal of the auctioneer to design an incentive compatible auction which maximizes expected revenue.
Auction Design has existed characterizations of the optimal auction only exist for a few settings. While Myerson's 's Nobel prize- winning work provides a clean characterization of the single-item optimum (Myerson, 1981), optimal multi-item auctions provably suffer from numerous formal measures of intractability (including computational intractability, high description complexity, non-monotonicity, and others) (Daskalakis et al., 2014; Chen et al., 2014; 2015; 2018; Hart & Reny, 2015; Thanassoulis, 2004).
rigorous mathematical field for several decades and yet, complete
An orthogonal line of work instead develops deep learning architectures to find the optimal auction. Duetting et al. (2019) initiated this direction by proposing RegretNet, a feed-forward architecture They frame the auction design problem as a constrained learning problem and lift the constraints into the objective via the augmented Lagrangian method. Training RegretNet involves optimizing this Lagrangian-penainn penalized objective, while simultaneously updating network parameters and the Lagrangian multipliers themselves. This architecture produces impressive results: recovering near- optimal auctions in several known multi-item settings, and discovering new mechanisms when theoretical optimum unknown.
Yet, this approach presents several limitations. On the conceptual front, our main insight connection to an exciting line of recent works (Hartline & Lucier, 2010; Hartline et al., 2011: Bei &
"Corresoonding author

---

Published as a conference paper at ICLR 2021
Huang, 2011; Daskalakis & Weinberg. 2012; Rubinstein & Weinberg, 2018; Dughmi et al., 2017; Cai et al., 2019) on e-truthful-to-truubie reductions." On the technical front, we identify three areas for improvement. First, their architecture is difficult to train in practice as the objective is non- stationary. Specifically, the I Lagrangian multipliers are time-dependent and they increase following pre-defined schedule, which requires careful hyperparameter tuning (see $3.1 for experiments illustrating this). Leveraging the aforementioned works in Auction Theory, we propose a stationary Lagrangian objective. Second, all prior work inevitably finds auctions which are not precisely incentive compatible, and does not provide a metric to compare, say, an auction with revenue 1.01 which is 0.002-truthful, or one with revenue 1 which is 0.001-truthful. We argue that our stationary Lagrangian objectíve serves as a good metric (and that the second auction of our short example "better" for our metric). Finally, their training procedure requires an inner-loop optimization (essentially, this inner loop is the bidders trying to maximize utility in the current auction), which is itself computationally expensive. We use amortized optimization to make this process more efficient.
CONTRIBUTIONS
This paper leverages recent work in Auction Theory to formulate the learning of revenuc-optimal auctions as a two-player game. We develop a new algorithm ALGnet (Auction Learning Game network) that produces competitive or better results compared to Duetting al. (2019)'s RegretNet. In addition to the conceptual contributions, our approach yields the following improvements (as RegretNet is already learning near-optimal auctions, our improvement over RegretNet not due to significantly higher optimal revenues).
Easier hyper- paper-parameter tuning: By constructing a inn-iindepnndent loss function, we circumvent the need to search for an adequate parameter scheduling. Our formulation also involves less hyperparameters, which makes it more robust.
A metric to compare auctions: We propose metric to compare the quality of two auctions which are not incentive compatible.
More efficient training: We replace the inner-loop optimization of prior work with a neural network, which makes training more efficient.
Online auctions: Since the learning formulation is time- invariavv ALGnet is able to quickly adapt in auctions where the bidders' valuation distributions varies over time. Such setting appears for instance in the online posted pricing problem studied in Bubeck et al. (2017).
Furthermore, these technical contributions together now imply a novel formulation of auction learning two-player game (not zero-sum) between auctioneer and a misreporter. The auctioneer is trying to design an incentive compatible auction that maximizes revenue while the misreporter is trying identify breaches in the truthfulness of these auctions. The paper decomposes as follows. Section 2 introduces the standard notions of auction design. Section 3 presents our game formulation for auction learning. Section 4 provides a description of ALGnet and its training procedure. Finally, Section 5 presents numerical evidence for the effectiveness of our approach.
RELATED WORK
Auction design and machine learning. Machine learning and computational learning theory have been used in several ways to design auctions from samples of bidder valuations. Machine learning has been used to amalyze the sample complexity of designing optimal avvenuemmxxmmizin auctions. This includes the framework of
settings (Morgenstern & Roughgarden, 2015; Huang et al., 2018 8; Hartline & Taggart, 2019; Roughgarden & Schrijvers, 2016; Gonczarowski & Nisan, 2017; Guo et al., 2019), multi-item auctions (Dughmi et al., 2014; Gonezarowski & Weinberg, 2018), combinatorial auctions (Balcan et al., 2016; Morgenstern & Roughgarden, 2016; Syrgkanis, 2017) Parkes, 2016). Other works have leveraged machine
and allocation mechanisms (Narasimhan learning to optimize different aspects of mechanisms (Lahaie, 2011; Dütting et al., 2015). Our approach is different as we build a deep learning architecture for auction design.
Auction design and deep learning. While Duetting et al. (2019) is the first paper to design auctions through deep learning, several other paper followed-up this work. Feng al. (2018) extended it to budget constrained bidders, Golowich et al. (2018) to the facility location problem. Tacchetti et al. (2019) built architectures based on the Vickrey- Clarke-Grove mechanism. Rahme et al. (2021) used permutation-cqquvarian networks to design symmetric auctions. Shen et al. (2019) and Duetting
By e-truthful, we mean the expected total regret R is bounded by s. See Prop. for definition of R.
2

---

Published as a conference paper at ICLR 2021
et al. (2019) proposed architectures that exactly satisfy incentive compatibility but are specific to single-bide bidder settings. While all the previously mentioned papers consider a non-stationary objective function, we formulate time-invariant objective that is easier to train and that makes comparisons between mechanisms possible.
2
AUCTION DESIGN AS A TIME-VARYING LEARNING PROBLEM
We first review the framework of auction design and the problem of finding truthful mechanisms. We then recall the learning problem proposed by Duetting et al. (2019) to find optimal auctions.
2.1 AUCTION DESIGN AND LINEAR PROGRAM
Auction design. We consider an auction with n. bidders and m items. We will denote by N = {1. (1.....n)) m and M (1.-.., m) the set of bidders and items. Each bidder i values item j at valuation denoted Vij- We will focus on additive auctions. These are auctions where the value of set S of items equal to the sum of the values of the elements in that set at Djes Uij. Additive auctions perhaps the most well-studied setting in multi-item auction design (Hart & Nisan, 2012; Li & Yao, 2013; Daskalakis et al., 2014; Cai et al., 2016; Daskalakis et al., 2017).
The auctioneer does not know the exact valuation profile V = (Vig) of the bidders in advance but he does know the distribution from which they are drawn: the valuation vector of bidder i, & = (U.1...., Umm) is drawn from a distribution D; over RT We will further assume that all bidders are independent and that Di =... Dr. As result V is drawn from D == Di= D
Definition 1. An auction is defined by a randomized allocation rule g = (gi...., 9n)) and a payment rule p (Pi.....P. PP)) where ge: Rnxm + [0, 11TH and p:: Raxm Rgo. Additionally for all items j and valuation profiles V, the 9i must satisfy E, (V)): <I
Given a bid matrix B (bis KENN))NNJJM... (B)], is the probability that bidder i receives object and (BB is the price bidder has to pay to the auction. The condition L, possibility for an item to be not allocated.
(V)), < allows the
Definition 2. The utility of bidder i is defined by uu B) 19
(B).
Bidders seek to maximize their utility and may report bids that are different from their true valuations. In the following, we will denote by B_; the (n-1) x m bid matrix without bidder i, and by (82 B-.) the m bid matrix that inserts B/ into row of B (for example: B = (b,, B):). We aim at auctions that incentivize bidders to bid their true valuations.
Definition 3. An auction (g. p) is dominant strategy incentive compatible (DSIC) if each bidder's utility is maximized by reporting truthfully matter what the other bidders report. For every bidder i, valuation ūn E Dú, bid b.' D; and bids B_; D_u (; (ū,, B_x)) 2 uz(ū;, (5.', B=))).
Definition 4. An auction is individually rational (IR) if for all i
N, 0g E D; and B D-i;
(T, (ū, B-+)) > 0.
(IR)
In a DSIC auction, the bidders have the incentive to truthfully report their valuations and therefore, the revenue on valuation profile V is Σ (VV.. Optimal auction design aims finding DSIC and IR auction that maximizes the expected revenue TeV := Bv~DD>> p: (V)). Since there is no known characterization of DSIC mechanisms the multi-item setting, we resort to the relaxed notion of ex-post regret. It measures the extent to which auction violates DSIC.
Definition 5. The ex-post regrei for bidder i is the maximum increase in his utility when considering all his possible bids and fixing the bids of others. For valuation profile V, it is given by rv:VV
max Em U,(,, (be', V-)) - -u uu, (U,, V-i)). In particular, DSIC is equivalent to
rv(V) 0, VVV.
(IC)
The bid b2 that achieves rv(V) is called the optimal misreport of bidder i for valuation profile V. Therefore, finding an optimal auction is equivalent the following linear program:
min Σ Pv(V) (MM))M
EVeD
s.t.
rv(V) = (i (T., B BL))) > O, ViEN, 6 D, D.......
ViEN, V.
(LP)
3

---

Published as a conference paper at ICLR 2021
2.2 AUCTION DESIGN AS LEARNING PROBLEM
As the space of auctions M may be large, will set parametric model. In what follows, consider the class of auctions (g" pP") encoded by a neural network of parameter to E Rd. The corresponding utility and regret function will be denoted by u/ and r."
Following Ductting et al. (2019), the formulation (LP) is relaxed: the IC constraint for all V D replaced by the expected constraint Dr> (V)] = for all i E N. The justification for this relaxation can be found in Duetting al. (2019). By replacing expectations with empirical averages, the learning problem becomes:
min wElt
ΣΣ
Pi (V(o) s.t.
P. = L
1 Σ
= Vie..
(LP)
The learning problem (T.P) does not ensure (IR). However, this constraint is usually built into the parametrization (architecture) of the model: by design, the only auction mechanism considered satisfy (IR). Implementation details can be found Duetting et al. (2019); Rahme et al. (2021) in Sec
3 AUCTION LEARNING AS A TWO-PLAYER GAME
We first present the optimization and the training procedures for (LP) proposed by Duetting al. (2019). We then demonstrate with numerical evidence that this approach presents two limitations: hyperparameter sensitivity and lack of interpretability. Using the concept of e-truthful truthful reductions, we construct a new loss function that circumvents these two aspects. Lastly, we resort to amortized optimization and reframe auction learning problem as two-player game.
3.1 THE AUGMENTED LAGRANGIAN METHOD AND ITS SHORTCOMINGS
Optimization and training. We briefly review the training procedure proposed by Duetting et al. (2019) to learn optimal auctions. The authors apply the augmented Lagrangian method to solve the constrained problem (I.P) and consider the loss:
<(w;A; L
Σ E=NEN
(V(()) + Σ (v(((
+P
Σ E (v((v)))) IEN
iEN
where À 12" vector of Lagrange multipliers and p is a parameter controlling the weight of the quadratic penalty. More details about the training procedure can be found in Appendix A.
Scheduling consistency problem. The parameters À and p time-varying, Indeed, their value changes according to a pre-defined scheduling of the following form: 1) Initialize X and p with respectively 2 and p², 2) Update every Tp iterations: -11 p² + c, where c pre-defined constant, 3) Update every Tx iterations according to X + X + p pu
Therefore, this scheduling requires to set up five hyper parameters (A" c, Tx. Some of the experiments found Duetting et al. (2019) were about learning an optimal mechanism for an n-bidder m-item auction (n x m) where the valuations are iid 2/(0, 1). Different scheduling parameters were used for different values of n and m. We report the values of the hyper parameters used for the x 3 x 10 and 5 10 settings in Table 1(a). A natural question is whether the choice of parameters heavily affects the performance. We proceed to a numerical investigation of this questions by trying different schedulings (columns) for different settings (rows) and report the results in Table 1(b).
4

---

Published as a conference paper at ICLR 2021
Table 1: (a): Scheduling parameters values set in Duetting al. (2019) to reach optimal auctions in settings with bidders, m objects and ii.d. valuations sampled from 2/(0, 1]. (b): Revenue rev == Ev>DIE>= [V)) and average regret per bidder reg == 1/n EVED Di=1 (V(V) for n x m settings when using the different parameters values set reported in (a).
Scheduling
x 2
x
10
5 x 10
1 x 2
3 x 10
5 x 10
ot
pd
0.25
Setting
ryt
ryt
ryt
50
0.25
Tx
102
10a
102
1 x
0.552
0.0001
0.573
0.0012
0.332
0.0179
7,
104
10a
10a
3 x
10
4.825
0.0007
5.527
0.0017
5.880
0.0047
x 10
4.768
0.0006
5.424
0.0033
6.749
0.0047
(a)
(b)
The auction returned by the network dramatically varies with the choice of scheduling parameters. When applying the parameters of 1 to 5 x 10, we obtain revenue that is lower by 30%! The performance of the learning algorithm strongly depends on the specific values of the hyperparameters. Finding an adequate scheduling requires an extensive and time consuming hyperparameter search.
Lack of interpretability. How should compare two mechanisms with different expected revenue and regret?
mechanism Mj with revenue Pı = 1.01 and an average total regret R 0.02 better than mechanism M2 with P2 1.0 and R₂ = 0.01 The approach in Duetting et al. (2019) cannot answer this question. To see that, notice that when Àι
An we can rewrite L(w; X; P + XR Rt Which mechanism is better depends the values of À and For example if better. Since the values of À and change with time, the Lagrangian approach in Duetting et al. (2019) cannot provide metric to compare two mechanisms.
and À = 0.1 we find that M1 is better, but if 1 and À = 10 then M2
3.2 TTME-INDEPENDENT AND INTERPRETABLE LOSS FUNCTION FOR AUCTION LEARNING
Our first contribution consists in introducing new loss function for auction learning that addresses the two first limitations of Duetting et al. (2019) mentioned in Section 3.1. We first motivate this loss in the one bidder case and then extend it to auctions with many bidders.
3.2.1 MECHANISMS WITH ONE BIDDER
Proposition 1. [Balcan et al. (2005), attributed to Nisan] Let M be an additive auction with 1 bidder and m items. Let P and R denote the expected revenue and regret, P = EVED [p(V) and
R = EVED (r(V). There exists a mechanism M with expected revenue P (vP / RR) and zero regret R =
proof of this proposition can be found in Appendix C. Comparing mechanisms straightfor- ward when both of them have zero-regret: the best one achieves the highest revenue. Prop. allows natural and simple extension of this criteria for non zero-regret mechanism with one bidder: we will say that Mj is better than M2 if and only if MT is better than M5:
Mi
M2 = (*(M)) > P* (Ma)
VP
R V2
Using our metric, we find that a one bidder mechanism with revenue of 1.00 and regret of 0.01 is "better" than one with revenue 1.01 and regret 0.02.
3.2.2 MECHANISMS WITH MULTIPLE BIDDERS
Let Mj and M2 be two mechanisms with bidders and m objects. Let P; and R; denote their total expected revenue and regret, P. = EVED Σy= (V)) and R. = EVED Σ)=r((()
We can
extend our metric derived in Section 3.2.1 the multiple bidder by the following:
Mj "better" than M₁ < Mi M2
P Ri VP
R₂
When n = 1 we recover the criteria from Section 3.2.1 that is backed by Prop. 1. When n > 1, considered major open problem whether the extension of Prop. still holds. Note that multi- bidder variant of Prop. does hold under a different solution concept termed "Bayesian Incentive Compatible" (Rubinstein & Weinberg, 2018; Cai et al., 2019), supporting the conjecture that Prop. 1
5

---

Published as a conference paper at ICLR 2021
indeed extends. Independently of whether not Prop. holds, this reasoning implies candidate loss function for the multi bidder-bderr setting which we can evaluate empirically.
This way of comparing mechanisms motivates the use of loss function: R) =(P,R)=-(VP-V instead of the Lagrangian from Section 3, and indeed this loss function works well in practice. We empirically find the loss function L. (P, R) (VP /R) R further accelerates training, as it further (slightly) biases towards mechanisms with low regret. Both of these loss function are ineeiindepnndett and hyperparametter-fre.
3.3
AMORTIZED MISREPORT OPTIMIZATION
To compute the regret r. (V) one has to solve the optimization problem: MAX,''RR" ( (0,' - 2 (c,, (0% V-+)). In Ductting et al. (2019), this optimiza- tion problem solved with an inner optimization loop for each valuation profile. In other words, computing the regret of each valuation profiee is solved separately and independently, from scratch. If two valuation profiles are very close to each other, one should expect that the resulting optimization problems to have close results. We leverage this to improve training efficiency.
We propose to amortize this inner loop optimization. Instead of solving all these optimization problems independently, will instead learn one neural network M that tries to predict the solution of all them. M takes as entry a valuation profile and maps it to the optimal misreport:
R Rexm
nxx
M
argmax ED (7, (0, V-:))
The loss Cy that M is trying minimize follows naturally from that definition and is then given by: L, (v,, w) = EVEn DS u, (T,, ([M*(V)), V-.))]
3.4 AUCTION LEARNING AS A TWO-PLAYER GAME
In this section, we combine the ideas from Sections 3.2 and 3.3 to obtain a new formulation for the auction learning problem as two-player game between Auctioneer with parameter and Misreporter with parameter sp. The optimal parameters for the auction learning problem (w" ,""" are Nash Equilibrium for this game.
The Auctioneer trying to design a truthful (IC) and rational (IR) auction that maximizes revenue. The Misreporter is trying maximize the bidders' utility, for the current auction selected by Auctioneer, w. This is achieved by minimizing the loss function C, w) wrt to (as discussed in Sec 3.3). The Auctioneer in turn maximizes expected revenue, for the current misreports chosen by Misreporter. This is achieved by minimizing Lm (w, ip) (VPw++ V Rm with respect to w (as discussed in See 3.2). Here, RF is an estimate of the total regret that auctioneer computes for the current Misreporter y,, R2 E/_ ΣiEN (uf ([M+(V)) V-.) uf (7i, (7, V-;)))
This game formulation can summarized as follows:
Misreporter
loss: (x, w)
Misreporter:
parameter: ip
Misreports
Allocation
(G)
Valuation Profile
Auctioneer
loss: Lm Lm(ww, ip)
Auctioneer:
Poyment
parameter: w
E,
Lm
Remark 1. The game formulation (G) reminds of Generative Adversarial Networks (Goodfellow el al., 2014). Contrary to GANs, it is not a zero-sum game.
2 An auction is Bayesian Incentive Compatible every bidder maximizes their expected utility by truthful reporting in expectation over the other bidders' truthful bids. Compare this to Dominant Strategy Incentive Compatible (our paper), where every bidder maximizes their expected utility by truthful reporting for all realizations of the other bidders' bids.

---

Published as a conference paper at ICLR 2021
4 ARCHITECTURE AND TRAINING PROCEDURE
We describe AL.Get, a feed-forward architecture solving for the game formulation (G) and then provide a training procedure. ALGnet consists in two modules that are the auctioneer's module and the misreporter's ' module. These components take as input bid matrix B = (br,) E R=*m and are trained jointly. Their outputs are used to compute the regret and revenue of the auction.
Notation. We use MLP(ddm, ni, h, dou)) to refer to fully-connected neural network with input dimension din output dimension daut and ny hidden layers of width h and tanh activation function.
sig denotes the sigmoid activation function. Given a matrix B = fbi...., ,6]" E R=**" we define for fixed i N, the matrix BBs) = [bc, by,.............. ......... bi-1, bet1, 5n]-
4.1 THE AUCTIONEER'S S MODULE It is composed of an allocation network that encodes randomized allocation gM R [0, 1 and a payment network that encodes a payment rule p":: Rum -> IR".
Allocation network. It computes the allocation probabily of item j to bidder i [ (B)l as [g (B)ls = [f[]; [B2(B)]s where fi: R=xm - [0, 1] and f2: Ruxm 00, 1 1|mx are functions computed by two ford-forward neural networks.
[f (B)l; is the probability that object j E M is allocated and is given by (B)( = sig (MLP(nm,,, nag ha, n))-
[f2 is the probability that item j E M is allocated to bidder i E N conditioned on object j being allocated. A first MLP computes Ij := MLP(nm, nay has ()) for all j M.
The network then concatenates all these vectors l, into matrix L E Ra A softmax activation function is finally applied to L to ensure feasibility i.e. for all j E M. Lij
1. 1.
Payment network. It computes the payment (B)]; for bidder i as [p" is Σラ= Bi (B))a,, where p:: Ra - [0, 1j" pr is the fraction of bidder's i utility that she has to pay the mechanism. We compute P.- = sig (MLP(rem, ny: np: 1)) (B()). Finally, notice that by construction (B)), < EE "i (B),s which ensures that (IR) is respected.
4.2 THE MISREPORTER S MODULE
The module consists an MLP(nm, nas, har, m) followed by a projection layer Proj that en- sure that the output of the network is in the domain D) of the valuation. For example when the valuations are restricted to [0, 1]. we can take Proj = sig, if they are non negative num- ber,we can take Proj SoftPlus. The optimal misreport for bidder is then given by Proj MLP(nm, RM, has, m) E RT. Stacking these vectors gives us the misreport matrix M (B).
4.3 TRAINING PROCEDURE AND OPTIMIZATION
We optimize the game (G) over the space of neural networks parameters (w, (p). The algo- rithm is easy to implement (Alg. 1).
Algorithm 1 ALGnet training
1: Input: number of agents, number of objects,
At each time 4, we sample a batch of valuation profiles of size B. The algorithm performs 7 updates for the Misreporter's 's network (line 9) and one update on the Auctioneer's 's network
2: Parameter: y > O: B, T, Tiitt Thimit, N.
3: Initialize misreport's 's and auctioneer's 's nets.
4: for I 1,...,7 do
5: if = O mod Tima and < Trimit then: Reinitialize Misreport Network Sample valuation batch S size B. for 8 I,.... do 50+h1 + 4p" -V (p" (S)) w1t1 + w² Wm ())
(line 10). Moreover, we often reinitialize the Misreporter's network every Timit steps in the early phases of the training (l < Tiimit.. This step is not necessary but we found empirically that it speeds up training.
6:
7:
8:
9:
10:
EXPERIMENTAL RESULTS
We show that ALGnet can recover near-optimal auctions for settings where the optimal solution is known and that it can find new auctions for settings where analytical solution are not known. Since RegretNet is already capable of discovering near optimal auctions, one cannot expect ALGnet to achieve significantly higher optimal revenue than RegretNet. The results obtained are competitive or better than the ones obtained in Duetting et al. (2019) while requiring much less hyperparameters (Section 3). We also evaluate ALGnet in online auctions and compare it to RegretNet.
7

---

Published as a conference paper at ICLR 2021
For each experiment, we compute the total revenue rev := EV EIEN P (V)] and average regret ryl := 1/n Ey... EieN ri" (V) on test set of 10, 000 valuation profiles. We run each experiment 5 times with different random seeds and report the average and standard deviation of these runs. In our comparisons we make sure that ALGnet and RegretNet have similar sizes for fairess (Appendix D).
5.1 AUCTIONS WITH KNOWN AND UNKNOWN OPTIMA
Known settings. We show that ALGnet is capable of recovering near optimal auction in different well-studied auctions that have an analytical solution. These are one bidder and two items auctions where the valuations of the two items 01 and are independent. We consider the following settings. (A): 01 and U2 are i.i.d. from O0, 1]. (B): 01 ~ U[4, 16] and 2/2 [4, 7], (C): in has density fi()) = (1 + 266 and d2 has density f2(v) = 6/(1 y)²
(A) is the celebrated Manelli-Vincent auction (Manelli & Vincent, 2006); (B) is a non-i.i.d. auction and (C) is non-i.i.d. heavy-tail auction and both of them are studied in Daskalakis et al. (201 7). We compare our results to the theoretical optimal auction (Table 2). (Duetting et al. (2019) does not evaluate RegretNet
settings (B) & (C)). During the training process, reg decreases 0 while rew and P converge to the optimal revenue. For (A), we also plot rev, ryt and P as function of the number of epochs and compare it to RegretNet (Fig. 1).
Contrary to ALGnet, we observe that RegretNet overestimates the rev- enue in the early stages of training at the expense of higher regret. As a consequence, AL.Gnet learns the optimal auction faster than Regret- Net while being schedule-free and requiring less hyperparameters.
Table 2: Revenue & regret of ALGnet for settings (A)(C).
Optimal
ALGnet (Ours)
Tew
ryt
Yee
rgl. (x 10 (3-
(A)
0.550
0.555 (=000019)
0.55 (#0.14)
(B)
9.781
0
9.737
(#.0443
0.75 (00177)
0.1706
0.1712
(+0.0012)
0.14 (+0.07)
Revenue: Bidder, Items, Uniform(0,1
0.010
Regret:
Bidder, 2 Items, Uniform[o.1 1]
pf: 1 Bidder, Items, Uniform(0.11
Optimal
0.008
RegretNet ALGnel
Revenue
Regreh
0.006
0.3
0.4
0.004
Optimal
Optimal RegretNet
ALGnet
0.002
0.3
RegreINet
0.000
0.0
ALGnet
40
20
(a)
Epoch
(b)
Epoch
(c)
Epoch
Revenue: 1 2 Items, Uniform[0,14g]
0.10
Regrot: B Items, Uniform(0.1-)
p:: 1 Bidder, Items, Uniform(001-0
ALGnet
1.0
0.08
RegretNet
1.0
Reverue
RegretNet Online
0.8
Optimal
0.6
0.6
ALGnet
0.04
Optimal
RegretNet
0.4
Regrethiet
RegretNet Online
0.02
0.2
Regretheet Online
0.2
Optimal
ALGnet
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.8
0.8
1.0
(d)
Time
(e)
Time
(f)
Time
Figure 1: (a-b-c) compares the evolution of the revenue, regret and P function of the number of epoch for RegretNet and ALGnet for setting (A). (d-e-f) plots the the revenue, regret and P as function of time for ALGnet and (offline & online) RegretNet for an online auction (Section 5.2).
Unknown and large-scale auctions. We now consider settings where the optimal auction un- known. We look at n-bidder m-item additive settings where the valuations sampled i.i.d from 24[0, 1] which we will denote by n x m. In addition to "reasonable" -sclle auctions (1 x 10 and 2 x 2), investigate large-scale auctions (3 x 10 and x 10) that much more complex. Only deep learning methods are able to solve them efficiently. Table 3 shows that ALGnet is able to discover auctions that yield comparable or better results than RegretNet.
5.2 ONLINE AUCTIONS
ALGnet is an online algorithm with a iime-independent loss function. We would expect it to perform well in settings where the underlying distribution of the valuations changes over time. We consider a one bidder and two items additive auction with valuations 8n and U/ sampled i.id from u(001 + f] where / in increased from 0 to 1 at steady rate. The optimal auction time has revenue
8

---

Published as a conference paper at ICLR 2021
Table 3:
Comparison of RegretNet and ALGnet. The values reported for RegretNet are found in Duetting et al. (2019), the numerical values for ryt and standard deviations are not available.
RegretNet
ALGnet (Ours)
Setting
TEV
rgl
rEv
rgl
1 X 2
0.554
< 1.0 10-3
0.555
(+000019)
0.55 10..10022 10-3
1055-100- 10-3)
X 10
3.461
3.0- 10-3
3.487
(#0.0135)
1.65 105--10--200.7--1101
2 x 2
0.878
<.0 10-3
0.879
(#0.0024)
0.58- 1.8-1100310.3--0000 10
3 x 10
5,541
< 2.0 10-3
5.562
(#0.0308)
1.93 199-1109(10.33-000
x 10
6.778
5.0 10-
6.781
(#0.0504)
3.85 10- 10
0.55 x (1 +)). We use ALGnet and two versions of RegretNet, the original offline version (Appendix A) and our own online version (Appendix B) and plot rev( (1) and (*(1) (Fig. 1). The offline version learns from fixed dataset valuations sampled online versions (as ALGnet) learns from a stream of data at each time t. Overall, ALGnet performs better than the other methods. It learns an optimal auction faster the initial (especially compared to RegretNet Online) and keep adapting to the distributional shift (contrary to vanilla RegretNet).
(i.e with ~ 2[0 1]mm) while the
6 CONCLUSION
We identified two inefficiencies in previous approaches to deep auction design and propose solutions, building upon recent trends and results from machine learning (amortization) and theoretical auction design (stationary Lagrangian). This resulted in a novel formulation of auction learning two- player game between an Auctioneer and a Misreporter and a new architecture ALGnet. ALGnet requires significantly fewer hyperparameters than previous Lagrangian approaches. We demonstrated the effectiveness of ALGnet on a variety of examples by comparing it to the theoretical optimal auction when is known, and to RegretNet when the optimal solution
known.
Acknowledgements. Jad Rahme would like to thank Ryan P. Adams for helpful discussions and feedback on the manuscript. Samy Jelassi thanks Arthur Mensch for fruitful discussions the subject and feedback on the manuscript. The work of Jad Rahme was funded by Princeton SEAS Innovation Grant. The work of Samy Jelassi is supported by the NSF CAREER CIF 1845360. The work of S. Matthew Weinberg was supported by NSF CCF-1717899.
REFERENCES
-loii-Florina Balcan, Avrim Blum, Jason D. Hartline, and Yishay Mansour, Mechanism design via machine learning. In 46th Annual IEEE Symposium on Foundations of Computer Science ( (FOCS 2005), 23-25 October 2005, Piusburgh, PA, USA, Proceedings, pp. 605-614. IEEE Computer Society, 2005. doi: 10.1 20009//SS.200..5.5.. URL https:/ /tt/://da.... org 1100//5CC... 20C5. 50.
Maria-Florina F Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. In Advances in Neural Information Processing Systems, pp. 2083-2091, 2016.
Xiaohui Bei and Zhiyi Huang. Bayesian Incentive Compatibility via Fractional Assignments. In the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
Sebastien Bubeck, Nikhil R Devanur, Zhiyi Huang, and Rad Niazadeh. Online auctions and multi- scale online learning. In Proceedings of the 2017 ACM Conference Economics and Computation, pp. 497-514, 2017.
Yang Cai, Nikhil Devanur, and S. Matthew Weinberg. duality based unified approach to bayesian mechanism design. In Proceedings of the 48th ACM Conference on Theory of (omputation((TOOC) 2016.
Yang Cai, Argyris Oikonomou, Grigoris Velegkas, and Mingfei Zhao. An efficient E-bic to BIC transformation and its application to black-box reduction in revenue maximization. CoRR, abs/1911.10172, 2019. URL http: //api:////vvvva////// wwwpaiiwwwwww...////o//aort.aaaa wwt./oo/ggg//ggooooo 19111

---

Published as a conference paper at ICLR 2021
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, and Mihalis Yannakakis. The complexity of optimal multidimensional pricing. In Proceedings of the Twenty- Ewenty-Fifth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pp. 2319-1328, 2014. doi: 10.1 (0.1137/1.981100 119711978816111774022.97 URL http:/ //x: /xxxxxx// doi. org/10. 1137/1 9781 977342..77
Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, and Mihalis Yannakakis. On the complexity optimal lottery pricing and randomized mechanisms. In 2015 IEEE 56th Annual Symposium Foundations of Computer Science, pp. 1479. IEEE, 2015.
Xi Chen, George Matikas, Dimitris Paparas, and Mihalis Yannakakis. On the complexity of simple and optimal deterministic mechanisms for an additive buyer. In Proceedings of the Twenty-Nint Annual ACM-SIAM Symposium on Discrete Algorithms,, pp. 2036 2069. SIAM, 2018.
Constantinos Daskalakis and Seth Matthew Weinherg. Symmetries and optimal multi-dimensional mechanism design. In Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 370-387, 2012.
Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. The complexity of optimal mechanism design. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 1302-1318, SIAM, 2014.
Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. Strong duality for a multiple-goe good monopolist. Econometrica, 85(3):735-767, 2017.
Paul Duetting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath.
Optimal auctions through deep learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1706-1715 1715, Long Beach, California, USA, 09-15 Jun 2019. press / vv /duetting 9a. html.
PMLR. URL http: http:://pooceedeeeeeeomo
Shaddin Dughmi, Li Han, and Noam Nisan. Sampling and representation complexity of revenue maximization. In International Conference on Web and Internet Economics, pp. 277-291, Springer, 2014.
Shaddin Dughmi, Jason D. Hartline, Robert Kleinberg, and Rad Niazadeh. Bernoulli factories and black-box reductions in mechanism design. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pp. 158-169, 2017. doi: 10. 304444 URL http: //ooi a.m. org/10 0. 1145/ 3055399. 3055492.
Paul Dütting, Felix Fischer, Pichayut Jirapinyo, John Lai, Benjamin Lubin, and David Parkes. Payment rules through discriminant-based classifiers. ACM Transactions on Economics and Computation (TEAC), 3(1):1-41, 2015.
Zhe Feng, Harikrishna Narasimhan, and David Parkes. Deep learning for revenue-optimal auctions with budgets. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, pp. 354 132..62. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Noah Golowich, Harikrishna Narasimhan, and David C. Parkes. Deep learning for mucti-facility location mechanism design. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2018), pp. 261-267, 2018. URL f files www.wooowooooooooooo ch ca_ceh___hhh ijcaillal 118 pdf.
//tppsss////ocs.////////ssssssss seas, harvard.
Yannai A. Gonczarowski and Noam Nisan. Efficient empirical revenue maximization in single- parameter auction environments. In Proceedings of the 49th Anmual ACM SIGACT Symposium Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pp. 866-868, 2017. doi: (4.1145/3055399.0555444 URL htL:ttp://ce /tttt::///..iie acm. htt///oi.ccccc.cooommoomoooo. 3055427.
Yannai A. Gonezarowski and S. Matthew Weinberg. The sample complexity of up-to-s multidi- mensional revenue maximization. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2018.
10

---

Published as a conference paper at ICLR 2021
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pp. 2672-2680, 2014.
Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Settling the sample complexity of single-paramen parameter revenue maximization. In Proceedings of the 51 Annual ACM SIGACT Symposium Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pp. 662-673, 2019. doi: 10.1145/331122763333222 URL https: /oii. orgg10 0e1e9/00.114/33311 1111113113222 3316325.
Sergiu Hart and Noam Nisan. Approximate Revenue Maximization with Multiple Items. In the 13th ACM Conference on Electronic Commerce (EC), 2012.
Sergiu Hart and Philip J. Reny. Maximizing Revenue with Multiple Goods: Nonmonotonicity and Other Observations. Theoretical Economics, 1033):893-922, 2015.
Jason D. Hartline and Brendan Lucier. Bayesian Algorithmic Mechanism Design. In the 42nd ACM Symposium on Theory of Computing (STOC), 2010.
Jason D. Hartline and Samuel Taggart. Sample complexity for non-truthful mechanisms. In Pro- ceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pp. 399-416, 2019. doi: 10.1155/3285263322622 URL
https: //t::///do..e org 111. 332992633223326.... 3329632.
Jason D. Hartline, Robert Kleinberg, and Azarakhsh Malekian. Bayesian Incentive Compatibility via Matchings. In the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
Zhiyi Huang, Yishay Mansour, and Tim Roughgarden. Making the most of your samples. SIAM Journal on Computing, 47(3):651-674, 2018.
Sébastien Lahaie. A kernel-based iterative combinatorial auction. In Twenty-Fifft AAAI Conference Artificial Intelligence, 2011.
Xinye Li and Andrew Chi-Chih Yao. On revenue maximization for selling multiple independently distributed items. Proceedings of the National Academy of Sciences, (10028):11222-1122 2013.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. 1rXiv:1711.05101, 2017.
arXiv preprint
Alejandro Manelli and Daniel Vincent. Bundling as an optimal selling mechanism for a multiple-good monopolist. Journal of Economic Theory, 127(1):1-35, 2006.
Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Conference on Learning Theory, pp. 1298-132 1318, 2016.
Jamie H Morgenstern and Tim Roughgarden. On the pseudo-dimensee of nearly optimal auctions. In Advances Neural Information Processing Systems, pp. 136 2015.
Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-1) 73, 1981.
Harikrishna Narasimhan and David C Parkes. general statistical framework for designing strategy- proof assignment mechanisms. In UAI'16 Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, 2016.
Jad Rahme, Samy Jelassi, Joan Bruna, and S. Matthew Weinberg, A permutation-equivariant neural network architecture for auction design. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 2021.
Tim Roughgarden and Okke Schrijvers. Ironing in the dark. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16. Maastricht. The Netherlands, July 24-28, 2016, pp. 1-18, 2016. doi: 10.1145/2944716.224909 URL http: doi. acm. org/ 100 11 1145/294071 00014477166229273333
org/10.

---

Published as a conference paper at ICLR 2021
Aviad Rubinstein and S Matthew Weinberg. Simple mechanisms for subadditive buyer and applications to revenue monotonicity. ACM Transactions on Economics and Computation (TEAC), 6(3-4):1-25, 2018.
Weiran Shen, Pingzhong Tang, and Song Zuo. Automated mechanism design via neural networks. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pp. 215-223. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
Vasilis Syrgkanis. A sample complexity measure with applications to learning optimal auctions. In Advances in Neural Information Processing Systems, pp. 5352-5359, 2017.
Andrea Tacchetti, DJ Strouse, Marta Garnelo, Thore Graepel, and Yoram Bachrach. A neural architecture for designing truthful and efficient auctions. arXiv preprint 1rxiv: 2019.
John Thanassoulis. Haggling over substitutes. Journal of Economic Theory, 117:217-245, 2004.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance 16(1):8-37, 1961.
12

---

Published as a conference paper at ICLR 2021
A TRAINING ALGORITHM FOR REGRET NET
We present the training algorithm for RegretNet, more details can be found in Duetting et al. (2019).
Algorithm 2 Training Algorithm.
Input: Minibatches Si...., ST of size B
2: Parameters: 0, 0, c > 0, REN, TEN, EN, ENN.
3: Initialize Parameters: p E R, w E R E
4: Initialize Misreports: (0) E DD, vle [B], ie
5:
..... 6: for 0,, T do
7: Receive minibatch S = (V(1) v(B)}.
8: for O..... do
ve E [B], i n: 1/4 t v/
9:
v uu (4, (1) v(!))
11:
Get Lagrangian gradient and update w':
12:
witt1 w v of Lww; X3; p²).
13:
Update p once T, iterations: if t is multiple of Tp then
15:
16:
p-+1 + pp
17:
else
18:
p²+1 p²
19:
20:
Update Lagrange multipliers once in Tx iterations:
if t a multiple of T3 then
22:
X f++ + X + (wo", (i V
else
24:
X++1 + X
13

---

Published as a conference paper at ICLR 2021
B TRAINING ALGORITHM FOR ONLINE REGRET NET
We present an online version of the training algorithm for RegretNet, more details can be found in Duetting al. (2019). This version mentionned in the orginal paper but the algorithm is explicitly written there. The following code is our own adaptation of the original RegretNet algorithm for online settings.
Algorithm 3 Training Algorithm.
1: Input: Valuation's 's Distribution D
2: Parameters: 7 > 0, 17 > O, c > O, REN, TEN, T, BENBEN
3: Initialize Parameters: p E R2 w" E ER,, Xo ER"
4: for / ,
, do
5: Sample minibatch S. = (V(,... ..... v(B} from distribution D.
6: Initialize Misreports: U, (t) E D;, v/ E [B], i N.
7:
8:
for R.....RR do
Ve E [B], i iE::
9:
( - v
v uf (u, (14 (()))
10:
11:
Get Lagrangian gradient and update w':
12:
w(+1 +- w v/V (w" X3; p²). )
13:
Update p once in Tp iterations: if is multiple of Tp then
15:
16:
pl+1 + p² +
17:
else
18:
p++1 t p
19:
20:
Update Lagrange multipliers once Tx iterations:
21:
if is multiple of Ty then
22:
X + pp Wi
23:
else
24:
A++1 + x
14

---

Published as a conference paper at ICLR 2021
C PROOF OF PROP. 1
Lemma 1, Let be one bidder m item mechanism with expected revenue P and expected regret
R, then VE O, there exists mechanism M' with expected revenue P' (1 ( 1= R and zero expected regret, R' = O.
Proof. For every valuation vector v E D, let g(v) and p(v) denote the allocation vector and price that M assigns to v.
We now consider the mechanism M' that does the following:
g' (v) g(0') p'(u) - =Ep
Where of is given by v' argma (u, g(t)) (1-s) p(o). By construction, the mechanism M' has zero regret, all we have to do now is bound its revenue. If we denote by R(v) the regret of the profile in the mechanism M, R(v) maxien (v, g(0) g(v) (p(i) p(u)) we have.
(v, (( p(6') (w, g(v)) p(u) + (v. g(²)) g(v)) (p(e') p())
< (v, g(v)) - p(v) + R(v)
Which we will write as:
(v, ((0)) p(b) > (v, ((())(")) -p(v) -R(v)
Second, we have by construction:
(u, g(v')) - (1- ()-=))(t') > (0, g(u)) - (1 -))(()
By summing these two relations we find
p(u') 3 p(u) R(v)
E
Finally get that:
1-E E
p'(v) > (1 - p(u)
R(v)
8
Taking the expectation we get:
1-E E
p' > (1 - E) P
R
5
Proposition Let M be an additive auction with 1 bidders and m items. Let P and R denote the total expected revenue and regret, P EVED [p(V)] and R = EveD [r(V)]. There exists mechanism M with expected revenue p =
2 (0= (VP (VP-VR) VR) and zero regret R = 0.
Proof. From Lemma we know that Ve > O, we can find a zero regret mechanism with revenue P' = (1 (1-s) 8) P -= R. By optimizing over we find that the best mechanism is the one correspond
to / The resulting optimal revenue is given by:
B PP
pr p=
R V
R= 2V 2 R (VP VR
V P
15

---

Published as a conference paper at ICLR 2021
D IMPLEMENTATION AND SETUP
We implemented ALGnet in PyTorch and all our experiments can be run on Google's Colab plateform (with GPU). Alg. I, used batches of valuation profiles of size B {500) and 'I' {160000, 240000}, Tiimie E {40000, 60000), Timie E {800, 1600} and T E {100}.
We used the AdamW optimizer (Loshchilov & Hutter, 2017) train the Auctioneer's and the Misreporter's s networks with learning rate E {0.0005, 0.001 J. Typical values for the architecture parameters are Na ny Thm E [3, 7] and hp f An {50, 100, 200}. These networks are similar in size to the ones used for RegretNet in Duetting et al. (2019).
For each experiment, we compute the total revenue rev EV DEEE P." (V)) and average regret ryl : 1/n EV-D DiEN rt (V) using test set of 10, 000 valuation profiles. We run each experiment 5 times with different random seeds and report the average and standard deviation of these runs.
16


Reviews:
[{"review_id": "ya2PlycZc3k", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors study the problem of optimal auction design using deep neural networks. Based on the structural insights in optimal mechanism in an additive auction with 1 bidder and m items, they propose a new loss function. This loss function is hyper-parameter free unlike Duetting et al. (2019) which is one of the early works in this field, making it more robust and interpretable. \nThe authors then propose a training method that resembles a two-player game to optimize the new loss function. The synthetic experiments (Table 3) show the designed algorithm, which does not require hyperparameter tuning, is comparable to the work of Duetting et al. (2019). \n\nPros: \n* The connection to the structural results in Balcan et al. (2005) to design the loss function.  \n* The illustration of the sensitivity of the loss function in Duetting et al. (2019) solidifies the message. \n* The training method that resembles a two-player game brings a new perspective to the problem (*)\n\nCons/Questions:\n* The paper lacks adequate comparisons, both conceptual and experimental, to other existing works.\n* In the experiments section, for Table 3 how the hyperparameters for RegretNet (Duetting et al. (2019)) is tuned is not clear. Such tuning is crucial for RegretNet as mentioned by authors. \n* In Table 2. comparison with RegretNet will be useful. \n* In Fig 1. why the online RegretNet and ALGnet converge to the same solution, despite the different loss functions?  \n* What are the depth and the width of the neural networks used in the experiments?\n* Is RegretNet the state-of-the-art for the different settings mentioned? (*) \n\nMinor:\n* The auctions reported have a maximum size of 5x10, which, in my opinion, should not be called a large scale.   \n\n\n(*) As an outsider to this field, whether this method is truly novel is hard for me to judge. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "b-Vzhp9l15w", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Objective of the paper:\nThe objective of the paper is to show that auction design can be views as a two-player game;  improving on past work, they provide schemes that give better performance and better time for learning.\n\nStrong Points:\n1)  The paper seems to offer improvements on recent past work.\n2)  The paper provides a clear background on auction theory relevant to the problem.\n3)  The paper delivers on the abstract.  \n4)  Some code is provided.  \n\nWeak Points:\n1)  It is not clear that the improvement over past work is large.  \n2)  The improvements/framework seem to rest on unproven assumptions, e.g., the use of the loss function in section 3.2.2, and the discussion of \"closeness\" in section 3.3.  This makes the paper somewhat unclear in terms of what it is offering -- heuristic approaches that improve (empirically) on the previous work?  If so, what are the limitations?  Are there situations the heuristic might be troublesome?  (Can you emphasize more clearly that your results are heuristic in nature, albeit based on theoretical formulations.)  \n\nOverall Rating:  I think this is an interesting paper.  I think the heuristics proposed offer benefits empirically and are well grounded, but the authors could do a better job clarifying the possible weak points of this heuristic approach compared to previous work.  The result is perhaps of interest to a specialized audience (people interested in auctions);  it's not clear that more general applications of the techniques are available.  \n\nQuestions for Authors:\nI was confused by Table 2 where you describe comparing to the \"optimal\" auction that has lower revenue than your auction results in 2 of 3 cases.  Is \"optimal\" here just signifying zero-regret?  Or is something else going on?\n\nIt is not clear to this reviewer that the auctions chosen are representative in any way -- I assume they've been used in previous works or are otherwise standard?  \n\nOther Feedback:  The paper is a bit confusing at times, but I think that is because the authors were forced to keep descriptions short in order to fit within page limits.  I think going back and offering a bit more description for a longer version would be useful.  Overall though the writing is fine.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "If2H_AYKZgp", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the auction design project through deep learning, following the direction pioneered by [Duetting et al '19]. The main contribution of this paper lies in two aspects: 1) they propose a time-independent lagrangian loss function which is motivated from eps-BIC to BIC transformation in [Rubinstein & Weinberg '18], and 2) the authors propose a GAN structure to compute the regret during training. The idea is simple and clean: design another NN to approximately compute the optimal misreport for each bidder.\n\nThe good:\n\n1. It lies in the intersection between Game Theory/Mechanism Design and Machine Learning, it should be of interest to a lot of people on both sides. It is a good fit for ICLR community.\n2. It focuses on an important question in mechanism design literature: multi-dimensional revenue-maximizing auction design.\n3. It is interesting and important that it can avoid hyper-parameter tuning for lagrangian loss function during training.\n\nThe drawbacks:\n\n1. It follows the spirit of [Duetting et al.] and also inherits the drawback there: the trained mechanism is not strictly IC and uninterpretable.\n\n2. The authors claim that they propose a metric to measure the performance of the nontruthful auctions, however, based on my understanding, it only holds for the single bidder case. For multiple bidders setting, as the authors state, they need to change to the BIC version of the regret, which is quite different with the expected ex post regret defined in this paper and the prior work [Duetting et al '19].  In this paper, all the simulations are based on the expected ex post regret. Therefore the new metric statement doesn't seem solid and the authors need to clarify.\n\nIn summary, this work is a good empirical paper, which simplifies the training procedure proposed by the original paper in [Duetting et al '19]. However, the authors need to clarify some statements in the paper. I think this paper can be accepted if there is room.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Dksfqwb99CG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper revisits a recent deep learning framework by Duetting et al (ICML’19) for learning Bayesian optimal auctions, which is a notoriously hard problem in theory. They propose two modifications to the Duetting et al architecture:\n•\tThe auctions computed by these algorithms are not exactly IC. To cope with that the learning objective penalizes by the regret of each agent from truthfully reporting their type. This leads to a question of choosing the relative weights of the revenue and the regret. Previous work had a complicated and brittle way of doing it, and the new paper proposes a simple formula that is inspired by auction theory and seems to work well in practice. The authors also propose to use this formula as a benchmark for comparing auctions with different revenue and regret guarantees.\n•\tThe training algorithm has to estimate the regret at each step, which requires an expensive optimization for the optimal deviation. The new paper proposes to amortize this optimization: after each gradient step of the auction, the optimal deviation probably did not change much so we can start it from the previous optimal deviation.\n\n\nThis paper makes nice contributions in an exciting new research direction towards insights on a classical problem. \n\n\nI’m still concerned about a couple of issues:\n•\tI don’t understand the relationship between this paper and Rahme et al. (“A Permutation-Equivariant Neural Network Architecture For Auction Design”): It also mentioned in passing in the introduction. I’m not familiar with the details of Rahme et al., but based on the abstract it seems like both propose improvements to the same Duetting et al. paper in the same setting. Many parts, e.g. structure of the introduction, are almost identical. Moreover, Rahme et al. claim to have a better algorithm than Duetting et al., so I’m not sure why the current paper doesn’t compare performance to that algorithm. (If these were written by the same authors, I’m not sure why they wrote 2 different papers?)\n•\tThe authors propose that the same theory-inspired formula they used for balancing regret and revenue be used to compare different mechanisms with different levels of revenue/regret. For multi-agent settings this approach sounds like a plausible heuristic, but they don’t bring enough support to convince me to use it as a metric. For single-agent settings, I would advocate to just apply the usual reduction to revelation principle, i.e. ask how much revenue the mechanism would get with a rational agent who exactly optimizes their bid. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CY-biY4Lk-l", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies how to design auctions using deep learning, as initiated by the work of Duetting et al. (2019). The authors argue that their new framework addresses several undesirability of the previous works, including extensive hyper-parameter tuning and unclear comparison between two auctions with different revenue and regret performance. Moreover, the new framework can be easily generalized to online environment.\n\nThe main novelty of this paper is to use a new optimization objective without relying on the Lagrangian method to formalize the objective. The new optimization objective is backed by a theorem stating that for a single-bidder environment, an auction with regret can be converted to an auction without regret with a revenue loss bounded by the square root of the regret, which also provides a convenient way to compare two auctions. Since the new objective does not consist of Lagrangian multipliers, no hyper-parameter tuning is required.\n\nThe empirical results further demonstrate the advantage of their new architectures.\n\nComments:\n\nThis paper is generally well-written and clear. The problem it studies is interesting and important, related to both game theory and deep learning, which is relevant and interesting to the deep learning community. It is nice to have a new architecture without extensive hyper-parameter tuning\n\n1. The author mentions that the theorem (that for a single-bidder environment, an auction with regret can be converted to an auction without regret with a revenue loss bounded by the square root of the regret) can be extended to the multi-bidder environment if using the notion of BIC. However, according to the definition, the regret is still computed in the ex-post level, which seems a bit strange. Could you elaborate more on this?\n\n2. Is it true that the misreport's utility is always 0 in any Nash equilibrium of the two-player game? Or this is only true for the optimal solution?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is a lot of agreement on this paper, also reflected in the ratings. There were some technical comments initially, on the approach not being IC and interpretable, missing links to other works and technical descriptions of the network and experiments. The authors cleared up many of these issues though with their responses, providing good arguments in favor of their work. In general, reviewers agree the paper would be interesting to be included in ICLR.
Decision: Accept (Poster)