Introduction
In the realm of Real-Time Bidding (RTB) for online advertisements, a seller (such as an ad exchange) frequently interacts with the same buyer (an advertiser) over multiple rounds. Standard economic theory dictates that if both parties value future money equally, the optimal strategy for the seller is to offer a constant "Myerson price" in every round.
However, in real-world scenarios, patience levels—represented by discount factors—are rarely symmetrical. A large platform might be highly patient ($\gamma_S \approx 1$), while a smaller advertiser might require immediate returns ($\gamma_B \ll 1$). Conversely, a cash-strapped seller might be less patient than the buyer. This paper investigates how these "patience imbalances" fundamentally alter optimal pricing strategies, demonstrating that the traditional Myerson price is often suboptimal.
Methodology: Handling Patience Imbalances
The authors divide the problem into two distinct scenarios based on which party is more patient:
1. The Less Patient Seller ($\gamma_S \le \gamma_B$) When the seller is less patient, the authors prove that a "Big Deal" algorithm is optimal. Instead of charging per round, the seller offers an upfront payment for all future copies of the good. This strategy pulls revenue forward to the start of the game, maximizing utility for an impatient seller.
2. The More Patient Seller ($\gamma_S \ge \gamma_B$) This scenario presents a complex "saddle-point" structure with an exponential number of discontinuities. The authors' primary breakthrough is reducing this computationally heavy problem to the optimization of a novel multivariate functional. This functional generalizes the one used to find the Myerson price, is continuously differentiable, and features a bilinear-like structure that allows for standard gradient-based optimization.
The $\tau$-step Approximation To manage long or infinite games where the number of variables would otherwise explode ($2^T - 1$), the authors introduce $\tau$-step algorithms. These algorithms dynamically adjust prices for only the first $\tau$ rounds and then remain constant. This provides a computationally efficient method to capture the majority of the available revenue boost without exhaustive variable computation.
Key Insights and Results
The central finding of the paper is the "death of constant pricing" in asymmetric settings. The folklore wisdom that constant pricing is optimal holds only when discount factors are identical. By transforming a jumpy optimization problem into a smooth multivariate functional, the authors enable standard optimizers to find dynamic pricing strategies that significantly outperform static baselines.
- Significant Revenue Boost: In cases where the seller is highly patient ($\gamma_S = 0.9$) and the buyer is impatient ($\gamma_B = 0.2$), even a simple 2-step algorithm increases revenue by over 20% compared to the static Myerson baseline.
- Rapid Convergence: The expected strategic revenue of $\tau$-step algorithms converges quickly to the theoretical optimal revenue as $\tau$ increases. A 2-step or 3-step algorithm gets surprisingly close to the maximum possible revenue, making these findings highly practical for engineering teams.
- Robustness to Uncertainty: Even if the seller only has a weak estimate of the buyer's discount factor (e.g., knowing it within a 4% margin), they can still extract over 99% of the optimal revenue.
Limitations and Future Work
While the paper provides a robust framework for asymmetric patience, it assumes the buyer's valuation $v$ remains fixed across all $T$ rounds, whereas real ad market valuations can fluctuate. Additionally, the study focuses on a single-seller, single-buyer interaction. Generalizing the multivariate functional to multi-buyer auctions remains an open challenge. Finally, the core proofs assume the seller knows the buyer's discount sequence exactly; future work could explore more adversarial settings where the buyer actively conceals their patience level.
Summary updated