# benefits_of_permutationequivariance_in_auction_mechanisms__1631f3ed.pdf

Benefits of Permutation-Equivariance in Auction Mechanisms

Tian Qin1, 2 Fengxiang He2 Dingfeng Shi2 Wenbing Huang3, 4 Dacheng Tao2

1University of Science and Technology of China 2JD Explore Academy, JD.com Inc. 3Gaoling School of Artificial Intelligence, Renmin University of China 4Beijing Key Laboratory of Big Data Management and Analysis Methods tqin@mail.ustc.edu.cn, fengxiang.f.he@gmail.com, shidingfeng@buaa.edu.cn, hwenbing@126.com, dacheng.tao@gmail.com

Designing an incentive-compatible auction mechanism that maximizes the auctioneer s revenue while minimizes the bidders ex-post regret is an important yet intricate problem in economics. Remarkable progress has been achieved through learning the optimal auction mechanism by neural networks. In this paper, we consider the popular additive valuation and symmetric valuation setting; i.e., the valuation for a set of items is defined as the sum of all items valuations in the set, and the valuation distribution is invariant when the bidders and/or the items are permutated. We prove that permutation-equivariant neural networks have significant advantages: the permutation-equivariance decreases the expected ex-post regret, improves the model generalizability, while maintains the expected revenue invariant. This implies that the permutation-equivariance helps approach the theoretically optimal dominant strategy incentive compatible condition, and reduces the required sample complexity for desired generalization. Extensive experiments fully support our theory. To our best knowledge, this is the first work towards understanding the benefits of permutation-equivariance in auction mechanisms.

1 Introduction

Optimal auction design [30] has wide applications in economics, including computational advertising [18], resource allocation [16], and supply chain [4]. In an auction, every bidder has a private valuation profile over all items, and accordingly, submits her bid profile. An auctioneer collects the bids from all bidders, and determines a feasible item allocation to the bidders as well as the prices the bidders need to pay. Consequently, every bidder receives her utility. From the auctioneer s perspective, the optimal auction mechanism is required to maximize her revenue, defined as the sum of all bidders payments. From the aspect of the bidders, the optimal auction mechanism needs to incentivize every bidder to bid their truthful valuation profiles (truthful bidding). This is summarized as the dominant strategy incentive compatible (DSIC) condition; i.e., truthful bidding is always the dominant strategy for every bidder [25].

The optimal auction mechanism can be approximated via neural networks [12, 29, 10]. The approximation error , or the distance to the DSIC condition, is usually measured by the ex-post regret, defined as the gap between the bidder s utility of truthful bidding and the utility when her bid profile is only the best to herself (selfish bidding), while the bid profiles of all other bidders are fixed in both cases [12]. When a bidder s ex-post regret is 0, truthful bidding is her dominant strategy. Therefore, the optimal auction design can be modeled as a linear programming problem, where the object is to maximize the expected revenue subject to the expected ex-post regret being 0 for all bidders [12].

Both authors contributed equally.

36th Conference on Neural Information Processing Systems (Neur IPS 2022).

Another major consideration in learning the optimal mechanism is the generalizability to unseen data, usually measured by the generalization bound, i.e., the upper bound of the gap between the expected revenue/ex-post regret and their empirical counterparts on the training data [12].

In this paper, we consider the popular setting of additive valuation and symmetric valuation [12, 29, 10]. The additive valuation condition defines the valuation for a set of items as the sum of the valuations for all items in this set. The symmetric valuation condition assumes the joint distribution of all bidders valuation profiles to be invariant when bidders and/or items are permutated. This setting covers many applications in practice. For example, when items are independent, the additive valuation condition holds. Moreover, if the auction is anonymous or the order of the items is not prior-known, the symmetric valuation condition holds.

We demonstrate that permutation-equivariant models have significant advantages in learning the optimal auction mechanism as follows. (1) We prove that the permutation-equivariance in auction mechanisms decreases the expected ex-post regret while maintaining the expected revenue invariant. Conversely, and equivalently, the permutation-equivariance promises a larger expected revenue, when the expected ex-post regret is fixed. (2) We show that the permutation-equivariance of auction mechanisms reduces the required sample complexity for desirable generalizability. We prove that the l ,1-distance between any two mechanisms in the mechanism space decreases when they are projected to the permutation-equivariant mechanism (sub-)space. This smaller distance implies a smaller covering number of the permutation-equivariant mechanism space, which further leads to a small generalization bound [12].

We further provide an explanation for the learning process of non-permutation-equivariant neural networks (NPE-NNs). In learning the optimal auction mechanism by an NPE-NN, we show that an extra positive term exists in the quadratic penalty of the ex-post regret based on the result (1). This term serves as a regularizer to penalize the non-permutation-equivariance . Moreover, this regularizer also interferes the revenue maximization, and thus affects the learning performance of NPE-NNs. This further explains the advantages of permutation-equivariance in auction design.

