Adversarial learning for revenue-maximizing auctions

Thomas Nedelec, Jules Baudet, Vianney Perchet, Noureddine El KarouiarXiv 2019 · OpenReview

TL;DR

This paper introduces a novel framework for strategic bidders to learn optimal bidding strategies in revenue-maximizing auctions, even when the seller's mechanism is unknown and data-driven. By framing the interaction as a reverse Stackelberg game, the authors demonstrate that bidders can significantly increase their utility by exploiting the seller's learning process, leading to substantial gains in both single-item and multi-item auction settings.

What Problem Does This Paper Address?

Modern online marketplaces, particularly for advertising, rely heavily on revenue-maximizing auctions. Sellers use vast amounts of historical bid data to dynamically optimize their auction mechanisms, aiming to extract maximum revenue. Traditionally, auction theory assumes bidders know the seller's objective and mechanism design. However, in reality, bidders often face complex, data-driven, and opaque mechanisms. This paper addresses the gap of how strategic bidders can learn to exploit these unknown, adaptive mechanisms to improve their own outcomes (utility), without needing to fully understand the seller's optimization algorithms. This is crucial because if bidders can exploit the system, it has implications for both bidder strategy and the seller's revenue.

Methods

The core of the paper's contribution lies in its novel numerical framework and the adversarial learning approach.

  • Reverse Stackelberg Game: The authors frame the interaction as a Stackelberg game where bidders are the leaders and the seller is the follower. This means bidders choose their strategies first, influencing the seller's mechanism design, which then reacts. This is a departure from traditional auction theory where the seller is the leader.
  • Adversarial Learning: Instead of assuming bidders know the seller's optimization algorithm (e.g., Myerson's auction or specific neural network architectures), the bidders employ an "exploration bidding policy." This policy involves sampling from a distribution of potential bidding strategies (e.g., linear shading or thresholded strategies) and using reinforcement learning techniques (like policy gradients) to optimize the parameters of this distribution. The goal is to maximize the bidder's utility by learning to "attack" or exploit the seller's learning process.
  • Neural Network Mechanisms: The seller's revenue-maximizing mechanism is modeled using neural networks (specifically, MyersonNet for single-item and RegretNet for multi-item auctions), which are trained to optimize revenue based on observed bids. The adversarial approach then probes the robustness of these learned mechanisms.

Datasets

The paper does not explicitly mention using pre-existing, large-scale datasets. Instead, it focuses on a simulated environment where bidders' value distributions are known (e.g., uniform or Generalized Pareto distributions). The experiments are conducted using these simulated distributions to evaluate the performance of the adversarial learning framework. The paper introduces a benchmark for evaluating adversarial attacks on seller learning mechanisms.

Key Insights and Ideas

  • Bidders Can Exploit Unknown Mechanisms: The most significant insight is that bidders can achieve substantial utility gains by strategically learning to bid against adaptive, data-driven sellers, even without knowing the seller's exact optimization algorithm. This highlights the vulnerability of current revenue-maximizing auction designs to adversarial behavior.
  • The "Price of Revealing Information": The framework quantifies the cost (in terms of lost utility) for bidders who bid truthfully versus those who strategically shade their bids. This provides a new lens for understanding economic interactions through an algorithmic perspective.
  • Multi-Item Auctions are Not Immune: The paper extends the adversarial learning concept to multi-item auctions, demonstrating that similar strategic advantages can be gained, opening up new avenues for research in complex auction settings where analytical solutions are scarce.
  • Auction Game is Not Zero-Sum: In some scenarios, particularly with few bidders, the strategic bidder's increased utility can coexist with increased seller revenue, suggesting that the interaction isn't always a direct trade-off.

Key Results

  • Significant Utility Gains: The adversarial learning approach leads to substantial increases in bidder utility. For instance, in a single-item setting with 3 bidders, a 20% utility uplift was observed. In multi-item settings, uplifts of up to 108% (Setting Ia) and 54% (Setting IIa) were reported for the strategic bidder.
  • Revenue Impact: While bidder utility increases, seller revenue can decrease. For example, in a three-bidder single-item setting, seller revenue decreased by 9% with linear shading. However, the paper notes that this is not always the case, and sometimes both utility and revenue can increase.
  • Robustness of Learned Mechanisms: The experiments demonstrate that neural network-based revenue-maximizing mechanisms, like MyersonNet and RegretNet, are not inherently robust to adversarial attacks from strategic bidders.

Limitations and Future Work

  • Computational Cost: The adversarial training process, especially when using neural networks for both bidder strategies and seller mechanisms, can be computationally intensive.
  • Exploration vs. Exploitation Trade-off: The paper uses a normal distribution for exploration, which doesn't fully exploit the learned strategy (variance is not driven to zero). While this makes the approach robust to changes in the seller's mechanism, it might limit the maximum achievable utility. Future work could explore optimizing the variance or using more advanced exploration strategies.
  • Generalizing Bidder Strategies: The current work focuses on linear and thresholded bidding strategies. Future research could explore using neural networks to parametrize more complex bidding strategies.
  • Adversarially-Robust Mechanisms: A natural extension is to design seller learning mechanisms that are inherently robust to adversarial attacks, ensuring revenue maximization even against strategic bidders. This would involve incorporating constraints into the seller's optimization process.
  • Combinatorial Auctions: Extending the framework to combinatorial auctions, where bidders bid on bundles of items, is a promising direction.

Summary updated

Abstract

We introduce a new numerical framework to learn optimal bidding strategies in repeated auctions when the seller uses past bids to optimize her mechanism. Crucially, we do not assume that the bidders know what optimization mechanism is used by the seller. We recover essentially all state-of-the-art analytical results for the single-item framework derived previously in the setup where the bidder knows the optimization mechanism used by the seller and extend our approach to multi-item settings, in which no optimal shading strategies were previously known. Our approach yields substantial increases in bidder utility in all settings. Our approach also has a strong potential for practical usage since it provides a simple way to optimize bidding strategies on modern marketplaces where buyers face unknown data-driven mechanisms.
BibTeX
@misc{nedelec2019adversarial,
  author = {Thomas Nedelec and Jules Baudet and Vianney Perchet and Noureddine El Karoui},
  title = {{Adversarial learning for revenue-maximizing auctions}},
  year = {2019},
  eprint = {1909.06806},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.06806},
}
Figure