Random-sampling mechanism

A random-sampling mechanism (RSM) is a truthful mechanism that uses sampling in order to achieve approximately-optimal gain.

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 the results of Bayesian optimal mechanism design theory. But often we do not know the distribution, or cannot assume that the valuations are drawn from a distribution. In this case, random-sampling mechanisms provide an alternative solution.

RSM for approximating the prior distribution

The first RSM was designed for a digital goods auction and the idea was later extended to more complex settings.

RSM without a prior distribution

Example: digital goods auction

Consider a company that wants to sell a digital good, such as a movie. The company wants to decide on the best price to charge for that movie. That decision depends on the valuations of the potential consumers - how much each consumer is willing to pay to buy a movie.

If the valuations of all potential consumers are known, then the company faces a simple optimization problem - selecting the price that maximizes the profit. For concreteness, suppose there is a set $S$ of consumers and that they are ordered by their valuation, so that the consumer with the highest valuation (willing to pay the largest price for the movie) is called "1", the next-highest is called "2", etc. The valuation of consumer $i$ is denoted by $v_{i}$, such that $v_{1}\geq v_{2}\geq \dots$. For every $i$, if the price is set to $p\in (v_{i+1},v_{i}]$, then only the first $i$ consumers buy the movie, so the profit of the company is $p\cdot i$. It is clear that in this case, the company is best-off setting the price at exactly $v_{i}$; in this case its profit is $v_{i}\cdot i$. Hence, the company's optimization problem is:

$\arg \max _{i\in S}(v_{i}\cdot i)$

The problem is that, usually, the valuations of the consumers are NOT known. The producer can try to ask them, but then they will have an incentive to report lower valuations in order to decrease the price. The random-sampling mechanism solves that problem in the following way:

• The consumers are asked to reveal their valuations.
• The consumers are split to two subsets, $S_{1}$ and $S_{2}$, using Simple random sampling: each consumer is selected to one of the samples by tossing a fair coin.
• In each subset $S_{j}$, an optimal price $p_{j}$ is calculated.
• The price $p_{1}$ is applied to the consumers in $S_{2}$, i.e: all consumers in $S_{2}$ who said that their valuation is at least $p_{1}$ receive the product and pay $p_{1}$; all consumers in $S_{2}$ who said that their valuation is less than $p_{1}$ do not receive the product and do not pay.
• The price $p_{2}$ is applied to the consumers in $S_{1}$ in a similar way.

The declaration of each consumer has no effect on the price that this consumer has to pay; the price is determined by the consumers in the other subset. Hence, it is a dominant strategy for the consumers to reveal their true valuation. In other words, this is a truthful mechanism.

Expected profit

The mechanism designer wants to maximize the profit. However, the price in each market is not the optimal price, so the profit is less than the optimal profit. How much less? Several increasingly better approximations have been calculated:

• By, the mechanism profit is at least 1/7600 of the optimal.
• By, the mechanism profit is at least 1/15 of the optimal.
• By, the mechanism profit is at least 1/4.68 of the optimal, and in most cases 1/4 of the optimal, which is tight.

General scheme

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 $G$ of possible offers. For every offer $g\in G$ and agent $i$, $g(i)$ is the amount that agent $i$ pays when presented with the offer $g$. In the digital-goods example, $G$ is the set of possible prices. For every possible price $p$, there is a function $g_{p}$ such that $g_{p}(i)$ is either 0 (if $v_{i}<p$) or $p$ (if $v_{i}\geq p$).

For every set $S$ of agents, the profit of the mechanism from presenting the offer $g$ to the agents in $S$ is:

$g(S):=\sum _{i\in S}g(i)$

and the optimal profit of the mechanism is:

$OPT_{G}(S):=\max _{g\in G}g(S)$

A generic random-sampling mechanism works as follows:

• The consumers are asked to reveal their valuations: each consumer $i$ reveals $g(i)$ for every $g\in G$.
• The consumers are split to two subsets, $S_{1}$ and $S_{2}$, using Simple random sampling: each consumer is selected to one of the samples by tossing a fair coin.
• In each subset $S_{j}$, an optimal offer $g_{j}$ is calculated as follows:

$g_{j}:=\arg \max _{g\in G}g(S_{j})$

• The offer $g_{1}$ is applied to the consumers in $S_{2}$, i.e: each consumer $i\in S_{2}$ who said that $g_{1}(i)>0$ receives the offered allocation and pays $g_{1}(i)$; all consumers in $S_{2}$ who said that their $g_{1}(i)=0$ do not receive and do not pay anything.
• The offer $g_{2}$ is applied to the consumers in $S_{1}$ in a similar way.

One shortcoming of this approach is that it is not envy-free, since agents in $S_{1}$ are given a different offer (price) than agents in $S_{2}$. In other words, there is price discrimination. This is inevitable in the following sense: there is no single-price strategyproof auction that approximates the optimal profit.

See also

• Market research
• Pricing

References