Suppose we want to sell some items in an auction and achieve maximum profit.
The crucial difficulty is that we do not know how much each buyer is willing to pay for an item.
If we know, at least, that the valuations of the buyers are random variables with some known probability distribution, then we can use a Bayesian-optimal mechanism.
In this case, random-sampling mechanisms provide an alternative solution.
Hence, it is a dominant strategy for the buyers to reveal their true valuation.
Intuitively, by the law of large numbers, if the market is sufficiently large then the empirical distributions are sufficiently similar to the real distributions, so we expect the RSEM to attain near-optimal profit.
The simplest case is digital goods auction.
There, step 4 is simple and consists only of calculating the optimal price in each sub-market.
Hence, the mechanism is called "Random-Sampling Optimal Price" (RSOP).
Even in a digital goods auction, RSOP does not necessarily converge to the optimal profit.
The convergence rate also depends on the number of possible "offers" considered by the mechanism.
[2] To understand what an "offer" is, consider a digital goods auction in which the valuations of the buyers, in dollars, are known to be bounded in
In general, the optimization problem may involve much more than just a single price.
of agents, the profit of the mechanism from presenting the offer
is: and the optimal profit of the mechanism is: The RSM calculates, for each sub-market
Profit oracle is another RSM scheme that can be used in large markets.
[3] It is useful when we do not have direct access to agents' valuations (e.g. due to privacy reasons).
All we can do is run an auction and watch its expected profit.
possible values (selected at random with unknown probabilities), the maximum-revenue auction can be learned using: calls to the oracle-profit.
RSMs were also studied in a worst-case scenario in which the market is small.
In such cases, we want to get an absolute, multiplicative approximation factor, that does not depend on the size of the market.
The first research in this setting was for a digital goods auction with Single-parameter utility.
[4] For the Random-Sampling Optimal-Price mechanism, several increasingly better approximations have been calculated: When the agents' valuations satisfy some technical regularity condition (called monotone hazard rate), it is possible to attain a constant-factor approximation to the maximum-profit auction using the following mechanism:[8] The profit of this mechanism is at least
This scheme can be generalized to handle constraints on the subsets of agents that can win simultaneously (e.g., there is only a finite number of items).
It can also handle agents with different attributes (e.g. young vs. old bidders).
The sample complexity of a random-sampling mechanism is the number of agents it needs to sample in order to attain a reasonable approximation of the optimal welfare.
The results in [8] imply several bounds on the sample-complexity of revenue-maximization of single-item auctions:[9] The situation becomes more complicated when the agents are not i.i.d (each agent's value is drawn from a different regular distribution) and the goods have limited supply.
, which immediately translates to a bound on their generalization error and sample-complexity.
They also prove bounds on the representation error of this class of auctions.
This is inevitable in the following sense: there is no single-price strategyproof auction that approximates the optimal profit.