×

zbMATH — the first resource for mathematics

Applications of \(\alpha \)-strongly regular distributions to Bayesian auctions. (English) Zbl 1406.91165
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 244-257 (2015).
Summary: Two classes of distributions that are widely used in the analysis of Bayesian auctions are the monotone hazard rate (MHR) and regular distributions. They can both be characterized in terms of the rate of change of the associated virtual value functions: for MHR distributions the condition is that for values \(v < v'\), \(\phi (v') - \phi (v) \geq v' - v\), and for regular distributions, \(\phi (v') - \phi (v) \geq 0\). The first author and T. Roughgarden [in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC’14. New York, NY: Association for Computing Machinery (ACM). 243–252 (2014; Zbl 1315.91026)] introduced the interpolating class of \(\alpha \)-Strongly Regular distributions (\(\alpha \)-SR distributions for short), for which \(\phi (v') - \phi (v) \geq \alpha (v' - v)\), for \(0 \leq \alpha \leq 1\). In this paper, we investigate five distinct auction settings for which good expected revenue bounds are known when the bidders’ valuations are given by MHR distributions. In every case, we show that these bounds degrade gracefully when extended to \(\alpha \)-SR distributions. For four of these settings, the auction mechanism requires knowledge of these distribution(s) (in the other setting, the distributions are needed only to ensure good bounds on the expected revenue). In these cases we also investigate what happens when the distributions are known only approximately via samples, specifically how to modify the mechanisms so that they remain effective and how the expected revenue depends on the number of samples.
For the entire collection see [Zbl 1326.68026].

MSC:
91B26 Auctions, bargaining, bidding and selling, and other market models
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bhattacharya, S., Goel, G., Gollapudi, S., Munagala, K.: Budget constrained auctions with heterogeneous items. In: STOC, pp. 379–388 (2010) · Zbl 1293.91077 · doi:10.1145/1806689.1806743
[2] Chawla, S., Malec, D.L., Malekian, A.: Bayesian mechanism design for budget-constrained agents. In: EC, pp. 253–262 (2011) · doi:10.1145/1993574.1993613
[3] Cole, R., Roughgarden, T.: The sample complexity of revenue maximization. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, pp. 243–252, 31 May–03 June 2014 · Zbl 1315.91026 · doi:10.1145/2591796.2591867
[4] Dhangwatnotai, P., Roughgarden, T., Yan, Q.: Revenue maximization with a single sample. In: EC, pp. 129–138 (2010) · Zbl 1318.91088 · doi:10.1145/1807342.1807364
[5] Hartline, J.D.: Mechanism design and approximation. Book draft (2014)
[6] Hartline, J.D., Karlin, A.: Profit maximization in mechanism design. In: Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.V. (eds.) Algorithmic Game Theory, chapt. 13, pp. 331–362. Cambridge University Press, Cambridge (2007) · doi:10.1017/CBO9780511800481.015
[7] Hartline, J.D., Roughgarden, T.: Simple versus optimal mechanisms. In: EC, pp. 225–234 (2009) · doi:10.1145/1566374.1566407
[8] Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981) · Zbl 0496.90099 · doi:10.1287/moor.6.1.58
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.