A Scalable Neural Network for DSIC Affine Maximizer Auction Design

Summary

AMAs is a parametric family of auctions that generalizes VCG and that is exactly DSIC (unlike mechanisms found with alternative regret-based approaches) and IR. This paper proposes a deep variant of AMAs. In particular, AMAs parameters are learned as outputs of a permutation-equivariant attention-based network. Near-optimal mechanisms within AMA family can be found by optimizing this network. it can be applied to both contextual and classic auctions. The theory is provided to show that the learned auctions are indeed DSIC and IR. Extensive experiments and ablations support the method’s usefulness. I will begin by saying that a deep variant of AMAs is a glaring gap in the literature, considering the popularity of deep regret-based approaches. Someone has to do it, and if done correctly, a paper like this absolutely should be published. Unfortunately, in my opinion, this particular version is not ready to be published yet.

Strengths

- The paper is clear and well-written. It cites and discusses the relevant literature and places itself within the context of the literature. - The goal of the paper, namely, a deep variant of AMAs, is worth pursuing. The paper is relevant to the conference. - The experiments and ablations that are provided are extensive and look sound. I especially like the case study in Fig 3. I was surprised to see such diverse allocations, and the allocation acting as a reserve price is especially cool. - The theory about the auctions being DSIC and IR is an essential part of the paper.

Weaknesses

- My biggest worry is that experimental comparison is unfair. Authors claim in Table 1b that they “omit CITransNet since it is designed for contextual auctions” and proceed to compare their approach to RegretNet. RegretNet is based on fully-connected layers, whereas AMenuNet uses attention layers. Ivanov et al. (2022) show that attention layers improve revenue for the same regret levels in auctions with larger input sizes. So CITransNet (and, ideally, RegretFormer) should be included for comparison in auctions without context, as they are expected to achieve higher revenue than RegretNet and AMenuNet. For example, in the 3x10 auction, the paper reports 5.59 revenue of AMenuNet vs 5.54 revenue of RegretNet. Judging from these results, it might seem that AmenuNet is strictly better than RegretNet (same revenue but always DSIC). However, RegretFormer in its paper reports more than 6.1 revenue in 3x10 for the regret of <= 0.005 (as indicated in Table 1, “The regret of both CITransNet and RegretNet is less than 0.005”). By the way, this only takes 2 attention-based blocks, as opposed to 3-5 used by AMenuNet. If this is included in the comparison with AMenuNet, the conclusion would be that zero regret actually comes at a cost of revenue. This would not diminish the authors' contributions or the usefulness of their method, but would simply be a more sound experimental design. - As Rahme et al. (2021) show, RegretNet is hyperparameter-sensitive. Choosing the wrong hyperparameters may decrease performance. The paper includes some settings that were not explored in the original RegretNet paper, like 3x1 and 5x5. However, in the appendix, it is only stated: “CITransNet and RegretNet. We follow the same hyperparameters in Duan et al. [2022] and Dütting et al. [2019].”. So for 3x1 and 5x5, it is not reported how the hyperparameters are selected, potentially resulting in unfair comparison. I would appreciate it if the authors could clarify this for me. As a suggestion, both Rahme et al. (2021) and Ivanov et al. (2022) propose alternative loss functions that are less sensitive to hyperparameters. - A potential issue with AMenuNet is that it requires a hand-selected menu size. I wonder if larger settings would require larger menu sizes and if this introduces scaling issues. An ablation would be welcome where AMenuNet is given different menu sizes in some small and large settings and we examine revenue as a function of the menu size. E.g., we could see that the approach performs well in settings both large and small given the same small menu sizes, in which case there are no scaling issues. - Compared to CITransNet or RegretFormer, there is nothing novel about the architecture, besides the softmax trick with annealed temperature to work with deterministic allocations. This is not a weakness per se, just a neutral fact.

Questions

- How are hyperparameters selected for RegretNet in novel settings (that did not appear in its original paper)? - Why do the authors think the learned menu is so diverse? If all allocations are trained on the same loss function, why is there no mode collapse (i.e., I could expect one “best” allocation to be repeated in all menu positions)? - 176-177: “In non-contextual auctions, similar 177 to word embedding [Mikolov et al., 2013], we embed the unique ID of each bidder or item…”. This looks like positional encoding. Doesn’t it make learned mechanisms not permutation equivariant? The network could discriminate items and participants. Shouldn’t the same dummy ID be provided for all participants and items for true permutation equivariance? - Why does AMenuNet outperform Lottery AMA, given that the parameters of AMAs are learned in both cases? We are used to attention outperforming everything else, but there is nothing to attend to in non-contextual auctions (as I understand, the input is always the same combination of IDs), so this is surprising to me.

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.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

For reasons mentioned in the weaknesses section, I think the method is a bit oversold.

Summary

This paper introduces AmenuNet, a scalable NN for the AMA design, which ensures DSIC and IR. And the experiments demonstrate the effectiveness of AMenuNet, including its revenue, scalability, and out-of-setting generalizability.

