- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes CoalitionNet, a deep learning-based method for learning collusion-resistant auctions. CoalitionNet consists of a "collusion generator" and a "mechanism network". The mechanism network is trained to maximize the expected revenue and minimize the expected coalition regret. The collusion generator can generate candidate coalition as well as collusive bids, and is trained to maximize the expected coalition regret. Experiments show that CoalitionNet successfully learns auctions with low coalition regrets, while existing baselines that only minimize the individual regret fail.
Critical strengths
- This paper integrates deep learning into collusion-resistant auction design, which is novel in my knowledge and meaningful.
- The methodology is straightforward and well presented. The experiment shows the potential of CoalitionNet in learning collusion-resistant auctions.
Critical weaknesses
I have a few concerns about the soundness of experimental designs.
- There lack simple settings (e.g., 2 bidders and 1 item) where analytically optimal collusion-resistant auctions exist. Without comparisons in such settings, it's hard to evaluate whether CoalitionNet can approximate the optimal auctions in simple settings (which I also believe is a natural evaluation).
- There lack simple baselines (e.g., run optimal auctions to each item independently, similar to Itemwise Myerson auction) that can serve as collusion-resistant baselines in general settings (for general bidders and items). Without comparisons to such baselines, it's hard to evaluate whether CoalitionNet can outperform simple baselines and thus be practically useful in general settings.
- The paper does not describe how "coal. regret" is computed for a sampled . In my understanding it can not be exactly computed with plausible computation load, so in experiments this value can only be computed heuristically. Therefore, the "coal. regret" is under estimated compared with the true coalition regrets. This is fine, but the paper should clearly state this, with description about how coalition regrets are empirically computed. Furthermore, if the computations of coalition regrets are similar to those used to train the "Collusion Generator", then it's likely that the under-estimation of CoalitionNet is more severe than other baselines.
Questions for authors
- In line 238, what is the role of in the methodology?
- In line 189-196, some questions about the "two critical challenges" claimed by the paper:
- Why does the paper claim "Combinatorial Search Space" as a challenge? I did not see how the CoalitionNet resolves this challenge. Sampling a coalition subset is a standard approach in my view either.
- I'm confused about what the second challenge "Gradient Vanishing in Joint Space" actually means. It seems to me that this challenge has not been acknowledged in existing works, and possibly the authors discovered this challenge in their researches. If so, it's better to provide empirical results to make the statement of this challenge more convincing.
- In Table 1, what dimension does "max. coal. regret" take "max" over?
- See my weaknesses above.
4 comments
Response to W3. We agree with the reviewer that the original manuscript lacked a clear description of how coalition regret is computed, as well as the potential under-estimation issue. We fully agree that computing exact coalition regret requires taking the continuous supremum over joint misreports across all non-empty coalitions, which is computationally intractable in high-dimensional settings such as . Therefore, the reported coal. regret metrics in our manuscript are empirical approximations. We will explicitly state this limitation and add a dedicated description of the evaluation protocol in Section 5.1 of the revised manuscript.
Specifically, for each sampled valuation profile , we enumerate all non-empty coalitions , hold non-coalition bids truthful ( for all ), and apply gradient ascent to directly optimize the coalition's total utility gain over the joint misreport . Additionally, as demonstrated in Section 5.5 and Figure 5 of the manuscript, our learned/gradient-based attacks are close to the strongest possible deviations against exhaustive grid search in tractable small-scale settings. This empirical validation justifies using gradient-based search to approximate worst-case coalition deviations in larger settings. The gradient-ascent attack is applied identically and independently across CoalitionNet and all baseline mechanisms to ensure a fair empirical comparison.
Response to Q1. is a stochastic exploration input, sampled as Gaussian noise and appended to each bidder token of the collusion generator. Its role is to produce diverse generator reports, allowing the generator to capture multiple distinct collusive bidding strategies for a given valuation profile.
Response to Q2a (Combinatorial Search Space). We apologize for the unclear exposition in the original manuscript, and we clarify below how CoalitionNet handles the coalition space. CoalitionNet does not simply sample a random coalition subset and evaluate that single subset alone. For naive subset sampling, each forward pass inspects only one out of coalitions, and the resulting utility signal can be noisy or misleading when non-benefiting members in cancel out gains or outside winners are excluded. Instead, our generator samples an active deviator set (composed of a prefix and a pivot bidder ) whose bids are modified while all remaining bidders report truthfully. Crucially, because any bidder in stays truthful, this single modified bid profile is simultaneously feasible for all superset coalitions . Given the induced utility changes , an external bidder increases the coalition's total utility if and only if . Consequently, rather than enumerating the supersets, the optimal superset is obtained analytically in time via Thus, although the generator still samples prefixes and pivots to explore the space of active deviations, the analytic envelope eliminates the exponential enumeration over the coalition supersets for any given active deviation. We will clarify this distinction in Section 4.
Response to Q2b (Gradient Vanishing). We apologize for the lack of clarity regarding the gradient vanishing challenge and the absence of empirical substantiation in our original submission. Here, gradient vanishing refers to the vanishing of the attack objective's gradient with respect to the jointly modified bids of the active deviators . Specifically, under a joint bid reduction, the sampled subset alone can experience a non-positive aggregate utility change even when an outside bidder benefits from the resulting allocation shift. As a result, the naive subset objective saturates on the flat zero-gradient plateau of , preventing outside beneficiaries from providing any optimization signal to . In contrast, our externality-guided objective retains the signed utility changes of members in and incorporates positive externalities from outside bidders, yielding non-zero gradients for the exact same joint report.
To quantify gradient vanishing empirically, we evaluate held-out profiles in the setting. For each active deviator size , we randomly sample an active set initialized with moderate bid shading () and compute the norm of the objective gradient with respect to the active bids, . We define a profile as experiencing gradient vanishing if , and report the vanishing rate as the percentage of profiles satisfying this criterion.
| Baseline | Vanishing rate (): naive vs. |
|---|---|
| RegretNet | 94/99/91/55% vs. 16/13/8/5% |
| RegretFormer | 100/100/97/71% vs. 18/28/27/18% |
| AMenuNet | 100/97/83/44% vs. 85/66/35/20% |
Across all three mechanisms, replacing naive with significantly reduces the vanishing-gradient rate (e.g., from 94–99% down to 13–16% on RegretNet for ). These results empirically verify the critical role of in providing dense gradient signals for joint deviations. Indeed, this vanishing-gradient bottleneck is precisely what we encountered when initially attempting to directly extend RegretNet's paradigm to the coalition setting, which motivated our externality-guided formulation. We apologize for this misunderstanding and will revise the manuscript to clarify this motivation and include these empirical results.
Response to Q3. We are sorry for the unclear definition of Max coal. regret and Avg coal. regret in Table 1. Both metrics are empirical estimates computed over sampled valuation profiles and all non-empty coalitions , where each per-profile, per-coalition regret is approximated via gradient ascent as described in our response to W3:
Max coal. regret: Themaxis taken over the coalition dimension (all non-empty coalitions ) for each sampled valuation profile , followed by taking the empirical expectation across the profiles:Avg coal. regret: Theavgtakes the empirical mean across both the coalition dimension and the profile dimension:
We will add these explicit definitions and equations to Section 5.1 and the caption of Table 1 in the revised manuscript.
Thank you for the authors' thorough response. Most of my main concerns are well addressed, and I decide to maintain my positive score.
Some comments:
- ICLR allows the authors to revise their manuscripts by submitting a new PDF. I would like to see that the authors implement their promised revision.
- Thank you for the further clarifications on the two challenges. The challenges and the proposed remedies really make sense to me, and I believe that the proposed remedies have independent value. It would be nice if the authors could conduct ablation studies to see how the ablated methods would perform if the challenge was not resolved. It would also be acceptable without additional ablation studies.
- For baselines, my initial concern is to compare CoalitionNet with baselines that are guaranteed to be collusion-resistant, not Itemwise Myerson. Itemwise Myerson is not collusion-resistant, so it is not the optimal baseline. I have not gone too far with revenue-optimal collusion-resistant single-item auctions, but I think "selling the item to the highest bidder with reserve price " should be a legal one, and I would like to see how CoalitionNet would compare with it (as well as other possible collusion-resistant baselines).
Responses to W1 & W2: 2×1 Optimal Benchmark Validation and 5×5 Itemwise Myerson Comparison
We thank the reviewer for raising these insightful comments and apologize for any misunderstandings caused by the lack of clarity in our original manuscript. We have conducted the corresponding supplementary experiments and address your concerns point by point as follows.
Response to W1. We added a 2×1 scenario, where each bidder's valuation is drawn i.i.d. from U[0,1]. The classical Myerson optimal auction for this case is a second-price auction (SPA) with reserve price r∗=0.5. Analytically, its truthful expected revenue is 5/12≈0.4167, while the canonical joint shading attack at 0.5 yields an attacked revenue of 3/8=0.375 and a revenue drop of 1/24≈0.0417. Here we measure three different methods, with each one evaluated over K=2,000 valuation profiles v(k)∼U[0,1]2. For learned mechanisms, results are averaged over three random seeds:
As shown in the results, CoalitionNet closely matches Myerson's truthful revenue while retaining 96.8% of SPA's attacked revenue, resulting in a revenue drop similar to the collusion-resistant mechanism. In contrast, RegretNet achieves high revenue under truthful bidding, but its attacked revenue drops sharply to 0.2317 under group deviations, incurring a substantially larger revenue drop of 0.1915. It shows that CoalitionNet can closely recover the classical results for collusion-resistant auctions, whereas learning-based mechanisms that only enforce individual IC fail to preserve revenue against collusive deviations.
Response to W2. We agree with the reviewer's comment that comparing against simple itemwise baselines is necessary, so we add Itemwise Myerson as a benchmark. It decomposes the multi-item auction into m=5 independent single-item Myerson optimal auctions (r∗=0.5) and we compare it against CoalitionNet in the 5×5 setting. Both methods are evaluated under the 5×5 additive valuation setting with valuations drawn i.i.d. from U[0,1], using the exact same K=1,000 shared evaluation profiles. To compute AvgCoal and MaxCoal (the mean and the per-profile maximum coalition regret across all 31 non-empty coalitions, respectively), we approximate the worst-case deviation using 50-step gradient ascent with 5 restarts.
As shown in the table above, although Itemwise Myerson achieves higher truthful revenue, it is vulnerable to coordinated bid shading across items: its attacked revenue falls sharply, resulting in a large revenue drop and high coalition regret. Meanwhile, CoalitionNet achieves higher attacked revenue than Itemwise Myerson while maintaining a substantially smaller revenue drop and lower coalition regret. It indicates that applying a single-item optimal auction independently to each item cannot withstand coordinated multi-item deviations, but CoalitionNet learns joint cross-item allocation and pricing rules that can preserve higher seller revenue under collusion.