Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms

References

• Agrawal S, Ding Y, Saberi A, Ye Y (2010) Correlation robust stochastic optimization. Proc. Twenty-First Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1087–1096.Google Scholar
• Agrawal S, Ding Y, Saberi A, Ye Y (2012) Price of correlations in stochastic optimization. Oper. Res. 60(1):150–162.Link, Google Scholar
• Allouah A, Besbes O (2018) Prior-independent optimal auctions. Proc. 2018 ACM Conf. Econom. Comput. (ACM, New York), 503.Google Scholar
• Archer A, Tardos É (2001) Truthful mechanisms for one-parameter agents. Proc. 42nd IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 482–491.Google Scholar
• Athey S, Ellison G (2011) Position auctions with consumer search. Quart. J. Econom. 126(3):1213–1270.Crossref, Google Scholar
• Azar Y, Chiplunkar A, Kaplan H (2018) Prophet secretary: Surpassing the 1-1/e barrier. Proc. 2018 ACM Conf. Econom. Comput. (ACM, New York), 303–318.Google Scholar
• Balseiro S, Golrezaei N, Mahdian M, Mirrokni V, Schneider J (2019) Contextual bandits with cross-learning. Adv. Neural Inform. Processing Systems 32:9676–9685.Google Scholar
• Bhalgat A, Feldman J, Mirrokni V (2012) Online allocation of display ads with smooth delivery. Proc. 18th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1213–1221.Google Scholar
• Calinescu G, Chekuri C, Pál M, Vondrák J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6):1740–1766.Crossref, Google Scholar
• Celis LE, Lewis G, Mobius M, Nazerzadeh H (2014) Buy-it-now or take-a-chance: Price discrimination through randomized auctions. Management Sci. 60(12):2927–2948.Link, Google Scholar
• Chakraborty T, Even-Dar E, Guha S, Mansour Y, Muthukrishnan S (2010) Approximation schemes for sequential posted pricing in multi-unit auctions. Saberi A, ed. Internet and Network Economics: 6th Internat. Workshop, WINE 2010, Lecture Notes in Computer Science, vol. 6484 (Springer-Verlag, Berlin, Heidelberg), 158–169.Google Scholar
• Chawla S, Sivan B (2014) Bayesian algorithmic mechanism design. ACM SIGecom Exchanges 13(1):5–49.Crossref, Google Scholar
• Chawla S, Hartline JD, Kleinberg RD (2007) Algorithmic pricing via virtual valuations. Proc. 8th ACM Conf. Electronic Commerce (ACM, New York), 243–251.Google Scholar
• Chawla S, Malec DL, Sivan B (2010a) The power of randomness in Bayesian optimal mechanism design. Proc. 11th ACM Conf. Electronic Commerce (EC-2010) (ACM, New York), 149–158.Google Scholar
• Chawla S, Hartline JD, Malec DL, Sivan B (2010b) Multi-parameter mechanism design and sequential posted pricing. Proc. Forty-Second ACM Sympos. Theory Comput. (ACM, New York), 311–320.Google Scholar
• Correa JR, Saona R, Ziliotto B (2019b) Prophet secretary through blind strategies. Proc. 13th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA 2019 (Society for Industrial and Applied Mathematics, Philadelphia), 1946–1961.Google Scholar
• Correa J, Foncea P, Pizarro D, Verdugo V (2019a) From pricing to prophets, and back! Oper. Res. Lett. 47(1):25–29.Crossref, Google Scholar
• Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Proc. 2017 ACM Conf. Econom. Comput. (ACM, New York), 169–186.Google Scholar
• Derakhshan M, Golrezaei N, Paes Leme R (2019) Lp-based approximation for personalized reserve prices. Proc. 2019 ACM Conf. Econom. Comput. (ACM, New York), 589–589.Google Scholar
• Dhangwatnotai P, Roughgarden T, Yan Q (2015) Revenue maximization with a single sample. Games Econom. Behav. 91:318–333.Crossref, Google Scholar
• Edelman B, Ostrovsky M, Schwarz M (2007) Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. Amer. Econom. Rev. 97(1):242–259.Crossref, Google Scholar
• Feldman J, Muthukrishnan S, Nikolova E, Pál M (2008) A truthful mechanism for offline ad slot scheduling. Internat. Sympos. Algorithmic Game Theory (Springer, Berlin-Heidelberg), 182–193.Google Scholar
• Golrezaei N, Lin M, Mirrokni V, Nazerzadeh H (2017) Boosted second-price auctions for heterogeneous bidders. Preprint, submitted August 12, https://dx.doi.org/10.2139/ssrn.3016465.Google Scholar
• Gonzalez T, Sahni S (1978) Preemptive scheduling of uniform processor systems. J. ACM 25(1):92–101.Crossref, Google Scholar
• Hajiaghayi MT, Kleinberg RD, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. 22nd AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 58–65.Google Scholar
• Hammond PJ (1979) Straightforward individual incentive compatibility in large economies. Rev. Econom. Stud. 46(2):263–282.Crossref, Google Scholar
• Hartline JD, Roughgarden T (2009) Simple vs. optimal mechanisms. Proc. 10th ACM Conf. Electronic Commerce (EC-2009) (ACM, New York), 225–234.Google Scholar
• Hill TP, Kertz RP (1982) Comparisons of stop rules and supremum expectations of i.i.d. random variables. Ann. Probab. 10:336–345.Crossref, Google Scholar
• Horvath EC, Lam S, Sethi R (1977) A level algorithm for preemptive scheduling. J. ACM 24(1):32–43.Crossref, Google Scholar
• Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. (N.S.) 83(4):745–747.Crossref, Google Scholar
• Krengel U, Sucheston L (1978) On semiamarts, amarts and processes with finite values. Adv. Probab. 4:197–266.Google Scholar
• Lucier B, Paes Leme R, Tardos E (2012) On revenue in the generalized second price auction. Proc. 21st Internat. Conf. World Wide Web (ACM, New York), 361–370.Google Scholar
• Ma W, Sivan B (2019) Separation between second price auctions with personalized reserves and the revenue optimal auction. Preprint, submitted June 27, https://arxiv.org/abs/1906.11657.Google Scholar
• Myerson RB (1981) Optimal auction design. Math. Oper. Res. 6(1):58–73.Link, Google Scholar
• Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic Game Theory (Cambridge University Press, New York).Crossref, Google Scholar
• Ostrovsky M, Schwarz M (2011) Reserve prices in internet advertising auctions: A field experiment. Proc. 12th ACM Conf. Electronic Commerce (ACM, New York), 59–60.Google Scholar
• Paes Leme R, Pál M, Vassilvitskii S (2016) A field guide to personalized reserve prices. Proc. 25th Internat. Conf. World Wide Web (International World Wide Web Conferences Steering Committee, Geneva), 1093–1102.Google Scholar
• Ronen A (2001) On approximating optimal auctions. Proc. 3rd ACM Conf. Electronic Commerce (ACM, New York), 11–17.Google Scholar
• Roughgarden T, Wang JR (2016) Minimizing regret with multiple reserves. Proc. 2016 ACM Conf. Econom. Comput. (ACM, New York), 601–616.Google Scholar
• Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Crossref, Google Scholar
• Varian HR (2007) Position auctions. Internat. J. Indust. Organ. 25(6):1163–1178.Crossref, Google Scholar
• Vondrák J (2007) Submodularity in combinatorial optimization. PhD thesis, Charles University, Prague.Google Scholar
• Yan Q (2011) Mechanism design via correlation gap. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 710–719.Google Scholar