Coordinating Followers to Reach Better Equilibria: End-to-End Gradient Descent for Stackelberg Games

Authors

  • Kai Wang Harvard University
  • Lily Xu Harvard University
  • Andrew Perrault The Ohio State University
  • Michael K. Reiter Duke University
  • Milind Tambe Harvard University

DOI:

https://doi.org/10.1609/aaai.v36i5.20457

Keywords:

Game Theory And Economic Paradigms (GTEP)

Abstract

A growing body of work in game theory extends the traditional Stackelberg game to settings with one leader and multiple followers who play a Nash equilibrium. Standard approaches for computing equilibria in these games reformulate the followers' best response as constraints in the leader's optimization problem. These reformulation approaches can sometimes be effective, but make limiting assumptions on the followers' objectives and the equilibrium reached by followers, e.g., uniqueness, optimism, or pessimism. To overcome these limitations, we run gradient descent to update the leader's strategy by differentiating through the equilibrium reached by followers. Our approach generalizes to any stochastic equilibrium selection procedure that chooses from multiple equilibria, where we compute the stochastic gradient by back-propagating through a sampled Nash equilibrium using the solution to a partial differential equation to establish the unbiasedness of the stochastic gradient. Using the unbiased gradient estimate, we implement the gradient-based approach to solve three Stackelberg problems with multiple followers. Our approach consistently outperforms existing baselines to achieve higher utility for the leader.

Downloads

Published

2022-06-28

How to Cite

Wang, K., Xu, L., Perrault, A., Reiter, M. K., & Tambe, M. (2022). Coordinating Followers to Reach Better Equilibria: End-to-End Gradient Descent for Stackelberg Games. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5219-5227. https://doi.org/10.1609/aaai.v36i5.20457

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms