Abstract
The Random Sampling Optimal Price (RSOP) auction is a fundamental mechanism in prior-free digital goods auctions. Despite a long-standing conjecture that its competitive ratio is 4, the best proven bound remained at 15 for years. This paper provides a much tighter analysis, proving that RSOP is 4-competitive for most scenarios and at most 4.68-competitive in the absolute worst case. These results are achieved through a combination of granular probabilistic decomposition, dynamic programming for small bidder sets, and tail bounds for larger instances.
The Challenge of Prior-Free Revenue Maximization
In algorithmic mechanism design, a seller aims to set a price for a digital good—such as a software license or an e-book—to maximize revenue without knowing the bidders' underlying value distributions. A "prior-free" approach avoids assumptions about these distributions. The Random Sampling Optimal Price (RSOP) auction is a classic solution to this problem:
- Bidders are randomly split into two groups, $A$ and $B$.
- The optimal single price for group $A$ is calculated and offered to everyone in group $B$.
- Conversely, the optimal price for group $B$ is offered to group $A$.
The performance of such an auction is measured by its competitive ratio: the factor by which the auction's revenue is worse than the optimal revenue achievable if all bids were known in advance. While researchers long conjectured the ratio was 4, proving this has been a significant technical hurdle.
Methodological Shift: Beyond Simple Balancedness
Previous analytical attempts often relied on showing "balancedness"—the idea that the two random sets $A$ and $B$ are roughly equal—occurs with high probability. This paper moves away from that coarse approach toward a more granular analysis.
The authors model the partitioning process as a random walk. As shown in Figure 1, the variable $s_j$ (representing the number of bidders from the top $j$ bids assigned to one partition) is analyzed against specific boundaries (like $\alpha = 3/4$). If the walk stays within these boundaries, the partitions are sufficiently balanced to guarantee high revenue.
Granular Decomposition and the $\lambda$ Factor
A key insight of the paper is that the auction's performance depends heavily on $\lambda$, the number of bidders willing to pay at least the optimal price. As $\lambda$ increases, the auction becomes more predictable and efficient. To handle the negative correlation between partition size and resulting revenue, the authors use Probabilistic Decomposition.
As illustrated in Figure 2, the authors break down the expected revenue into a series of disjoint events based on varying levels of balancedness (represented by the lines $\alpha_1$ through $\alpha_9$). This allows for a much tighter summation of expected revenue than previous "all-or-nothing" balancedness proofs.
For cases where $\lambda$ is small (pathological cases), the authors employ Dynamic Programming and Exhaustive Search over "Equal Revenue Instances"—theoretical bid vectors where every possible sale price yields the same total revenue. These instances are traditionally the hardest for sampling auctions to handle.
Key Results and the "Magic" Number 6
The refined analysis yields several breakthrough bounds:
- General Bound: RSOP is at least 1/4.68-competitive (approx. 21.3% of optimal revenue) for any instance with at least 2 bidders.
- The Threshold of 6: If there are at least 6 bids at or above the optimal price ($\lambda \ge 6$), the auction is 4-competitive, finally matching the famous conjecture for the vast majority of practical instances.
- Asymptotic Performance: As the number of high bidders approaches infinity, the competitive ratio improves further to approximately 3.52.
- Upper Bound: The authors also demonstrate that RSOP can never be better than 2.65-competitive, narrowing the window for the true theoretical limit.
Conclusion and Future Work
By bringing the worst-case bound down to 4.68 and confirming the 4-competitive conjecture for $\lambda \ge 6$, this work significantly closes the gap in our understanding of random sampling auctions. While the absolute worst case ($\lambda=2$) still sits slightly above 4, the combinatorial techniques developed here—specifically the analysis of equal revenue instances—provide a roadmap for proving tighter bounds in more complex scenarios, such as double auctions or limited-supply mechanisms.
Summary updated