Research map / Multi-agent systems and games / Games and equilibria
Maximizing utility in multi-agent environments by anticipating the behavior of other learners
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.
Studies how an optimizer that knows a learner's mean-based online algorithm (replicator dynamics, MWU, best response) should play repeated games, giving a polynomial-time optimal strategy for zero-sum continuous-time games and an NP-hardness result for general-sum games against best-response learners.
Problem
How should an optimizer play a repeated two-player game against a learner running a known mean-based online learning algorithm (MWU, replicator dynamics, best response), and can the optimal strategy be computed efficiently?
Approach
Exploits the known learner dynamics to plan ahead: in zero-sum games against replicator dynamics the optimal reward is achieved by a constant minmax-type strategy found by convex optimization of a log-sum-exp function, while in general-sum games optimizing against a best-response learner is NP-hard via reduction from Hamiltonian cycle.
Key results
- For zero-sum games against replicator dynamics, the optimal reward is achieved by a constant strategy computable in polynomial time via convex optimization of a log-sum-exp function.
- Optimal continuous-time reward lies in [T·Val(A), T·Val(A)+log(m)/η], and discrete-time MWU with constant strategy yields at least the continuous-time utility.
- Against best-response learners in general-sum games, there is no FPTAS for maximizing optimizer utility unless P=NP (reduction from Hamiltonian cycle).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| plan ahead with an optimal constant strategy against Replicator Dynamics | optimizer in zero-sum continuous games · Zero-sum continuous games | optimizer utility: [T Val(A), T Val(A) + ln(m)/η] | Helped |
| play the continuous-time optimal strategy in each discrete round | optimizer against MWU · Zero-sum discrete games | optimizer utility: R*disc(0, T, A, -A) ≥ R*cont(0, T, A, -A) | Helped |
| use discrete rather than continuous play | optimal optimizer in zero-sum games with entries in [-1,1] · Zero-sum games with entries in [-1,1] | optimizer utility: ηT/2 | Helped |
| alternate pure actions across rounds | optimizer against MWU in Matching Pennies · Matching Pennies | optimizer utility: T/2 · tanh(η) | Helped |
| alternate split strategies x′ and x″ around a minmax strategy | optimizer against MWU in games satisfying the two-best-response assumption · Zero-sum games satisfying the two-best-response assumption | optimizer utility: T Val(A) + C_A ηT | Helped |
| optimize a pure-action sequence against a Best Response learner | optimizer in general-sum repeated games · General-sum repeated games against Best Response | computational complexity of optimal control: NP-hard | Hurt |
| use Frank-Wolfe for approximate strategy computation | optimizer against Replicator Dynamics · Zero-sum continuous games | runtime: O(mn/(εη)) | Helped |
Surprising findings
- A discrete-time optimizer against MWU can gain roughly ηT/2 more than the best continuous-time optimizer, with the gap tight up to tanh(η)T/2 in matching pennies.
Limitations
- Hardness result only shows distinguishing reward T from T-1; open whether o(T) approximation is efficient
- Fictitious play/best response is not no-regret; open for MWU with small step size in general-sum games
- General-sum continuous-time optimum has no closed form
Experimental setup
Metrics: optimizer cumulative utility
Baselines: Stackelberg value value of the game (minmax strategy)
Builds on: multiplicative weights update Stackelberg equilibrium mean-based learning analysis
Closest papers by meaning
- Is Learning in Games Good for the Learners? (NeurIPS 2023 · similarity 0.89)
- Impact of Decentralized Learning on Player Utilities in Stackelberg Games (ICML 2024 · similarity 0.89)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.89)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.88)
- Learning from Delayed Feedback in Games via Extra Prediction (NeurIPS 2025 · similarity 0.88)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.88)
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.