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$

See also

• Market research
• Pricing