AI summaryⓘ
The authors study a type of game where two players repeatedly interact, and one tries to learn and adapt based on past actions. While it's known that finding stable outcomes (Nash equilibria) is easier in certain simple games, the authors show that planning against a learning player remains very hard even in these simpler setups. Specifically, they prove that predicting and optimizing how a learner will behave over time is computationally tough unless a major open problem in computer science is solved. They also identify some special cases where the problem becomes easier. Overall, this work highlights a clear complexity difference between computing equilibria and strategically planning against learning agents.
learning algorithmsmulti-agent environmentsNash equilibriumbimatrix gamesrank-1 gamesReplicator DynamicsMultiplicative Weights Updatezero-sum gamescomputational complexityNP-hardness
Abstract
Learning algorithms are often used to make decisions in repeated multi-agent environments. When another player understands how a learner adapts from past experience, that player can plan strategically across rounds to influence the learner's future behavior. Recent work shows that optimizing against Replicator Dynamics, the continuous-time analogue of Multiplicative Weights Update, is tractable in zero-sum games but can be hard in unrestricted general-sum games. We study the first structured class beyond zero sum: bimatrix games satisfying $\text{rank}(A+B)=1$, for which Nash equilibria can be computed in polynomial time. Our main result shows that this equilibrium tractability does not extend to planning against learning dynamics. Unless $\mathsf{P}=\mathsf{NP}$, approximating the optimizer's optimal continuous-time reward within a fixed additive constant is NP-hard even when $\text{rank}(A+B)=1$, the learner starts from the uniform state, and the optimizer is restricted to constant strategies. The hardness persists for bounded payoff matrices and polynomially bounded horizons. We complement this result with structural characterizations of several tractable special cases. Thus rank-one games already separate efficient equilibrium computation from strategic planning against a learning opponent.