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?
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 knownprobability 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 anyprobability 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.
- ^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.
- ^ Jump up to:ab 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.