Research map / Multi-agent systems and games / Games and equilibria
Understanding Model Selection for Learning in Strategic Environments
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.
Shows that in strategic (general Nash) settings, restricting model class expressivity can yield strictly better equilibrium outcomes (a Braess-like paradox), and proposes successive elimination to select the best model class in games.
Problem
How strategic interactions affect the relationship between model class expressivity and equilibrium performance, i.e., whether larger model classes always improve outcomes when the learner faces strategic environments.
Approach
Shows that in strongly monotone convex games, if the Nash equilibrium is not Pareto optimal, a unilateral restriction of the learner's action set (model class) yields a Nash equilibrium with strictly lower learner loss; treats model class choice as a strategic action and proposes successive elimination to identify the best model class from a candidate set.
Key results
- Theorem: in a strongly monotone two-player game, if the unique Nash equilibrium is not Pareto optimal, a restriction of the learner's model class yields a Nash equilibrium with strictly lower learner loss.
- In a 50-state Markov game example, learner payoff at Nash increases as the policy class is restricted toward uniform policies, for several discount factors.
- Successive elimination identifies the best model class after O(n(L^2 log(n/delta)+L^3)/(mu^2 Delta*)) environment interactions with probability at least 1-delta.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| restrict the learner's model class | strongly monotone Nash games with a non-Pareto-optimal equilibrium · General Nash environments | learner loss | Helped |
| restrict the learner's policy class toward uniform policies | 50-state Markov game · Multi-agent reinforcement learning | learner payoff at Nash | Mixed |
| use the less expressive feature-restricted classifier | strategic participation dynamics · Strategic classification | learner loss at Nash | Helped |
| use the smaller linear feature class instead of the class with an added exponential feature | strategic linear regression · Stackelberg environment where the learner follows | learner loss at equilibrium | Helped |
Surprising findings
- Restricting the learner's policy or model class can strictly improve equilibrium payoff even with infinite data, a Braess-like paradox.
- In strategic linear regression under Stackelberg learner-follows, a larger feature class yields higher loss at equilibrium than a nested smaller class.
Limitations
- Main results rely on strong monotonicity and a unique Nash equilibrium, which is an assumption made for illustration.
- The constructive restriction in the theorem uses information about the environment's loss, which the learner may not have.
- Analysis ignores sample size and generalization error; finite-sample effects are left to future work.
Experimental setup
Metrics: learner loss at Nash equilibrium payoff at equilibrium suboptimality gap
Builds on: Braess' paradox strategic classification performative prediction continuous games
Closest papers by meaning
- Causal Strategic Learning with Competitive Selection (AAAI 2024 · similarity 0.88)
- Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions (NeurIPS 2024 · similarity 0.87)
- Strategic Classification With Externalities (ICLR 2025 · similarity 0.86)
- The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.86)
- The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability (ICML 2025 · similarity 0.86)
- Strategic Classification with Non-Linear Classifiers (NeurIPS 2025 · 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.