zbMATH — the first resource for mathematics

Sequential posted price mechanisms with correlated valuations. (English) Zbl 1406.91138
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, 1-15 (2015).
Summary: We study the revenue performance of sequential posted price mechanisms and some natural extensions, for a general setting where the valuations of the buyers are drawn from a correlated distribution. Sequential posted price mechanisms are conceptually simple mechanisms that work by proposing a “take-it-or-leave-it” offer to each buyer. We apply sequential posted price mechanisms to single-parameter multi-unit settings in which each buyer demands only one item and the mechanism can assign the service to at most \(k\) of the buyers. For standard sequential posted price mechanisms, we prove that with the valuation distribution having finite support, no sequential posted price mechanism can extract a constant fraction of the optimal expected revenue, even with unlimited supply. We extend this result to the case of a continuous valuation distribution when various standard assumptions hold simultaneously. In fact, it turns out that the best fraction of the optimal revenue that is extractable by a sequential posted price mechanism is proportional to the ratio of the highest and lowest possible valuation. We prove that for two simple generalizations of these mechanisms, a better revenue performance can be achieved: if the sequential posted price mechanism has for each buyer the option of either proposing an offer or asking the buyer for its valuation, then a \(\varOmega (1/\max \{1,d\})\) fraction of the optimal revenue can be extracted, where \(d\) denotes the “degree of dependence” of the valuations, ranging from complete independence (\(d=0\)) to arbitrary dependence (\(d = n-1\)). When we generalize the sequential posted price mechanisms further, such that the mechanism has the ability to make a take-it-or-leave-it offer to the \(i\)-th buyer that depends on the valuations of all buyers except \(i\), we prove that a constant fraction \((2 - \sqrt{e})/4 \approx 0.088\) of the optimal revenue can be always extracted.
For the entire collection see [Zbl 1326.68026].

91B24 Microeconomic theory (price theory and economic markets)
Full Text: DOI
[1] Adamczyk, M., Sviridenko, M., Ward, J.: Submodular stochastic probing on matroids. In: STACS 2014 (2014) · Zbl 1359.90111
[2] Adamczyk, M., Borodin, A., Ferraioli, D., de Keijzer, B., Leonardi, S.: Sequential posted price mechanisms with correlated valuations. CoRR, abs/1503.02200 (2015) · Zbl 1406.91138
[3] Babaioff, M., Dughmi, S., Kleinberg, R., Slivkins, A.: Dynamic pricing with limited supply. In: EC 2012 (2012) · doi:10.1145/2229012.2229023
[4] Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: SODA 2007 (2007) · Zbl 1302.68133
[5] Babaioff, M., Immorlica, N., Lucier, B., Weinberg, S.M.: A simple and approximately optimal mechanism for an additive buyer. In: FOCS 2014 (2014) · doi:10.1109/FOCS.2014.11
[6] Blum, A., Hartline, J.D.: Near-optimal online auctions. In: SODA 2005 (2005) · Zbl 1297.91075
[7] Blum, A., Kumar, V., Rudra, A., Wu, F.: Online learning in online auctions. Theor. Comput. Sci. 324, 137–146 (2004) · Zbl 1091.91028 · doi:10.1016/j.tcs.2004.05.012
[8] Blumrosen, L., Holenstein, T.: Posted prices vs. negotiations: an asymptotic analysis. In: EC 2008 (2008) · doi:10.1145/1386790.1386801
[9] Börgers, T.: An Introduction to the Theory of Mechanism Design. Oxford University Press, Oxford (2015) · Zbl 1316.91001 · doi:10.1093/acprof:oso/9780199734023.001.0001
[10] Chawla, S., Fu, H., Karlin, A.: Approximate revenue maximization in interdependent value settings. In: EC 2014, pp. 277–294 (2014) · doi:10.1145/2600057.2602858
[11] Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: STOC 2010 (2010) · Zbl 1293.91078 · doi:10.1145/1806689.1806733
[12] Clarke, E.H.: Multipart pricing of public goods. Public Choice 11(1), 17–33 (1971) · doi:10.1007/BF01726210
[13] Cremer, J., McLean, R.P.: Full extraction of the surplus in bayesian and dominant strategy auctions. Econometrica 56(6), 1247–1257 (1988) · Zbl 0661.90104 · doi:10.2307/1913096
[14] Devanur, N.R., Morgenstern, J., Syrgkanis, V., Weinberg, S.M.: Simple auctions with simple strategies. In: EC 2015, pp. 305–322 (2015) · doi:10.1145/2764468.2764484
[15] Dobzinski, S., Fu, H., Kleinberg, R.D.: Optimal auctions with correlated bidders are easy. In: STOC 2011 (2011) · Zbl 1288.91102 · doi:10.1145/1993636.1993655
[16] Feldman, M., Gravin, N., Lucier, B.: Combinatorial auctions via posted prices. In: SODA 2015 (2015) · Zbl 1372.91049 · doi:10.1137/1.9781611973730.10
[17] Groves, T.: Incentives in teams. Econometrica 41, 617–631 (1973) · Zbl 0311.90002 · doi:10.2307/1914085
[18] Gupta, A., Nagarajan, V.: A stochastic probing problem with applications. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 205–216. Springer, Heidelberg (2013) · Zbl 1321.92032 · doi:10.1007/978-3-642-40708-6
[19] Hart, S., Nisan, N.: Approximate revenue maximization with multiple items. In: EC 2012 (2012) · Zbl 1414.91151 · doi:10.1145/2229012.2229061
[20] Hartline, J.D., Roughgarden, T.: Simple versus optimal mechanisms. SIGecom Exch. 8(1), 5:1–5:3 (2009) · doi:10.1145/1598780.1598785
[21] Kleinberg, R., Leighton, T.: The value of knowing a demand curve: bounds on regret for online posted-price auctions. In: FOCS 2003 (2003)
[22] Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities. In: STOC 2012 (2012) · Zbl 1286.60037 · doi:10.1145/2213977.2213991
[23] Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981) · Zbl 0496.90099 · doi:10.1287/moor.6.1.58
[24] Ronen, A.: On approximating optimal auctions. In: EC 2001 (2001) · doi:10.1145/501158.501160
[25] Roughgarden, T., Talgam-Cohen, I.: Optimal and near-optimal mechanism design with interdependent values. In: EC 2013 (2013) · doi:10.1145/2492002.2482606
[26] Rubinstein, A., Weinberg, S.M.: Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. In: EC 2015, pp. 377–394 (2015) · doi:10.1145/2764468.2764510
[27] Sandholm, T.W., Gilpin, A.: Sequences of take-it-or-leave-it offers: near-optimal auctions without full valuation revelation. In: Faratin, P., Parkes, D.C., Rodríguez-Aguilar, J.-A., Walsh, W.E. (eds.) AMEC 2003. LNCS (LNAI), vol. 3048, pp. 73–91. Springer, Heidelberg (2004)
[28] Segal, I.: Optimal pricing mechanisms with unknown demand. Am. Econ. Rev. 93(3), 509–529 (2003) · doi:10.1257/000282803322156963
[29] Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Financ. 16(1), 8–37 (1961) · doi:10.1111/j.1540-6261.1961.tb02789.x
[30] Yan, Q.: Mechanism design via correlation gap. In: SODA 2011 (2011) · Zbl 1377.91108 · doi:10.1137/1.9781611973082.56
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.