# Maximizing utility in multi-agent environments by anticipating the behavior of other learners

arXiv: https://arxiv.org/abs/2407.04889 · HTML: https://mlsanity.com/paper/2407.04889/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 46 references that are in the map.
- First posted on arXiv 5 Jul 2024.

## Builds on (most cited first, 27 of 27)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [Strategizing against Learners in Bayesian Games](https://mlsanity.com/paper/2205.08562/) (2022)
- [On Last-Iterate Convergence Beyond Zero-Sum Games](https://mlsanity.com/paper/2203.12056/) (2022)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Econometrics for Learning Agents](https://mlsanity.com/paper/1505.00720/) (2015)
- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [Auctions Between Regret-Minimizing Agents](https://mlsanity.com/paper/2110.11855/) (2021)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [Selling to Multiple No-Regret Buyers](https://mlsanity.com/paper/2307.04175/) (2023)
- [How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agents](https://mlsanity.com/paper/2112.07640/) (2021)
- [Pareto-Optimal Algorithms for Learning in Games](https://mlsanity.com/paper/2402.09549/) (2024)
- [Bid Prediction in Repeated Auctions with Learning](https://mlsanity.com/paper/2007.13193/) (2020)
- [No-Regret Learning in Dynamic Stackelberg Games](https://mlsanity.com/paper/2202.04786/) (2022)
- [Tight Lower Bounds for Multiplicative Weights Algorithmic Families](https://mlsanity.com/paper/1607.02834/) (2016)
- [Efficient Stackelberg Strategies for Finitely Repeated Games](https://mlsanity.com/paper/2207.04192/) (2022)
- [Persuading a Behavioral Agent: Approximately Best Responding and Learning](https://mlsanity.com/paper/2302.03719/) (2023)
- [Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games](https://mlsanity.com/paper/2203.12074/) (2022)
- [Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games](https://mlsanity.com/paper/2306.05216/) (2023)
- [Fast Algorithms for Rank-1 Bimatrix Games](https://mlsanity.com/paper/1812.04611/) (2018)
- [The Optimal Strategy against Hedge Algorithm in Repeated Games](https://mlsanity.com/paper/2312.09472/) (2023)

## Built on by (most cited first, 8 of 8)

- [Learning and Computation of Phi-Equilibria at the Frontier of Tractability](https://mlsanity.com/paper/2502.18582/) (2025)
- [Computational Intractability of Strategizing against Online Learners](https://mlsanity.com/paper/2503.04202/) (2025)
- [Orchestrator: Active Inference for Multi-Agent Systems in Long-Horizon Tasks](https://mlsanity.com/paper/2509.05651/) (2025)
- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)
- [Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent](https://mlsanity.com/paper/2510.22471/) (2025)
- [Learning in Repeated Multi-Objective Stackelberg Games with Payoff Manipulation](https://mlsanity.com/paper/2508.14705/) (2025)
- [Learning Safely Without Knowing the World:COMPASS-Hedge](https://mlsanity.com/paper/2603.22348/) (2026)
- [No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics](https://mlsanity.com/paper/2604.05129/) (2026)

## Abstract (arXiv)

Learning algorithms are often used to make decisions in sequential decision-making environments. In multi-agent settings, the decisions of each agent can affect the utilities/losses of the other agents. Therefore, if an agent is good at anticipating the behavior of the other agents, in particular how they will make decisions in each round as a function of their experience that far, it could try to judiciously make its own decisions over the rounds of the interaction so as to influence the other agents to behave in a way that ultimately benefits its own utility. In this paper, we study repeated two-player games involving two types of agents: a learner, which employs an online learning algorithm to choose its strategy in each round; and an optimizer, which knows the learner's utility function and the learner's online learning algorithm. The optimizer wants to plan ahead to maximize its own utility, while taking into account the learner's behavior. We provide two results: a positive result for repeated zero-sum games and a negative result for repeated general-sum games. Our positive result is an algorithm for the optimizer, which exactly maximizes its utility against a learner that plays the Replicator Dynamics -- the continuous-time analogue of Multiplicative Weights Update (MWU). Additionally, we use this result to provide an algorithm for the optimizer against MWU, i.e.~for the discrete-time setting, which guarantees an average utility for the optimizer that is higher than the value of the one-shot game. Our negative result shows that, unless P=NP, there is no Fully Polynomial Time Approximation Scheme (FPTAS) for maximizing the utility of an optimizer against a learner that best-responds to the history in each round. Yet, this still leaves open the question of whether there exists a polynomial-time algorithm that optimizes the utility up to o(T).