Random-sampling mechanism

A random-sampling mechanism (RSM) is a mechanism that uses sampling to achieve strategyproofness.

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

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 the consumers 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}(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.

See also

• Market research
• Pricing