Prior-independent mechanism

Last updated May 03, 2021

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 items to potential buyers. The seller wants to price the items in a way that will maximize his profit. The optimal prices depend on the amount that each buyer is willing to pay for each item. The seller does not know these values, but he assumes that the values are random variables with some unknown probability distribution.

A PIM usually involves a random sampling process. The seller samples some valuations from the unknown distribution, and based on the samples, constructs an auction that yields approximately-optimal profits. The major research question in PIM design is: what is the sample complexity of the mechanism? I.e, how many agents it needs to sample in order to attain a reasonable approximation of the optimal welfare?

Single-item auctions

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

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.^[3]
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, 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:^[2]

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

Single-parametric agents

^[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:

O{\bigg (}({H \over \epsilon })^{2}(D\ln({H \over \epsilon })+\ln({1 \over \delta })){\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-\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.

Multi-parametric agents

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 $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 $n$ buyers, then the social welfare is approximately optimal. The competitive ratio implied by their Theorem 6.3 is, with probability $1-\delta$ , at least

1-O{\bigg (}{\sqrt {h^{3}n^{0.5}m^{4}\ln ^{2}m\ln ^{2}{1 \over \delta } \over {\text{OptimalWelfare}}}}{\bigg )}

.^[7]

Alternatives

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.

Related Research Articles

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 what the others do, you fare best or at least not worse by being truthful.

A double auction is a process of buying and selling goods with multiple sellers and multiple buyers. Potential buyers submit their bids and potential sellers submit their ask prices to the market institution, and then the market institution chooses some price p that clears the market: all the sellers who asked less than p sell and all buyers who bid more than p buy at this price p. Buyers and sellers that bid or ask for exactly p are also included. A common example of a double auction is stock exchange.

A first-price sealed-bid auction (FPSBA) is a common type of auction. It is also known as blind auction. In this type of auction, all bidders simultaneously submit sealed bids so that no bidder knows the bid of any other participant. The highest bidder pays the price that was submitted.

Competitive equilibrium is a concept of economic equilibrium introduced by Kenneth Arrow and Gérard Debreu in 1951 appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated.

Revenue equivalence is a concept in auction theory that states that given certain conditions, any mechanism that results in the same outcomes also has the same expected revenue.

In combinatorial mathematics and extremal set theory, the Sauer–Shelah lemma states that every family of sets with small VC dimension consists of a small number of sets. It is named after Norbert Sauer and Saharon Shelah, who published it independently of each other in 1972. The same result was also published slightly earlier and again independently, by Vladimir Vapnik and Alexey Chervonenkis, after whom the VC dimension is named. In his paper containing the lemma, Shelah gives credit also to Micha Perles, and for this reason the lemma has also been called the Perles–Sauer–Shelah lemma.

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.

The distributional learning theory or learning of probability distribution is a framework in computational learning theory. It has been proposed from Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert Schapire and Linda Sellie in 1994 and it was inspired from the PAC-framework introduced by Leslie Valiant.

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.

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 he knows that they are random variables and he knows the probability distribution of these variables.

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.

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.

In mechanism design and auction theory, a profit extraction mechanism is a truthful mechanism whose goal is to win a pre-specified amount of profit, if it is possible.

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.

Bayesian-optimal pricing is a kind of algorithmic pricing in which a seller determines the sell-prices based on probabilistic assumptions on the valuations of the buyers. It is a simple kind of a Bayesian-optimal mechanism, in which the price is determined in advance without collecting actual buyers' bids.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

Regularity, sometimes called Myerson's regularity, is a property of probability distributions used in auction theory and revenue management. Examples of distributions that satisfy this condition include Gaussian, uniform, and exponential; some power law distributions also satisfy regularity. Distributions that satisfy the regularity condition are often referred to as "regular distributions".

Adding controlled noise from predetermined distributions is a way of designing differentially private mechanisms. This technique is useful for designing private mechanisms for real-valued functions on sensitive data. Some commonly used distributions for adding noise include Laplace and Gaussian distributions.

Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is no envy. Two kinds of envy are considered:

In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used.

References

↑ Dhangwatnotai, Peerapong; Roughgarden, Tim; Yan, Qiqi (2015). "Revenue maximization with a single sample". Games and Economic Behavior. 91: 318–333. doi: 10.1016/j.geb.2014.03.011 .
1 2 Cole, Richard; Roughgarden, Tim (2014). "The sample complexity of revenue maximization". Proceedings of the 46th Annual ACM Symposium on Theory of Computing - STOC '14. p. 243. arXiv: 1502.00963 . doi:10.1145/2591796.2591867. ISBN 9781450327107.
↑ Hartline, Jason D.; Roughgarden, Tim (2009). "Simple versus optimal mechanisms". Proceedings of the tenth ACM conference on Electronic commerce - EC '09. p. 225. doi:10.1145/1566374.1566407. ISBN 9781605584584.
↑ On the Pseudo-Dimension of Nearly Optimal Auctions. NIPS. 2015. arXiv: 1506.03684 . Bibcode:2015arXiv150603684M.
↑ Devanur, Nikhil; Hartline, Jason; Karlin, Anna; Nguyen, Thach (2011). "Prior-Independent Multi-parameter Mechanism Design". Internet and Network Economics. Lecture Notes in Computer Science. 7090. p. 122. doi:10.1007/978-3-642-25510-6_11. ISBN 978-3-642-25509-0.
↑ Chawla, Shuchi; Hartline, Jason D.; Malec, David; Sivan, Balasubramanian (2013). "Prior-independent mechanisms for scheduling". Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13. p. 51. arXiv: 1305.0597 . doi:10.1145/2488608.2488616. ISBN 9781450320290.
↑ Hsu, Justin; Morgenstern, Jamie; Rogers, Ryan; Roth, Aaron; Vohra, Rakesh (2016). "Do prices coordinate markets?". Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016. p. 440. arXiv: 1511.00925 . doi:10.1145/2897518.2897559. ISBN 9781450341325.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[dhang15-1] Dhangwatnotai, Peerapong; Roughgarden, Tim; Yan, Qiqi (2015). "Revenue maximization with a single sample". Games and Economic Behavior. 91: 318–333. doi: 10.1016/j.geb.2014.03.011 .

[cr15-2] 1 2 Cole, Richard; Roughgarden, Tim (2014). "The sample complexity of revenue maximization". Proceedings of the 46th Annual ACM Symposium on Theory of Computing - STOC '14. p. 243. arXiv: 1502.00963 . doi:10.1145/2591796.2591867. ISBN 9781450327107.

[hr09-3] Hartline, Jason D.; Roughgarden, Tim (2009). "Simple versus optimal mechanisms". Proceedings of the tenth ACM conference on Electronic commerce - EC '09. p. 225. doi:10.1145/1566374.1566407. ISBN 9781605584584.

[4] On the Pseudo-Dimension of Nearly Optimal Auctions. NIPS. 2015. arXiv: 1506.03684 . Bibcode:2015arXiv150603684M.

[dhkn11-5] Devanur, Nikhil; Hartline, Jason; Karlin, Anna; Nguyen, Thach (2011). "Prior-Independent Multi-parameter Mechanism Design". Internet and Network Economics. Lecture Notes in Computer Science. 7090. p. 122. doi:10.1007/978-3-642-25510-6_11. ISBN 978-3-642-25509-0.

[6] Chawla, Shuchi; Hartline, Jason D.; Malec, David; Sivan, Balasubramanian (2013). "Prior-independent mechanisms for scheduling". Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13. p. 51. arXiv: 1305.0597 . doi:10.1145/2488608.2488616. ISBN 9781450320290.

[hmrrv16-7] Hsu, Justin; Morgenstern, Jamie; Rogers, Ryan; Roth, Aaron; Vohra, Rakesh (2016). "Do prices coordinate markets?". Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016. p. 440. arXiv: 1511.00925 . doi:10.1145/2897518.2897559. ISBN 9781450341325.

[1]

[2]

[3]

[4]

[5]

[6]

[7]