Deep Reinforcement Learning for Sequential Combinatorial Auctions

Thank you for your thoughtful review and positive assessment of our work.

Complexity:

Can you elaborate on what you mean by complexity?

In Appendix D, we include the training curves which plot the expected revenue with respect to the number of updates. Our approach converges much more quickly compared to PPO in terms of the number of updates as well as time taken. For the 10 agents and 10 items setting, our method required 20 minutes. We terminated PPO at around 5 hours.

Reliance on agents' valuation distributions:

Please refer to the comment here.

Thank you for your thoughtful review!

We appreciate your suggestions and would love to know if there are specific baselines you have in mind. This way, we can potentially incorporate additional experiments and update our results accordingly. We’ll address the remaining points on weaknesses shortly.

Choice of Baselines:
We focused on PPO and SAC, as they are the state-of-the-art methods for continuous action spaces. As noted in Section 1, DQN and other Q-learning approaches are suitable only for discrete action spaces, which limits their applicability here. TRPO, while valuable, is considered a predecessor to PPO, and it tends to be less sample-efficient and slower in practice. Empirically, PPO often demonstrates superior performance, which is why we chose to prioritize it over TRPO in our results. We also tested DDPG in some settings, but it proved unstable in our experiments.

Thank you for your detailed review and thoughtful feedback!

Scaling:
Our settings are quite different from Pieroth et. al. (they focus on computing equilibrium strategies). Our focus is on the inverse problem (given truth telling is the equilibrium, what are the rules of a revenue-optimal auction).

Our approach demonstrates strong scalability, achieving results for settings with up to 50 agents and 50 items—far exceeding the capabilities of existing differentiable economics-based methods for auction design.

Scaling Further: The primary limitation of running RochetNet with all possible bundle prices arises from hardware constraints. For m > 10 items, the need to output 2^m bundle prices introduces significant memory and computational demands. However, if we restrict ourselves to subadditive valuations, we can scale up to m = 50 items, with scaling linear in terms of space and O(m log m) in terms of computation.

We can, however, expand scalability in terms of the number of bidders while keeping the number of items fixed. For example, with 200 bidders, we can process them in batches of 50—starting with the last 50 bidders, followed by the preceding 50, and so on. This strategy serves as a natural hybrid between our DP and FPI approaches, allowing us to achieve optimal results. Importantly, this method is constrained only by computational time and not memory.

Reliance on value distribution:
Please refer to the comment here

Baselines:

We would love to know if there are specific baselines you have in mind.

We focused on PPO and SAC, as they are the state-of-the-art methods for continuous action spaces. As noted in Section 1, DQN and other Q-learning approaches are suitable only for discrete action spaces, which limits their applicability here. TRPO, while valuable, is considered a predecessor to PPO, and it tends to be less sample-efficient and slower in practice. Empirically, PPO often demonstrates superior performance, which is why we chose to prioritize it over TRPO in our results. We also tested DDPG in some settings, but it proved unstable in our experiments.

Order of Agents:
If the bidder types (value distributions) are identical, the order doesn't affect the outcome as we are concerned with expected revenue. However, if they are not identical, we can train RochetNets at each state over an equal mixture of these types. This would add the benefit of being order agnostic!

It is important to note that our focus on strategy-proof mechanisms prevents the use of agents' reports or dynamically realized orders to modify the menu, as doing so would compromise incentive compatibility.

Hyperparameters:
As shown in Table 5 in the Appendix, most hyperparameters were set to default values for all the settings. Empirical evidence from our experiments indicates that our approach is relatively robust to variations in hyperparameters. This robustness stems from its reliance on first-order gradients for updates, in contrast to traditional RL methods, which rely heavily on exploratory noise and involve tuning numerous hyperparameters.

I thank the authors for their response and increased my score. However, I still believe more domain-specific SOTA works should be included for baseline comparison

Thank you for updating the score and engaging with us. If there are any domain-specific state-of-the-art methods you believe we should consider, we would greatly appreciate your suggestions.

Much of the existing work in this domain consists of existential results, with constructive approaches typically limited to highly restrictive settings. In this paper, we have introduced what we believe to be the first general-purpose approach to designing mechanisms for the sequential auction setting. In addition to comparing against standard mechanism baselines (e.g., selling item-wise and bundle-wise), we have also evaluated our method against standard reinforcement learning approaches such as PPO and SAC. We would be happy to incorporate further baselines if you have any additional recommendations.

Thank you for your detailed review and thoughtful feedback!

On Relevance and General Interest
Our work contributes to the emerging field of AI for Economics Theory, showcasing how reinforcement learning can effectively solve complex mechanism design problems that are analytically intractable.

There is an existing body of literature regarding the use of deep learning for the design of multi-item auctions. This area has garnered significant interest within the machine learning community, as evidenced by numerous papers presented at conferences such as ICML, NeurIPS, and ICLR. Notably, works like "Optimal Auctions through Deep Learning" at ICML-19 and others such as [Curry et al., NeurIPS-20], [Rahme et al., ICLR-21], [Duan et al., ICML-22], [Ivanov et al., NeurIPS-22], and [Duan et al., NeurIPS-23] have contributed to the exploration of deep learning approaches for improving multi-item auction design, as cited in our paper.

In addition, we want to highlight that our approach shows promise for broader applicability. For problems featuring large action and continuous spaces, wherever we can model transitions differentiably (for instance in physics or robotics), we anticipate our approach outperforming existing standard RL methods. In this paper, we employ multiple RochetNets to compute the policy (which is most suited for learning menu-based mechanisms). However, for a general MDP, alternative methods could be explored. For instance, one could use linear programming (LP) or convex optimization to compute optimal policies in the continuous space, leverage gradient computation techniques proposed by [1] to obtain gradients through the solutions, and integrate this with fitted policy iteration.

References
[1] Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., & Kolter, J. Z. (NeurIPS 2019).
Differentiable convex optimization layers

Real-world examples
Sequential auctions are frequently used in real life for their simplicity and strategy-proofness guarantees. For instance, companies like Costco and Amazon use Sequential Mechanisms with Entry Fees. To the best of our knowledge, we didn’t find any publicly available dataset (as most of these datasets are proprietary). If you know any please suggest them and we will include them. As a fallback, we have endeavored to capture some real-world structures through different distributions (symmetric, asymmetric) and different valuation types (additive, k-demand, combinatorial).

FPI citation
Thanks for pointing this out. We have updated our paper with the required citations for FPI.

Thank you for providing a rebuttal. I agree that AI for Economics Theory is an emerging topic. It is the specific combination of three (sequential auction + combinatorial + numerical solution) that makes the topic niche. As you discussed companies like Costco and Amazon use Sequential Mechanisms with Entry Fees, could you provide enough evidence that this is exactly how they work and it fits close enough to your setting/your combination of three?