Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium

References

• Araman VF, Caldentey R (2011) Revenue management with incomplete demand information. Cochran JJ, Cox LA Jr, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Ashlagi I, Monderer D, Tennenholtz M (2012) Robust learning equilibrium. Working paper, Technion–Israel Institute of Technology, Haifa, Israel.Google Scholar
• Badanidiyuru A, Kleinberg R, Slivkins A (2013) Bandits with knapsacks. Proc. 2013 IEEE 54th Annual Sympos. Foundations Comput. Sci. FOCS ’13 (IEEE Computer Society, Washington, DC), 207–216.Crossref, Google Scholar
• Badanidiyuru A, Langford J, Slivkins A (2014) Resourceful contextual bandits. Balcan MF, Feldman V, Szepesvri C, eds. Proc. Machine Learn. Res. 35:1109–1134.Google Scholar
• Balseiro S, Kim A, Mahdian M, Mirrokni V (2017) Budget management strategies in repeated auctions. Proc. 26th Internat. Conf. World Wide Web (ACM, New York), 15–23.Crossref, Google Scholar
• Balseiro SR, Besbes O, Weintraub GY (2015) Repeated auctions with budgets in ad exchanges: Approximations and design. Management Sci. 61(4):864–884.Link, Google Scholar
• Balseiro SR, Feldman J, Mirrokni V, Muthukrishnan S (2014) Yield optimization of display advertising with ad exchange. Management Sci. 60(12):2886–2907.Link, Google Scholar
• Beck A, Teboulle M (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3):167–175.Crossref, Google Scholar
• Benveniste A, Priouret P, Metivier M (1990) Adaptive Algorithms and Stochastic Approximations (Springer, New York).Crossref, Google Scholar
• Besbes O, Gur Y, Zeevi A (2015) Non-stationary stochastic optimization. Oper. Res. 63(5):1227–1244.Link, Google Scholar
• Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Proc. 16th Internat. Conf. World Wide Web. WWW ’07 (ACM, New York), 531–540.Crossref, Google Scholar
• Borodin A, El-Yaniv R (1998) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Brafman RI, Tennenholtz M (2004) Efficient learning equilibrium. Artificial Intelligence 159(1–2):27–47.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
• Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Charles DX, Chakrabarty D, Chickering M, Devanur NR, Wang L (2013) Budget smoothing for internet ad auctions: A game theoretic approach. ACM Conf. Electronic Commerce EC ’13 (ACM, New York), 163–180.Crossref, Google Scholar
• Conitzer V, Kroer C, Sodomka E, Stier-Moses N (2018) Multiplicative pacing equilibria in auction markets. Proc. 14th Conf. Workshop Internet Network Econom. (WINE '18) (Springer-Verlag, Cham, Switzerland).Google Scholar
• Duchi J, Hazan E, Singer Y (2011) Adaptive subgradient methods for online learning and stochastic optimization. J. Machine Learn. Res. 12(July):2121–2159.Google Scholar
• eMarketer (2016a) More than two-thirds of us digital display ad spending is programmatic. Accessed July 10, 2017, https://www.emarketer.com/Article/More-Than-Two-Thirds-of-US-Digital-Di splay-Ad-Spending-Programmatic/1013789.Google Scholar
• eMarketer (2016b) Us digital ad spending to surpass tv this year. Accessed July 10, 2017, https://www.emarketer.com/Article/US-Digital-Ad-Spending-Surpass-TV-thi s-Year/1014469.Google Scholar
• Fudenberg D, Levine D (1998) The Theory of Learning in Games (MIT Press, Cambridge, MA).Google Scholar
• Han Z, Zheng R, Poor HV (2011) Repeated auctions with Bayesian nonparametric learning for spectrum access in cognitive radio networks. IEEE Trans. Wireless Comm. 10(3):890–900.Crossref, Google Scholar
• Hannan J (1957) Approximation to Bayes risk in repeated plays. Dresher M, Tucker AW, Wolfe P, eds. Contributions to the Theory of Games, vol. 3 (Princeton University Press, Princeton, NJ), 97–140.Google Scholar
• Hart S, Mas-Colell A (2000) A simple adaptive procedure leading to correlated equilibria. Econometrica 68(5):1127–1150.Crossref, Google Scholar
• Hart S, Mas-Colell A (2013) Simple Adaptive Strategies, vol. 4 (World Scientific Publishing Company, Singapore).Crossref, Google Scholar
• Hazan E, Agarwal A, Kale S (2007) Logarithmic regret algorithms for online convex optimization. Machine Learn. 69(2/3):169–192.Crossref, Google Scholar
• Hon-Snir S, Monderer D, Sela A (1998) A learning approach to auctions. J. Econom. Theory 82(1):65–88.Crossref, Google Scholar
• Iyer K, Johari R, Sundararajan M (2014) Mean field equilibria of dynamic auctions with learning. Management Sci. 60(12):2949–2970.Link, Google Scholar
• Jiang C, Beck CL, Srikant R (2014) Bidding with limited statistical knowledge in online auctions. SIGMETRICS Performance Evaluation Rev. 41(4):38–41.Crossref, Google Scholar
• Karande C, Mehta A, Srikant R (2013) Optimizing budget constrained spend in search advertising. Proc. 6th ACM Internat. Conf. Web Search Data Mining (ACM, New York), 697–706.Crossref, Google Scholar
• Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Proc. 16th Annual ACM-SIAM Symp. Discrete Algorithms SODA ’05 (Society for Industrial and Applied Mathematics, Philadelphia), 630–631.Google Scholar
• Kushner HJ, Yin GG (2003) Stochastic Approximation and Recursive Algorithms and Applications (Springer, New York).Google Scholar
• Lai T (2003) Stochastic approximation. Ann. Statist. 31(2):391–406.Crossref, Google Scholar
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, New York).Google Scholar
• Mirrokni VS, Gharan SO, Zadimoghaddam M (2012) Simultaneous approximations for adversarial and stochastic online budgeted allocation. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms SODA ’12 (Society for Industrial and Applied Mathematics, Philadelphia), 1690–1701.Crossref, Google Scholar
• Nedic A, Ozdaglar A (2009) Distributed subgradient methods for multi-agent optimization. IEEE Trans. Automatic Control 54(1):48–61.Crossref, Google Scholar
• Nemirovski A, Yudin D (1983) Problem Complexity and Method Efficiency in Optimization (John Wiley, New York).Google Scholar
• Nemirovski A, Juditsky A, Lan G, Shapiro A (2009) Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4):1574–1609.Crossref, Google Scholar
• Rosen JB (1965) Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33(3):520–534.Crossref, Google Scholar
• Sani A, Neu G, Lazaric A (2014) Exploiting easy data in online optimization. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Proc. Neural Inform. Processing Systems 2014 Conf. (Curran Associates, Inc., Red Hook, NY), 810–818.Google Scholar
• Seldin Y, Slivkins A (2014) One practical algorithm for both stochastic and adversarial bandits. Proc. Machine Learn. Res. 32(2): 1287–1295.Google Scholar
• Shalev-Shwartz S (2012) Online learning and online convex optimization. Foundations Trends Machine Learn. 4(2):107–194.Crossref, Google Scholar
• Talluri K, van Ryzin G (1998) An analysis of bid-price controls for network revenue management. Management Sci. 44(11):1577–1593.Link, Google Scholar
• Talluri KT, van Ryzin GJ (2004) The Theory and Practice of Revenue Management, International Series in Operations Research and Management Science, vol. 68 (Springer, New York).Crossref, Google Scholar
• Tsybakov AB (2008) Introduction to Nonparametric Estimation (Springer, New York).Google Scholar
• Weed J, Perchet V, Rigollet P (2016) Online learning in repeated auctions. Proc. Machine Learn. Res. 49:1562–1583.Google Scholar
• Yao ACC (1977) Probabilistic computations: Toward a unified measure of complexity. Proc. Foundations Comput. Sci. (FOCS) 18th IEEE Sympos. (Institute of Electrical and Electronics Engineers, Washington, DC), 222–227.Crossref, Google Scholar
• Zhou Y, Chakrabarty D, Lukose R (2008) Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems (Springer, Berlin), 566–576.Crossref, Google Scholar
• Zinkevich M (2003) Online convex programming and generalized infinitesimal gradient ascent. Fawcett T, Mishra N, eds. Proc. 20th Internat. Conf. Machine Learn. (AAAI Press, Menlo Park, CA), 928–936.Google Scholar