Robust Stackelberg Equilibria

• 成果类型: Article; Early Access
• 署名作者: Gan, Jiarui; Han, Minbiao; Wu, Jibang; Xu, Haifeng
• 署名单位: University of Oxford; University of Chicago
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02291-4
• 发表日期: 2025-11-12
• 关键词: Stackelberg Games; robust optimization; Algorithmic game theory; learning in games; Nash equilibria; games; strategies; complexity

摘要

This paper provides a systematic study of the robust Stackelberg equilibrium (RSE), which naturally extends the widely adopted solution concept of the strong Stackelberg equilibrium (SSE). The RSE accounts for any possible up-to-delta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta $$\end{document} suboptimal follower responses in Stackelberg games and is adopted to improve the robustness of the leader's strategy through worst-case analysis. While a few variants of robust Stackelberg equilibrium have been considered in the previous literature, the RSE solution concept we consider is importantly different - in some sense, it relaxes previously studied robust Stackelberg strategies and is applicable to much broader sources of uncertainties. We provide a thorough investigation of several fundamental properties of RSE, including its utility guarantees, algorithmics, and learnability. We first show that the RSE always exists and is thus well-defined. Then we characterize how the leader's utility in RSE changes with the robustness level considered. On the algorithmic side, we show that, in sharp contrast to the tractability of computing an SSE, it is NP-hard to obtain a fully polynomial approximation scheme (FPTAS) for any constant robustness level. Nevertheless, we develop a quasi-polynomial approximation scheme (QPTAS) for RSE. Finally, we examine the learnability of the RSE in a natural learning scenario, where both players' utilities are not known in advance, and provide almost tight sample complexity results on learning the RSE. As a corollary of this result, we also obtain an algorithm for learning SSE, which strictly improves a key result of Bai et al. [5] in terms of both utility guarantee and computational efficiency.