Multiplicative Pacing Equilibria in Auction Markets

References

• Abrams Z, Mendelevitch O, Tomlin J (2007) Optimal delivery of sponsored search advertisements subject to budget constraints. Proc. 8th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 272–278. https://dl.acm.org/doi/proceedings/10.1145/1250910.Google Scholar
• Agarwal D, Ghosh S, Wei K, You S (2014) Budget pacing for targeted online advertisements at LinkedIn. Proc. 20th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining. https://dl.acm.org/doi/proceedings/10.1145/2623330.Google Scholar
• Amin K, Kearns M, Key P, Schwaighofer A (2012) Budget optimization for sponsored search: Censored learning in MDPs. de Freitas N, Murphy K, eds. Proc. 28th Conf. Uncertainty Artificial Intelligence (AUAI Press, Corvallis, Oregon),54–63. http://www.auai.org/uai2012/proceedings.pdf.Google Scholar
• Asadpour A, Bateni MH, Bhawalkar K, Mirrokni V (2019) Concise bid optimization strategies with multiple budget constraints. Management Sci. 65(12):5785–5812.Link, Google Scholar
• Ashlagi I, Braverman M, Hassidim A, Lavi R, Tennenholtz M (2010) Position auctions with budgets: Existence and uniqueness. B. E. J. Theoret. Econom. 10(1). doi: 10.2202/1935-1704.1648.Google Scholar
• Azevedo EM, Budish E (2019) Strategy-proofness in the large. Rev. Econom. Stud. 86(1):81–116.Google Scholar
• Balseiro SR, Gur Y (2019) Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Sci. 65(9):3952–3968.Link, 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 S, Kim A, Mahdian M, Mirrokni V (2021) Budget-management strategies in repeated auctions. Oper. Res. ePub ahead of print March 8, https://doi.org/10.1287/opre.2020.2073.Link, 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 (Association for Computing Machinery, New York), 1213–1221. https://dl.acm.org/doi/proceedings/10.1145/2339530.Google Scholar
• Bhattacharya S, Conitzer V, Munagala K, Xia L (2010) Incentive compatible budget elicitation in multi-unit auctions. Charikar M, ed. Proc. 21st Annual ACM-SIAM Symp Discrete Algorithms. 19. https://doi.org/10.1137/1.9781611973075.47.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 (Association for Computing Machinery, New York), 531–540. https://dl.acm.org/doi/proceedings/10.1145/1242572.Google Scholar
• Charles D, Chakrabarty D, Chickering M, Devanur NR, Wang L (2013) Budget smoothing for internet ad auctions: A game theoretic approach. Proc. 14th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 163–180. https://doi.org/10.1145/2482540.2482583.Google Scholar
• Ciocan DF, Iyer K (2021) Tractable equilibria in sponsored search with endogenous budgets. Oper. Res. 69(1):227–244.Link, Google Scholar
• Cole R, Devanur NR, Gkatzelis V, Jain K, Mai T, Vazirani VV, Yazdanbod S (2017) Convex program duality, Fisher markets, and Nash social welfare. Proc. 2017 ACM Conf. Econom. Comput. (EC ′17) (Association for Computing Machinery, New York), 459–460. https://doi.org/10.1145/3033274.3085109.Crossref, Google Scholar
• Conitzer V, Kroer C, Panigrahi D, Schrijvers O, Sodomka E, Stier-Moses NE, Wilkens C (2022) Pacing equilibrium in first-price auction markets. Management Sci. Forthcoming.Google Scholar
• Debreu G (1952) A social equilibrium existence theorem. Proc. Natl. Acad. Sci. USA 38(10). https://doi.org/10.1073/pnas.38.10.886.Crossref, Google Scholar
• Devanur NR, Hayes TP (2009) The AdWords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 71–78.Google Scholar
• Devanur NR, Sivan B, Azar Y (2012) Asymptotically optimal algorithm for stochastic AdWords. Proc. 13th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 388–404. https://doi.org/10.1145/2229012.2229043.Google Scholar
• Devanur NR, Jain K, Sivan B, Wilkens CA (2011) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Proc. 12th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 29–38.Google Scholar
• Dobzinski S, Lavi R, Nisan N (2012) Multi-unit auctions with budget limits. Games Econom. Behav. 74(2):486–503.Crossref, Google Scholar
• Eisenberg E, Gale D (1959) Consensus of subjective probabilities: The pari-mutuel method. Ann. Math. Statist. 30(1):165–168.Crossref, Google Scholar
• Fan K (1952) Fixed-point and minimax theorems in locally convex topological linear spaces. Proc. Natl. Acad. Sci. USA 38(2):121–126.Crossref, Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. Proc. 2009 50th Annual IEEE Symp. Foundations Comput. Sci. (IEEE Computer Society), 117–126. https://doi.ieeecomputersociety.org/10.1109/FOCS.2009.72.Google Scholar
• Feldman J, Muthukrishnan S, Pal M, Stein C (2007) Budget optimization in search-based advertising auctions. Proc. 8th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 40–49. https://doi.org/10.1145/1250910.1250917.Google Scholar
• Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C (2010) Online stochastic packing applied to display ad allocation. de Berg M, Meyer U, eds. Eur. Symp. Algorithms (Springer, Berlin), 182–194. https://link.springer.com/chapter/10.1007/978-3-642-15775-2_16.Google Scholar
• FICO (2016) Xpress optimization suite. Accessed May 2021, http://www.fico.com/en/products/fico-xpress-optimization-suite.Google Scholar
• Garg R, Kapoor S (2006) Auction algorithms for market equilibrium. Math. Oper. Res. 31(4):714–729.Link, Google Scholar
• Garg R, Kapoor S, Vazirani V (2004) An auction-based market equilibrium algorithm for the separable gross substitutability case. Jansen K, Khanna S, Rolim JDP, Ron D, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Springer, Berlin), 128–138. https://link.springer.com/chapter/10.1007%2F978-3-540-27821-4_12.Crossref, Google Scholar
• Glicksberg IL (1952) A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points. Proc. Amer. Math. Soc. (American Mathematical Society), 3(1):170–174. https://www.jstor.org/stable/2032478.Google Scholar
• Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to AdWords. Proc. 19th Annual ACM-SIAM Symp. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 982–991. https://dl.acm.org/doi/10.5555/1347082.1347189.Google Scholar
• Goel G, Mirrokni V, Leme RP (2015) Polyhedral clinching auctions and the AdWords polytope. J. ACM 62(3):1–27.Crossref, Google Scholar
• Goel G, Mirrokni V, Leme RP (2020) Clinching auctions with online supply. Games Econom. Behav. 123:342–358.Crossref, Google Scholar
• Gummadi R, Key P, Proutiere A (2012) Optimal bidding strategies and equilibria in dynamic auctions with budget constraints. 8th Ad Auctions Workshop, Valencia Spain. https://sites.google.com/site/adauctions2012/accepted-papers.Google Scholar
• Kapoor S, Mehta A, Vazirani V (2007) An auction-based market equilibrium algorithm for a production model. Theoret. Comput. Sci. 378(2):153–164.Crossref, Google Scholar
• Klemperer P (2010) The product-mix auction: A new auction design for differentiated goods. J. Eur. Econom. Assoc. 8(2–3):526–536.Crossref, Google Scholar
• Kroer C, Peysakhovich A (2019) Scalable fair division for ‘at most one’ preferences. Preprint, submitted September 24, 2019, https://arxiv.org/abs/1909.10925.Google Scholar
• Kroer C, Peysakhovich A, Sodomka E, Stier-Moses NE (2022) Computing large market equilibria using abstractions. Oper. Res. Forthcoming.Link, Google Scholar
• Mahdian M, Nazerzadeh H, Saberi A (2012) Online optimization with uncertain information. ACM Trans. Algorithms 8(1):1–29.Crossref, Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching. J. ACM 54(5):22.Crossref, Google Scholar
• Mirrokni VS, Gharan SO, Zadimoghaddam M (2012) Simultaneous approximations for adversarial and stochastic online budgeted allocation. Rabani Y, ed. Proc. 23rd Annual ACM-SIAM Symp. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1690–1701. https://epubs.siam.org/doi/book/10.1137/1.9781611973099.Google Scholar
• Nesterov Y, Shikhman V (2018) Computation of Fisher–Gale equilibrium by auction. J. Oper. Res. Soc. China 6(3):349–389.Crossref, Google Scholar
• Ozdaglar A (2010) Game theory with engineering applications. Doctoral course. Lecture 5. Accessed May 2021, http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-254-game-theory-with-engineering-applications-spring-2010/lecture-notes/MIT6_254S10_lec05.pdf.Google Scholar
• Xu J, Lee K, Li W, Qi H, Lu Q (2015) Smart pacing for effective online ad campaign optimization. Proc. 21st ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 2217–2226. https://doi.org/10.1145/2783258.2788615.Google Scholar
• Zhang W, Yuan S, Wang J (2014) Optimal real-time bidding for display advertising. Proc. 20th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 1077–1086. https://dl.acm.org/doi/10.1145/2623330.2623633.Google Scholar
• Zhang W, Zhang Y, Gao B, Yu Y, Yuan X, Liu T-Y (2012) Joint optimization of bid and budget allocation in sponsored search. Proc. 18th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining. (Association for Computing Machinery, New York), 1177–1185.Google Scholar
• Zhou Y, Chakrabarty D, Lukose R (2008) Budget constrained bidding in keyword auctions and online knapsack problems. Proc. 17th Internat. Conf. World Wide Web (Association for Computing Machinery, New York), 1243–1244. https://dl.acm.org/doi/10.1145/1367497.1367747.Google Scholar