Optimal-er Auctions through Attention
Authors: Dmitry Ivanov
Iskander Safiulin
Igor Filippov
Ksenia Balabaeva
Venue: NeurIPS 2022 Accept (2022)
Keywords: automated mechanism design
attention
transformers
optimal auctions
revenue
incentive-compatibility

Abstract: RegretNet is a recent breakthrough in the automated design of revenue-maximizing auctions. It combines the flexibility of deep learning with the regret-based approach to relax the Incentive Compatibility (IC) constraint (that participants prefer to bid truthfully) in order to approximate optimal auctions. We propose two independent improvements of RegretNet. The first is a neural architecture denoted as RegretFormer that is based on attention layers. The second is a loss function that requires explicit specification of an acceptable IC violation denoted as regret budget. We investigate both modifications in an extensive experimental study that includes settings with constant and inconstant numbers of items and participants, as well as novel validation procedures tailored to regret-based approaches. We find that RegretFormer consistently outperforms RegretNet in revenue (i.e. is optimal-er) and that our loss function both simplifies hyperparameter tuning and allows to unambiguously control the revenue-regret trade-off by selecting the regret budget.

Optimal-er Auctions through Attention
Dmitry Ivanov*
Iskander Safiulin Independent researcher Russia
Igor Filippov
HSE University & Technion
Independent researcher Russia
Israel
Ksenia Balabaeva ITMO University BIOCAD Russia
Abstract
RegretNet is a recent breakthrough in the automated design of revenue -oneuue--mxmmizigg auctions. It combines the flexibilityy of deep learning with the regret-based approach to relax the Incentive Compatibility (IC) constraint (that participants prefer to bid truthfully) in order to approximate optimal auctions. We propose two independent improvements of RegretNet. The first is a neural architecture denoted as Regret- Former that based on attention layers. The second is loss function that requires explicit specification of an acceptable IC violation denoted as regret budget. We investigate both modifications in an extensive experimental study that includes settings with constant and inconstant numbers of items and participants, as well as novel validation procedures tailored to regret- basedd approaches. We find that RegretFormer consistently outperforms RegretNet in revenue (i.e. is optimal-er) and that our loss function both simplifies hyperparameter tuning and allows unambiguously control the revenue-regret trade-off by selecting the regret budget
Introduction
Several decades ago, Myerson 42 has proposed a general solution for the problem of optimal (revenue-maxinn maximizing) design of single-item auctions. Despite the collaborative effort of the com- munity, the results of same generality for the multi-item auctions have not been obtained. As an alternative to analytical solutions, automated auction design 7 takes perspective of constrained optimization. In particular, the objective is to maximize the revenue while satisfying the Incentive Compatibility (IC) and Individual Rationality (IR) constraints. This framework provide approxi- mate solutions settings where the optimal mechanisms are unknown, as well as hint at what the analytical solutions may look like. Whereas the early algorithms utilize linear programming and classic machine learning, modern algorithms focus on deep learning.
Dütting et al. 17 are the pioneers of this approach with their RegretNet architecture. RegretNet is neural network that represents mechanism by mapping matrix of bids that n participants report for items into probabilistic allocation matrix and payment vector. It is trained via differential optimization on a mixture of two objectives: maximize revenue and minimize regret, which is relaxation of the IC constraint proposed in [5 RegretNet recovers near-optimal revenue in the analytically solved settings and outperforms the previous oatte-of-hheaat while having vanishing regret guarantees. In this paper, propose two independent improvements of RegretNet.
First, we propose a neural architecture based on attention layers. We name RegretFormer after the widely-known Transformers [60]. An illustration of the architecture is provided in Figure
technion. ddimonnnaemaill.nn divanov@campus. tec.piiitttteiinnnommm ac
*Code is available here
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

item features (m, kl
allocation (n-1, m)
attention
solimac
mean
matull
bids b (n, m)
initial features (n, m,
attended features (n, m, k)
exchangeable input layer
participant-wise attention
payments
participant features (n,
P.
N self-attention layers
Figure 1: Our architecture RegretFormer. The description is provided in Section 3.1
RegretFormer has several crucial properties. On the one hand, is by design insensitive to the order of items and participants, which is desirable for learning symmetric auctions. Note that it can also be modified to learn asymmetric mechanisms. On the other hand, does not assume a predetermined constant input size, which allows one network to learn from data consisting of auctions of varying sizes, well as to generalize settings unseen during training.
Second, we propose an alternative objective. Instead optimizing arbitrary mixtures of revenue and regret, approach maximizes revenue given explicitly specified regret budget, which is an acceptable violation of the IC constraint. This is technically implemented through the method of Lagrange multipliers and dual gradient descent. Our approach allows unambiguously balance revenue and regret by varying the regret budget. As a bonus, we find that our loss function is significantly less sensitive to the choice of loss-related hyperparameters.
conduct an extensive experimental study to verify the strengths of our modifications. Specifically, compare and existing architectures in both symmetric and asymmetric settings with constant input size, as well as in novel settings with inconstant input size. We find that RegretFormer consis- tently outperforms existing architectures in revenue given the same regret budget. We additionally verify this result with two novel validation procedures. The first procedure is based on estimating the regret of network given the optimal misreports approximated by another network. The second procedure is based on network distillation. Regarding our loss modification, we confirm that specifying the regret budget results in the intended revenue-regret trades-off.
2 Background
2.1 Problem statement
Let N (1,...,,) n. be set of bidders, M = (1,....m) be set of items. Fach bidder evaluates all items with valuation function U; 2M -> TR. In our study, we only consider additive valuations, meaning that for each item j M bidder has valuation function is (i),,, and valuation of a subset S .M equals to the sum valuations of the items in the subset u; (S))) = (j)sv;(i). The valuation function can also extended evaluate probabilistic assignments: (z(z)) (f), where zij is the probability that participant i is assigned item j.
The valuation function v; is drawn independently from the distribution F; over all possible valuation functions V₁, A set of valuations of all bidders forms a valuation profile v (U1,..., Un).. An auctioneer does not know the bidders' valuations
their distribution F (Fi, F.). but has sample L (v) .... e of valuation profiles drawn from F. The bidders independently report their bids = (b,, b,) E V. based on which the auction allocates the items and charges payments. pn).p p- (P1....,Px)) of probabilistic allocation rules 9; : + [0, 1] and payment rules V + R
Formally, the auction is defined as tuple (g (91 ....
Define the bidder's utility as ui(v;, b) v; (bx()) valuation Y; as v-4- Similarly, define the bids without b, as b.s. and the valuation profile all bidders except i V- 1R Vj. An auction is dominant strategy incentive compatible (DSIC) if the utility
(b).). Define the valuation profile without the

---

of each bidder is maximized by reporting their true valuations regardless of bids of other bidders: Vi, v, b: u,(u,, v) 2 (1, U-;)). An auction ex-post individually rational (IR) if each agent's utility is non-negative for all possible valuations and bids: Vi, b: uz(us, (b,, v- > 0.
Define the revenue of a profile auction design is to maximize the expected revenue subject to DSIC and IR constraints. The problem analytically solved for the auctions with one item in the seminal work of Myerson [42), provided the valuation distributions are known. There are no general solutions for auctions with m > 1.
sum of bidders' payments (p)s(e). The goal of the optimal
The task of optimal auction design can be viewed as optimization machine learning problem. In this case, the expected revenue takes the place of the objective. There is a class of auctions (g(w), p(w)) .M parameterized with profiles I drawn as independent and identically distributed variables from F. Then, the goal of the optimization procedure is find auction that minimizes the negated expected revenue - -Er (x; w)] while satisfying DSIC and IR constraints.
Fd' for some d N and set of bidder valuation
2.2 RegretNet
RegretNet [17] is deep learning solution for the optimal auction design. It can be used for multi- bidder and multi-item settings, the analytical solutions for which are unknown.
The architecture of RegretNet consists of two networks: the allocation network and the payment network. Both networks take flattened constant-sized bid matrix Bao as an input and process through several fully-connected layers.
The allocation network maps matrix of bids categorical distributions of allocations between participants for each item: Anet (Brm) = Zum, where 4y is the probability of allocating the j-th item the i-th bidder. To allow for the possibility of item remaining unallocated, the output of the final layer has the size (n + 1)- m, imitating an additional dummy participant with zero valuations. Then, obtain properly scaled allocation probabilities softmax activation is applied to the output of the final layer corresponding to each item. Specifically, Riy = E EE n++ Ed where žig denotes the unnormalized allocation probability (i.e. logit).
participants for each item, the
The payment network maps a matrix of bids to a vector of pay values: Pnet (B"m) = P", where P: is the fraction of the i-th bidder expected utility that the bidder transfers to the auctioneer. The payment is then computed as p. = p: Ej=1 Zipbij for i 1..... To properly scale P, E [o, 1], sigmoid activation is applied to the output of the final layer. Because the payment cannot exceed the bidder's expected utility, the mechanisms discovered by RegretNet always satisfy the IR constraint.
m
Given a sample of profiles I., RegretNet aims to optimize the following empirical objective:
min 1 ΣΣ pi(v'ww)
[
(1)
s.t. rgt. (g: - V,ENL
where rgt; denotes the i-th bidder's s ex-post regret. Regret is a quantifiable relaxation of the DSIC constraint first introduced [15. It is defined as the difference between the i-th bidder's utilities given the optimal misreport (that provides the highest utility) and the truthful bid:
rgt: (v': w) = max (u(v), (v/, )) w) u(rl, w)) of
To solve the constrained optimization problem over the space of the network parameters w, the authors of RegretNet employ the augmented Lagrangian method. This yields a loss function that combines revenue maximization with penalty for violations of DSIC constraints:
Louter (w) =
ΣΣ - P. X.R + L
(3)
3

---

where B denotes mini-batch, P. = EiEB Pi(u"; w) is the average revenue from the i-th par- ticipant, R2 [s] LieB (v, w';w) w) is the average approximate regret of the i-th participant, and (r w) (u(r), (1/ vL :) w(vt, w)) is an approximation of rgl.- To find the approximate regret, the optimal misreports of estimated via gradient descent in the inner optimization loop by minimizing the i-th participant negated utility as a function of their misreport:
Linner (eft) u((u (u,", v)
(4)
The Lagrange multipliers X and p periodically updated throughout the training according to the schedules: A <- X pR, and t p p PA- The starting values of A and p and the learning rate Pa are hyperparameters that control the trade-off between revenue and regret of the learned mechanism.
2.3 EquivariantNet
EquivariantNet is alternative architecture proposed by Rahme et al. [51] to effectively deal with symmetric auctions. It relics on a theorem originally proven by [IO] that there exists an optimal solution for symmetric auction that is eermutation-equivariaan i.c. insensitive to the order of inputs.
Like RegretNet, EquivariantNet has allocation network and payment network. Both networks consist of compositions of exchangeable layers that preserve definition is provided in the Appendix. The authors observe that EquiavariantNer produces competitive results but does not outperform RegretNet in revenue.
-euittaaiii--uuiiiiiannee (25]. Their
2.4 Related work
Early work that explores the automated solutions auction design formulates the problem as linear
program 77 54 8 or searches within specific families of DSIC auctions [35] [5]. The former
approach suffers from scalability issues due the curse of dimensionality 224. while the latter approach searches within a limited family of auctions that might not contain the optimal mechanism. Classic machine learning has also been applied to the auction design 34
15
but these approaches
are considered less flexible and general than the deep learning alternatives
17
In recent years, multiple extensions of RegretNet have been proposed, including the extensions the
optimal auction design with budget constraints [18] fairness constraints [33] and human preferences
desirable allocations
[49]. well the problem of faculty allocation 199 and the matching
problem [53]. Shen et al. [56] and Dütting et al. [17] propose alternatives to RegretNet that are exactly DSIC but that are only applicable auctions with one bidder. Curry et al. [9] combine the
approach of searching within limited families of DSIC auctions with deep learning. Rahme et al. [52] propose simplified loss function for RegretNet that casier to tune, as well as a potentially faster regret estimation procedure based on training adversarial bidder network. Deep learning has been applied to other aspects of mechanism design, such as iterative combinatorial auctions [62]. minimizing economic burden on bidders within the Groves family of auctions (58), optimal bidding strategies [46] 45) optimal redistribution mechanisms (3,, and E-commerce advertising [36).
Several studies have combined reinforcement learning with auction design [59 29 47 11. A plethora of research has also focused on the questions of sample complexity designing revenue-maximizing
auctions 66 41 [3 3 40
39
43
57
20
28
26
23
3 Our modifications of RegretNet
In this section, we describe our two modifications RegretNet. The first modification is a novel neural architecture for the optimal auction design, which denote as RegretFormer. The second modification an alternative constrained objective that yields a more convenient loss function.
3.1 RegretFormer: enhancing RegretNet with attention layers
The neural architecture of RegretNet has several issues. One issue is the sensitivity of RegretNet to the order of items and participants in the input bid matrix. Such order should not affect the outcome of symmetric auction [10 50). Even in non-symmetric auctions, permutationn-qquivariann

---

The architecture of RegretFormer is illustrated in Figure The network takes the matrix of bids B as the input. First, we apply an exchangeable layer 25 to transform each bid into an initial vector of features that contains information about other bids. Then, we apply item-wiss wise (i.e. row-wise) and participant- wise (i.e. column-wise wwsee) self-attention layers [60] to each feature vector corresponding to each bid. For given bid, the outputs of the two self-attention layers are transformed into a single feature vector through a fully-connected layer. These self-attention transformations can be applied several times. Finally, by averaging over rows and columns we transform the output of self-attention layers into the allocation matrix 2um and the payment vector P". Note that each layer shares the parameters across all bids to ensure that the network is insensitive to the order of bids and is applicable solutions sometimes achieve near-optimal revenue 22 30 31 32]. This makes the option to wire equivariance the input order into the architecture desirable. Another issue that RegretNet assumes a constant number of participants and items. This severely limits its practical applicability due to the inability to generalize to unseen input sizes and learn from data with heterogenous input sizes. Finally, the fully-connected layers used in RegretNet have limited expressivity and may not have the right inductive biases for auction design. As a remedy, we propose RegretFormer.
to different input sizes. The detailed definitions and order of all layers are provided in the Appendix.
Our architecture has several advantages. On the one hand, it leverages the expressivity of attention layers that help to achieve tfate-of-the-art performance in many diverse and complex problems, e.g. [2 63). We empirically demonstrate the superiority of RegretFormer in Section 4 On the other hand, maintains the equivariance and the invariance the order of items and participants. The former forces the resulting mechanisms to be symmetric, which drastically reduces the solution search space. The latter allows RegretFormer to learn from data with inconstant input sizes, as well as to generalize to unseen settings. Note that RegretFormer can still learn asymmetric mechanisms by utilizing positional encoding, which we demonstrate empirically.
We note that a concurrent work by Duan et al. [1] also combines Transformers and RegretNet. However, their focus is on integrating contextual information of bidders and items into the framework, whereas we perform a wider and more accurate comparison of neural architectures.
3.2 Specifying regret budget
Both RegretNet and EquivariantNet optimize a mixture of two conflicting objectives namely revenue maximization and regret minimization, and control their trade-off with hyperparameters like initial values and schedules of the Lagrange multipliers. There are two issues with this approach. The first issue is sensitivity. These hyperparameters have to precisely tuned for each experiment, and as Rahme et al. (52) show, may massively degrade the performance if selected improperly. The second issue is uninterpretability. While increasing any As P, Aa tightens the regret budget of the learned mechanism, the exact effect of such changes resulting revenue and regret is unpredictable. Furthermore, the recipe for hyperparameter selection in new settings is unclear. Rahme et al. [52) propose a mixture of objectives that mitigates the first issue, but the second issue remains unresolved.
We propose an alternative perspective that mitigates both issues. Instead of balancing the two objectives, we maximize the revenue given maximal regret budget Rmez. which is pre-specified by the designer. This corresponds to a relaxed version of the constrained objective TT)
ΣΣ min
pi(o';
T IEL IEN
(5)
s.t.
(g'; ; w) S Rmaz
IELIEN
Instead of the constrained objective (5), we optimize its dual by introducing the Lagrange multiplier y (note that Rmaz does not depend on w and thus can be dropped):
Louter (w) = E
Σ R4
(6)
SEN
BEN
Critically, unlike the original RegretNet we do not hand-select the Lagrange multiplier. Instead, ? is dynamically updated to enforce the constraint satisfaction while exhausting all available regret
5

---

budget Rman- To this end, we employ dual gradient descent gradient update of the network parameters w to minimize and one update of y according to:
4 Specifically, we iterate between one
Σ P.) - -log( (agg)) )) IE
1 t max 0,7 117775 7
log
R
(7)
IEN
where V is the learning rate for the dual variable. For convenience, in 7 we normalize the regret estimate by revenue. This way, Rmar [0. 1] specifies the regret budget percentage of revenue. We also apply logarithms to both terms of the difference in (7) for faster convergence of y.
Additionally, we apply decreasing schedule to Rmar. If the regret budget Rmaz is too tight at the beginning of training, the network may fail to escape the local optima of low revenue and zero regret. To avoid that, we initialize Rmaz at a higher value Retert and exponentially anneal it to the desirable budget Hend throughout the training. This leads the network to first find the solutions with high revenue and then tighten the regret. This results in the following update rule for the regret budget:
Ranax f- max (Reaas
Ramax)
where Rmalt
controls the speed of annealing of Ranas to Rend
Another example of applying dual gradient descent to enforce constraint can be found in [48]
The proposed approach has several advantages. On the one hand, it resolves the dichotomy of two conflicting objectives. While the regret budget needs to be explicitly set based on the designer's preferences. all other hyperparameters are then straightforward tune by maximizing the revenue given the specified regret budget. This is unlike the original objective of RegretNet (3) where the regret budget is chosen implicitly through specifying uninterpretable loss-related hyperparameters like Ao P. Pa. On the other hand, our approach is also significantly less sensitive to loss-related hyperparameters. We empirically demonstrate this by using the same hyperparameterss related the budget Rmar and its schedule all our experiments, in contrast to the objective (3) that requires a uniquely tuned set of loss-related hyperparameters perform well in a given setting [52
4 Experiments
In this section, we empirically investigate our modifications. We compare our RegretFormer with RegretNet and EquivariantNet in settings with a constant number of participants and items used by Dütting et al. [17]. as well as in novel settings with inconstant input sizes that we denote as multi-settings. All three networks are trained given the same regret budgets using our approach from Section 3.2 Additionally, we vary regret budgets and further investigate the differences between the architectures using novel validation procedures. In all experiments, the valuations of all participants additive and are independently drawn for each item from the Uniform distribution: v, v,()) U(0, 1]. Training details, hyperparameters, and additional results are reported in the Appendix.
4.1 Comparison of architectures under constant input sizes
The settings only differ in the number of participants n and items we denote them as nxm. We conduct experiments five settings: [1x2, 2x2, 2x3, 2x5, 3x 3x10). The 1x2 setting is the celebrated Manelli- Vincent auction, the analytical solution for which is provided in 37 The optimal revenue for this auction equals 0.55. For the rest of the settings, the analytical solutions are unknown.
We compare our and existing neural architectures in the five settings given two different regret budgets Rmez E {10- 3 10-41, We additionally include the classic VCG [6 22 and Myerson 42 mechanisms for comparison, both of which are DSIC and ex- ex-post IR, The Myerson auctions are optimal for m 1. We report its two extensions item is sold separately and the "bundled' where all items are sold as a single bundle.
multi-good settings: the 'item-wise' where each
We report the results in Table Additionally, we report the learning curves in the Appendix.
In all settings but 1x2 and given both regret budgets, RegretFormer outperforms both RegretNet and EquivariantNet in revenue. The performance gap is absent in the simplest setting but becomes

---

Table 1: Architecture comparison. Like in [16]. revenue is summed over participants, and regret is averaged over participants. The highest revenue in setting is highlighted in bold font. For brevity. we only report aggregated standard deviations: the average standard deviation of revenue is 0.006 for 1x2, 0.01 1 for 2x2, 0.009 for 2x3, 0.033 for 2x5, 0.019 for 3x10; the average standard deviation of regret is 0.00018 for Rmax 10-3 0.00003 for Ryar 10-1
RegretNet
EquivariantNet
RegretFormer
Rmaz
setting
revenue
regret
revenue
regret
revenue
regret
10 10-3
1x2
0.572
0.0007
0.586
0.00065
0.571
0.00075
2x2
0.889
0.00055
0.878
0.0008
0.908
0.00054
2x3
1.317
0.00102
1.365
0.00084
1.416
0.00089
2x5
2.339
0.00142
2.437
0.00146
2.453
0.00102
3x 10
5.59
0.00204
5.744
0.00167
6.121
0.00179
10-4 4
1x2
0,551
0.00007
0.548
0.00013
0.556
0.00014
2x2
0,825
0.00005
0.75
0.00005
0.861
0.00006
2x3
1.249
0.00007
1.226
0.0001
1.327
0.00011
2x5
2.121
0.00013
2.168
0.00017
2.339
0.00015
3x10
5.02
0.00062
5.12
0.00025
5.745
0,00022
VCG
Myerson item-wise revenue
Myerson
bundled
Rmaz
setting
revenue
regret
regret
revenue
regret
1x2
0.5
0,544
2x2
0.667
0.833
0
0.839
2x3
1.25
1.278
2x5
1.667
2.083
0
2.188
3x10
5.312
5.003
Table 2: Ratio of the estimated regret to the regret budget. Our approach from Section 3.2 implies that this ratio should be close to 1 during training. Optimal misreports estimated by minimizing (4) using 50 and 1000 gradient descent steps during training and validation, respectively.
RegretNet valid
EquivariantNet train
RegretFormer train
Ryaa
setting
train
valid
valid
10 10-3
1x2
1.12
1.22
1.04
1.11
1.01
1.31
2x2
0.97
1.24
1.41
1.82
0.89
1.19
2x3
1.07
1.55
1.11
1.23
1.02
1.26
2x.5
0.94
1.21
1.11
1.2
0.8
0.83
3x
0.89
1.09
0.9
0.87
1.03
0.88
10-4
1x2
0.94
1.27
0.92
2.37
1.31
2.52
2x2
0.95
1.94
1.73
1.33
0.93
1.39
2x3
1.52
1.12
1.57
1.63
1.6
1.66
2x5
1.04
1.23
1.02
1.57
0.95
1.28
3x10
0.9
3.71
1.05
1.46
0.88
1.15
especially prominent in the larger settings. While permutation-equiiariaace of RegretFormer likely plays role, cannot fully explain the results since EquivarintNet also has this property. We, therefore, attribute the superiority of RegretFormer to the expressivity of attention layers.
Additionally, in Figure 2] we provide solutions found by RegretNet and RegretFormer in the Ix2 setting. Both networks find allocation probabilities that smoothly approximate the optimal solution.
In the bigger settings, EquivariantNet surprising since was not observed by the authors of EquivariantNet, but it can simply be explained by the fact that they do not test the architecture in settings that complex enough.
also outperform RegretNet. This result is somewhat
Given the smallest regret budget, both baselines sometimes underperform Myerson. While Regret- Former outperforms Myerson in revenue, its regret is still non-zero. This highlights potential
7

---

(c)
(d)
Prob. of alboating tem
Prob. allocating ttem
Prob. of allocating item
Prob. of allocating temm
3
100
9A
0.6
2.
0.0
02
044
1.0
(c)
(f)
(h)
Prob. allocating item 1
Prob. of aallcating item
Prob: af atocating item
Prot. of sllocating tem
6.-
6.5
03
0.5
5.-
55
06
0.4
04
04
02
02
02
4.0
0.
20.0
7.5
Figure 2: Allocation probabilities: (a, b) RegretNet in 1x2; (c, d) RegretFormer in 1x2; (c, RegretFormer without PE the asymmetric setting; (g. h) RegretFormer with PE in the asymmetric setting. The optimal mechanisms deseribed by the regions separated by the dashed black lines, with the numbers black denoting the optimal probability of allocation in the region.
problem of the regret-based approach: when any violations of DSIC are highly undesirable, better revenue might be achieved with classic mechanisms that are also guaranteed be DSIC.
potential downside of RegretFormer compared to the basclines is that it takes longer to train and requires more parameters to reach optimal performance. We elaborate on this in the Appendix.
4.2
Does regret budget function as indented?
The core feature of our approach from Section 3.2 is that the resulting regret should be uniquely and unambiguously specified through the regret budget. In particular, the total regret normalized by the total revenue should equal the regret budget. To verify this quantitatively, we present the ratios of the estimated normalized total regret to the regret budget in Table 2 A ratio higher than means that the regret budget is exceeded, and vice versa. Below summanze findings.
During training, the ratios are indeed close for all three architectures, meaning that our approach functions intended. Additionally, we report the ratios estimated during validation, which involves more gradient descent steps find optimal misreports than during training, making the regret estimates more precise. Unsurprisingly, these are usually than the ratios estimated during training. For a tighter regret approximation and better match with the budget, one could increase the number of the inner optimization steps during training, provided that longer training time is acceptable.
4.3 Is the performance gap genuine?
In [ we have observed that RegretFormer outperforms both baselines and have attributed its success to the expressivity attention layers. However, there an alternative explanation.
Recall that regret is approximated in the inner optimization (4) by repeatedly back-propan prekpppppgggging through the whole neural network w. It follows that regret approximation depends on the neural architecture, including the number, the types, the size, and the order of layers. Due to the absence of regret approximation procedure that is identical for all networks, there no guarantee that similar regret estimates between different neural architectures correspond to actual similar regret values, i.e. for different architectures W1. W2 R(w1) ~ R(w2) + R(w1) ~ R(w2). where R(w) is the expected regret and i(w) is its approximation. In particular, we are concerned whether RegretFormer achieves higher revenues due to approximating the regret worse, rather than due to maximizing the revenue better. We design two procedures to test this hypothesis.

---

Table Cross-misrepont regret estimates. The highest regret for network is highlighted with bold.
setting
regret of
misreports of EquivariantNet
RegretNet
RegretFormer
1x2
RegretNet
0.00079
0.00043
0,00074
EquivariantNet
0.00102
0.00071
0.00129
RegretFormer
0.00076
0.00046
0.00092
2x2
RegretNet 0,00050
0,0003
0.00024
EquivariantNet 0.00021
0.00050
0.00022
RegretFormer 0.00065
0.00056
0.00059
2x3
RegretNet 0.00116
0.00062
0.00044
EquivariantNet 0.00020
0.00071
0.00028
RegretFormer 0.00072
0.00087
0.00094
2x5
RegretNet 0.00149
0.00065
0.00060
EquivariantNet
0,00075
0.00142
0.00071
RegretFormer 0.00089
0.00120
0.00109
3x10
RegretNet 0.00198
0,00035
0,00012
EquivariantNer 0.00035
0.00168
0.00014
RegretFormer 0.00178
0.00178
0.00222
Table 4: Asymmetric setting from Daskalakis et al.
Rmaa 10-3
Optimal
RegretNet
RegretFormer
RegretFormer PE
revenue 9.781
regret
revenue
regret 0.0072
revenue
regret 0.0102
revenue 10.056
regret 0.0099
0
9.951
9.967
The first procedure is denoted as 'cross-misreports. is based on estimating the regret of one network on the optimal misreports approximated by another network: R.ross (w1, W2) = Tgt, (v (w2), u²; w.). We apply this procedure to the trained networks in all five set-
[ Lienrgt, tings given Rmaz 10-3 3, all networks approximate regret equally well, we expect the regret estimated on cross-min misreports to not exceed the normally computed regret. However, if the regret estimates RegretFormer were higher on the misreports estimated by RegretNet EquivariantNet, this would point toward poor regret approximation by RegretFormer.
We report the results in Table 3 regret: in all settings, it finds misreports that produce regret either higher than or within a standard deviation from the misreports of the other two architectures.
We do find any evidence that RegretFormer underestimates the
The second procedure is based on network distillation. The results are similar to Table 3 in that RegretFormer does not appear underestimate the regret, report them in the Appendix.
4.4 Learning asymmetric mechanisms using positional encoding
To handle asymmetric distributions, our architecture can be augmented with Positional Encoding (PE) common technique for transformers to incorporate information about the order of elements. To demonstrate this, we study a setting with one bidder, two items, and non-identically distributed valuations over items, where U1 U[4, 16] and U2 U14,, 7]. The optimal mechanism is given by Daskalakis et al. [[T] We apply RegretNet, RegretFormer without PE, and RegretFormer with PE given Rmaa 10-3 As PE, we to the input (estimated as sine and cosine functions of caiition-dependen frequencies) proposed by Vaswani et al. [60]. Note that this PE has learnable parameters.
common technique that adds arbitrary numbers from [-1, I]
The results are reported in Table While RegretFormer with PE unsurprisingly performs on par with RegretNet, RegretFormer without PE learns symmetric solution that is not much worse. In Figure 2 we provide illustrations of solutions found by the two versions of RegretFormer. These show that RegretFormer with PE closely approximates the allocation probabilities of the optimal mechanism.

---

Table 5: selti-setting results. We report the highest regret identified with the cross-mi misssportp procedure (see full cross-misreport results in the Appendix). (*) Note that EquivariantNet achieves unrealistically high revenue for a much higher regret.
RegretNet
EquivariantNet(*)
RegretFormer
Setting
revenue
regret
revenue
regret
revenue
regret
average
2.573
0.00352
2.889
0.00989
2.703
0.00391
2x3
1.386
0.00305
1.504
0.00554
1.432
0.00246
2x4
1,855
0.00341
2.070
0.00925
1,951
0.00317
2x5
2.339
0.00362
2.646
0.01270
2.471
0.00391
2x6
2.866
0.00425
3.226
0.01597
3.006
0.00439
2x7
3.346
0.00457
3.834
0.01951
3.553
0.00481
3x3
1,652
0.00322
1.795
0.00358
1.708
0.00251
3x4
2.217
0.00264
2.449
0.00508
2.312
0.00336
3x5
2.786
0.00277
3.108
0.00709
2.911
0.00421
3x6
3.362
0.00340
3.787
0.00916
3.521
0.00476
3x7
3.921
0.00430
4.467
0.01101
4.140
0.00553
whereas RegretFormer without PE finds symmetric solution that resembles some middle ground between the optimal allocation probabilities for the two items.
4.5 Comparison of architectures in multi-settings
In practice, it may be desirable for single network to be applicable to multiple input sizes, e.g. to save computation due to limited data. To test our network such cases, we introduce multi-settting. A multi-setting is a uniform mixture of constant-sized settings studied so far. In our experiments, we mix the following settings: (2x3, 2x4, 2x5, 2x6, 2x7, 3x3, 3x4, 3x5, 3x6, 3x7). We set Rmaz 10-3 To adapt RegretNet to multi-settings, we fix the input size for the maximum possible number of items and participants in a multi-setting and pad unused valuations with zeros.
The results are presented in Table 5 Comparing RegretFormer with RegretNet, our architecture consistently achieves higher revenue for the same regret budget. While EquivariantNet achieves even higher revenue, after applying our cross-misreport validation procedure we find that EquivariantNet fails minimize regret due poorly approximating optimal misreports. Full results of cross- misreport validation, as well as out-of-setting experiments, are reported in the Appendix.
Conclusion
In this study, we achieve new state-of-the-art in the application of deep learning to optimal auction design. Our RegretFormer leverages recent advances in deep learning to unlock the full potential of regret-based optimization while enforcing the equivariance and the invariance to the order of participants and items. We test the effectiveness of RegretFormer in multiple experimental settings and find that our network consistently outperforms the existing analogues. addition, we rethink objective formulation of RegretNet. The resulting loss function disentangles balancing the revenue- regret trade-off and optimizing the performance, as well as reduces the burden of hyperparameter tuning. Finally, suggest two validation procedures for comparing regret- based approaches that may find use in future studies.
Acknowledgments
All authors. We sincerely thank Xeniya Adayeva for creating the illustration of RegretFormer| I You can contact Xeniya at xeniya.adayevae gmail.com regarding scientific illustrations.
Dmitry Ivanov. This research was supported in part through computational resources of HPC facilities HSE University, Russian Federation. Support from the Basic Research Program of the National Research University Higher School of Economics is gratefully acknowledged.
10

---

References
[1] R. Ai, B. Lyu, Z. Wang, Z. Yang, and M. I. Jordan. A reinforcement learning approach in multi-phase second-price auction design. arXiv preprint arXiv:2210. 10278, 2022.
[2] S. Alaei, Hartline, R. Niazadeh, E. Pountourakis, and Y. Yuan. Optimal auctions anony-
mous pricing. Games and Economic Behavior, 118:494-510, 2019.
[3] M.-F. F. Balcan, T. Sandholm, and E. Vitercik. Sample complexity of automated mechanism
design. Advances in Neural Information Processing Systems, 29, 2016.
[4] S. Boyd, S. P. Boyd, and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
[5] E. H. Clarke. Multipart pricing of public goods. Public choice, pages 17-33, 1971.
[6] R. Cole and T. Roughgarden. The sample complexity of revenue maximization. In Proceedings of the forty-sixth annual ACM symposium Theory of computing, pages 243-252, 2014.
[7] V. Conitzer and T. Sandholm. Complexity of mechanism design. In Proceedings of the Eighteenth conference on Uncertainty in artificial intelligence, pages 103-110, 2002.
[8] V. Conitzer and T. Sandholm. Self-interested automated mechanism design and implications for optimal combinatorial auctions. In Proceedings of the 5th ACM Conference Electronic Commerce, pages 132-141, 2004.
[9] M. Curry, T. Sandholm, and J. P. Dickerson. Differentiable economics for randomized affine maximizer auctions. CoRR, abs/2202.02872, 2022. URL htt./httpp://rzzivorr//aaaa
02872
[10] C. Daskalakis and S. M. Weinberg. Symmetries and optimal multi-dimensional mechanism design. In Proceedings of the 13th ACM conference on Electronic commerce, pages 370-387, 2012.
[11] C. Daskalakis, A. Deckelbaum, and C, Tzamos. Strong duality for multiple-good monopolist. Econometrica, 85(3):735-767, 2017.
[12] Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume 1 (Long and Short Papers), pages 4171-4186. Association for Computational Linguistics, jun 2019.
[13] Dhangwatnotai, T. Roughgarden, and Yan. Revenue maximization with a single sample. Games and Economic Behavior, 91:318-23 (1118-33,,22 2015.
[14] Z. Duan, J. Tang, Y. Yin, Z. Feng, X. Yan, M. Zaheer, and X. Deng. A context- -ontext-integrated transformer- based neural network for auction design. In International Conference on Machine Learning. PMLR, 2022.
[15] P. Dütting, F. Fischer, P. Jirapinyo. J. K. Lai, B. Lubin, and D. C. Parkes. Payment rules through discriminant-base classifiers. ACM Transactions on Economics and Computation, 3(1), 2015.
[16] Dütting, Z. Feng, N. Golowich, H. Narasimhan, D. C. Parkes, and S. S. Ravindranath. Machine learning for optimal economic design. In The Future of Economic Design, pages 495-515. Springer, 2019.
[17] Dütting, Z. Feng. H. Narasimhan, D. Parkes, and S. S. Ravindranath. Optimal auctions through deep learning. In International Conference on Machine Learning, pages 1706-1715. PMLR, 2019.
[18] Z. Feng, H. Narasimhan, and D. C. Parkes. Deep learning for revenue-optinee auctions with budgets. In Proceedings of the 17th International Conference on Aulonomous Agents and Multiagent Systems, pages 354-362, 2018.
[19] N. Golowich, H. Narasimhan, and D. C. Parkes. Deep learning for multi-facility location mechanism design. In IJCAI, pages 261-267, 2018.
[20] Y. A. Gonczarowski and N. Nisan. Efficient empirical revenue maximization in single-parameter auction environments. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 8566868,777 2017.

---

[21] Y. A. Gonczarowski and S. M. Weinberg. The sample complexity of up-to-E multi-dimensional revenue maximization. Journal of the ACM (JACM), 68(3):1-28, 2021.
[22] T. Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages
617-631, 1973.
[23] C. Guo, Z. Huang, and X. Zhang. Settling the sample complexity of single-parameter revenue maximization. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, pages 662-673, 2019.
[24] M. Guo and V. Conitzer. Computationally feasible automated mechanism design: General approach and case studies. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 24, pages 1676-1679, 2010.
[25] J. Hartford, D. Graham, K. Leyton-Brown Broww, and S. Ravanbakhsh. Deep models of interactions across sets. In International Conference on Machine Learning, pages 1909-1918. PMIR, 2018.
[26] Hartline and S. Taggart. Sample complexity for non-truthful mechanisms. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 399-416, 2019.
[27] J. D. Hartline and T. Roughgarden. Simple versus optimal mechanisms. In Proceedings of the 10th ACM conference on Electronic commerce, pages 225-234, 2009.
[28] Z. Huang, Y. Mansour, and T. Roughgarden. Making the most of your samples. SIAM Journal on Computing, 47(3):651-66 1-66444, 2018.
[29] Jin, Song, H. Li, K. Gai, J. Wang, and W. Zhang. Real-time bidding with multi multi-agent reinforcement learning in display advertising. In Proceedings of the 27th ACM international conference on information and knowledge management, pages 2193-2201, 2018.
[30] Y. Jin, P. Lu, Q. Qi, Z. G. Tang, and T. Xiao. Tight approximation ratio of anonymous pricing. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, pages 674-685, 2019.
[31] Y. Jin, P. Lu, Z. G. Tang, and T. Xiao. Tight revenue gaps among simple mechanisms. SIAM Journal on Computing, 49(5):927-958, 2020.
[32] Kothari, S. Singla, D. Mohan, A. Schvartzman, and S. M. Weinberg, Approximation schemes for a unit-demand buyer with independent items via symmetries. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 220-232. IEEE, 2019.
[33] K. Kuo, A. Ostuni, F. Horishny, M. J. Curry, S. Dooley, P.-y. Chiang, T. Goldstein, and J. P. Dickerson. Proportionnet: Balancing fairness and revenue for auction design with deep learning. arXiv preprint arXiv:2010.063398 2020.
[34] S. Lahaie. A kernel-based iterative combinatorial auction. In Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
[35] A. Likhodedov, T. Sandholm, al. Approximating revenue- maximizing combinatorial auctions.
In AAAI, volume 5, pages 267-274, 2005.
[36] X. Liu, C. Yu, Z. Zhang. Z. Zheng, Y. Rong, H. Lv, D. Huo, Y. Wang, D. Chen, J. Xu, et al. Neural auction: End-to-end learning of auction mechanisms for e-commerce advertising. In Proceedings of the 27th ACM SIGKDI Conference on Knowledge Discovery & Data Mining, pages 3364,336,, 2021.
[37] A. M. Manelli and D. R. Vincent. Bundling as optimal selling mechanism for a multiple-good monopolist. Journal of Economic Theory, 127(1):1-35, 2006.
[38] Manisha, C. Jawahar, and S. Gujar. Learning optimal redistribution mechanisms through neural networks. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 345-353, 2018
[39] M. Mohri and A. M. Medina. Learning algorithms for second-price auctions with reserve. The Journal of Machine Learning Research, 17(1):632-2263 2016.
[40] Morgenstern and T. Roughgarden. Learning simple auctions. In Conference on Learning Theory, pages 1298-1318. 8. PMLR, 2016.
[41] J. H. Morgenstern and T. Roughgarden. On the pseudo-dimension of nearly optimal auctions. Advances in Neural Information Processing Systems, 28, 2015.
[42] R. B. Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
12

---

[43] H. Narasimhan and D. C. Parkes. A general statistical framework for designing strategy- proof assignment mechanisms. In UAI' 16 Proceedings of the Phirot-Second Conference on Uncertainty in Artificial Intelligence, 2016.
[44] H. Narasimhan, S. B. Agarwal, and D. C. Parkes. Automated mechanism design without money via machine learning. In Proceedings of the 25th International Joint Conference on Artificial Intelligence, 2016.
[45] T. Nedelec, N. EI Karoui, and V. Perchet. Learning to bid in aevenue-maximizie auctions. In International Conference on Machine Learning, pages 4781-4789. PMLR, 2019.
[46] T. Nedelec, J. Baudet, V. Perchet, and N. El Karoui. Adversarial learning for revenue- maximizing auctions. In 20th International Conference on Autonomous Agents and Multiagent Systems, 2021.
[47] K. T. Nguyen. A bandit learning algorithm and applications to auction design. Advances in Neural Information Processing Systems, 33; 13:12070-12079 2020.
[48] X. B. Peng, A. Kanazawa, S. Toyer, P. Abbeel, and S. Levine. Variational discriminator bottleneck: Improving imitation learning, inverse rl, and gans by constraining information flow. In International Conference on Learning Representations, 2018.
[49] N. Peri, M. Curry, S. Dooley, and J. Dickerson. Preferencenet: Encoding human preferences in auction design with deep learning. Advances in Neural Information Processing Systems, 34, 2021.
[50] T. Qin, F. He, D. Shi, W. Huang, and D. Tao. Benefits of permutationn-quuiariincc in auction mechanisms. Advances in Neural Information Processing Systems, 35, 2022.
[51] J. Rahme, S. Jelassi, J. Bruna, and S. M. Weinberg. A permutaaionn-equivaiini neural network architecture for auction design. Proceedings of the AAAI Conference on Artificial Intelligence 3566):5664-5672, May 2021. URL https://ojs aaai org/ index. wwtpinxxxpp.pppppppppmppe artticee view/16711
[52] Rahme, S. Jelassi, and S. Weinberg. Auction learning as a two-player game. In Inter- national Conference Learning Representations, 2021. URL https: net/ forum?2d=-HHeee061166
[53] S. S. Ravindranath, Z. Feng, S. L., Ma, S. D. Kominers, and C. Parkes. Deep learning for two-sided matching. arXiv preprint arXiv: (it.::107.0322,, 2021.
[54] T. Sandholm. Automated mechanism design: A new application area for search algorithms. In International Conference on Principles and Practice of Constraint Programming, pages 19-36. Springer, 2003.
[55] T. Sandholm and A. Likhodedov. Automated design of rexenue-maximizing combinatorial auctions. Operations Research, 6305):1000-1025 2015.
[56] W. Shen, P. Tang, and S. Zuo. Automated mechanism design via neural networks. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 115-223,,20 2019.
[57] V. Syrgkanis. A sample complexity measure with applications learning optimal auctions. Advances in Neural Information Processing Systems, 30, 2017.
[58] A. Tacchetti, D. Strouse, M. Garnelo, T. Graepel, and Y. Bachrach. A neural architecture for designing truthful and efficient auctions. CoRR, abs/1907.05181, 2019. URL http:
/ //axxiv.org/aaaa hbt///9b/1990.... 051881
[59] Tang. Reinforcement mechanism design. In IJCAI, pages 1146-5150, 2017.
[60] A. Vaswani, Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and
I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[61] W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 37, 1961.
[62] J. Weissteiner and S. Seuken. Deep Saaning-powertt iterative combinatorial auctions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2284-2293, 2020.
13

---

[63] L. Yuan, Y. Chen, T. Wang. W. Yu, Y. Shi, Z.-H. Jiang, F. E. Tay, J. Feng, and S. Yan. Tokens- to-token vit: Training vision transformers from scratch on imagenet. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 558-567, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yss]
(b) Did you describe the limitations of your work? [Yes] See the end of Section 4.1.
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not foresee such an impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] We include the code as a URL.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes] See the Appendix.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] In Table 1, we report aggregated standard deviations.
In the Appendix, we report the learning curves with the error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See the Appendix.
14


Reviews:
[{"review_id": "wxnZnSzFksN", "reviewer": "Reviewer_M3wB", "summary": "The use of deep learning for mechanism design is an expanding area. One important paper in the field, RegretNet, directly uses deep neural networks to approximate strategyproof and revenue-maximizing auctions. The current work builds on RegretNet in several ways. First, it uses an attention-based architecture -- this seems to work well, and has the key advantage of being permutation-equivariant (a desirable property, as it is known that permutation-equivariant mechanisms are optimal for symmetric auction design problems and often good in general). It also allows networks trained on one input size to generalize successfully to other input sizes. Second, the authors prevent a modified training algorithm that makes it easier to specify an acceptable small violation of the strategyproofness constraint, while reducing the complexity of tuning RegretNet's strange hyperparameters. The authors test their method and show performance that usually beats previous methods across a wide range of settings.", "questions": "- How might your architecture be modified to support unit-demand constraints (i.e. both rows and columns of the allocation matrix sum to <=1)? Is it as straightforward as just tacking the RegretNet approach on the end?\n\n- How might your method be modified when equivariance is undesirable (e.g. for non-symmetric valuation distributions where you really do want to discriminate against one bidder)?", "limitations": "- The claim, mentioned as an aside, that the Myerson auction relies on having the full parametric valuation distribution seems not entirely correct to me, and I think this should be clarified. For one thing, Duetting et al. gives the \"MyersonNet\" architecture in their appendix; for another, there is a lot of work (cited with admirable thoroughness in the related work section) on sample complexity of revenue maximizing auctions where you can learn to approximate the right reserve price. I think methods like these would count as a \"Myerson baseline\" but work fine from samples.\n\n- The authors are honest about where their work has limitations (e.g. low regret budget underperforming Myerson). I think a little bit more discussion and speculation about reasons the performance of the high/low regret budgets is warranted, although the NeurIPS page limit may prevent this.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality\n    - It's a fairly natural idea to use transformers for auctions, because apparently people can use them for everything else too. There is concurrent work (CITransNet of Duan et al.) that also uses transformers and has some of the same advantages (generalization, equivariance).\n    - In addition to the transformer idea, this paper presents some useful techniques, either explicitly claimed as contributions (e.g. the tweaked training objective) or implicitly (the methodology for making sure the performance gap is real).\n- Significance:\n    - I think this is a significant and valuable piece of work. It presents new state-of-the-art results for automated mechanism design, a new training procedure which is easier to work with, and is very methodologically careful in the way it evaluates performance.\n- Quality\n    - The quality is high, especially in the extremely thorough experiments. It's particularly nice that the authors take the time (section 4.2) to do experiments to make sure apparent outperformance is not just due to \"gradient obfuscation\" interfering with the misreport procedure, but is more likely due to actually finding a better mechanism.\n    - The actual results in terms of performance don't seem like a complete slam dunk. It is true that in basically all cases, the RegretFormer *architecture* does better than the RegretNet/EquivariantNet architectures.\nAnd for the medium 10^{-4} regret budget, things look great. But for the high regret budget, revenues seem oddly high across all networks. And for the low regret budget, revenues are depressingly low. So I am convinced that the RegretFormer architecture is better than previous alternatives, but have some reservations about the new training method (although it still seems to have advantages).\n- Clarity\n    - Everything is explained quite clearly.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vpf3QxmClAz", "reviewer": "Reviewer_u7uQ", "summary": "This paper modifies the RegreNet architecture and training in the following ways -  \n(1) it replaces the neural network architecture with a transformer  \n(2) it replaces the augmented lagrangian optimization with a new loss formulation (rather than enforcing IC violation to be strictly 0, it only requires them to be at some threshold $R_{max}$", "questions": "(1) Is Eqn (6) missing a term perhaps something like $\\max (\\tilde{R} - R_{max}, 0)$ ?   \n(2) There are other symmetric distributions where this architecture can be tested - single bidder but from the uniform interval [c, c+1], uniform triangle settings/correlated valuations, and settings with unit-demand valuations where we know the optimal solution analytically.  \n(3) How is the regret computed at test time? How many samples of misreports are initialized and how many gradient descent steps to compute them? What is the size of the test set?  \n(4) Can you visualize the solution for the 1x2 setting? The optimal auction is given by Maneli and Vincent which has 4 deterministic menu options. This achieves a revenue of $0.55$. Selling it as a grand bundle has revenue that's slightly less than $0.55$ My intuition is that the setting when $R_{max} = 1e-5$, the latter is recovered based on the revenue values reported. If this is the case, perhaps the proposed optimization algorithm here is sensitive to $\\gamma$ initialization as well.\n(5) Would be possible to use tools from [Certifying Strategyproof Auction Networks](https://arxiv.org/abs/2006.08742) to compute regret more accurately?", "limitations": "Discussed above!", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**: \nThe paper aims to tackle problems that are significant and relevant and are in the right direction - it would be nice to use optimization methods that were less sensitive to the hyperparameters than the augmented Lagrangian optimization method.\n\n**Weaknesses**: \n(1) The contribution is not significantly novel. The use of transformers was already proposed by [54]\n(2) The transformer architecture has limitations - it can't handle asymmetric distributions.\n(3) Eqn (6) doesn't seem to be a proper relaxation of the optimization problem in (5). \n(4) The evaluation is limited. The authors only consider uniform distribution on the interval\n(5) Missing details on regret computation at test time\n(6) I'm not convinced that the cross-misreport testing rules out the possibility of regret being accurate. The loss landscapes are very different for different neural network architectures. While low regret on cross misreports is a necessary condition, it isn't a sufficient one. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "um3VouMv09w", "reviewer": "Reviewer_Yfdp", "summary": "This paper presents a new architecture for auction design, RegretFormer, which is based on the Transformer architecture. Unlike the original RegretNet, RegretFormer is invariant to the number of items and bidders and is permutation equivariant due to attention mechanisms. In addition, the authors relax the loss objective by introducing a regret budget $R_{max}$ to allow for smoother training and more robustness to hyperparameters. RegretFormer is shown to outperform baselines in both revenue and regret overall. Moreover, the authors confirm the validity of the regret estimates via a novel cross-misreports approach where the regret of one network is estimated on the optimal misreports approximated by another network. The results show that there is little evidence of over-estimate/bias in the regret estimates.", "questions": "- What is the size of your networks in terms of number of parameters compared to baselines? It would nice to see these number to ensure that the comparison between baselines is fair enough.\n- How robust is RegretFormer to different hyperparameters compared to RegretNet and EquivariantNet?\n- The generalization results in Table 3 show that RegretFormer outperforms EquivariantNet when trained on 3x10 setting but the same is not true for smaller settings like 1x2 and 2x2? Do you have intuition on why this is the case?\n- How much does RegretFormer benefit from the modified loss objective? An small ablation study would be helpful here.", "limitations": "While the results are positive, I found the paper to be lacking in terms of analysis of the results to better understand the advantages/disadvantages of RegretFormer. For example, how sample efficient is RegretFormer compared to baselines?", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n- The RegretFormer architecture offers desirable properties of invariance and permutation equivariance due to attention.\n- The authors propose a smoother loss function that allows for pre-specification of a regret budget.\n- The cross-misreport experiments offer a nice approach to validate the regret estimates which may be heavily biased by the trained network.\n\n### Weakness:\n- The authors claim that there modified loss function is more robust to hyperparameters. However, there are no experiments to prove this. It would be nice to see the performance under different hyperparameters compared to baselines.\n- While RegretFormer is well justified for this problem, the architecture itself is a straightforward application of the transformer architecture.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PMIR8mEE3oC", "reviewer": "Reviewer_VVEG", "summary": "This paper introduces a transformer-based network architecture called RegretFormer to address the problem of optimal auction design. RegretFormer differs from prior optimization techniques that frame the problem as a mini-max between regret and revenue. Instead, RegretFormer defines a fixed regret budget and maximizes revenue. Maximum regret is used as a single interpretable hyperparameter to tune the auction design. The transformer architecture allows for variable sized inputs, and attention is used to enforce equivariance. RegretFormer only studies symmetric auctions, leaving asymmetric auctions (with the use of positional encoding) as future work. Different from prior works (c.f. RegretNet and EquivarientNet), RegretFormer uses a single network to predict both allocations and payments. Lastly, this paper proposes two supplemental evaluation protocols, namely cross-misreport regret estimates and network distillation to verify that the performance improvement over prior works is genuine.\n", "questions": "1. How long does it take to train RegretFormer when compared to RegretNet and EquivariantNet. How does this scale according to the size of the auction? \n2. Since the distribution of bids are different depending on the size of the auction, it isn't clear why we would expect \"zero-shot\" out-of-setting generalization by default. Is it the case that the RegretFormer architecture allows us to fine tune for new settings with fewer examples?\n3. Does evaluating with the proposed \"fair\" protocol defined above change any conclusions?\n", "limitations": "Authors highlight that although modulating the maximum regret parameter should proportionally change revenue, this sometimes does not hold. Since the interpretable maximum regret parameter is a key selling point of this work, it would be useful to implement the proposed solution (L247) to show that this tighter revenue/regret ratio holds. Authors also present general limitations of a regret-based approach to auction design, highlighting that under the smallest regret budget, regret is still non-zero. \nIt would be helpful to make limitations of this method an explicit subsection. The current writeup (L250) reads as \"all methods have limitations, but RegretFormer does better\", which isn't particularly helpful for understanding where RegretFormer fails.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is generally well written and clear. The main takeaways are clear and the authors appropriately juxtapose their work in the context of prior work (c.f. RegretNet and EquivariantNet) and make it clear how their work differs. The authors convincingly show that RegretFormer performs better than both RegretNet and EquivariantNet. Moreover, the authors ask the right question - is the performance gap genuine? Authors devise protocols for addressing this question. \n\nThe cross-misreport regret estimate, although well motivated, is not convincing because there is no empirical proof to suggest how much an adversarially constructed example would underestimate regret. Without this point of reference, it's difficult to interpret the results presented in Table 3 (given variance between training runs). However, the network distillation seems to have the opposite problem, the result is convincing, but since RegretFormer is able to outperform EquivariantNet and RegretNet, the motivation that network architecture of RegretFormer impairs its ability to approximate optimal misreports isn't a major concern. To be clear, these attempts at deeply understanding if the performance improvement by RegretFormer is genuine are appreciated.\n\nOne concern about evaluation is w.r.t setting a maximum regret for comparison (Table 1). From the main paper, it's not clear how maximum regret is enforced for RegretNet and  EquivariantNet since these are optimized as a mini-max of regret and revenue. According to Appendix 1.2, it seems like exponential annealing is used to achieve this constraint. However, since this is not how either RegretNet or EquivariantNet are normally trained and (L182) both models are sensitive to the hyperparameters and training protocol, is the comparison with RegretFormer at a fixed maximum regret fair? Here's a protocol that may address this concern: First, train RegretNet using the standard unconstrained (w.r.t maximum regret) optimization. Given the maximum regret of the trained RegretNet, set this is the maximum regret of RegretFormer and train the model. Now the comparison is fair. This protocol can be naturally extended to EquivariantNet. Ideally, it might be the case that RegretFormer still outperforms prior methods.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept