Learning in Stackelberg Games with Non-myopic Agents

References

• Abernethy JD, Cummings R, Kumar B, Taggart S, Morgenstern JH (2019) Learning auctions with robust incentive guarantees. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, Garnett R, eds. Adv. Neural Inform. Processing Systems (NeurIPS) (Curran Associates, Inc., Red Hook, NY), 11587–11597.Google Scholar
• Abreu D (1988) On the theory of infinitely repeated games with discounting. Econometrica 56(2):383–396.Crossref, Google Scholar
• Ahn H-S, Gümüş M, Kaminsky P (2007) Pricing and manufacturing decisions when demand is a function of prices in multiple periods. Oper. Res. 55(6):1039–1057.Link, Google Scholar
• Ainslie G (1992) Picoeconomics: The Strategic Interaction of Successive Motivational States Within the Person (Cambridge University Press, Cambridge, UK).Google Scholar
• Amin K, Rostamizadeh A, Syed U (2013) Learning prices for repeated auctions with strategic buyers. Burges CJC, Bottou L, Ghahramani Z, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems (NIPS) (Curran Associates, Inc., Red Hook, NY), 1169–1177.Google Scholar
• Ananthakrishnan N, Haghtalab N, Podimata C, Yang K (2024) Is knowledge power? On the (im)possibility of learning from strategic interaction. Globersons A, Mackey L, Belgrave D, Fan A, Paquet U, Tomczak JM, Zhang C, eds. Adv. Neural Inform. Processing Systems (NeurIPS) (PMLR, New York), 23852–23880.Google Scholar
• Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time analysis of the multiarmed bandit problem. Machine Learn. 47(2–3):235–256.Crossref, Google Scholar
• Badanidiyuru A, Kleinberg R, Slivkins A (2018) Bandits with knapsacks. J. ACM 65(3):13.Crossref, Google Scholar
• Balcan M-F, Blum A, Haghtalab N, Procaccia AD (2015) Commitment without regrets: Online learning in Stackelberg security games. Roughgarden T, Feldman M, Schwarz M, eds. ACM Conf. Econom. Comput. (EC) (ACM, New York), 61–78.Google Scholar
• Besbes O, Zeevi A (2009) Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Oper. Res. 57(6):1407–1420.Link, Google Scholar
• Blackwell D (1965) Discounted dynamic programming. Ann. Math. Statist. 36(1):226–235.Crossref, Google Scholar
• Blum A, Haghtalab N, Procaccia AD (2014) Learning optimal commitment to overcome insecurity. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems (NIPS) (Curran Associates, Inc., Red Hook, NY), 1826–1834.Google Scholar
• Blum A, Haghtalab N, Procaccia AD (2017) Learning to play Stackelberg security games. Abbas AE, Tambe M, von Winterfeldt D, eds. Improving Homeland Security Decisions (Cambridge University Press, Cambridge, UK), 604–626.Crossref, Google Scholar
• Chen X, Wang Y (2023) Robust dynamic pricing with demand learning in the presence of outlier customers. Oper. Res. 71(4):1362–1386.Link, Google Scholar
• Chen X, Krishnamurthy A, Wang Y (2024) Robust dynamic assortment optimization in the presence of outlier customers. Oper. Res. 72(3):999–1015.Link, Google Scholar
• Chen Y, Liu Y, Podimata C (2020) Learning strategy-aware linear classifiers. Larochelle H, Ranzato M, Hadsell R, Balcan M-F, Lin H-T, eds. Adv. Neural Inform. Processing Systems (NeurIPS) (Curran Associates, Inc., Red Hook, NY), 15265–15276.Google Scholar
• Collina N, Arunachaleswaran ER, Kearns M (2023) Efficient Stackelberg strategies for finitely repeated games. Agmon N, An B, Ricci A, Yeoh W, eds. Internat. Conf. Autonomous Agents Multiagent Systems (AAMAS) (IFAAMAS), 643–651.Google Scholar
• Conitzer V, Sandholm T (2006) Computing the optimal strategy to commit to. Feigenbaum J, Chuang JC-I, Pennock DM, eds. ACM Conf. Electronic Commerce (EC) (ACM, New York), 82–90.Google Scholar
• Dong J, Roth A, Schutzman Z, Waggoner B, Wu ZS (2018) Strategic classification from revealed preferences. Tardos É, Elkind E, Vohra R, eds. ACM Conf. Econom. Comput. (EC) (ACM, New York), 55–70.Google Scholar
• Drutsa A (2017) Horizon-independent optimal pricing in repeated auctions with truthful and strategic buyers. Barrett R, Cummings R, Agichtein E, Gabrilovich E, eds. Internat. Conf. World Wide Web (WWW) (ACM, New York), 33–42.Google Scholar
• Drutsa A (2020) Optimal non-parametric learning in repeated contextual auctions with strategic buyer. Daumé H, Singh A, eds. Internat. Conf. Machine Learn. (ICML) (PMLR, New York), 2668–2677.Google Scholar
• Even-Dar E, Mannor S, Mansour Y (2006) Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. J. Machine Learn. Res. 7:1079–1105. Google Scholar
• Ferrari JR (1995) Procrastination and Task Avoidance: Theory, Research, and Treatment (Springer Science and Business, New York).Crossref, Google Scholar
• Flaxman AD, Kalai AT, McMahan HB (2005) Online convex optimization in the bandit setting: Gradient descent without a gradient. Buchsbaum A, ed. ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 385–394.Google Scholar
• Fudenberg D, Maskin E (1986) The folk theorem in repeated games with discounting or with incomplete information. Econometrica 54(3):533–554.Crossref, Google Scholar
• Fudenberg D, Kreps DM, Maskin ES (1990) Repeated games with long-run and short-run players. Rev. Econom. Stud. 57(4):555–573.Crossref, Google Scholar
• Gael MA, Vernade C, Carpentier A, Valko M (2020) Stochastic bandits with arm-dependent delays. Daumé H, Singh A, eds. Internat. Conf. Machine Learn. (ICML) (PMLR, New York), 3348–3356.Google Scholar
• Golrezaei N, Jaillet P, Liang JCN (2023a) Incentive-aware contextual pricing with non-parametric market noise. Ruiz FJR, Dy JG, van de Meent J-W, eds. Internat. Conf. Artificial Intelligence Statistics (AISTATS) (PMLR, New York), 9331–9361.Google Scholar
• Golrezaei N, Javanmard A, Mirrokni VS (2021) Dynamic incentive-aware learning: Robust pricing in contextual auctions. Oper. Res. 69(1):297–314.Link, Google Scholar
• Golrezaei N, Manshadi V, Schneider J, Sekar S (2023b) Learning product rankings robust to fake users. Oper. Res. 71(4):1171–1196.Link, Google Scholar
• Grünbaum B (1960) Partitions of mass-distributions and of convex bodies by hyperplanes. Pacific J. Math. 10(4):1257–1261.Crossref, Google Scholar
• Gupta A, Koren T, Talwar K (2019) Better algorithms for stochastic bandits with adversarial corruptions. Beygelzimer A, Hsu D, eds. Conf. Learn. Theory (COLT) (PMLR, New York), 1562–1578.Google Scholar
• Haghtalab N, Fang F, Nguyen TH, Sinha A, Procaccia AD, Tambe M (2016) Three strategies to success: Learning adversary models in security games. Kambhampati S, ed. Internat. Joint Conf. Artificial Intelligence (IJCAI) (IJCAI/AAAI Press), 308–314.Google Scholar
• Hardt M, Megiddo N, Papadimitriou C, Wootters M (2016) Strategic classification. Sudan M, ed. Innovations Theoret. Comput. Sci. (ITCS) (ACM, New York), 111–122.Google Scholar
• Haupt A, Hadfield-Menell D, Podimata C (2023) Recommending to strategic users. Preprint, submitted February 13, https://arxiv.org/abs/2302.06559.Google Scholar
• Joulani P, Gyorgy A, Szepesvári C (2013) Online learning under delayed feedback. Internat. Conf. Machine Learn. (ICML) (PMLR, New York), 1453–1461.Google Scholar
• Kalai AT, Vempala S (2006) Simulated annealing for convex optimization. Math. Oper. Res. 31(2):253–266.Link, Google Scholar
• Kanoria Y, Nazerzadeh H (2014) Dynamic reserve prices for repeated auctions: Learning from bids. Liu TY, Qi Q, Ye Y, eds. Web and Internet Economics. WINE 2014, Lecture Notes in Computer Science, vol. 8877 (Springer, Cham, Switzerland), 232.Crossref, Google Scholar
• Kearns M, Pai M, Roth A, Ullman J (2014) Mechanism design in large games: Incentives and privacy. Naor M, ed. Innovations Theoret. Comput. Sci. (ITCS) (ACM, New York), 403–410.Google Scholar
• Kiekintveld C, Jain M, Tsai J, Pita J, Ordóñez F, Tambe M (2009) Computing optimal randomized resource allocations for massive security games. Sierra C, Castelfranchi C, Decker KS, Sichman JS, eds. Internat. Conf. Autonomous Agents Multiagent Systems (AAMAS) (IFAAMAS), 689–696.Google Scholar
• Kirby KN, Petry NM, Bickel WK (1999) Heroin addicts have higher discount rates for delayed rewards than non-drug-using controls. J. Experiment. Psych. General 128(1):78–87.Crossref, Google Scholar
• Kleinberg RD, Leighton FT (2003) The value of knowing a demand curve: Bounds on regret for online posted-price auctions. IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 594–605.Google Scholar
• Korzhyk D, Yin Z, Kiekintveld C, Conitzer V, Tambe M (2011) Stackelberg vs. Nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness. J. Artificial Intelligence Res. 41:297–327.Crossref, Google Scholar
• Krishnamurthy A, Lykouris T, Podimata C, Schapire RE (2023) Contextual search in the presence of adversarial corruptions. Oper. Res. 71(4):1120–1135.Link, Google Scholar
• Laibson D (1997) Golden eggs and hyperbolic discounting. Quart. J. Econom. 112(2):443–478.Crossref, Google Scholar
• Lancewicki T, Segal S, Koren T, Mansour Y (2021) Stochastic multi-armed bandits with unrestricted delay distributions. Meila M, Zhang T, eds. Internat. Conf. Machine Learn. (ICML) (PMLR, New York), 5969–5978.Google Scholar
• Lee YT, Sidford A, Vempala SS (2018) Efficient convex optimization with membership oracles. Conf. Learn. Theory (COLT) (PMLR, New York), 1292–1294.Google Scholar
• Letchford J, Conitzer V, Munagala K (2009) Learning and approximating the optimal strategy to commit to. Mavronicolas M, Papadopoulou VG, eds. Internat. Sympos. Algorithmic Game Theory (SAGT) (Springer, Berlin, Heidelberg), 250–262.Google Scholar
• Levin AY (1965) An algorithm for minimizing convex functions. Doklady Akademii Nauk SSSR 160:1244–1247.Google Scholar
• Littman ML (1994) Markov games as a framework for multi-agent reinforcement learning. Cohen WW, Hirsh H, eds. Internat. Conf. Machine Learn. (ICML) (Morgan Kaufmann, San Francisco), 157–163.Google Scholar
• Liu Y, Cooper WL (2015) Optimal dynamic pricing with patient customers. Oper. Res. 63(6):1307–1319.Link, Google Scholar
• Liu J, Huang Z, Wang X (2018) Learning optimal reserve price against non-myopic bidders. Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Adv. Neural Inform. Processing Systems (NeurIPS) (Curran Associates, Inc., Red Hook, NY), 2042–2052.Google Scholar
• Lobel I (2020) Dynamic pricing with heterogeneous patience levels. Oper. Res. 68(4):1038–1046.Link, Google Scholar
• Lobel I, Paes Leme R, Vladu A (2018) Multidimensional binary search for contextual decision-making. Oper. Res. 66(5):1346–1361.Link, Google Scholar
• Lykouris T, Mirrokni VS, Paes Leme R (2018) Stochastic bandits robust to adversarial corruptions. Diakonikolas I, Kempe D, Henzinger M, eds. ACM SIGACT Sympos. Theory Comput. (STOC) (ACM, New York), 114–122.Google Scholar
• Lykouris T, Simchowitz M, Slivkins A, Sun W (2025) Corruption-robust exploration in episodic reinforcement learning. Math. Oper. Res. 50(2):1277–1304.Link, Google Scholar
• McSherry F, Talwar K (2007) Mechanism design via differential privacy. IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 94–103.Google Scholar
• Mohri M, Muñoz Medina A (2014) Optimal regret minimization in posted-price auctions with strategic buyers. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems (NIPS) (Curran Associates, Inc., Red Hook, NY), 1871–1879.Google Scholar
• National Research Council (1999) Pathological Gambling: A Critical Review (National Academies Press, Washington, DC).Google Scholar
• Newman DJ (1965) Location of the maximum on unimodal surfaces. J. ACM 12(3):395–398.Crossref, Google Scholar
• Nguyen TH, Yadav A, Bosansky B, Liang Y (2019) Tackling sequential attacks in security games. Alpcan T, Vorobeychik Y, Baras JS, Dán G, eds. Internat. Conf. Decision Game Theory Security (GameSec) (Springer, Berlin, Heidelberg), 331–351.Google Scholar
• Nissim K, Smorodinsky R, Tennenholtz M (2012) Approximately optimal mechanism design via differential privacy. Goldwasser S, ed. Innovations Theoret. Comput. Sci. (ITCS) (ACM, New York), 203–213.Google Scholar
• Peng B, Shen W, Tang P, Zuo S (2019) Learning optimal strategies to commit to. AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 2149–2156.Google Scholar
• Pike-Burke C, Agrawal S, Szepesvari C, Grunewalder S (2018) Bandits with delayed, aggregated anonymous feedback. Dy JG, Krause A, eds. Internat. Conf. Machine Learn. (ICML) (PMLR, New York), 4105–4113.Google Scholar
• Pita J, John R, Maheswaran R, Tambe M, Yang R, Kraus S (2012) A robust approach to addressing human adversaries in security games. van der Hoek W, Padgham L, Conitzer V, Winikoff M, eds. Internat. Conf. Autonomous Agents Multiagent Systems (AAMAS) (IFAAMAS), 660–665.Google Scholar
• Ross D, Sharp C, Vuchinich RE, Spurrett D (2012) Midbrain Mutiny: The Picoeconomics and Neuroeconomics of Disordered Gambling: Economic Theory and Cognitive Science (MIT Press, Cambridge, MA).Google Scholar
• Slivkins A (2019) Introduction to multi-armed bandits. Foundations Trends Machine Learn. 12(1–2):1–286.Crossref, Google Scholar
• Steel P (2007) The nature of procrastination: A meta-analytic and theoretical review of quintessential self-regulatory failure. Psych. Bull. 133(1):65–94.Crossref, Google Scholar
• Suranovic SM, Goldfarb RS, Leonard TC (1999) An economic theory of cigarette addiction. J. Health Econom. 18(1):1–29.Crossref, Google Scholar
• Tambe M (2011) Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Vernade C, Cappé O, Perchet V (2017) Stochastic bandit models for delayed conversions. Elidan G, Kersting K, Ihler A, eds. Conf. Uncertainty Artificial Intelligence (UAI) (AUAI Press).Google Scholar
• Weinberger MJ, Ordentlich E (2002) On delayed prediction of individual sequences. IEEE Trans. Inform. Theory 48(7):1959–1976.Crossref, Google Scholar
• Xu H, Tran-Thanh L, Jennings NR (2016) Playing repeated security games with no prior knowledge. Jonker CM, Marsella S, Thangarajah J, Tuyls K, eds. Internat. Conf. Autonomous Agents Multiagent Systems (AAMAS) (ACM, New York), 104–112.Google Scholar
• Zimmert J, Seldin Y (2021) Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. J. Machine Learn. Res. 22(1):28.Google Scholar
• Zuo S, Tang P (2015) Optimal machine strategies to commit to in two-person repeated games. Bonet B, Koenig S, eds. AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1071–1078.Google Scholar