Experiments in extensive auction settings are conducted to verify our theory. We design permutationequivariant versions of Regret Net (Regret Net-PE and Regret Net-test) by projecting the Regret Net [12] to the permutation-equivariant mechanism space in the training and test stage respectively. The empirical results show that permutation-equivariance helps: (1) significantly improve the revenue while maintain the same ex-post regret; (2) record the same revenue with a significantly lower ex-post regret; and (3) narrow the generalization gaps between the training ex-post regret and its test counterpart. These results fully support our theory.

Related works. Myerson completely solves the optimal auction design problem in one-item auctions [23]. However, solutions are not clear when the number of bidders/items exceeds one [12]. Initial attempts have been presented on the characterization of optimal auction mechanisms [20, 26, 9] and algorithmic solutions [1, 2, 27]. Remarkable advances have been made in the required sample complexity for learning the optimal auction mechanism in various settings, including single-item auctions [5, 21, 16], multi-item single-bidder auctions [11], combinatorial auctions [3, 32], and allocation mechanisms [24]. Machine learning-based auction design (automated auction design) have obtained considerable progress [6, 7, 31]. The optimal auction design is modeled as a linear programming problem [6, 7]. However, early works suffer from the scalability issues that the number of the constraints grows exponentially when the bidder number and the item numbers increase. To address this issue, recent works propose to learn the optimal auction mechanism by deep learning. Regret Net is designed for multi-bidder and multi-item settings [12]. Then, Regret Net is developed to meet more restrictive constraints, such as the budget condition [14] and the certifying strategyproof condition [8]. Rahme et al. [29] propose the first equivariant neural network-based auction mechanism design method with significant empirical advantages. Ivanov et al. [17] propose a Regret Former which (1) introduces attention layers to Regret Net to learn permutation-equivariant auction mechanisms, and (2) adopts a new interpretable loss function to control the revenue-regret trade-off. Duan et al. [10] extend the applicable domain to contextual settings. All these works make remarkable contributions in designing new algorithms from the empirical aspect only. However, the theoretical foundations are still elusive. To our best knowledge, our paper is the first work on theoretically studying the benefits of permutation equivariance in auction design via deep learning.

2 Notations and Preliminaries

Auction. Suppose n bidders are bidding m items in an auction. Every bidder i has her biddercontext (feature) xi X, while every item j is associated with its item-context (feature) yj Y. The bidder i has a private valuation vij V R 0 for the item j, which is sampled from a conditioned distribution P( |xi, yj). The value profile vi = (vi1, . . . , vim) is unknown to the auctioneer. For the simplicity, we define x = (x T 1 , . . . , x T n)T , y = (y1, . . . , ym), v = (v T 1 , . . . , v T n )T , v i = (v T 1 , . . . , v T i 1, v T i+1, . . . , v T n )T , and (v i, v i) = (v T 1 , . . . , (v i)T . . . , v T n )T .

Every bidder submits a bid profile bi to the auctioneer according to her valuation profile. Then, the auctioneer determines a feasible item allocation g(b, x, y) and corresponding payments p(b, x, y) as per an auction mechanism (g, p). Consequently, every bidder receives her utility as

ui(vi, b, x, y) =

j=1 gij(b, x, y) vij pi(b, x, y).

The auction mechanism (g, p) consists of an allocation rule g : Rn m X n Ym Rn m and a payment rule p : Rn m X n Ym Rn m, where gij is the probability of allocating item j to the bidder i, and pi = Pm j=1 pij is the price that the bidder i should pay. To avoid allocating an item over once, the allocation rule is constrained such that Pn i=1 gij(b, x, y) 1 for all j [m]. Every vi in our notations can be replaced by bi. Thus, we can define the similar notations: b i = (b T 1 , . . . , b T i 1, b T i+1, . . . , b T n)T , (bi, v i) = (v T 1 , . . . , (bi)T . . . , v T n )T and (vi, b i) = (b T 1 , . . . , (vi)T . . . , b T n)T .

Optimal auction mechanism. An auction mechanism (g, p) is defined to be dominant strategy incentive compatible (DSIC), if truthful bidding is always a dominant strategy of every bidder; i.e.,

ui(vi, (vi, b i), x, y) ui(vi, b, x, y),

for all i [n], v, b Vn m, x X n and y Ym. In addition, an auction mechanism (g, p) is called individually rational (IR), if for any bidder-contexts x X n, any item-contexts y Ym, any bidder i [n] x X n, valuation profile and bid profile v, b Vn m, truthful bidding always leads to a non-negative utility, i.e., ui(vi, (vi, b i), x, y) 0. If an auction mechanism is DSIC and IR, a rational bidder with an obvious dominant strategy will play it (bidding truthfully). Moreover, an optimal auction mechanism is required to maximize the auctioneer s expected revenue rev = E(v,x,y) Pn i=1 pi(v, x, y) .

Auction design. The ex-post regret regi(v, x, y) for the bidder i is defined as

