Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers the learning problem arising from seller revenue optimization in repeated auctions, with an approximate incentive compatibility constraint, under the assumption that the joint distribution of context and values is available to the learner (at least an empirical version). It studies whether averaging the learnt payment and allocation functions over permutations of items (resp. bidders) reduces bias error term and statistical error term when the distribution is invariant by permutation of the items (resp. bidders).
strengths_and_weaknesses: 1. The structure of the paper and of the exposition is clear.

2. The writing itself should be improved as a certain number of quantities are not formally defined or even not defined at all (or just in the appendix).
    * l. 125 I would have expected a more formal definition of $f(x)\sigma_m$
    * Th 3.5 introduces covering numbers ${\cal N}_{\infty,1}(\cdot,\cdot)$. I guess $\infty,1$ refers to some distance, but it is only provided in appendix
    * $v^{(l)}, x^{(l)}, y^{(l)}$ are probably samples in Th. 3.6
    * $\omega$ is again only defined in appendix (Th. 3.6) 
    * $\widehat{reg}_i(\omega)$ (Th. 3.6) is not defined at all (even in appendix)
    * I guess $rgt_i = reg_i$ ?
Most of these are "_guessable_" or defined somewhere in the appendix, but remember the paper should be self-contained.

3. I find the contributions are a bit light. Indeed, Th. 3.1 follows quickly from the definition, Th. 3.6 is mostly a corollary of results in [10]. So the strongest contribution is Th. 3.5 on the dominance of covering number that comes from the projection contracting the distances. Still, in the end, the message is clear. 
questions: How does the statistical error provided in Th. 3.6 compares to those of empirical Myerson auctions ?
limitations: Suggestions:

1. I feel the proof of Th. 3.1 could be deferred to appendix or at least shortened as it mostly comes from the definitions + convexity of max function.

2. About the case $Q_3$ (both item and user symmetry), isn't the optimal auction a second-price auction with one optimized reserve price? A sanity check could be to compare the error term of the auction learnt by the RegNet to the learning of this unique reserve price.

3. As an additional direction, the authors could compare the aggregation method to other classes of equivariant models they cite in the introduction, either theoretically or empirically (or both).
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The use of deep neural networks for automated mechanism design is increasingly important. Several recent papers have observed that when valuation distributions are symmetric, a symmetric auction is optimal. Thus, neural networks for mechanism design ought to respect this symmetry by using architectures (i.e. DeepSets, attention) that are permutation-equivariant. The current paper theoretically analyzes the effect of equivariance: they give a technique for projecting non-equivariant mechanisms onto the set of equivariant mechanisms, and show that it has several nice properties. Most importantly, it always preserves auction revenue while weakly improving expected violations of strategyproofness. From a learning theory perspective, learning over the class of the projected mechanisms also has better generalization guarantees. And, the projection technique is constructive so the authors can actually train these mechanisms and show they perform decently.
strengths_and_weaknesses: *Originality*

I'm not convinced this is hugely original. It seems mainly to borrow other techniques related to equivariant ML. I think that's fine -- it's putting pieces together in an interesting and important way, but there is no really new technique here.

The paper claims in one sentence to be the first work explaining the benefits of permutation equivariance in auction design via deep learning. This is arguably not true depending on how one parses the word "explaining". Previous works looking at equivariant networks for auction design are at least pointed out and cited, but I think they should be given more discussion and the claim about being "the first" should be weakened or qualified. Doing this would not detract from the significance of the paper, in fact it would enhance the motivation for the results in this paper.

*Quality*

The quality of the paper seems high, the theoretical results are reasonable, and the empirical results are convincing enough given they are not the main focus. 

*Clarity*

The paper is clear. There are good proof sketches in the main text and the full proofs are easy to follow. Some of the early definitions may be too compressed and hard to follow, but I think this is the fault of the conference page limits and not the fault of the authors.

*Significance*

This is a thoughtful contribution to an important topic in auction design. There are already several papers looking at symmetry in automated mechanism design, but this is a new, clear, and useful perspective.
questions: Do you have any thoughts or speculation on how orbit averaging interacts with the gradient-based computation of best untruthful bids? Is it possible that it is somehow "harder to optimize" the misreports when orbit averaging, compared to normal RegretNet?

You consider both bidder-permutation and item-permutation. In addition to comparing against the Myerson auction in the 1 item setting and looking at bidder-permutation, it might make sense to compare to some of the known multi-item mechanisms in the 1 bidder setting (e.g. the Manelli-Vincent mixed bundling mechanism as in the original RegretNet paper), and look at item-permutation. Training a 2-item 1 agent orbit averaged mechanism could be interesting in this case (where the optimal mechanism is in fact item-equivariant).
limitations: In addition to focusing a little more on previous work about equivariant auctions in the background sections, it would enhance the experiment section to include results from other equivariant auction networks where the comparison makes sense. I don't think running lots of new experiments is necessary, but where the numbers can be compared, I think this should be done.

