betaFeedback

WorksComputer Science

Fictitious Play When Agents Are Not Expected-Utility Maximizers: A Geometric Analysis in 22-Action Games

Abstract

Fictitious play (FP) is one of the earliest and most fundamental learning procedures in games, where each agent independently chooses a best response to the empirical distribution of opponents' past actions by maximizing the expected payoff with respect to it. However, learning agents may not always be expected-utility maximizers: they may use nonlinear evaluation functionals to account for the uncertainty induced by the opponents, e.g., via risk measures. In this work, we study nonlinear fictitious play (NL-FP), in which each pure action is evaluated by a general, possibly nonlinear functional of the payoff distribution induced by the opponent's empirical belief. To analyze NL-FP, we first identify a single-crossing property (SCP) of evaluation functionals that preserves the classical geometry of FP in 2×22\times2 games. Furthermore, we conduct a novel geometric analysis of the convergence behavior of NL-FP in 2×22\times2 games, even when the SCP fails. Beyond 2×22\times2 games, we show that the convergence of NL-FP in 2×n2\times n (n≥3n\ge3) games may fail even for continuous-time NL-FP, when the two-action player uses conditional value-at-risk (CVaR) in a 2×32\times3 game. In addition, we identify a finite-crossing condition that ensures convergence of the selected continuous-time dynamics and the discrete-time iterates in general 2×n2\times n games, which also provides new insights into the global landscape of continuous-time classical FP in such games.

Introduction

Fictitious play (FP) is one of the earliest and most fundamental learning procedures in games [1]. It is a canonical model of adaptive and independent learning in repeated game playing, requiring neither coordination among agents1 nor knowledge of opponents’ payoffs. The idea behind FP is simple: each agent repeatedly best responds to the empirical distribution of opponents’ past actions, i.e., the empirical belief about the opponent’s mixed strategy. Specifically, agent ii selects its action akia_k^i at iteration k≥0k \ge0 according to

aki∈arg maxaiE[ri(ai,A−i)],A−i∼π^k−i,(1)a_k^i \in\mathop{\rm arg\,max}_{a^i} \mathbb{E}\left[r^i\left(a^i,A^{-i}\right)\right], \qquad A^{-i} \sim\hat{\pi}_k^{-i}, \tag*{(1)}

where rir^i is the payoff function for agent ii, and π^k−i\hat{\pi}_k^{-i} is the empirical belief based on the opponent’s actions before iteration kk (see also Equation (II.5)). The convergence of empirical beliefs to the Nash equilibrium set was established in two-player zero-sum games [2], 2×22 \times2 games [3, 4], nondegenerate 2×n2 \times n games [5], and potential games [6], under the assumptions and tie-breaking conventions of the respective results. Despite these positive results, nonconvergence of FP is known to occur even in 3×33 \times3 games [7].

Classical FP evaluates each action by its expected payoff against the empirical distribution of opponents’ past actions. In particular, each action’s evaluation is linear in the empirical belief. Such linear evaluation is considered natural, and is consistent with the seminal results by von Neumann and Morgenstern [8], Nash [9], and Harsanyi [10] that laid the foundations of the expected-utility maximization framework in game theory.

More generally, however, agents may evaluate payoff distributions using nonlinear alternatives that account for features beyond their means, such as downside risk, tail outcomes, and probability weighting. A substantial literature developed such alternatives, including coherent and convex risk measures [11, 12], optimized certainty equivalents [13], conditional value-at-risk (CVaR) [14], mean-semivariance and other downside-risk criteria [15], spectral risk measures [16], rank-dependent expected utility [17], and cumulative prospect theory (CPT) [18]. Within the literature of game theory and multi-agent learning, prior work studied equilibrium existence, computation, and learning in games with non-expected-utility preferences [19], mean-variance equilibria and stochastic FP [20], CPT-based learning [21], and risk-sensitive equilibrium concepts [22].