max b i Vm ui(vi, (b i, v i), x, y) ui(vi, v, x, y).

An auction mechanism (g, p) is DSIC, if and only if Pn i=1 regi(v, x, y) = 0 for any value profile v Vn m, bidder-context x X n, and item-context y Ym. Suppose the payment rule p satisfies pi(b, x, y) Pm j=1 gij(b, x, y)bij, which implies that each bidder has a nonnegative utility. Then, the auction design can be modeled as a linear programming problem that maximizes the expected revenue E(v,x,y)[Pn i=1 pi(v, x, y)] subject to the expected ex-post regret E(v,x,y)[Pn i=1 regi(v, x, y)] = 0. Without loss of generality, the ex-post regret may refer to the average of all bidders ex-post regrets. Definition 2.1. Suppose the network s parameter is ω, and the bidder i s empirical payment and expost regret are defined as 1

L PL l=1 pω i (v(l), x(l), y(l)), and d regi(ω) = 1

L PL l=1 regω i (v(l), x(l), y(l)), where the sample set {(v(l), x(l), y(l))}L l=1 is i.i.d. sampled from the following prior distribution, P(v, x, y) = Qn,m i,j=1 P(vij|xi, yj)PXi(xi)PYj(yj).

Equivariant mapping. We define a mapping f as G-equivariant if ψg f = f ρg for two chosen group linear representations ρ and ψ and any g in group G.

Definition 2.2 (Permutation-Equivariant Mapping). A permutation-equivariant mapping is defined to be f : Rn m Rn m that for any instance x Rn m, and permutation matrices σn Rn n and σm Rm m, we have f(σnxσm) = σnf(x)σm.

In this paper, we consider the bidder-permutation σn Rn n and item-permutation σm Rm m. Specifically, we define a mapping f is bidder-symmetric or item-symmetric, if f(σnx) = σnf(x) or f(xσm) = f(x)σm, respectively. Moreover, we define an auction mechanism (g, p) as biddersymmetric or item-symmetric, if the allocation rule g and the payment rule p are both biddersymmetric or item-symmetric.

Orbit averaging. For any feature mapping f : F G, the orbit averaging Q on f is defined as Qf = 1 |G| P g G ψ 1 g f ρg, where ρ and ψ are two chosen group representations acting on the feature spaces F and G, respectively. Orbit averaging can project any mapping to be equivariant:

Proposition 2.3. Orbit averaging Q is a projection to the equivariant mapping space {f : ψ f = f ρ}, i.e., ψ Qf = Qf ρ and Q2 = Q. In particular, if f is already equivariant, then Qf = f.

Moreover, Qu and Qreg refer to the utility and the ex-post regret induced by Qg and Qp. For the simplicity, we denote the orbit averagings that modify the auction mechanism to be biddersymmetric, item-symmetric, and bidder/item-symmetric by bidder averaging Q1, item averaging Q2, and bidder-item aggregated averaging Q3. Besides, a detailed proof of the feasibility of the projected mechanisms can be found in Appendix A.1.

Hypothesis complexity. The generalizatbility to unseen data is usually measured by the generalization bound, which depends on the hypothesis set s complexity. To characterize the complexity of the hypothesis set, we introduce the following definitions of covering number N ,1 and its corresponding distance l ,1. Based on the covering number, we can obtain a generalization bound in Theorem 3.6.

Definition 2.4 (l ,1-distance). Let X be a feature space and F a space of functions from X to Rn. The l ,1-distance on the space F is defined as l ,1(f, g) = maxx X (Pn i=1 |fi(x) gi(x)|).

Definition 2.5 (Covering number). Covering number N ,1(F, r) is the minimum number of balls with radius r that can cover F under l ,1-distance.

3 Theoretical Results

This section presents the theoretical results. For simplicity, we view p = (p1, . . . , pn)T as a n 1 matrix to present the prices the bidders should pay. We first prove that the permutation-equivariance induces the same expected revenue and a smaller expected ex-post regret in Section 3.1. Next in Section 3.2, we prove that the permutation-equivariant mechanism space has a smaller covering number, which promises a smaller required sample complexity and a better generalization. Detailed proofs are omitted from the main text and given in supplementary materials due to space limitation.

3.1 Benefits for Revenue and Ex-Post Regret

In this section, we discuss the benefits for the revenue and the ex-post regret in the conditions of bidder-symmetry and item-symmetry separately, and then discuss the benefits when both of them hold. Based on these results, we also study the learning process of non-permutation-equivariant neural networks for auction design.

3.1.1 Benefits in the Bidder/Item-Symmetry Condition

When the bidders come from the same distribution, the joint valuation distribution f is invariant under bidder-permutation, i.e. f(σnv, σnx, y) = f(v, x, y) for any σn Sn. Meanwhile, when the items are indistinguishable, the joint distribution f is invariant under item-permutation, i.e., f(vσm, x, yσm) = f(v, x, y) for any σm Sm. Both conditions do not always hold simultaneously. In this section, we study them separately.

