محفوظ في:
| المؤلفون الرئيسيون: | , , , , |
|---|---|
| التنسيق: | Preprint |
| منشور في: |
2023
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://arxiv.org/abs/2302.01421 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1866929290022486016 |
|---|---|
| author | Maheshwari, Chinmay Cheng, James Sasty, S. Shankar Ratliff, Lillian Mazumdar, Eric |
| author_facet | Maheshwari, Chinmay Cheng, James Sasty, S. Shankar Ratliff, Lillian Mazumdar, Eric |
| contents | In this paper, we present an efficient algorithm to solve online Stackelberg games, featuring multiple followers, in a follower-agnostic manner. Unlike previous works, our approach works even when leader has no knowledge about the followers' utility functions or strategy space. Our algorithm introduces a unique gradient estimator, leveraging specially designed strategies to probe followers. In a departure from traditional assumptions of optimal play, we model followers' responses using a convergent adaptation rule, allowing for realistic and dynamic interactions. The leader constructs the gradient estimator solely based on observations of followers' actions. We provide both non-asymptotic convergence rates to stationary points of the leader's objective and demonstrate asymptotic convergence to a \emph{local Stackelberg equilibrium}. To validate the effectiveness of our algorithm, we use this algorithm to solve the problem of incentive design on a large-scale transportation network, showcasing its robustness even when the leader lacks access to followers' demand. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_01421 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Follower Agnostic Methods for Stackelberg Games Maheshwari, Chinmay Cheng, James Sasty, S. Shankar Ratliff, Lillian Mazumdar, Eric Optimization and Control Artificial Intelligence Computer Science and Game Theory Dynamical Systems 91A65 In this paper, we present an efficient algorithm to solve online Stackelberg games, featuring multiple followers, in a follower-agnostic manner. Unlike previous works, our approach works even when leader has no knowledge about the followers' utility functions or strategy space. Our algorithm introduces a unique gradient estimator, leveraging specially designed strategies to probe followers. In a departure from traditional assumptions of optimal play, we model followers' responses using a convergent adaptation rule, allowing for realistic and dynamic interactions. The leader constructs the gradient estimator solely based on observations of followers' actions. We provide both non-asymptotic convergence rates to stationary points of the leader's objective and demonstrate asymptotic convergence to a \emph{local Stackelberg equilibrium}. To validate the effectiveness of our algorithm, we use this algorithm to solve the problem of incentive design on a large-scale transportation network, showcasing its robustness even when the leader lacks access to followers' demand. |
| title | Follower Agnostic Methods for Stackelberg Games |
| topic | Optimization and Control Artificial Intelligence Computer Science and Game Theory Dynamical Systems 91A65 |
| url | https://arxiv.org/abs/2302.01421 |