Nonetheless, when it comes to fictitious play as a learning procedure, these developments did not address the following basic question: How does the choice of evaluation functional shape the convergence and geometry of FP? In this paper, we study nonlinear fictitious play (NL-FP), which retains the empirical-belief updates of classical FP but evaluates each action through a general, possibly nonlinear functional of its induced payoff distribution (Equation (II.7)). This formulation includes classical FP as a special case, and allows us to examine which properties of the evaluation functional preserve convergence and which can undermine it. The following fundamental questions regarding NL-FP naturally arise:

  1. Does nonlinear FP converge in 2×n2 \times n games under general evaluations?

  1. When does nonlinear FP converge, and when can convergence fail?

  1. When convergence occurs, where does nonlinear FP converge to?

Towards answering these questions, we focus on the canonical model of learning in 22-action games, i.e., games in which at least one player has two actions. The convergence of classical FP in nondegenerate 2×n2 \times n games [5], together with the nonconvergence result in 3×33 \times3 games [7], makes the former a natural setting and starting point. We begin by introducing ρ\rho-Nash equilibrium (ρ\rho-NE), where ρ=(ρ1,ρ2)\rho= (\rho^1, \rho^2) denotes the players’ evaluation functionals. This notion generalizes the standard Nash equilibrium and reduces to it when both players evaluate payoffs by expectation. In 2×22 \times2 games, the response of each player is determined by a scalar advantage function. We first show that the single-crossing property (SCP) of the advantage function preserves the geometry of classical FP, establishing the convergence of NL-FP. We further identify several sufficient conditions on evaluation functionals, under which the advantage function satisfies SCP. However, we also show that several functionals commonly used in finance and decision theory indeed violate SCP. Hence, one of our major contributions is to further establish the convergence of NL-FP even when SCP fails. Furthermore, we also show that such positive convergence results can be fragile beyond 2×22 \times2 Continuous-time positive results use the selection rules stated in the respective results; the finite-grid analysis uses equilibrium stopping. Discrete-time positive results use pure best responses, with the tie-breaking restrictions stated in the respective results.

GameConditionsContinuousDiscreteReference
2×22 \times2Strict single-crossing property (Definition III.1)✓✓Prop. III.5
2×22 \times2Single-crossing property (Definition III.1)✓✓Prop. III.7
2×22 \times2Finite-crossing (Assumption IV.1)✓✓Thms. IV.2, V.1
2×32 \times3CVaR row player and risk-neutral column player✗—Prop. VI.1
2×n2 \times nFinite-crossing and nondegeneracy (Assumptions VI.4 and VI.5)✓✓Thms. VI.6, VI.9

Table 1. Convergence of nonlinear fictitious play. ✓: convergence to a ρ\rho-NE under the stated core assumptions; ✗: nonconvergence can occur; —: not established in this work.

games, even when only the two-action player is risk-averse. We summarize our key contributions as follows, and list our main results in Table 1.

  • We identify the SCP of advantage functions as a key condition for preserving the convergence of classical FP [4], and provide sufficient conditions on the evaluation functionals to identify SCP. In particular, we verify the SCP of several broad classes of nonlinear functionals. However, we show that SCP may not hold for several functionals common in finance and decision theory.

  • We prove the convergence of the continuous-time NL-FP dynamicsand the discrete-time NL-FP iterates under a finite-crossing condition in 2×22 \times2 games, via a novel geometric analysis of a finite planar grid.

  • We show that the convergence of continuous-time NL-FP in 2×n2 \times n games does not hold in general, by constructing a nonconvergent counterexample where the two-action player uses CVaR in a 2×32 \times3 game, in sharp contrast to the 2×22 \times2 case.

  • We further identify a finite-crossing condition that ensures convergence of the continuous-time NL-FP dynamics and the discrete-time NL-FP iterates in 2×n2 \times n games when the row best response depends on a linear statistic of the opponent’s strategy. Our geometric analysis reveals the basin–separatrix landscape and, under stronger simple interior column-crossing assumptions, provides an alternative proof of the classical FP convergence result [5].