Strengths

Originality: 1.Proposes a new automated auction design method: The paper proposes a new automated auction design method that uses a neural network to construct AMA parameters, thereby improving scalability and revenue performance. 2.Combines deep learning and game theory: The paper combines deep learning and game theory to propose a new method for solving the DSIC problem in multi-item auctions, which is a novel approach. Quality: 1.Experimental results demonstrate the effectiveness of the proposed method: The paper demonstrates the effectiveness of the proposed method in extensive experiments, including performance in different environments and scalability in large auctions. 2.Theoretical proof ensures the DSIC property of the auction: The paper ensures the DSIC property of the auction through theoretical proof, thereby improving the quality of the auction. Clarity: 1.Clear paper structure: The paper has a clear structure, strong logic, and is easy to understand. 2.Detailed experimental section: The experimental section of the paper is detailed, including experimental settings, results, and analysis, making it easy for readers to understand and reproduce. Importance: 1.Contribution to the field of automated auction design: The proposed method in the paper makes an important contribution to the field of automated auction design, helping people design high-revenue auction mechanisms. 2.Inspirational significance for the combination of deep learning and game theory: The paper explores the combination of deep learning and game theory, providing inspiration for related research in the field.

Weaknesses

1.Lack of comparison with existing methods: The paper does not compare the proposed method with some existing industrial methods, such as DNA, NMA, which makes it difficult to evaluate the novelty and effectiveness of the proposed method in industry. 2.Limited applicability: The proposed method is only verified on small-scale data sets, lacking demonstrations on large-scale industrial scenarios. 3.Expression problem: some typos need to be optimized.

Questions

1.Lack of modeling of full contextual externalities. 2.Lack of comparison with WVCG, NMA.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

No.

Summary

This paper proposes a new architecture for learning auctions that are DSIC (but not necessarily revenue optimal) auctions. The authors' main contribution lies in a transformer-based permutation equivariant architecture designed to calculate the allocations, weights, and boosts variables utilized by AMA-based approaches.

Strengths

The primary strength of this novel architecture resides in its capacity to effectively handle the following aspects: 1. **Contextual and non-contextual auctions:** The architecture demonstrates the ability to accommodate both contextual and non-contextual auction settings, allowing for a broader range of applications. 2. **Equivariance for varying auction sizes:** The architecture exhibits permutation equivariance, enabling it to handle auctions of different sizes without requiring significant modifications. 3. **Better scalability:** In comparison to existing approaches, the proposed architecture exhibits improved scalability, providing a more efficient and scalable solution for auction learning tasks.

Weaknesses

This paper shares similarities with the work of Curry et al. [2022] on Differential Economics for Randomized AMA auctions. However, a key distinction is that the allocation menus in this paper are parameterized by a neural network, in contrast to directly being parameterized through autograd variables. Additionally, the proposal of contextual auction design through the transformer architecture has been previously suggested by Dual et al. [2022]. Consequently, the contributions of this paper may not be considered highly novel. Nevertheless, the authors demonstrate improved revenue performance over existing approaches, as evidenced in Table 2.

Questions

In the context of classical auctions, is there any intuition for why optimizing the neural network that outputs an allocation works better than directly optimizing the allocation variables?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

2 fair

Limitations

N/A

Summary

Revenue maximizing strategyproof auction design with multidimensional types has proven to be extremely challenging. The lack of theoretical progress even in simple problem instances has motivated the use of machine-learning-based techniques to approximately learn high-performing auctions. One approach, typified by “RegretNet” and its followup works, involves the use of neural networks as function approximators to directly represent auction mechanisms — the training process optimizes revenue and strategyproofness. However, although the mechanisms learned by these neural network based approaches are qualitatively good and likely near to the true optimal mechanism, the enforcement of the strategyproofness constraints is not perfect — a significant limitation. Another line of work searches within some restricted class of mechanisms, all of which are guaranteed to be strategyproof, for one that performs well. The current work builds on this latter approach. Like some previous work, they focus on the class of affine maximizer auctions, which are guaranteed to be strategyproof. However, previous work directly optimized the parameters and possible outcomes of the auction. They instead treat the mechanism itself as the outcome of a neural network. Crucially, this neural network does not see the bids as input — at most, it sees some informative “context” features — so strategyproofness is preserved. Also, even for auctions without context, training using this architecture seems to perform better than optimizing the parameters directly. The neural network uses a transformer architecture, which comes with some advantages — it allows for permutation-equivariance, a useful property which is satisfied by optimal auctions when the bidders are anonymous. In experiments, the authors find that their method performs very well -- getting higher revenue than previous strategyproof approaches and even performing comparably to the unconstrained neural network approaches in some cases.

Strengths

The experiments are done quite well and follow standard methodology, the baselines are well-chosen, the method is explained clearly, the results show a clear improvement on existing work, and the technique opens up capabilities in new settings.

