Random-sampling mechanism

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

A random-sampling mechanism (RSM) is a truthful mechanism that uses sampling in order to achieve approximately-optimal gain in prior-free mechanisms 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 with some known probability distribution, 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.

A random-sampling mechanism (RSM) is a truthful mechanism that uses sampling in order to achieve approximately-optimal gain in prior-free mechanisms 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 with some known probability distribution, 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. 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374127560 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001374127560 · captured 1788994646.0 · version history

Cite this page as: encyclopegia.org, “Random-sampling mechanism”, snapshot enwiki-001374127560. https://encyclopegia.org/a/random-sampling-mechanism

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.