Organization. The rest of the paper is organized as follows. Section II introduces the game model, nonlinear evaluation functionals, ρ\rho-NE, and the continuous-time dynamics and discrete-time iterates of NL-FP. § 4 studies the convergence of NL-FP under the SCP in 2×22 \times2 games. Section IV establishes the convergence of continuous-time NL-FP under the finite-crossing assumption and characterizes the global landscape and local geometry in 2×22 \times2 games. § 6 proves the convergence of discrete-time NL-FP under the finite-crossing assumption in 2×22 \times2 games. Section VI extends the analysis to 2×n2 \times n games, presenting a counterexample in a 2×32 \times3 game, a new geometric analysis of classical FP in 2×n2 \times n games, and sufficient conditions for continuous- and discrete-time NL-FP convergence in 2×n2 \times n games. § 8 concludes the paper. We defer a detailed discussion of related work to Appendix § 9.

Preliminaries

Preliminaries

Notation. Let a<ba < b be two real numbers. We denote by D([a,b])\mathcal{D}([a,b]) and D\mathcal{D} the space of all cumulative distribution functions (CDFs) supported on [a,b][a,b] and the space of all CDFs on the reals, respectively. For a positive integer nn, [n]:={1,2,⋯ ,n}[n] := \{1,2,\cdots,n\}; we also set [0]:=∅[0] := \varnothing. Let Δn:={v∈Rn∣1nTv=1,v≥0n}\Delta_n := \{v \in\mathbb{R}^n \mid\mathbf{1}_n^{\mathsf{T}}v = 1, v \geq\mathbf{0}_n\} be the probability simplex in Rn\mathbb{R}^n. 1n\mathbf{1}_n and 0n\mathbf{0}_n denote the nn-dimensional vector whose components are all ones and all zeros, respectively. eie_i denotes the one-hot vector whose ii-th component is 1. We denote by (u,v;p)(u,v;p) a two-point distribution where uu occurs with probability pp and vv otherwise. For a vector v∈Rn\mathbf{v} \in\mathbb{R}^n and q∈Δn\mathbf{q} \in\Delta_n, we use (v,q)(\mathbf{v},\mathbf{q}) to denote the discrete probability distribution ∑i∈[n]qiδvi\sum_{i\in[n]}q_i\delta_{v_i}. For two random variables X∼FX \sim F and Y∼GY \sim G, we say that YY dominates XX if ∀x∈R\forall x \in\mathbb{R}, F(x)≥G(x)F(x) \geq G(x), and we write Y⪰XY \succeq X or X⪯YX \preceq Y. We write X=dYX \overset{d}{=} Y if XX and YY have the same probability distributions. We denote the support of a probability distribution FF by supp⁡(F)\operatorname{supp}(F). In the following, we start with introducing the key setting: 2×22 \times2 and 2×n2 \times n bimatrix games.

Matrix games

2×22 \times2 bimatrix games. We consider a 2×22 \times2 bimatrix game GG:

L (w.p. qq)R (w.p. 1−q1-q)
U (w.p. pp)(a,e)(a,e)(b,f)(b,f)
D (w.p. 1−p1-p)(c,g)(c,g)(d,h)(d,h)

where p∈[0,1]p \in[0,1] and q∈[0,1]q \in[0,1] denote the probability of choosing U for player 1 and L for player 2, respectively. For fixed q∈[0,1]q \in[0,1], player 1’s payoff distributions are (a,b;q)(a,b;q) under U and (c,d;q)(c,d;q) under D, respectively. For fixed p∈[0,1]p \in[0,1], player 2’s payoff distributions are (e,g;p)(e,g;p) under L and (f,h;p)(f,h;p) under R, respectively.

