Top

Published in:

2018 | OriginalPaper | Chapter

Prophet Inequalities vs. Approximating Optimum Online

Authors : Rad Niazadeh, Amin Saberi, Ali Shameli

Published in: Web and Internet Economics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We revisit the classic prophet inequality problem, where the goal is selling a single item to an arriving sequence of buyers whose values are drawn from independent distributions, to maximize the expected allocated value. The usual benchmark is the expected value that an omniscient prophet who knows the future can attain. We diverge from this framework and compare the performance of the best single pricing mechanism with the best optimum online mechanism.

Somewhat surprisingly, we show that the original tight prophet inequality bounds comparing the single-pricing with the optimum offline are tight even when we use the optimum online as a benchmark, both for the identical and non-identical distributions. Moreover, we incorporate linear programming to characterize this benchmark, and show how this approach leads to a modular way of designing prophet inequalities, hence reconstructing the results of [31] and [13] with somewhat simpler proofs.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Robust and Approximately Stable Marriages Under Partial Information

next chapter Optimal Mechanism Design with Risk-Loving Agents

Although the focus of this paper is not on truthful mechanism design, all of our mechanisms are pricing and hence truthful.

We drop lower order terms by using \(\approx \).

In the case of non-atomic distributions, this LP is essentially a continuous program with uncountably many variables. In the case of discrete distributions, the LP has finitely many variables.

Note that we assume the true \(\pi \) is the unitary ordering, but that is without loss of generality.

Abolhassani, M., Ehsani, S., Esfandiari, H., HajiAghayi, M., Kleinberg, R., Lucier, B.: Beating \(1-1\)/e for ordered prophets. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 61–71. ACM (2017)

Alaei, S.: Bayesian combinatorial auctions: expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2), 930–972 (2014)MathSciNetCrossRef

Alaei, S., Hartline, J., Niazadeh, R., Pountourakis, E., Yuan, Y.: Optimal auctions vs. anonymous pricing. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1446–1463. IEEE (2015)

Anari, N., Niazadeh, R., Saberi, A., Shameli, A.: Nearly optimal pricing algorithms for production constrained and laminar bayesian selection. arXiv preprint arXiv:1807.05477 (2018)

Azar, P.D., Kleinberg, R., Weinberg, S.M.: Prophet inequalities with limited information. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1358–1377. Society for Industrial and Applied Mathematics (2014)

Azar, Y., Chiplunkar, A., Kaplan, H.: Prophet secretary: Surpassing the \(1-1\)/e barrier. In: Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 303–318. ACM (2018)

Babaioff, M., Immorlica, N., Lucier, B., Weinberg, S.M.: A simple and approximately optimal mechanism for an additive buyer. ACM SIGecom Exch. 13(2), 31–35 (2015)CrossRef

Beyhaghi, H., Golrezaei, N., Leme, R.P., Pal, M., Siva, B.: Improved approximations for free-order prophets and second-price auctions. arXiv preprint arXiv:1807.03435 (2018)

Cai, Y., Daskalakis, C., Weinberg, S.M.: Optimal multi-dimensional mechanism design: reducing revenue to welfare maximization. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 130–139. IEEE (2012)

10.

Cai, Y., Devanur, N.R., Weinberg, S.M.: A duality based unified approach to Bayesian mechanism design. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pp. 926–939. ACM (2016)CrossRef

11.

Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 311–320. ACM (2010)

12.

Chawla, S., Miller, J.B.: Mechanism design for subadditive agents via an ex-ante relaxation. In: Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 579–596. ACM (2016)

13.

Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mechanisms for a random stream of customers. In: Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 169–186. ACM (2017)

14.

Correa, J., Saona, R., Ziliotto, B.: Prophet secretary through blind strategies. arXiv preprint arXiv:1807.07483 (2018)

15.

Düetting, P., Feldman, M., Kesselheim, T., Lucier, B.: Prophet inequalities made easy: stochastic optimization by pricing non-stochastic inputs. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 540–551. IEEE (2017)

16.

Dütting, P., Fischer, F., Klimm, M.: Revenue gaps for discriminatory and anonymous sequential posted pricing. arXiv preprint arXiv:1607.07105 (2016)

17.

Ehsani, S., Hajiaghayi, M., Kesselheim, T., Singla, S.: Prophet secretary for combinatorial auctions and matroids. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 700–714. SIAM (2018)CrossRef

18.

Esfandiari, H., Hajiaghayi, M., Liaghat, V., Monemizadeh, M.: Prophet secretary. SIAM J. Discrete Math. 31(3), 1685–1701 (2017)MathSciNetCrossRef

19.

Feldman, M., Fu, H., Gravin, N., Lucier, B.: Simultaneous auctions are (almost) efficient. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 201–210. ACM (2013)

20.

Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1014–1033. Society for Industrial and Applied Mathematics (2016)

21.

Göbel, O., Hoefer, M., Kesselheim, T., Schleiden, T., Vöcking, B.: Online independent set beyond the worst-case: secretaries, prophets, and periods. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 508–519. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43951-7_43CrossRefMATH

22.

Hajiaghayi, M.T., Kleinberg, R., Sandholm, T.: Automated online mechanism design and prophet inequalities. AAAI. vol. 7, pp. 58–65 (2007)

23.

Hartline, J.D.: Approximation in mechanism design. Am. Econ. Rev. 102(3), 330–336 (2012)CrossRef

24.

Hartline, J.D., Roughgarden, T.: Simple versus optimal mechanisms. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 225–234. ACM (2009)

25.

Hill, T.P., Kertz, R.P.: Comparisons of stop rule and supremum expectations of IID random variables. Ann. Probab. 10(2), 336–345 (1982)MathSciNetCrossRef

26.

Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 123–136. ACM (2012)

27.

Krengel, U., Sucheston, L.: On semiamarts, amarts, and processes with finite value. Probab. Banach Spaces 4, 197–266 (1978)MathSciNet

28.

Lee, E., Singla, S.: Optimal online contention resolution schemes via ex-ante prophet inequalities. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 112. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)

29.

Lucier, B.: An economic view of prophet inequalities. ACM SIGecom Exch. 16(1), 24–47 (2017)CrossRef

30.

Rubinstein, A.: Beyond matroids: secretary problem and prophet inequality with general constraints. In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, pp. 324–332. ACM (2016)

31.

Samuel-Cahn, E.: Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4), 1213–1216 (1984)MathSciNetCrossRef

32.

Yan, Q.: Mechanism design via correlation gap. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 710–719. Society for Industrial and Applied Mathematics (2011)

Title: Prophet Inequalities vs. Approximating Optimum Online
Authors: Rad Niazadeh
Amin Saberi
Ali Shameli
Publisher: Springer International Publishing
Book: Web and Internet Economics
Print ISBN: 978-3-030-04611-8

Electronic ISBN: 978-3-030-04612-5

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-04612-5_24

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner