A random-sampling mechanism (RSM) is a truthful mechanism that uses sampling in order to achieve approximately-optimal gain in prior-free mechanisms and prior-independent mechanisms.
Contents
- Market halving scheme
- Profit oracle scheme
- RSM in small markets
- Market halving digital goods
- Single sample physical goods
- Sample complexity
- Envy
- References
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. But often we do not know the distribution. In this case, random-sampling mechanisms provide an alternative solution.
Market-halving scheme
When the market is large, the following general scheme can be used:
- The buyers are asked to reveal their valuations.
- The buyers are split to two sub-markets,
M L M R - In each sub-market
M s F s - The Bayesian optimal mechanism (Myerson's mechanism) is applied in sub-market
M R F L M L F R
This scheme is called "Random-Sampling Empirical Myerson" (RSEM).
The declaration of each buyer has no effect on the price he has to pay; the price is determined by the buyers in the other sub-market. Hence, it is a dominant strategy for the buyers to reveal their true valuation. In other words, this is a truthful mechanism.
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. However, this is not necessarily true in all cases. It has been proved to be true in some special cases.
The simplest case is digital goods auction. There, step 4 is simple and consists only of calculating the optimal price in each sub-market. The optimal price in
Even in a digital goods auction, RSOP does not necessarily converge to the optimal profit. It converges only under the bounded valuations assumption: for each buyer, the valuation of the item is between 1 and
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. For example, we may want to sell several different digital goods, each of which may have a different price. So instead of a "price", we talk on an "offer". We assume that there is a global set
For every set
and the optimal profit of the mechanism is:
The RSM calculates, for each sub-market
The offer
Profit-oracle scheme
Profit oracle is another RSM scheme that can be used in large markets. 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. In a single-item auction, where there are
calls to the oracle-profit.
RSM in small markets
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.
Market-halving, digital goods
The first research in this setting was for a digital goods auction with Single-parameter utility.
For the Random-Sampling Optimal-Price mechanism, several increasingly better approximations have been calculated:
Single-sample, physical goods
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:
The profit of this mechanism is at least
Sample complexity
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 imply several bounds on the sample-complexity of revenue-maximization of single-item auctions:
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. When the agents come from
discuss arbitrary auctions with single parameter utility agents (not only single-item auctions), and arbitrary auction-mechanisms (not only specific auctions). Based on known results about sample complexity, they show that the number of samples required to approximate the maximum-revenue auction from a given class of auctions is:
where:
In particular, they consider a class of simple auctions called
Envy
A disadvantage of the random-sampling mechanism is that it is not envy-free. E.g., if the optimal prices in the two sub-markets