To measure the non-permutation-equivariance of the mechanism, we introduce the conception of regret gap between the projected mechanism and the original mechanism as below,

(g, p; v, x, y) = max v Vn m

i=1 ui(vi, (v i, v i), x, y) max v Vn m

i=1 [Q u]i(vi, (v i, v i), x, y),

where v is the valuation profiles, vi is the valuation profile of bidder i, x is the bidder-context, y is the item-context, and the orbit averaging Q can be the bidder averaging Q1 or the item averaging Q2.

The bidder averaging Q1 and the item averaging Q2 acting on the allocation rule g and the payment rule p, respectively, are as below,

Q1g(v, x, y) = 1

σn Sn σ 1 n g(σnv, σnx, y), Q1p(v, x, y) = 1

σn Sn σ 1 n p(σnv, σnx, y),

Q2g(v, x, y) = 1

σm Sm g(vσm, x, yσm)σ 1 m , and Q2p(v, x, y) = 1

σm Sm p(vσm, x, yσm).

We thus can prove the following theorem that characterizes the benefits of permutation-equivariance for revenue and ex-post regret in the condition of bidder/item-symmetry. Theorem 3.1 (Benefits for revenue and ex-post regret in the condition of bidder/item-symmetry). When the valuation distribution is invariant under permutations of bidders/items, the projected mechanism has the same expected revenue and a smaller expected ex-post regret, that is,

i=1 [Q p]i(v, x, y) = E(v,x,y)

i=1 pi(v, x, y) , and (1)

i=1 regi(v, x, y) E(v,x,y)

i=1 [Q reg]i(v, x, y) = E(v,x,y) h (g, p; v, x, y) i 0,

where p is the payment rule, reg is the ex-post regret, and Q is the bidder/item averaging.

A smaller expected ex-post regret implies this mechanism is closer to the dominant strategy incentive compatible condition. Conversely, and equivalently, when the expected ex-post regrets are fixed, the projected auction mechanism has a larger expected revenue. For any auction mechanism, in the bidder/item-symmetry condition, we can project it through the bidder/item averaging. Remark 3.2. The mechanism space can be decomposed into the direct sum of the permutationequivariant mechanism space {M : QM = M} and the complementary space {N : QN = 0} [13]. Thus, a mechanism M has a unique decomposition: M = QM + N. The pure permutationequivariant part QM contains all and only the permutation-equivariance of the mechanism M. The pure non-permutation-equivariant part N is independent from the permutation-equivairance. In this way, we may study the influence of permutation-equivariance by comparing the mechanism M and its permutation equivariant part QM.

3.1.2 Interplay between Bidder-Symmetry and Item-Symmetry.

If the valuation distribution is invariant under both bidder-permutation and item-permutation, we can project the mechanism to be permutation-equivariant with respect to both bidder and item in two steps (by mapping Q1 Q2 or mapping Q2 Q1). Consequently, the projected mechanism has the same expected revenue and a smaller expected ex-post regret. Equivalently, we can also project an auction mechanism to be bidder-symmetric and item-symmetric immediately by the bidder-item aggregated averaging Q3 as below,

Q3g(v, x, y) = 1 n!m!

σm Sm σ 1 n g(σnvσm, σnx, yσm)σ 1 m , and

Q3p(v, x, y) = 1 n!m!

σm Sm σ 1 n p(σnvσm, σnx, yσm).

We can prove that the bidder-item aggregated averaging Q3 is the composition of the orbit averaging operators Q1 and Q2, as shown in the following lemma. This lemma shows that the order of Q1 and Q2 would not influence their composition. Lemma 3.3. The bidder-item aggregated averaging is the composition of bidder averaging and item averaging: Q3 = Q1 Q2 = Q2 Q1.

Based on this lemma, we can prove the following theorem on the benefits of permutation-equivariance for revenue and ex-post regret in the condition of both bidder-symmetry and item-symmetry.

Theorem 3.4 (Benefits for revenue and ex-post regret in the condition of both bidder-symmetry and item-symmetry). When the valuation distribution is invariant under both item-permutation and item-permutation, then the projected mechanism has a same expected revenue and a smaller expected ex-post regret, that is,

i=1 Q3pi(v, x, y) = E(v,x,y)

i=1 pi(v, x, y) and

i=1 regi(v, x, y) E(v,x,y)

i=1 [Q3reg]i(v, x, y) = E(v,x,y) h 3(g, p; v, x, y) i 0,

where p is the payment rule, reg is the ex-post regret, and Q3 is the bidder-item aggregated averaging.

The difference between bidder-symmetry and item-symmetry is significant in practice. For example, for a symmetric valuation distribution, when the mechanism is already bidder-symmetric but not item-symmetric, we can project it to be item-symmetric to gain an extra benefit from item-symmetry. That means, the two regret gaps induced by Q1 and Q2 are additive as below,

