Random-sampling mechanism
   HOME

TheInfoList



OR:

A random-sampling mechanism (RSM) is a
truthful mechanism In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about ...
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 mechanism A Prior-independent mechanism (PIM) is a mechanism in which the designer knows that the agents' valuations are drawn from some probability distribution, but does not know the distribution. A typical application is a seller who wants to sell some i ...
s. 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. It is a mapping or a function from possible outcomes (e.g., the po ...
with some known
probability distribution In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
, then we can use a
Bayesian-optimal mechanism A Bayesian-optimal mechanism (BOM) is a mechanism in which the designer does not know the valuations of the agents for whom the mechanism is designed, but the designer knows that they are random variables and knows the probability distribution of th ...
. 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, M_L ("left") and M_R ("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 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 called a biased or unfair coin. In th ...
. # In each sub-market M_s, an
empirical distribution function In statistics, an empirical distribution function (commonly also called an empirical Cumulative Distribution Function, eCDF) is the distribution function associated with the empirical measure of a sample. This cumulative distribution function ...
F_s is calculated. # The
Bayesian-optimal mechanism A Bayesian-optimal mechanism (BOM) is a mechanism in which the designer does not know the valuations of the agents for whom the mechanism is designed, but the designer knows that they are random variables and knows the probability distribution of th ...
(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 In game theory, strategic dominance (commonly called simply dominance) occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play. Many simple games can be solved using dominance. The ...
for the buyers to reveal their true valuation. In other words, this is a
truthful mechanism In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about ...
. Intuitively, by the
law of large numbers In probability theory, the law of large numbers (LLN) is a theorem that describes the result of performing the same experiment a large number of times. According to the law, the average of the results obtained from a large number of trials shou ...
, 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 In auction theory, a digital goods auction is an auction in which a seller has an unlimited supply of a certain item. A typical example is when a company sells a digital good, such as a movie. The company can create an unlimited number of copies ...
. 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. 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 ,h/math>. 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) 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_ g(i) and the optimal profit of the mechanism is: :OPT_G(S) := \max_ g(S) The RSM calculates, for each sub-market M_s, an optimal offer g_s, calculated as follows: ::g_s := \arg\max_ 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.


Profit-oracle scheme

''Profit oracle'' is another RSM scheme that can be used in large markets. 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.


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.


Market-halving, digital goods

The first research in this setting was for a
digital goods auction In auction theory, a digital goods auction is an auction in which a seller has an unlimited supply of a certain item. A typical example is when a company sells a digital good, such as a movie. The company can create an unlimited number of copies ...
with Single-parameter utility. For the Random-Sampling Optimal-Price mechanism, several increasingly better approximations have been calculated: * By, the mechanism profit is at least 1/7600 of the optimal. * By, the mechanism profit is at least 1/15 of the optimal. * By, the mechanism profit is at least 1/4.68 of the optimal, and in most cases 1/4 of the optimal, which is tight.


Single-sample, physical goods

When the agents' valuations satisfy some technical regularity condition (called
monotone hazard rate In auction theory, particularly Bayesian-optimal mechanism design, a virtual valuation of an agent is a function that measures the surplus that can be extracted from that agent. A typical application is a seller who wants to sell an item to a poten ...
), it is possible to attain a constant-factor approximation to the maximum-profit auction using the following mechanism: * 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 , 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).


Sample complexity

The
sample complexity The sample complexity of a machine learning algorithm represents the number of training-samples that it needs in order to successfully learn a target function. More precisely, the sample complexity is the number of training-samples that we need to ...
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: * 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. * For a 1-\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/\epsilon^2) when the agents' distributions have
monotone hazard rate In auction theory, particularly Bayesian-optimal mechanism design, a virtual valuation of an agent is a function that measures the surplus that can be extracted from that agent. A typical application is a seller who wants to sell an item to a poten ...
, and O(1/\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-\epsilon-approximation of the optimal expected revenue in single-item auctions is: * at most O(\ln^3) - using a variant of the empirical Myerson auction. * at least \Omega() (for monotone-hazard-rate regular valuations) and at least \Omega() (for arbitrary regular valuations). 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 The sample complexity of a machine learning algorithm represents the number of training-samples that it needs in order to successfully learn a target function. More precisely, the sample complexity is the number of training-samples that we need to ...
, they show that the number of samples required to approximate the maximum-revenue auction from a given class of auctions is: :O\bigg(()^2(D \ln ()+\ln())\bigg) where: * the agents' valuations are bounded in ,H/math>, * the pseudo-
VC dimension VC may refer to: Military decorations * Victoria Cross, a military decoration awarded by the United Kingdom and also by certain Commonwealth nations ** Victoria Cross for Australia ** Victoria Cross (Canada) ** Victoria Cross for New Zealand * Vic ...
of the class of auctions is at most D, * the required approximation factor is 1-\epsilon, * the required success probability is 1-\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 \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.


Envy

A disadvantage of the random-sampling mechanism is that it is not
envy-free Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by a ...
. 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 Price discrimination is a microeconomic pricing strategy where identical or largely similar goods or services are sold at different prices by the same provider in different markets. Price discrimination is distinguished from product different ...
. This is inevitable in the following sense: there is no single-price
strategyproof In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about ...
auction that approximates the optimal profit.


See also

*
Market research Market research is an organized effort to gather information about target markets and customers: know about them, starting with who they are. It is an important component of business strategy and a major factor in maintaining competitiveness. Mark ...
*
Pricing Pricing is the process whereby a business sets the price at which it will sell its products and services, and may be part of the business's marketing plan. In setting prices, the business will take into account the price at which it could acqui ...
*
Consensus estimate Consensus estimate is a technique for designing truthful mechanisms in a prior-free mechanism design setting. The technique was introduced for digital goods auctions and later extended to more general settings. Suppose there is a digital good that ...
- an alternative approach to
prior-free mechanism design 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 w ...
.


References

{{reflist Mechanism design Sampling techniques