Research map / Learning theory and algorithms / Submodular and game algorithms
Generative Adversarial Equilibrium Solvers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Generative Adversarial Equilibrium Solvers (GAN-style generator/discriminator) that learn generalized Nash equilibria in pseudo-games and competitive equilibria in Arrow-Debreu economies from sampled problem instances, with convergence and sample complexity bounds.
Problem
Computing generalized Nash equilibria (GNE) and competitive equilibria (CE) in pseudo-games is PPAD-hard in the worst case and existing solvers are slow, ill-conditioned, or hyperparameter-sensitive, especially when many instances must be solved over a distribution.
Approach
Reformulate expected exploitability minimization as a min-max problem in which a discriminator network outputs best responses for each player, making the objective Lipschitz-continuous and avoiding inner convex programs; train with a nested stochastic gradient descent-ascent ("stochastic exploitability descent").
Key results
- In linear, Cobb-Douglas, Leontief, and mixed CES exchange economies, the solver's output is on average better than at least 99% of action profiles in normalized exploitability and achieves lower average exploitability than baselines.
- Outperforms tâtonnement and exploitability descent in distribution in all markets except Cobb-Douglas, where tâtonnement is guaranteed to converge.
- On the Kyoto JI model, predicted GNE types match analytical regions except Regions 1 and 2a, with testing normalized exploitability about 99.5% better than average feasible profiles.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Generative Adversarial Equilibrium Solvers instead of the specialized baselines | Arrow-Debreu exchange economies · Linear, Cobb-Douglas, Leontief, and mixed CES economies | average normalized exploitability | Helped |
| Use Generative Adversarial Equilibrium Solvers instead of the specialized baselines | Arrow-Debreu exchange economies · Exchange economies | test exploitability distribution | Mixed |
| Predict exchange-economy equilibria with NEES | NEES · Arrow-Debreu exchange economies | normalized exploitability relative to action profiles: 99% | Helped |
| Soft-start tâtonnement from NEES prices with added uniform noise | Tâtonnement · Scarf economy | distance of final prices from equilibrium | Hurt |
| Predict Kyoto equilibria with NEES | NEES · Kyoto Joint Implementation Mechanism | normalized exploitability relative to feasible action profiles: 99.5% | Helped |
| Predict equilibrium types with NEES | NEES · Kyoto Joint Implementation Mechanism, Regions 1 and 2a | qualitative equilibrium-type agreement | Hurt |
Surprising findings
- Soft-starting tâtonnement from the solver's output can be worse than using the solver alone, since GNE and CE are not locally stable.
- Neural equilibrium mappings that soft-start Nash equilibrium dynamics do not carry over to pseudo-games.
Limitations
- Convergence guarantees hold only for affine generators and discriminators and strongly concave payoffs; general function approximators get only generalization bounds.
- Predicted GNE types fail to match analytical regions 1 and 2a in the Kyoto model.
- Strong concavity assumption is stronger than needed in practice and differs from monotonicity assumptions in GNE literature.
Experimental setup
Datasets: synthetic exchange economies (linear, Cobb-Douglas, Leontief, CES) synthetic Kyoto Joint Implementation pseudo-games Scarf economy normal-form games
Benchmarks: Arrow-Debreu exchange economies (linear, Cobb-Douglas, Leontief, mixed CES) Scarf economy Kyoto Joint Implementation pseudo-game
Metrics: normalized exploitability test exploitability distribution
Baselines: tâtonnement exploitability descent (Augmented Descent Ascent)
Builds on: exploitability descent Augmented Descent Ascent differentiable economics neural equilibrium mappings Arrow-Debreu competitive equilibrium
Closest papers by meaning
- Do GANs always have Nash equilibria? (ICML 2020 · similarity 0.90)
- Finding Mixed Nash Equilibria of Generative Adversarial Networks (ICML 2019 · similarity 0.90)
- Many Paths to Equilibrium: GANs Do Not Need to Decrease a Divergence At Every Step (ICLR 2018 · similarity 0.89)
- Learning Nash Equilibria in Rank-1 Games (ICLR 2024 · similarity 0.88)
- The Mechanics of n-Player Differentiable Games (ICML 2018 · similarity 0.88)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.