I think the authors should further spell out how orbit averaging interacts with the allocation constraints (items sum to one). This was a question I had as I was reading the paper. I checked and saw that orbit averaging should preserve feasibility of allocations, but I think it makes sense to explicitly reassure the reader that this holds, rather than leaving the reader to check it.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studied permutation-equivariant auction mechanisms, which, roughly, are auctions that do not depend on the labeling of the bidders/items. Permutation equivariant auctions are a promising solution concept for settings where the bidder/item distributions are symmetric. The authors prove that permutation equivariant auctions never decrease revenue, and always yield better ex-post regret (bringing the auction closer to being perfectly incentive compatible). The authors explore generalization guarantees, and provide experimental evidence for the benefits of permutation-equivariant auctions.
strengths_and_weaknesses: This paper studies a relevant, important, and difficult question: the design of optimal auctions. However, I think there are many points that need to be addressed. First, I found the paper to generally be difficult to read. Permutation equivariance is never given a clear definition in the auction context – instead it is abstractly defined for arbitrary maps via group representations (I don’t know if the authors should assume that the NeurIPS audience is intimately familiar with group theory jargon). Then, my understanding was that permutation equivariance is obtained by projecting any map via an orbit-averaging operator (but I wasn’t sure why this is the case). *I think that lines 157-158 more or less make this clear: the allocation function and payment are being averaged over all permutations of the bidders (or items) to obtain a symmetric auction. 

This brings me to the second main concern that there is almost no comparison to previous work on symmetric auctions/study of permutation equivariance. Permutation equivariance is the main contribution of Rahme et al. [25] in the context of auction design, but there is nearly zero discussion or comparison to their results.

My reading is that the main contribution of this paper is a novel way to view permutation equivariance: any auction can be converted into a permuation equivariant one via the orbit averaging operator. If this is indeed the main contribution, I think the intuition for what is going on ought to be much more clearly spelled out (because it seems like an elegant and novel contribution!). 

The overall writing style (flow/sentence structure/grammar/spelling) could also use a lot of improvement which would make the paper easier to read and follow.
questions: How do the results of this paper compare to Rahme et al. [25]? My understanding is that the approach in this paper involves a conversion of any auction mechanism to a permutation-equivaraint one via orbit averaging. Is this a subset of the set of permutation equivariant mechanisms considered by Rahme et al? 

In Theorem 3.5, wouldn’t covering number inequalities follow from the simple fact that the set of all permutation equivariant auctions is a subset of the set of all auctions? (I think this is what lines 261-263 is saying.) Is there a more quantitative gap that can be obtained? 

limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work studies the benefits of incorporating permutation-equivariance into a neural network (NN) trained to function as an auction mechanism in auctions with additive valuations and symmetric bidders and/or items. The authors prove that incorporating permutation-equivariance which reflects the bidder/item symmetries 1) decreased the expected ex-post regret (measures "distance" to the space of dominant strategy incencitve compatible, "truthful", auctions) of the bidders, 2) maintains the expected auctioneer revenue, and 3) improves mechanism generalizability (e.g, to other bidder valuation profiles), intuitively via a reduction of the auction mechanism hypothesis space. Permutation-equivariance is achieved by "orbit" averaging the NN outputs (item allocations and bidder payments) over all possible permutations of bidders/items. Experiments are conducted in both single-item (theoretically optimal mechanism is known) and multi-item auctions. Properties 1, 2, and 3 are supported by the experiments in all 2, 3, and 5 bidder auctions.
strengths_and_weaknesses: This work proves several properties conjectured and partially explored empirically in previous work [25]. Most of the exposition is clear. Overall, given the existence of the previous work [25] at AAAI, I find the work a bit incremental and, therefore, lacks significance beyond [25]. The authors do not compare / contrast the permutation-equivariant NN in [25] with their own (unclear if RegretNet-PE is original), and only include one comparison with that model at the end of their appendix (also without any discussion of EquivariantNet). The theorems proven in this paper are interesting, but not very surprising (esp generalizability, reducing the hypothesis space typically improves generalizability). It's unclear how useful the sample complexity bounds are and experiments are not conducted to empirically confirm the complexity bound.
questions: - In Sec 3.1.2, should there be a $\sigma_m^{-1}$ on the right side of the definition of $Q_3 p(v, x, y)$? Same with $Q_2 p(v, x, y)$ in Sec 3.1.1? If not, why not?
- In Table 1, does the, for example, "2 x 1 Uniform" header mean "number of bidders x number of items Distribution of valuations"? I did not see this explained anywhere.
- Is RegretNet-PE your model? I did not see your model named in the text anywhere (maybe I missed it) and had to infer this.
- The conclusions you draw from the experimental results appear to be over simplifications. Your first claim (1) appears to be violated in the 5 x 1 setting (your revenue is 0.633 vs optimal is 0.667). Your second claim (2) is also violated in the 5 x 3 setting (ex-post regret increases vs RegretNet, yours is 31.2 vs RegretNet 28.4). Please report accurate conclusions. If I'm misunderstanding your table, please clarify.
- How would you apply your approach to settings where subsets of the items/bidders are symmetric? Can you just average over the permutations within the subset? This might be a nice note to add to the exposition.
- Can you please compare/contrast RegretNet-PE with EquivariantNet? More generally, can you list the contributions of your work that go beyond [25]?
limitations: Can you comment on the computational expense of your approach? Averaging over all possible permutations presumably increases the number of forward passes of your NN by a factorial amount. Therefore, this approach is only feasible when the number of symmetric bidders/items is small.
review_title: null

Meta-review: metareview: Most reviews are in the positive direction. The reviewers gave comments on having better discussions of related work and improving presentation by making definitions more clear. I think the authors can further improve the paper based on these comments.
confidence: Less certain
Decision: Accept