2×n2 \times n bimatrix games. Let (A,B)(A,B) be a two-player bimatrix game where A∈R2×n,B∈Rn×2A \in\mathbb{R}^{2 \times n}, B \in\mathbb{R}^{n \times2} are the deterministic payoff matrix for player 1 and player 2, respectively. For convenience, we write A=(A1⋅,A2⋅)T,B=(Bj⋅)j∈[n]A = (A_{1\cdot}, A_{2\cdot})^{\mathsf{T}}, B = (B_{j\cdot})_{j\in[n]}, where Ai⋅∈Rn,Bj⋅∈R2A_{i\cdot} \in\mathbb{R}^n, B_{j\cdot} \in\mathbb{R}^2 are the transposed row vectors of AA and BB, respectively. Let p∈[0,1]p \in[0,1] denote the probability with which player 1 uses row action 1, and let q∈Δn\mathbf{q} \in\Delta_n be player 2’s mixed strategy. The payoff distribution for player 1 choosing action i∈{1,2}i \in\{1,2\} if player 2 chooses mixed strategy q\mathbf{q} is (Ai⋅,q)(A_{i\cdot},\mathbf{q}). Analogously, (Bj1,Bj2;p)(B_{j1},B_{j2};p) is the payoff distribution for player 2 choosing action j∈[n]j \in[n] if player 1 chooses action 1 with probability pp.

We introduce the setup for two-player strategic-form games, which will be useful in defining the best-response correspondence and Nash equilibrium.

Two-player strategic-form games. A two-player strategic-form game is specified by the tuple G=⟨A1,A2,r1,r2⟩G = \langle A^1,A^2,r^1,r^2\rangle. Here AiA^i is the finite action set of player ii, and ri:A→Rr^i : \mathcal{A} \to\mathbb{R} is the payoff function of player ii, where A:=A1×A2\mathcal{A} := A^1 \times A^2. The two players simultaneously choose actions ai∈Aia^i \in A^i, forming the action profile a:=(a1,a2)a := (a^1,a^2), after which player ii receives payoff ri(a1,a2)r^i(a^1,a^2). We allow each player to independently randomize over her actions. A mixed strategy of player ii is a probability distribution πi∈Δ(Ai)\pi^i \in\Delta(A^i), where πi(ai)\pi^i(a^i) denotes the probability of choosing action aia^i. The mixed-strategy profile of the two players is denoted by π:=(π1,π2)\pi:= (\pi^1,\pi^2). The random payoff for player ii choosing pure action aia^i if the opponent player playing mixed strategy π−i\pi^{-i} is ri(ai,A−i)r^i(a^i,A^{-i}), A−i∼π−iA^{-i}\sim\pi^{-i}, where the randomness comes from π−i\pi^{-i}. The payoff distribution of ri(ai,A−i)r^i(a^i,A^{-i}) is given by ri(ai,A−i)∼(ri(ai,⋅),π−i)r^i(a^i,A^{-i})\sim(r^i(a^i,\cdot),\pi^{-i}).

Two-player games with nonlinear evaluation functionals

