A random-sampling mechanism (RSM) is a
truthful mechanism
In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly- dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have privat ...
that uses
sampling in order to achieve approximately-optimal gain in
prior-free mechanism
A prior-free mechanism (PFM) is a mechanism in which the designer does not have any information on the agents' valuations, not even that they are random variables from some unknown probability distribution.
A typical application is a seller who wa ...
s and
prior-independent mechanisms.
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
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. The term 'random variable' in its mathematical definition refers ...
with some known
probability distribution
In probability theory and statistics, a probability distribution is a Function (mathematics), function that gives the probabilities of occurrence of possible events for an Experiment (probability theory), experiment. It is a mathematical descri ...
, then we can use a
Bayesian-optimal mechanism. But often we do not know the distribution. In this case, random-sampling mechanisms provide an alternative solution.
RSM in large markets
Market-halving scheme
When the market is large, the following general scheme can be used:
# The buyers are asked to reveal their valuations.
# The buyers are split to two sub-markets,
("left") and
("right"), using
simple random sampling
In statistics, a simple random sample (or SRS) is a subset of individuals (a sample (statistics), sample) chosen from a larger Set (mathematics), set (a statistical population, population) in which a subset of individuals are chosen randomization, ...
: each buyer goes to one of the sides by tossing a
fair coin
In probability theory and statistics, a sequence of Independence (probability theory), independent Bernoulli trials with probability 1/2 of success on each trial is metaphorically called a fair coin. One for which the probability is not 1/2 is ca ...
.
# In each sub-market
, an
empirical distribution function
In statistics, an empirical distribution function ( an empirical cumulative distribution function, eCDF) is the Cumulative distribution function, distribution function associated with the empirical measure of a Sampling (statistics), sample. Th ...
is calculated.
# The
Bayesian-optimal mechanism (Myerson's mechanism) is applied in sub-market
with distribution
, and in
with
.
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
In game theory, a strategy ''A'' dominates another strategy ''B'' if ''A'' will always produce a better result than ''B'', regardless of how any other player plays. Some very simple games (called straightforward games) can be solved using domi ...
for the buyers to reveal their true valuation. In other words, this is a
truthful mechanism
In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly- dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have privat ...
.
Intuitively, by the
law of large numbers
In probability theory, the law of large numbers is a mathematical law that states that the average of the results obtained from a large number of independent random samples converges to the true value, if it exists. More formally, the law o ...
, 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
is applied to
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
, where
is some constant. The convergence rate of RSOP to optimality depends on
. The convergence rate also depends on the number of possible "offers" considered by the mechanism.
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