Random-sampling mechanism

When the market is large, the following general scheme can be used:{{Cite Algorithmic Game Theory 2007}}{{rp|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 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.{{Cite journal|doi=10.1016/j.jcss.2007.08.002|title=Reducing mechanism design to algorithm design via machine learning|journal=Journal of Computer and System Sciences|volume=74|issue=8|pages=1245|year=2008|last1=Balcan|first1=Maria-Florina|author1-link= Maria-Florina Balcan |last2=Blum|first2=Avrim|author2-link=Avrim Blum|last3=Hartline|first3=Jason D.|last4=Mansour|first4=Yishay|doi-access=free}}

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\backslash 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

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

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

and the optimal profit of the mechanism is:

:$OPT\_G(S)\; :=\; \backslash max\_\{g\backslash in\; G\}\; g(S)$

The RSM calculates, for each sub-market $M\_s$, an optimal offer $g\_s$, calculated as follows:

::$g\_s\; :=\; \backslash arg\backslash max\_\{g\backslash in\; G\}\; g(M\_s)$

The offer $g\_L$ is applied to the buyers in $M\_R$, i.e.: each buyer $i\backslash 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.

Profit oracle is another RSM scheme that can be used in large markets.{{cite conference|title=Designing And Learning Optimal Finite Support Auctions|year=2007|conference=SODA|author=Edith Elkind|author-link=Edith Elkind}} It is useful when we do not have direct access to agents' valuations (e.g. due to privacy reasons). All we can do is run an auction and watch its expected profit. In a single-item auction, where there are $n$ bidders, and for each bidder there are at most $K$ possible values (selected at random with unknown probabilities), the maximum-revenue auction can be learned using:

:$O(n^2\; K^2)$

calls to the oracle-profit.

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 with Single-parameter utility.{{Cite book|doi=10.1007/3-540-44676-1_35|chapter=Competitive Auctions for Multiple Digital Goods|title=Algorithms — ESA 2001|volume=2161|pages=416|series=Lecture Notes in Computer Science|year=2001|last1=Goldberg|first1=Andrew V.|last2=Hartline|first2=Jason D.|isbn=978-3-540-42493-2|citeseerx=10.1.1.8.5115}}

For the Random-Sampling Optimal-Price mechanism, several increasingly better approximations have been calculated:

• By,{{cite journal|doi=10.1016/j.geb.2006.02.003|title=Competitive auctions|journal=Games and Economic Behavior|volume=55|issue=2|pages=242|year=2006|last1=Goldberg|first1=Andrew V.|last2=Hartline|first2=Jason D.|last3=Karlin|first3=Anna R.|last4=Saks|first4=Michael|last5=Wright|first5=Andrew}} the mechanism profit is at least 1/7600 of the optimal.
• By,{{cite book|doi=10.1007/11600930_89|chapter=On the Competitive Ratio of the Random Sampling Auction|title=Internet and Network Economics|volume=3828|pages=878|series=Lecture Notes in Computer Science|year=2005|last1=Feige|first1=Uriel|last2=Flaxman|first2=Abraham|last3=Hartline|first3=Jason D.|last4=Kleinberg|first4=Robert|isbn=978-3-540-30900-0|citeseerx=10.1.1.136.2094}} the mechanism profit is at least 1/15 of the optimal.
• By,{{Cite book|doi=10.1145/1566374.1566402|chapter=On random sampling auctions for digital goods|title=Proceedings of the tenth ACM conference on Electronic commerce - EC '09|pages=187|year=2009|last1=Alaei|first1=Saeed|last2=Malekian|first2=Azarakhsh|last3=Srinivasan|first3=Aravind|isbn=9781605584584|citeseerx=10.1.1.758.3195|s2cid=582565}} the mechanism profit is at least 1/4.68 of the optimal, and in most cases 1/4 of the optimal, which is tight.

When the agents' valuations satisfy some technical regularity condition (called monotone hazard rate), it is possible to attain a constant-factor approximation to the maximum-profit auction using the following mechanism:{{cite journal|doi=10.1016/j.geb.2014.03.011 | volume=91 | title=Revenue maximization with a single sample | journal=Games and Economic Behavior | pages=318–333| year=2015 | last1=Dhangwatnotai | first1=Peerapong | last2=Roughgarden | first2=Tim | last3=Yan | first3=Qiqi | doi-access=free }}

• Sample a single random agent and query his value (the agents are assumed to have single-parameter utility).
• On the other agents, run a VCG auction with reserve-price determined by the sampled agent.

The profit of this mechanism is at least $\{n-1\; \backslash over\; 4n\}$, where $n$ is the number of agents. This is 1/8 when there are two agents, and grows towards 1/4 as the number of agents grows. This scheme can be generalized to handle constraints on the subsets of agents that can win simultaneously (e.g., there is only a finite number of items). It can also handle agents with different attributes (e.g. young vs. old bidders).

The sample complexity of a random-sampling mechanism is the number of agents it needs to sample in order to attain a reasonable approximation of the optimal welfare.

The results in imply several bounds on the sample-complexity of revenue-maximization of single-item auctions:{{cite conference|doi=10.1145/2591796.2591867|chapter=The sample complexity of revenue maximization|title=Proceedings of the 46th Annual ACM Symposium on Theory of Computing - STOC '14|pages=243|year=2014|last1=Cole|first1=Richard|last2=Roughgarden|first2=Tim|isbn=9781450327107

|arxiv=1502.00963}}

• For a $1/4$-approximation of the optimal expected revenue, the sample-complexity is $1$ - a single sample suffices. This is true even when the bidders are not i.i.d.{{cite conference|doi=10.1145/1566374.1566407|chapter=Simple versus optimal mechanisms|title=Proceedings of the tenth ACM conference on Electronic commerce - EC '09|pages=225|year=2009|last1=Hartline|first1=Jason D.|last2=Roughgarden|first2=Tim|isbn=9781605584584}}
• For a $1-\backslash epsilon$-approximation of the optimal expected revenue, when the bidders are i.i.d OR when there is an unlimited supply of items (digital goods), the sample-complexity is $O(1/\backslash epsilon^2)$ when the agents' distributions have monotone hazard rate, and $O(1/\backslash epsilon^3)$ when the agents' distributions are regular but do not have monotone-hazard-rate.

The situation becomes more complicated when the agents are not i.i.d (each agent's value is drawn from a different regular distribution) and the goods have limited supply. When the agents come from $k$ different distributions, the sample complexity of $1-\backslash epsilon$-approximation of the optimal expected revenue in single-item auctions is:

• at most $O(\{k^\{10\}\backslash over\; \backslash epsilon^7\}\backslash ln^3\{k\backslash over\backslash epsilon\})$ - using a variant of the empirical Myerson auction.
• at least $\backslash Omega(\{k\backslash over\; \backslash sqrt\{\backslash epsilon\backslash ln\; k\}\})$ (for monotone-hazard-rate regular valuations) and at least $\backslash Omega(\{k\backslash over\; \backslash epsilon\})$ (for arbitrary regular valuations).

{{cite conference|title=On the Pseudo-Dimension of Nearly Optimal Auctions|year=2015|conference=NIPS|url=http://papers.nips.cc/paper/5766-on-the-pseudo-dimension-of-nearly-optimal-auctions|arxiv=1506.03684|bibcode=2015arXiv150603684M}} discuss arbitrary auctions with single-parameter utility agents (not only single-item auctions), and arbitrary auction-mechanisms (not only specific auctions). Based on known results about sample complexity, they show that the number of samples required to approximate the maximum-revenue auction from a given class of auctions is:

:$O\backslash bigg((\{H\backslash over\; \backslash epsilon\})^2(D\; \backslash ln\; (\{H\backslash over\; \backslash epsilon\})+\backslash ln(\{1\backslash over\backslash delta\}))\backslash bigg)$

where:

• the agents' valuations are bounded in $[1,H]$,
• the pseudo-VC dimension of the class of auctions is at most $D$,
• the required approximation factor is $1-\backslash epsilon$,
• the required success probability is $1-\backslash delta$.

In particular, they consider a class of simple auctions called $t$-level auctions: auctions with $t$ reserve prices (a Vickrey auction with a single reserve price is a 1-level auction). They prove that the pseudo-VC-dimension of this class is $O(nt\; \backslash ln\; (nt))$, which immediately translates to a bound on their generalization error and sample-complexity. They also prove bounds on the representation error of this class of auctions.

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.{{cite conference | url=http://dl.acm.org/citation.cfm?id=644145 | title=Competitiveness via consensus | access-date=7 January 2016 | author=Andrew V. Goldberg and Jason D. Hartline | book-title=Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms | year=2003 | conference=SODA '03}}

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

{{reflist}}

Category:Mechanism design

Category:Sampling techniques