Random-sampling mechanism

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

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 (this is the prior-free setting). In this case, random-sampling mechanisms provide an alternative solution.

RSM in large markets

When the market is large, the following general scheme can be used:^[1]:341-344

1. The buyers are asked to reveal their valuations.
2. The buyers are split to two sub-markets, $M_L$ ("left") and $M_R$ ("right"), using Simple random sampling: each buyer goes is selected to one of the sides by tossing a fair coin.
3. In each sub-market $M_s$, an empirical distribution function $F_s$ is calculated.
4. The Bayesian optimal mechanism (Myerson's mechanism) is applied in sub-market $M_R$ with distribution $F_L$, and in $M_L$ with $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 $M_L$ is applied to $M_R$ and vice-versa. Hence, the mechanism is called "Random-Sampling Optimal Price" (RSOP). This case is simple because it always calculates feasible allocations. I.e, it is always possible to apply the price calculated in one side to the other side. This is not necessarily the case with physical goods.

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 $h$, where $h$ is some constant. The convergence rate of RSOP to optimality depends on $h$. The convergence rate also depends on the number of possible "offers" considered by the mechanism.^[2]

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 $[1,h]$. If the mechanism uses only whole dollar prices, then there are only $h$ possible offers.

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)$

The RSM calculates, for each sub-market $M_s$, an optimal offer $g_s$, calculated as follows:

$g_s := \arg\max_{g\in G} g(M_s)$

The offer $g_L$ is applied to the buyers in $M_R$, i.e: each buyer $i\in M_R$ who said that $g_L(i)>0$ receives the offered allocation and pays $g_L(i)$; each buyer in $M_R$ who said that $g_L(i)=0$ do not receive and do not pay anything. The offer $g_R$ is applied to the buyers in $M_L$ in a similar way.

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. The first research in this setting was for a digital goods auction.^[3]

For the RSOP mechanism, several increasingly better approximations have been calculated:

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

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 $M_L$ and $M_R$ are different, then buyers in each sub-market are offered a different price. 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.^[7]

See also

• Market research
• Pricing
• Consensus estimate - an alternative approach to prior-free mechanism design.

References

1. Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
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.
3. 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.
4. Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R.; Saks, Michael; Wright, Andrew (2006). "Competitive auctions". Games and Economic Behavior 55 (2): 242. doi:10.1016/j.geb.2006.02.003.
5. Feige, Uriel; Flaxman, Abraham; Hartline, Jason D.; Kleinberg, Robert (2005). "On the Competitive Ratio of the Random Sampling Auction". Internet and Network Economics. Lecture Notes in Computer Science 3828. p. 878. doi:10.1007/11600930_89. ISBN 978-3-540-30900-0.
6. Alaei, Saeed; Malekian, Azarakhsh; Srinivasan, Aravind (2009). "On random sampling auctions for digital goods". Proceedings of the tenth ACM conference on Electronic commerce - EC '09. p. 187. doi:10.1145/1566374.1566402. ISBN 9781605584584.
7. 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.