Prior-independent mechanism

The results in [1] imply several bounds on the sample-complexity of revenue-maximization of single-item auctions:[2]

• For a ${\displaystyle 1/4}$-approximation of the optimal expected revenue, the sample-complexity is ${\displaystyle 1}$ - a single sample suffices. This is true even when the bidders are not i.i.d.[3]
• For a ${\displaystyle 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 ${\displaystyle O(1/\epsilon ^{2})}$ when the agents' distributions have monotone hazard rate, and ${\displaystyle 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 ${\displaystyle k}$ different distributions, the sample complexity of ${\displaystyle 1-\epsilon }$-approximation of the optimal expected revenue in single-item auctions is:[2]

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

[4] 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:

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

where:

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

In particular, they consider a class of simple auctions called ${\displaystyle t}$-level auctions: auctions with ${\displaystyle 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 ${\displaystyle 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.

Devanur et al study a market with different item types and unit demand agents.[5]

Chawla et al study PIMs for the makespan minimization problem.[6]

Hsu et al study a market with different item types. The supplies are fixed. The buyers can buy bundles of items, and have different valuations on bundles. They prove that, if ${\displaystyle n}$ buyers are sampled independently from some unknown distribution, an optimal price-vector is calculated, and this price-vector is then applied to a fresh sample of ${\displaystyle n}$ buyers, then the social welfare is approximately optimal. The competitive ratio implied by their Theorem 6.3 is, with probability ${\displaystyle 1-\delta }$, at least

${\displaystyle 1-O{\bigg (}{\sqrt {h^{3}n^{0.5}m^{4}\ln ^{2}m\ln ^{2}{1 \over \delta } \over {\text{OptimalWelfare}}}}{\bigg )}}$.[7]

Prior-independent mechanisms (PIM) should be contrasted with two other mechanism types:

• Bayesian-optimal mechanisms (BOM) assume that the agents' valuations are drawn from a known probability distribution. The mechanism is tailored to the parameters of this distribution (e.g., its median or mean value).
• Prior-free mechanisms (PFM) do not assume that the agents' valuations are drawn from any probability distribution (known or unknown). The seller's goal is to design an auction that will produce a reasonable profit even in worst-case scenarios.

From the point-of-view of the designer, BOM is the easiest, then PIM, then PFM. The approximation guarantees of BOM and PIM are in expectation, while those of PFM are in worst-case.

• Market research
• Algorithmic pricing