Timezone: »

Exploitability Minimization in Games and Beyond
Denizalp Goktas · Amy Greenwald

Wed Dec 07 05:00 PM -- 07:00 PM (PST) @

Pseudo-games are a natural and well-known generalization of normal-form games, in which the actions taken by each player affect not only the other players' payoffs, as in games, but also the other players' strategy sets. The solution concept par excellence for pseudo-games is the generalized Nash equilibrium (GNE), i.e., a strategy profile at which each player's strategy is feasible and no player can improve their payoffs by unilaterally deviating to another strategy in the strategy set determined by the other players' strategies. The computation of GNE in pseudo-games has long been a problem of interest, due to applications in a wide variety of fields, from environmental protection to logistics to telecommunications. Although computing GNE is PPAD-hard in general, it is still of interest to try to compute them in restricted classes of pseudo-games. One approach is to search for a strategy profile that minimizes exploitability, i.e., the sum of the regrets across all players. As exploitability is nondifferentiable in general, developing efficient first-order methods that minimize it might not seem possible at first glance. We observe, however, that the exploitability-minimization problem can be recast as a min-max optimization problem, and thereby obtain polynomial-time first-order methods to compute a refinement of GNE, namely the variational equilibria (VE), in convex-concave cumulative regret pseudo-games with jointly convex constraints. More generally, we also show that our methods find the stationary points of the exploitability in polynomial time in Lipschitz-smooth pseudo-games with jointly convex constraints. Finally, we demonstrate in experiments that our methods not only outperform known algorithms, but that even in pseudo-games where they are not guaranteed to converge to a GNE, they may do so nonetheless, with proper initialization.

Author Information

Denizalp Goktas (Brown University)
Amy Greenwald

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors

  • 2023 Poster: Convex-Concave Zero-Sum Stochastic Stackelberg Games »
    Denizalp Goktas · Arjun Prakash · Sadie Zhao · Amy Greenwald
  • 2022 Spotlight: Lightning Talks 6B-2 »
    Alexander Korotin · Jinyuan Jia · Weijian Deng · Shi Feng · Maying Shen · Denizalp Goktas · Fang-Yi Yu · Alexander Kolesov · Sadie Zhao · Stephen Gould · Hongxu Yin · Wenjie Qu · Liang Zheng · Evgeny Burnaev · Amy Greenwald · Neil Gong · Pavlo Molchanov · Yiling Chen · Lei Mao · Jianna Liu · Jose M. Alvarez
  • 2022 Spotlight: Zero-Sum Stochastic Stackelberg Games »
    Denizalp Goktas · Sadie Zhao · Amy Greenwald
  • 2022 Spotlight: Lightning Talks 4A-1 »
    Jiawei Huang · Su Jia · Abdurakhmon Sadiev · Ruomin Huang · Yuanyu Wan · Denizalp Goktas · Jiechao Guan · Andrew Li · Wei-Wei Tu · Li Zhao · Amy Greenwald · Jiawei Huang · Dmitry Kovalev · Yong Liu · Wenjie Liu · Peter Richtarik · Lijun Zhang · Zhiwu Lu · R Ravi · Tao Qin · Wei Chen · Hu Ding · Nan Jiang · Tie-Yan Liu
  • 2022 Poster: Zero-Sum Stochastic Stackelberg Games »
    Denizalp Goktas · Sadie Zhao · Amy Greenwald
  • 2021 Poster: Convex-Concave Min-Max Stackelberg Games »
    Denizalp Goktas · Amy Greenwald