3(g, p; v, x, y) = 1(g, p; v, x, y) + 2(Q1g, Q1p; v, x, y).

In general, E[ 2(g, p; v, x, y)] = E[ 2(Q1g, Q1p; v, x, y)] and thus E[ 3(g, p; v, x, y)] = E[ 1(g, p; v, x, y)] + E[ 2(g, p; v, x, y)]. Thus, the benefits from bidder-symmetry and itemsymmetry are additive but not strictly independent .

3.1.3 Insights on Training Non-Permutation-Equivariant Mechanism

Because the expected revenue is always the same for the original mechanism and the projected permutation-equivariant mechanism, we only consider the gradient caused by the expected ex-post regret. We can decompose the original expected ex-post regret into the sum of the expected ex-post regret of the projected mechanism and the expectation of the regret gap as below,

i=1 regi(v, x, y) = E(v,x,y)

i=1 [Q3reg]i(v, x, y) + E(v,x,y) h 3(g, p; v, x, y) i .

The regret gap 3(g, p; ) follows from the non-permutation-equivariance of the mechanism M. When the distance l(M, QM) tends to 0, the regret gap converges to 0. When the auction mechanism has a negligible ex-post regret, the expectation of the regret gap is also close to 0. That means, the mechanism is close to being permutation-equivariant. However, even using a symmetric dataset or adopting data augmentation in training, the learned mechanism will not be permutation-equivariant in general [19]. As a result, to achieve negligible ex-post regret, the non-permutation-equivariant models need to learn more samples to approach permutation-equivariance. That is because the non-permutation-equivariant part (expected regret gap) would mislead the gradient of the expected regret but have no benefit to the expected revenue and the expected ex-post regret.

On the other hand, the regret gap can be viewed as a regularizer in the ex-post regret to penalize the non-permutation-equivariance of the mechanism. When the optimizer tries to minimize the ex-post regret, the auction mechanism approaches to be permutation-equivariant. Therefore, if the mechanism achieves a negligible ex-post regret, it is almost to be permutation-equivariant. This result can explain why Regret Net struggles to find permutation-equivariant auction mechanisms [29]. However, in complex settings, it will be harder for non-permutation-equivariant models to approach the negligible ex-post regret. It can explain why the permutation-equivariant models show a significant improvement in complex settings, compared with that they have similar performances in simple settings [10, 17], which shows the great importance of adopting permutation-equivariant models in complex settings.

3.2 Benefits for Generalization

In this section, we study permutation-equivariance from the aspect of generalizability [22, 15], which characterizes the performance gap of a learned mechanism on collected training data and unseen data.

We first study the covering number of the permutation-equivariant mechanism space. Let U = {uω : ω Ω} and P = {pω : ω Ω} be the spaces of all possible utilities and payment rules, and

Q U = {Q u : u U} and Q P = {Q p : p P} the spaces of all projected utilities and payment rules. In addition, let N ,1(U, r) and N ,1(P, r) be the minimum numbers of balls with radius r that can cover U and P under l ,1-distance, respectively. We obtain the following result, which indicates the projected permutation-equivariant mechanism space has smaller covering numbers. Theorem 3.5 (Covering number of the permutation-equivariant mechanism space). The space of all projected bidder-symmetric mechanisms has smaller covering numbers, that is,

N ,1(Q1U, r) N ,1(U, r) and N ,1(Q1P, r) N ,1(P, r).

The space of all projected item-symmetric mechanisms has smaller covering numbers, that is,

N ,1(Q2U, r) N ,1(U, r) and N ,1(Q2P, r) N ,1(P, r).

Intuitively, the orbit averaging Q narrows the distance between two mechanisms: l(QM, QM ) l(M, M ), for any two mechanisms. Then, any r-cover A for space U or space P induces an r-cover QA for space QU or space QP.

Combining with Lemma 3.3, we have the following results,

N ,1(Q3U, r) = N ,1(Q1Q2U, r) N ,1(Q2U, r) N ,1(U, r) and N ,1(Q3P, r) = N ,1(Q1Q2P, r) N ,1(Q2P, r) N ,1(P, r).

We then prove that two generalization bounds of permutation-equivariant mechanisms, which characterize the gap between the expected revenue/ex-post regret and their empirical counterparts. Similar generalization results are existing in previous works [10, 12]. Theorem 3.6 (Generalization bounds of permutation-equivariant mechanisms). If for any bidder, her valuation satisfies that vi(S) 1 for any S [m], then with probability at least 1 δ, we have the

following inequalities with ϵ q

