Research map / Learning theory and algorithms / Submodular and game algorithms
Evolutionary Prediction Games
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.
Introduces evolutionary prediction games, modeling retrained classifiers and user-group self-selection as population games, showing competitive exclusion under oracle learners and stable mutualistic coexistence under finite data, surrogate losses, and label noise.
Problem
Feedback loops between repeatedly retrained prediction models and user populations: how learning shapes which user groups survive, dominate, or coexist over time.
Approach
Models each group's fitness as its marginal accuracy under a classifier trained on the current population mixture, yielding a population game analyzed with evolutionary game theory and potential-game structure; shows oracle retraining drives competitive exclusion, while realistic learning (surrogate losses, finite data, interpolation, label noise) can stabilize mutualistic coexistence; also propos
Key results
- On CIFAR-10 with horizontal-flip groups, the unstable mixed equilibrium reaches 93.5 ±0.1% accuracy versus 92.6 ±0.1% at single-group equilibria.
- On MNIST with complementary label noise, a stable coexistence equilibrium achieves 80.4 ±0.2% test accuracy against an 84% noise-limited upper bound.
- On ACSIncome with three states, one group (NY) is driven below 1% share around t≈316, after which the remaining groups' accuracy disparity shrinks to about 0.2%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply dynamics-aware stabilization to the CIFAR-10 mixed equilibrium | ResNet-9 on CIFAR-10 with original and horizontally flipped images · CIFAR-10 | accuracy: 92.6 \pm 0.1\% -> 93.5 \pm 0.1\% | Helped |
| Introduce complementary label noise across the two groups | Convolutional neural network on MNIST · MNIST | test accuracy | Helped |
| Allow the population to evolve under linear-SVM fitness | Linear SVM on ACSIncome groups from CA, NY, and TX · ACSIncome | accuracy disparity: \approx2\% -> \approx 0.2\% | Mixed |
| Repeatedly retrain an oracle classifier on the current population mixture | Evolutionary prediction game · Theoretical analysis | population coexistence | Hurt |
| Use hinge loss with ℓ2 regularization instead of oracle 0-1-loss learning | Evolutionary prediction game · Theoretical construction | population coexistence | Helped |
Surprising findings
- With label noise, accuracy is higher for the minority group, so groups naturally balance each other and coexist.
- Fairness audits can look fair only because some groups were already driven out of the population.
Limitations
- Results assume non-overlapping groups, no exogenous user inflow, and fixed-size sampling from the current distribution only.
- Limiting-behavior results are silent on finite-time trajectories and convergence rates.
- Experiments are small-scale simulations of replicator dynamics rather than live user dynamics.
Experimental setup
Datasets: CIFAR-10 MNIST Folktables ACSIncome
Benchmarks: CIFAR-10 MNIST ACSIncome
Metrics: group accuracy population accuracy fitness population proportion over time
Baselines: standard retraining (oracle classifier) ERM with hinge loss linear SVM
Builds on: performative prediction replicator dynamics stateful performative prediction potential games
Closest papers by meaning
- Tapes Together Strong: The Co-evolution of Computation and Cooperation (NeurIPS 2026 · similarity 0.86)
- Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Bandits (NeurIPS 2025 · similarity 0.86)
- Look-Ahead Reasoning on Learning Platforms (NeurIPS 2025 · similarity 0.86)
- Reaching a Consensus in Predictive Loops (NeurIPS 2026 · similarity 0.86)
- Causal Strategic Learning with Competitive Selection (AAAI 2024 · similarity 0.85)
- Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.85)
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.