Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria
Gabriele Farina (),
Christian Kroer () and
Tuomas Sandholm ()
Additional contact information
Gabriele Farina: MIT EECS, Cambridge, Massachusetts 02139
Christian Kroer: Industrial Engineering and Operations Research Department, Columbia University, New York, New York 10027
Tuomas Sandholm: Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213; and Strategy Robot, Inc., Pittsburgh, Pennsylvania 15232; and Optimized Markets, Inc., Pittsburgh, Pennsylvania 15232; and Strategic Machine, Inc., Pittsburgh, Pennsylvania 15232
Operations Research, 2025, vol. 73, issue 5, 2430-2457
Abstract:
We study the application of iterative first-order methods to the problem of computing equilibria of large-scale extensive-form games. First-order methods must typically be instantiated with a regularizer that serves as a distance-generating function (DGF) for the decision sets of the players. In this paper, we introduce a new weighted entropy-based distance-generating function. We show that this function is equivalent to a particular set of new weights for the dilated entropy distance–generating function on a treeplex while retaining the simpler structure of the regular entropy function for the unit cube. This function achieves significantly better strong-convexity properties than existing weight schemes for the dilated entropy while maintaining the same easily implemented closed-form proximal mapping as the prior state of the art. Extensive numerical simulations show that these superior theoretical properties translate into better numerical performance as well. We then generalize our new entropy distance function, as well as general dilated distance functions, to the scaled extension operator. The scaled extension operator is a way to recursively construct convex sets, which generalizes the decision polytope of extensive-form games as well as the convex polytopes corresponding to correlated and team equilibria. Correspondingly, we give the first efficiently computable distance-generating function for all those strategy polytopes. By instantiating first-order methods with our regularizers, we achieve several new results, such as the first method for computing ex ante correlated team equilibria with a guaranteed 1 / T rate of convergence and efficient proximal updates. Similarly, we show that our regularizers can be used to speed up the computation of correlated solution concepts.
Keywords: Market; Analytics; and; Revenue; Management; extensive-form games; first-order methods; distance-generating functions; equilibrium computation; adversarial team games (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:
Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.0633 (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:5:p:2430-2457
Access Statistics for this article
More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().