Weaknesses

There have since been many improvements on RegretNet in addition to CITransNet, with and without contexts. It could be interesting to compare to some of these as well. The section describing the auction architecture is extremely dense. It's possible this had to be compressed a lot for the NeurIPS page limit, but I found it hard to follow. I ended up looking at the diagram+code and found this much easier to understand than the written part.

Questions

Where do you get the reported revenues for the other methods? Are these experiments you ran yourself or taken from another paper? If reproduced yourself, how do they compare to reported results in other papers? Your table 1 has some methods in bold even when RegretNet/CITransNet outperform them. I admit it does say in the caption that bold means “best among DSIC methods”, and the DSIC methods are separated by bars, but when reading the paper, the first thing I did was immediately look at that table, so I still found it confusing. I think it would be good to find a way to make this even more obvious.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

The authors adequately discuss the limitations of their approach (the main one being that it deals with a restricted class of auctions, unlike the RegretNet approaches).

Rebuttal response

Thank you for the detailed answers to my questions! 1. I understand your position and let me state again that I do think the paper makes a valuable contribution. That said, comparing with relevant baselines is essential, and I guess we disagree on what are the relevant baselines in this case. I would not mind as much if it only was the case that these baselines are likely to outperform the method in question. But they are using similar attention-based architectures. And the paper does compare with RegretNet (as it should) which uses a "weaker" architecture. Regarding RegretNet outperforming AMenuNet 4 out of 6 times, the absolute difference is small, and there are 2 out of 6 times when the reverse is true. I am not even sure the result is statistically significant. At the very least, I advise including metrics reported in the respective papers of EquivariantNet, RegretNet, and CITransNet, for the settings that intersect with your paper. Also, I advise including an ablation where attention layers in AMenuNet are replaced with fully-connected layers. If this performed worse (although either outcome would be interesting), it would also show that attention > fully-connected. In conjunction, these two changes (and an explicit discussion), would be a sufficient alternative. 2. This is reasonable, thank you for clarifications! I suggest adding this to the appendix. 3. This is very interesting, thanks! I also wonder about a smaller setting like 2x2 but I leave this consideration with the authors. 4. and 6. I see, thank you for the clarification! 5. I agree with every word in your response. I understand why distinguishing agents is essential in asymmetric settings. But I still think this makes the architecture non-permutation-equivariant, and this has not been addressed in the rebuttal. I will elaborate. Consider a setting with two participants. The first has an id "1" and its valuation (for all items) is sampled from U[0, 1]. The second has an id "2" and its valuation is sampled from U[0, 2]. Yes, not providing an id would not learn an optimal auction, but it would be symmetric, and the architecture (let's say, an attention layer) -- permutation-equivariant. If we encode positions "1" and "2" before the attention layers, the optimal auction is in the space of solutions so it can be learned, but the architecture is no longer permutation-equivariant. Do we suddenly get the best of both worlds when we call "1" and "2" not positions but ids? No, we learn a mechanism that is not symmetric. We effectively encoded positions. It does not matter that technically the attention layers are permutation-equivariant. In the prior literature, permutation-equivariant architecture == symmetric mechanisms, and non-permutation-equivariant architecture == asymmetric mechanisms. So it is confusing to me that the method is claimed to be permutation-equivariant while learning asymmetric mechanisms. On top of that -- what's so great about permutation equivariance in this case? The paper cites Quin et al. [2022], but they "consider the popular additive valuation and symmetric valuation setting". The EquivariantNet also only experiments with symmetric settings. And the property to generalize (lines 340-341) is not due to equivariance -- NLP routinely applies positional encodings (order matters) that work for sentences of varying lengths. The paper treats attention-based architecture as equivariant regardless of the positional (or id) encoding. So answering the question of what's so great about equivariance is actually not easy -- is it the equivariance or the attention layers that are great? It could be answered with ablations with fully-connected layers (like RegretNet) and deepset layers (like EquivariantNet) since both don't use attention and only the latter is equivariant. But this might be too deep of a rabbit hole to prove something about the property that AMenuNet does not even possess (as argued above). To be clear, this is a nitpick, but the paper seems to make a big deal out of equivariance, and I do not think it should. To conclude, I still believe the paper oversells and the soundness should be improved. The rebuttal did not change my opinion. I leave my score unchanged and I leave it to ACs to decide how important these concerns are. But feel free to let me know if I missed/misinterpreted something.

Response to the rebutatal

1. Can you please elaborate on what's novel in the neural network-based AMA method - is this a simple change in the output layer to output menus or something different? 2. In the case of non-contextual auctions, I understand that the inputs are fixed for a given setting. In this case, are you claiming/ observing that optimizing a parameterized function to generate a set of outputs is easier than directly optimizing the outputs itself? 3. Regarding permutation equivariance, how do you achieve permutation symmetry concerning the bids once you have the allocations and boosts? Can you use similar techniques with Lottery AMA parameters as well?