δ + max{log N ,1(P, ϵ

3), log N ,1(U, ϵ

i=1 pω i (v, x, y) 1

i=1 pω i (v(l), x(l), y(l)) ϵ, and (3)

i=1 regω i (v, x, y)

i=1 d regi(ω) ϵ, (4)

where L is the number of samples, U and P are the spaces of all possible utilities and payment rules.

Equivalently, we can rewrite this result in the form of the sample complexity, Corollary 3.7. For any ϵ > 0, δ (0, 1), and mechanism parameter ω, when the sample complexity

δ + max n log N ,1(P, ϵ

3), log N ,1(U, ϵ

6) o , with probability at least 1 δ, the generalization bounds, eqs. (3) and (4), hold. Remark 3.8. Combining Theorem 3.5, we have proved that the permutation-equivariance can improve the generalizability.

4 Experiments

This section presents our experimental results. More details and results are presented in the supplementary materials.

Model architecture. We project Regret Net [12] to the permutation-equivariant mechanism space via employing bidder-item aggregated averaging for the bidder-symmetry and item-symmetry condition. The projected model is called Regret Net-PE. We also project the well-trained Regret Net, called Regret Net-Test. Specifically, Regret Net is an auction mechanism defined as (gω, pω), in which both the allocation rule gω and the payment rule pω are neural networks that consist of three fullyconnected layers, and ω is the overall model parameter of the auction mechanism. The detailed architecture is given in the supplementary materials.

Comparison with Equivariant Net. Regret Net uses two feed-forward fully-connected networks to learn the allocation rule and payment rule, respectively. We denote the weight matrix in the

Table 1: Experimental results. "n m Uniform" refers that there are n bidders and m items, and the valuations are i.i.d. drawn from the uniform distribution U[0, 1]. To simplify, we multiply all results by a factor of 105 for the ex-post regret and generalization error (GE).

Method 2 1 Uniform 3 1 Uniform 5 1 Uniform Revenue Regret GE Revenue Regret GE Revenue Regret GE

Optimal 0.417 0 - 0.531 0 - 0.672 0 -

Regret Net 0.415 17.4 6.00 0.535 18.3 11.4 0.658 15.9 6.40 Regret Net-Test 0.415 16.3 - 0.535 13.3 - 0.658 6.50 - Regret Net-PE 0.420 14.6 3.90 0.541 16.4 10.2 0.677 13.2 5.10

Table 2: Experimental results. "n m Uniform" refers that there are n bidders and m items, and the valuations are i.i.d. sampled from the uniform distribution U[0, 1].

Method 1 2 Uniform 2 2 Uniform Revenue Regret Revenue Regret

Regret Net 0.562 0.00061 0.870 0.00070 Equivariant Net 0.551 0.00013 0.873 0.00100 Regret Net-Test 0.562 0.00052 0.870 0.00054 Regret Net-PE 0.563 0.00037 0.913 0.00067

layer ℓas W (ℓ). Both Equivariant Net and Regret Net-PE inherit the architecture of Regret Net (with some modifications), but utilize different approaches to realize the permutation-equivariance. Equivariant Net applies parameter-sharing in every layer during training, to constrain W (ℓ) to be equivariant. In contrast, Regret Net-PE employs orbit averaging to be permutation-equivariant. Specifically, Regret Net-PE adopts a weight matrix IK W (ℓ)(ρT g1 . . . ρT g K)T in the first layer, weight matrices IK W (ℓ) in the following layers, and multiples a matrix (ρ 1 g1 , . . . , ρ 1 g K) to the output layer, where K is the scale of the group G = {g1, . . . , g K}, ρgk represents the permutation operator on bidders and items, IK is an identity matrix, and is the Kronecker product. It is worth noting that Regret Net-PE is only designed for verifying our theory.

Auction settings. We first adopt the two-bidder single-item, two-bidder single-item, three-bidder single-item, and five-bidder single-item settings in the experiments that compare the learned mechanisms with theoretical optimal mechanisms. The optimal auction mechanism for any single-item auction is known [23]. We thus compare the mechanisms leaned by our method with the optimal auction mechanisms in the single-item settings. Also, we compare Regret Net-PE and Equivariant Net in the one-bidder, two-item setting, and the two-bidder, two-item setting. Besides, we employ a multivariate uniform distribution U[0, 1]m to model the bidder valuation profiles. In all settings, we sample 640,000 data points for training and 5,000 points for test. Due to the space limitation, we place the results of two-bidder five-item and five-bidder three-item settings in Appendix B.2.

Model training. We optimize the auction mechanism model via solving the following optimization problem, following the standard settings [12, 29, 10, 17],

Lρ(ω, λ) = 1

i=1 pω i (v(l), x(l), y(l)) +

i=1 λid regi(ω) + ρ

i=1 d regi(ω) 2 ,

where λ Rn is the Lagrange multiplier and ρ > 0 is the factor of the quadratic regularization term. During the training process, the objective function Lρ(ω, λ) is minimized via Adam with a learning rate of 0.001 with respect to the model parameter ω and the Lagrange multiplier λ is updated once in every 100 iterations, until the ex-post regret is smaller than 0.001. The regularization factor ρ is set to 1.0 initially and gradually increased along the training process. In calculating the best bid profile v i of every bidder i, we first randomly initialize the bid profiles once in training and 1,000 times in test, optimize each of them individually via Adam with the same settings, and take the best one as the approximated best bidding.

Evaluation. We leverage three metrics to evaluate the performance of the auction mechanism, which are: (1) the empirical revenue d rev, (2) the empirical ex-post regret averaging across all bidders, i.e., d reg = 1 n Pn i=1 d regi, and (3) the generalization error defined on top of regrets, i.e., GE = |d regtest d regtrain|, where d regtest and d regtrain are the empirical ex-post regrets during test and training, respectively.

Computing resource. The experiments are conducted on 1 GPU (NVIDIA Tesla V100 16GB) and 10 CPU cores (Intel Xeon Processor E5-2650 v4 @ 2.20GHz).

Experimental results. We train a Regret Net and a Regret Net-PE on the training data. The welltrained Regret Net is then projected to be permutation-equivariant, denoted as Regret Net-Test . The results are collected in Tables 1 and 2.

From Tables 1 and 2, we observe that (1) compared to Regret Net, Regret Net-PE has a significantly higher revenue with a lower ex-post regret, and narrows the generalization gap between the training ex-post regret and its test counterpart; (2) compared to Regret Net, Regret Net-Test receives the same revenue with a significantly lower ex-post regret; and (3) under comparable ex-post regrets, Regret Net-PE has considerably higher revenue than Equivariant Net, while all permutation-equivariant models (Regret Net-Test and Regret Net-PE) can outperform Regret Net. These results show significant benefits of permutation-equivariance on revenue, ex-post regret, and generalizability, which fully supports our theoretical findings in Theorems 3.1, 3.4, and 3.5.

5 Conclusion and future works

In this paper, under additive valuation and symmetric valuation setting, we study the benefits of permutation-equivariance in auction mechanisms in two aspects: a better performance and a better generalization. First, we prove a smaller expected ex-post regret and the same expected revenue when projecting a mechanism to be permutation-equivariant. Next, we propose the permutation-equivariant mechanism space has a smaller covering number, which promises the permutation-equivariant models a better generalization. Extensive experiments are conducted to verify our theoretical results. Our results help understand the optimal auction mechanisms characterization and the learning processes difference between non-equivariant models and equivariant models.

Beyond the additive valuation setting, an interesting direction is to extend our results to other conditions, including the combinatorial and the unit-demand auctions. Meanwhile, the understanding of the difference in the aspect of the training process between non-equivariant models and equivariant models is still elusive.

Social impact. Our results can help understand and design optimal auction mechanisms for symmetric valuation distribution. As a result, our work could inspire more near-optimal auction mechanisms and promote economic growth. No potential negative social impact is identified.

Acknowledgments and Disclosure of Funding

This work was supported in part by the Major Science and Technology Innovation 2030 New Generation Artificial Intelligence Key Project (No. 2021ZD0111700), the National Natural Science Foundation of China (No. 62006137), and the Beijing Outstanding Young Scientist Program (No. BJJWZYJH012019100020098).

We sincerely appreciate Hang Yu, Xiaowen Wei, Kaifan Yang, Shaopeng Fu, and Qingsong Zhang for the valuable comments and the anonymous Neur IPS reviewers for the helpful feedback.

[1] S. Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. The 16th Annual Symposium on Foundations of Computer Science, 2011.

[2] S. Alaei, H. Fu, N. Haghpanah, and J. Hartline. The simple economics of approximately optimal auctions. The 16th Annual Symposium on Foundations of Computer Science,, 2013.

[3] M.-F. F. Balcan, T. Sandholm, and E. Vitercik. Sample complexity of automated mechanism design. Neural Information Processing Systems (Neur IPS), 2016.

[4] L. Chen, L. Wang, and Y. Lan. Auction models with resource pooling in modern supply chain management. Modern Supply Chain Research and Applications, 2019.

[5] R. Cole and T. Roughgarden. The sample complexity of revenue maximization. In ACM symposium on Theory of computing, 2014.

[6] V. Conitzer and T. Sandholm. Complexity of mechanism design. Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI), 2002.

[7] V. Conitzer and T. Sandholm. Self-interested automated mechanism design and implications for optimal combinatorial auctions. In ACM Conference on Electronic Commerce, 2004.

[8] M. Curry, P.-Y. Chiang, T. Goldstein, and J. Dickerson. Certifying strategyproof auction networks. Neural Information Processing Systems (Neur IPS), 2020.

[9] C. Daskalakis, A. Deckelbaum, and C. Tzamos. Strong duality for a multiple-good monopolist. Econometrica, 2017.

[10] Z. Duan, J. Tang, Y. Yin, Z. Feng, X. Yan, M. Zaheer, and X. Deng. A context-integrated transformer-based neural network for auction design. ar Xiv preprint ar Xiv:2201.12489, 2022.

[11] S. Dughmi, L. Han, and N. Nisan. Sampling and representation complexity of revenue maximization. Web and Internet Economic, 2014.

[12] P. Dütting, Z. Feng, H. Narasimhan, D. Parkes, and S. S. Ravindranath. Optimal auctions through deep learning. In International Conference on Machine Learning (ICML), 2019.

[13] B. Elesedy and S. Zaidi. Provably strict generalisation benefit for equivariant models. In International Conference on Machine Learning (ICML), 2021.

[14] Z. Feng, H. Narasimhan, and D. C. Parkes. Deep learning for revenue-optimal auctions with budgets. In the 17th International Conference on Autonomous Agents and Multiagent Systems, 2018.

[15] F. He and D. Tao. Recent advances in deep learning theory. ar Xiv preprint ar Xiv:2012.10931, 2020.

[16] J. Huang, Z. Han, M. Chiang, and H. V. Poor. Auction-based resource allocation for cooperative communications. IEEE Journal on Selected Areas in Communications, 2008.

[17] D. Ivanov, I. Safiulin, K. Balabaeva, and I. Filippov. Optimal-er auctions through attention. ar Xiv preprint ar Xiv:2202.13110, 2022.

[18] B. J. Jansen and T. Mullen. Sponsored search: an overview of the concept, history, and technology. International Journal of Electronic Business, 2008.

[19] C. Lyle, M. van der Wilk, M. Kwiatkowska, Y. Gal, and B. Bloem-Reddy. On the benefits of invariance in neural networks. ar Xiv preprint ar Xiv:2005.00178, 2020.

[20] A. M. Manelli and D. R. Vincent. Bundling as an optimal selling mechanism for a multiple-good monopolist. Journal of Economic Theory, 2006.

[21] M. Mohri and A. M. Medina. Learning theory and algorithms for revenue optimization in second-price auctions with reserve. International Conference on Machine Learning (ICML), 2013.

[22] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018.

[23] R. B. Myerson. Optimal auction design. Mathematics of operations research, 1981.

[24] H. Narasimhan and D. C. Parkes. A general statistical framework for designing strategy-proof assignment mechanisms. Uncertainty in Artificial Intelligence (UAI), 2016.

[25] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic game theory. Cambridge University Press, 2007.

[26] G. Pavlov. Optimal mechanism for selling two goods. The BE Journal of Theoretical Economics, 2011.

[27] G. Popescu. An algorithmic characterization of multi-dimensional mechanisms. Computing Reviews, 2012.

[28] O. Puny, M. Atzmon, H. Ben-Hamu, E. J. Smith, I. Misra, A. Grover, and Y. Lipman. Frame averaging for invariant and equivariant network design. International Conference on Learning Representations (ICLR), 2022.

[29] J. Rahme, S. Jelassi, J. Bruna, and S. M. Weinberg. A permutation-equivariant neural network architecture for auction design. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.

[30] T. Roughgarden. Twenty lectures on algorithmic game theory. Cambridge Books, 2016.

[31] T. Sandholm and A. Likhodedov. Automated design of revenue-maximizing combinatorial auctions. Operations Research, 2015.

[32] V. Syrgkanis. A sample complexity measure with applications to learning optimal auctions. Neural Information Processing Systems (Neur IPS), 2017.

1. For all authors...

(a) Do the main claims made in the abstract and introduction accurately reflect the paper s contributions and scope? [Yes] Our contributions are stated in the 4th-8th sentences of the abstract, and the 4th-6th paragraphs of the introduction. The scope is described in the related work section. (b) Did you describe the limitations of your work? [Yes] We describes the problem setting we considered in the 3rd paragraph of the introduction. Our contributions are for this problem setting. (c) Did you discuss any potential negative societal impacts of your work? [Yes] Our work is committed to learn the optimal auction mechanism. No negative societal impact is identified. (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have read the ethics review guidelines. We ensure that our paper conforms all of them.

2. If you are including theoretical results...

(a) Did you state the full set of assumptions of all theoretical results? [Yes] We state all of our assumptions in the third paragraph of introduction, the first paragraph of preliminary, Theorem 3.1, and Theorem 3.2. Wherever we use an assumption, we always state it again. (b) Did you include complete proofs of all theoretical results? [Yes] Full proofs are given in the supplemental material.

3. If you ran experiments...

(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [No] We are associated in a industrial organization. The code is currently under review of our organization. (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We mostly follow the setting of the Regret Net. Other details are given in Sections 4 and B. (c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [No] (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] They are given in Section 4.

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...

(a) If your work uses existing assets, did you cite the creators? [Yes] They are given in Section 4. (b) Did you mention the license of the assets? [Yes] They are given in Section 4.

(c) Did you include any new assets either in the supplemental material or as a URL? [No]

We are associated in a industrial organization. The code is currently under review of our organization. (d) Did you discuss whether and how consent was obtained from people whose data you re using/curating? [Yes] The data is synthetic in our data. (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] The data is synthetic in our data. No personally identifiable information or offensive content is contained. 5. If you used crowdsourcing or conducted research with human subjects...

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] (c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]