References

  1. [1]G. W. Brown, “Iterative solution of games by fictitious play,” in Activity Analysis of Production and Allocation, ser. Cowles Commission Monograph, T. C. Koopmans, Ed. New York: John Wiley & Sons, 1951, no. 13, pp. 374–376.
  2. [2]J. Robinson, “An iterative method of solving a game,” Annals of Mathematics, vol. 54, no. 2, pp. 296–301, 1951.DOI
  3. [3]K. Miyasawa, “On the convergence of the learning process in a 2×2 non-zero-sum two-person game,” Econometric Research Program, Princeton University, Research Memorandum 33, Oct. 1961.
  4. [4]A. Metrick and B. Polak, “Fictitious play in 2 × 2 games: A geometric proof of convergence,” Economic Theory, vol. 4, no. 6, pp. 923–933, 1994.DOI
  5. [5]U. Berger, “Fictitious play in 2 × n games,” Journal of Economic Theory, vol. 120, no. 2, pp. 139–154, 2005.DOI
  6. [6]D. Monderer and L. S. Shapley, “Fictitious play property for games with identical interests,” Journal of Economic Theory, vol. 68, no. 1, pp. 258–265, 1996.DOI
  7. [7]L. S. Shapley, “Some topics in two-person games,” RAND Corporation, Research Memorandum RM-3672-PR, Jun. 1963.
  8. [8]J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior. Princeton University Press, 1944.
  9. [9]J. Nash, “Non-cooperative games,” Annals of Mathematics, vol. 54, no. 2, pp. 286–295, 1951.
  10. [10]J. C. Harsanyi, “Games with incomplete information played by ‘Bayesian’ players, I–III: Part I. The basic model,” Management Science, vol. 14, no. 3, pp. 159–182, 1967.
  11. [11]P. Artzner, F. Delbaen, J.-M. Eber, and D. Heath, “Coherent measures of risk,” Mathematical Finance, vol. 9, no. 3, pp. 203–228, 1999.
  12. [12]H. Föllmer and A. Schied, “Convex measures of risk and trading constraints,” Finance and Stochastics, vol. 6, no. 4, pp. 429–447, 2002.DOI
  13. [13]A. Ben-Tal and M. Teboulle, “An old-new concept of convex risk measures: The optimized certainty equivalent,” Mathematical Finance, vol. 17, no. 3, pp. 449–476, 2007.
  14. [14]R. T. Rockafellar and S. Uryasev, “Optimization of conditional value-at-risk,” The Journal of Risk, vol. 2, no. 3, pp. 21–41, 2000.DOI
  15. [15]J. Estrada, “Mean-semivariance behavior: Downside risk and capital asset pricing,” International Review of Economics & Finance, vol. 16, no. 2, pp. 169–185, 2007.
  16. [16]C. Acerbi, “Spectral measures of risk: A coherent representation of subjective risk aversion,” Journal of Banking & Finance, vol. 26, no. 7, pp. 1505–1518, 2002.DOI
  17. [17]J. Quiggin, “A theory of anticipated utility,” Journal of Economic Behavior & Organization, vol. 3, no. 4, pp. 323–343, 1982.DOI
  18. [18]A. Tversky and D. Kahneman, “Advances in prospect theory: Cumulative representation of uncertainty,” Journal of Risk and Uncertainty, vol. 5, no. 4, pp. 297–323, 1992.
  19. [19]A. Fiat and C. Papadimitriou, “When the players are not expectation maximizers,” in Proceedings of the International Symposium on Algorithmic Game Theory, ser. Lecture Notes in Computer Science, vol. 6386. Springer, 2010, pp. 1–14.
  20. [20]O. Slumbers, D. H. Mgunі, S. B. Blumberg, S. McAleer, Y. Yang, and J. Wang, “A game-theoretic framework for managing risk in multi-agent systems,” in Proceedings of the 40th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 202. PMLR, 2023, pp. 32 059–32 087.arxiv.org/abs/2205.15434
  21. [21]S. R. Phade and V. Anantharam, “Learning in games with cumulative prospect theoretic preferences,” Dynamic Games and Applications, vol. 13, no. 1, pp. 265–306, 2023.
  22. [22]E. Mazumdar, K. Panaganti, and L. Shi, “Tractable multi-agent reinforcement learning through behavioral economics,” in International Conference on Learning Representations, vol. 2025, 2025, pp. 18 058–18 072.
  23. [23]M. Frittelli and E. Rosazza Gianin, “Putting order in risk measures,” Journal of Banking & Finance, vol. 26, no. 7, pp. 1473–1486, 2002.DOI
  24. [24]R. A. Howard and J. E. Matheson, “Risk-sensitive Markov decision processes,” Management Science, vol. 18, no. 7, pp. 356–369, 1972.DOI
  25. [25]H. Föllmer and A. Schied, Stochastic Finance: An Introduction in Discrete Time, 2nd ed. Walter de Gruyter, 2004.
  26. [26]S. Mohammadi, X. Gao, and K. Zhang, “Entropic risk-sensitive evolutionary learning and equilibrium selection in coordination games,” arXiv preprint arXiv:2609.08677, 2026. [Online]. Available: https://arxiv.org/abs/2609.08677
  27. [27]R. T. Rockafellar and S. Uryasev, “Conditional value-at-risk for general loss distributions,” Journal of Banking & Finance, vol. 26, no. 7, pp. 1443–1471, 2002.DOI
  28. [28]N. Kartik, S. Lee, and D. Rappoport, “Single-crossing differences in convex environments,” The Review of Economic Studies, vol. 91, no. 5, pp. 2981–3012, 2024.arxiv.org/abs/2212.12009
  29. [29]J. Estrada, “Mean-semivariance optimization: A heuristic approach,” Journal of Applied Finance, vol. 18, no. 1, pp. 57–72, 2008.DOI
  30. [30]T. Pham Dinh and Y.-S. Niu, “An efficient DC programming approach for portfolio decision with higher moments,” Computational Optimization and Applications, vol. 50, no. 3, pp. 525–554, 2011.
  31. [31]R. Zhou and D. P. Palomar, “Solving high-order portfolios via successive convex approximation algorithms,” IEEE Transactions on Signal Processing, vol. 69, pp. 892–904, 2021.arxiv.org/abs/2008.00863
  32. [32]M. O. Sayin, F. Parise, and A. Ozdaglar, “Fictitious play in zero-sum stochastic games,” SIAM Journal on Control and Optimization, vol. 60, no. 4, pp. 2095–2114, 2022.arxiv.org/abs/2010.04223
  33. [33]A. Ozdaglar, M. O. Sayin, and K. Zhang, “Independent learning in stochastic games,” in Proceedings of the International Congress of Mathematicians 2022, D. Beliaev and S. Smirnov, Eds. EMS Press, 2023, vol. 7, pp. 5340–5373.arxiv.org/abs/2111.11743
  34. [34]C. Park, K. Zhang, and A. Ozdaglar, “Multi-player zero-sum Markov games with networked separable interactions,” in Advances in Neural Information Processing Systems, vol. 36. Curran Associates, Inc., 2023, pp. 37 354–37 369.arxiv.org/abs/2307.09470
  35. [35]M. O. Sayin, K. Zhang, and A. Ozdaglar, “Fictitious play in Markov games with single controller,” in Proceedings of the 23rd ACM Conference on Economics and Computation. Association for Computing Machinery, 2022, pp. 919–936.arxiv.org/abs/2205.11389
  36. [36]O. Unlu, E. Bitar, and F. Parise, “Fictitious play in Markov potential games,” SSRN Working Paper 6712798, 2026. [Online]. Available: https://ssrn.com/abstract=6712798DOI
  37. [37]V. P. Crawford, “Equilibrium without independence,” Journal of Economic Theory, vol. 50, no. 1, pp. 127–154, 1990.DOI
  38. [38]E. Dekel, Z. Safra, and U. Segal, “Existence and dynamic consistency of Nash equilibrium with non-expected utility preferences,” Journal of Economic Theory, vol. 55, no. 2, pp. 229–246, 1991.DOI
  39. [39]K. Ritzberger, “On games under expected utility with rank dependent probabilities,” Theory and Decision, vol. 40, no. 1, pp. 1–27, 1996.
  40. [40]K. Keskin, “Equilibrium notions for agents with cumulative prospect theory preferences,” Decision Analysis, vol. 13, no. 3, pp. 192–208, 2016.DOI
  41. [41]S. R. Phade and V. Anantharam, “On the geometry of Nash and correlated equilibria with cumulative prospect theoretic preferences,” Decision Analysis, vol. 16, no. 2, pp. 142–156, 2019.
  42. [42]Y. Zhang and E. Mazumdar, “Provably convergent actor-critic for MARL through risk-aversion,” in Proceedings of the 43rd International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 306. PMLR, 2026, pp. 157 700–157 762.arxiv.org/abs/2602.12386
  43. [43]C. Berge, Topological Spaces: Including a Treatment of Multi-valued Functions, Vector Spaces and Convexity. Edinburgh and London: Oliver and Boyd, 1963, translated by E. M. Patterson.
  44. [44]S. Kakutani, “A generalization of Brouwer’s fixed point theorem,” Duke Mathematical Journal, vol. 8, no. 3, pp. 457–459, 1941.DOI
  45. [45]T. M. Apostol, Calculus: Multi-Variable Calculus and Linear Algebra, with Applications to Differential Equations and Probability, 2nd ed. Wiley, 1969, vol. 2.

Paper details

vlnc:W_e5athffq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6.0 Astra, AI assistance

View statement
Looking for related papers…
Contents