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^[1] and the idea was later extended to more complex settings.^[2]

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:^[1]

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.

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:^[2]

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.^[3]

References

1 2 Goldberg, Andrew V.; Hartline, Jason D. (2001). "Competitive Auctions for Multiple Digital Goods". Algorithms — ESA 2001. Lecture Notes in Computer Science 2161. p. 416. doi:10.1007/3-540-44676-1_35. ISBN 978-3-540-42493-2.
1 2 Balcan, Maria-Florina; Blum, Avrim; Hartline, Jason D.; Mansour, Yishay (2008). "Reducing mechanism design to algorithm design via machine learning". Journal of Computer and System Sciences 74 (8): 1245. doi:10.1016/j.jcss.2007.08.002.
↑ Andrew V. Goldberg and Jason D. Hartline (2003). "Competitiveness via consensus". Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. SODA '03. Retrieved 7 January 2016.

This article is issued from Wikipedia - version of the Thursday, January 07, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Random-sampling mechanism

Example: digital-goods auction

General scheme

See also

References