Exponential Lower Bounds for Fictitious Play in Potential Games
Authors: Ioannis Panageas
Nikolas Patris
Stratis Skoulakis
Volkan Cevher
Venue: NeurIPS 2023 poster (2023)
Keywords: fictitious play
convergence rate
potential games

Abstract: Fictitious Play (FP) is a simple and natural dynamic for repeated play with many applications in game theory and multi-agent reinforcement learning. It was introduced by Brown and its convergence properties for two-player zero-sum games was established later by Robinson. Potential games [Monderer and Shapley 1996] is another class of games which exhibit the FP property [Monderer and Shapley 1996], i.e., FP dynamics converges to a Nash equilibrium if all agents follows it. Nevertheless, except for two-player zero-sum games and for specific instances of payoff matrices [Abernethy et. al. 2021] or for adversarial tie-breaking rules [Daskalakis and Pan, 2014], the \textit{convergence rate} of FP is unknown. In this work, we focus on the rate of convergence of FP when applied to potential games and more specifically identical payoff games. We prove that FP can take exponential time (in the number of strategies) to reach a Nash equilibrium, even if the game is restricted to \textit{two agents}. To prove this, we recursively construct a two-player coordination game with a unique Nash equilibrium. Moreover, every approximate Nash equilibrium in the constructed game must be close to the pure Nash equilibrium in $\ell_1$-distance.

Exponential Lower Bounds for Fictitious Play in Potential Games
Ioannis Panageas' University of California, Irvine ipanageaBics eci.edu
Nikolas Patris* University of California, Irvine npatrisQuci,. edu
Stratis Skoulakis" LIONS, EPFL
Volkan Cevher LIONS, EPFL
efstratios. hwwrrttoo..stoulakieeeee.......
volkan. cehher@ppllc
Abstract
Fictitious Play (FP) is a simple and natural dynamic for repeated play with many applications in game theory and multi-agent reinforcement learning. It was intro- duced by Brown 4 and convergence properties for two-player zero-sum games was established later by Robinson [22]. Potential games [19] is another class of games which exhibit the FP property 18), i.e., FP dynamics converges to a Nash equilibrium if all agents follows it. Nevertheless, except for two-player zero-sum games and for specific instances of payoff matrices [1] or for adversarial tie-breaking rules [9], the convergence rate of FP is unknown. In this work, we focus on the rate of convergence of FP when applied to potential games and more specifically identical payoff games. We prove that FP can take exponential time (in the number strategies) to reach a Nash equilibrium, even the game is restricted two agents and for arbitrary tie-br tie-breaking rules. To prove this, recursively construct a two-player coordination game with a unique Nash equilibrium. More- over, every approximate Nash equilibrium in the constructed game must be close to the pure Nash equilibrium in lj disttannce.
Introduction
In 1949 Brown
proposed uncoupled dynamics called fictitious play so capture the behavior of selfish agents engaged in a repeatedly-player game. Fictitious play assumes at round t= 1, each agent selects arbitrary action. At each round f 2, each player plays best response pure action to the opponents' empirical strategy; empirical strategy is defined to be the average the past chosen strategies.
Due to its simplicity and natural behavioral assumptions, fictitious play is one of the most seminal and well-studied game dynamics [7]. Despite the fact that fictitious play does not converge to Nash equilibrium (NE) general normal-fome games, there are several important classes games at which the empirical strategies always converge that in the case of two-player zero-sum games, the empirical strategy profiles converge to min-max equilibrium of the game; Robinson's proof use smart inductive argument the number of strategies of the game. Later, Monderer and Shapley [8] established that the case N-player potential games, the empirical strategies also converge NE. Summing up, the following theorem is true:
NE. In her seminal work, Robinson 22] showed
'qqual contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Informal Theorem 122.18 In hwo-player zero-sum and N --plyer potential games, the empirical strategy profiles of fictitious play converge to a NE for any initialization and tiebbrekiing ruld
The above convergence results are asymptotic in the sense that they do not provide guarantees on the number of rounds needed by fictitious play to reach approximate NE. Karlin [3] conjectured
that in the case of two-player zero-sum games, fictitious play requires ((1/=²) rounds to reach an e-approximate NE. Daskalakis et. al. [9] disproved the strong version of Karlin's conjecture by providing an adversarial tie-breaking rule for which fictitious play requires exponential number of rounds (with respect to the number of strategies) order to converge an e-approximate NE. On the other hand, for the case of potential games and despite the foundational work of Monderer et al. [88] no lower bound results have been established. Therefore, the central focus of our work address the following question."
Q: Does fictitioos play in potential games admit convergence to an upproximate NE with rates that depend polynomially the number of actions and the desired accuracy?
Our contributions Our work provides a negative answer on the above question. Specifically, we present hwo-player potential game for which fictitious play requires super-exponential time with respect to the number actions to reach an approximate NE.
There exists two-player potential game (more specifically both agents have identical payoffs) in which both agents admit n actions and for which fictitious play requires Q (4n ((2 2))) + =.//) rounds order reach an e-approximate NE. Moreover, the result holds for any tie- bre-breaknng rule and uniformly random initialization.
Theorem 1.1 (Main result, formally stated Theorem 3.1).
Remark 1.2. Daskalakis et al. provide an exponential lower bound on the convergence fictitious play assuming an adversarial tie-breaking rule, meaning that ties are broken in favor of slowing down the convergence rate. To this point, not known whether fictitious play with a consistent tie-breaking rule (e.g. lexicographic) converges in polynomial time not, except for special cases, c.g., diagonal payoff matrices [I]. We would like to note that our lower bound construction holds for any tie-breaking rule. The latter indicates interesting discrepancy between two-player zero-sum and two-player potential games.
Related Work The work of Daskalakis et al. [ provides a lower bound on the convergence rate of fictitious play for the case of two-player zero-sum games using an adversarial tie-breaking rule and the most closely related to Another important work is [. in which they demonstrate that when the tie-breaking rule is predetermined (c.g., using lexicographical tie-breaking). the convergence rate of fictitious play becomes polynomial in the number of strategies, specifically with rate of O (#), as Karlin's conjecture states. is important to note that this result holds true only for diagonal matrices.
Other works include the examination of fictitious play convergence for near pear-potential games 6 and the investigation of the necessary conditions that games must meet for fictitious play to converge to a NE B.. We note that neither of these works provide convergence rates for fictitious play. On the other hand, fast convergence rates of continuous time fictitious play for regular, as introduced by Harsanyi [10], potential games are established [25]. Additional works on continuous time fictitious play can be found in [21], and references there in.
Fictitious play has found various application in Multi-agent Reinforcement Learning as well (see 20 23
and (2 for a survey and references therein), extensive form games [1]. and control theory 15 14) It possesses not only an intuitive game theoretic interpretation but also other attractive properties, such as its simplicity with no need for step-size parameter. These traits have contributed to its status as a pivotal topic of study, leading to numerous works aiming to establish convergence in broader settings [16]]
2 3
Technical overview The technical overview of this paper provides high-level roadmap of the key contributions. In Section 3 we outline the steps towards proving Theorem 3.1 by recursively constructing payoff matrix of carefully crafted structural properties. In that matrix, starting from the
TTie-brakking rule when selecting between two or more different best-response actions. Due to the vastness of the literature in fictitious play, it is not possible to include all the works that have either been used or been inspired by this method.
2

---

lower-left element, the sequence of successive increments form a spiraling trajectory that converge towards the element of maximum value. We demonstrate that fictitious play has follow the same trajectory, passing through all non-zero elements, to reach the unique pure Nash equilibrium, as illustrated in Figure 2 crucial component of the proof is provided by an induction argument that emulates the movement of fictitious play and provides a super-exponentia lower bound on the number rounds needed.
Preliminaries
2.1 Notation and Definitions
Notation Let be the set of real numbers, and [n] = {1,2..... be the set of actions. We define An the probability simplex, which is the set of n-dimensional probability vectors, i... A, = {I E R" I; 2 0, Σ I; = =}. We use e; to denote the i-th elementary vector, and to refer to coordinate of vector, which a vector is referring to.
either 2; [rl. The superscripts are used to indicate the time at
Normal-form Games In a two-player normal-form game A E _= and B E Raxm where n and m are the respective pure strategies the row and the column player. If the row player selects strategy i [m]] and the column player selects strategy j E [m]. then their respective payoffs are Ai for the row player and Bij for the column player.
given a pair of payoff matrices
The agents can use randomization. A mixed strategy for the row player is probability distribution a Ap over the n rows, and a mixed strategy for the column player a probability distribution y E Am over the m columns. After the row player selects mixed strategy E A.. and the column player selects mixed strategy y E Am. their expected payoffs are x. Ay and x By, respectively.
Potential Games A two-player potential game is class of games that admit a unique function 2 referred to as a potential function, which captures the incentive of all players to modify their strategies. In other words, if a player deviates from their strategy, then the difference in payoffs is determined by a potential function evaluated at those two strategy profiles. We can express this formally follows:
Definition 2.1 (Two-player Potential Game). For any given pair of strategies (r, y) and a pair of unilateral deviations x' by the row player and y by the column player, the difference their utility is equivalent to the difference in the potential function.
(z') Ay- - x Ay (br', v) ((x,8) and x A x. T Ty - v²) (( v)
Remark 2.2. We note + is a function that characterizes the equilibria of the game as the strategy profiles that maximize the potential function.
In this work, we focus on a specific type of potential games called identical payoff games, where both players receive the same payoff.
Definition 2.3 (Identical Payoff Games). A two-player normal-fomn game (A, B) is called identical B.
payoff if and only
In this scenario, it is apparent that the potential function is given by 4(x, v) = Ayy Finally we provide the definition of an approximate NE.
Definition 2.4 (e-Nash Equilibrium). strategy profile (x*,n") E An Am is called approximate NE and only if
(x*) T Ay 2 x Ay" -e VI A. and (x)) By 2 (x*) By
Vy E Am
In words, approximate Nash equilibrium is strategy profile in which no player improve their payoff significantly by unilaterally changing their strategy, but the strategy profile may not necessarily satisfy the precise definition of Nash equilibrium.
Remark 2.5. We highlight two special cases of the cNNE Firstly, when is equal to zero, it is referred to as an exact Nash equilibrium. Secondly, when the support of strategies is of size 1, is called pure Nash equilibrium. It is worth noting that potential games always admit pure NE.
3

---

2.2 Fictitious Play
Fictitious play natural uncoupled game dynamics at which each agent chooses best response to their opponent's s empirical mixed strategy. Since there might be several best response actions at given round, fictitious play might contain different sequences play; see Definition 2.6
Definition 2.6 (Fictitious Play). An infinite sequence of pure strategy profiles
(10), )(),, (f(0) ).. ..... called fictitious play sequence if and only if at each round 2
1-
L-
10 E argmax
Σ Agu ie(n =
and jr aaggax jE(m]
B
==1
The empirical strategy profile of row and column player time T is defined a(3) 125=11(0))) and gi() = E egt)) where eq0;, Eyt the elementary basis vectors. Definition 2.7 (Cumulative utility vector). For an infinite sequence of pure strategy profiles (())))....... (())), the cumulative utility vectors of the row and column player at round t 2 1 are defined as,
[-1 R Σ Aejos and C
1-1 Σ T B.
Remark 2.8. Fictitious play assumes that each agent selects at each round / E [7] a strategy with maximum cumulative utility. The latter decision-making algorithm also known Follow the Leader. We remark that the latter alternative interpretation provides direct generalization of fictitious play in N-player games.
In their seminal work, Monderer et al. 18 established that in case of identical payoff games the empirical strategies of any fictitious play sequence converges asymptotically to a NE.
Theorem 2.9 (118). Let a fictitious play sequence (()) ( ( ...)).
an identical
payoff game described with matrix A. Then, there exists round T such that for any 2 T the empirical strategy profile (ā(() ()) converges to NE with rate of l/t.
On the positive side, Theorem 2.9 establishes that any fictitious play sequence converges to a Nash equilibrium in the case of potential games On the negative side, Theorem 2.9 does not provide any convergence rates, since the round T* depends on the specific fictitious play sequence and its dependence on the number of strategies is rather unclear.
3 Main Result
In this section, we outline the steps towards proving Theorem 3.1 as it is stated below, Firstly, we introduce a carefully constructed payoff matrix A of size n x n and analyze its structural properties in Section 3.1 Next, in Section 3.2) we investigate the behavior of fictitious play when the game is an two-player identical payofi game with this matrix A. We also present set of key statements that necessary for proving the main theorem. Finally, in Section 3.3 fundamental Lemma
provide proof for the
Theorem 3.1. Let an identical payoff game defined with the matrix of size n x n and consider any fictitious play sequence (i j()), )..)....,, (()),. with (it)) (n, 1). In case the empirical strategy profile (a(T), ()) is e-approximate Nash equilibrium then it holds
T20 Ω (2 2)1)
n
Moreover, the lower bound T is independent of the tie-breaking rule. Finally, the initialization is chosen uniformly at random, then the expected number of rounds to reach an e-approximate Nash
equilibrium ((n[n/ 21t)* +1/n/t
2
For the sake of exposition, we have stated Theorem 2.9 only for the case of identical payoff games. However. remark that the same theorem holds for general N player potential games.

---

(2 (2+2)
0
(= +
3)
2
3
0
0
7
0
(2)
K
(2
0
(0)
10
0
9
(z +
4
(z 1)
0
0
0
Recursive construction of
(b) An example for and
3.1 Construction and Analysis the Payoff Matrix A
We begin by introducing our recursive construction for the payoff matrix, which we use to establish the formal statement of Theorem 3.1
Definition 3.2. For any 0 and even, consider the following matrix K=()).
+ + 1. For n = 2, k²)) = ++1 0
2. For n 2 4,
(2) = 2 and (x) for j & {1)-
Row n.
(x)(2) = = (=) 2 and Ki}(2) = 0 for any j $ (1,n).
Column 1
(=)(=) = 2, (x) = = and Kzy(2) = 0 for j $ (1,
Row
(z) = + 33 K (a (2) = 4 and Kn (2) = 0 for j {1, - 1}.
Column
For all i,j E f2...., 11 x f2..... . 1}. KTy K 4
In Figures la and lb provide schematic representation of Definition 3.2 and an illustrative example for n and z = 0. For the sake of simplicity, we have intentionally omitted the remaining zeros in the outer rows, and columns of the matrix.
The construction of the payoff matrix exhibits an interesting circular pattern, which begins at the lower left corner and extends along the outer layer of the matrix. More specifically. the first increment occurs in the same column the starting point, i.e., position (1, 1) on the first row. The pattern then proceeds to the next greater element on the same row but different column, i.e., at position (1, n), and the last increment before entering the inner sub-matrix is located on the same column but on the (n 1)-th row.
Sequence of increments: (n, 1) + (1, - (1, (n 1, (n 1,1)
Km~2(s+4)
The increments have been carefully selected ensure that there are alternating changes in row and column when starting from the lower-left corner and following the successive increments, until reaching the sub-matrix in the center. Once inside the sub- mabrix, similar pattern continues. As we will explore later on, the structure of the payoff dictates the behavior of fictitious play. We denote the payoff matrix under consideration as A, which defined as A K,, (0). The subsequent statements establish the key properties of A.
Observation 3.3 (Structural Properties of matrix A). Let the matrix K*((), then for
{0, ..... 2 1} the following hold:
The only elements with non-zer values in column + 1 are located at positions i and n and have values 4i and 4i respectively.
The only non-zero elements of row i i+ 1 are located at positions i and i, and have values 4i + 2 and 4i + 3, respectively.
The only non-zero elements of column i are located positions and n and have values 4i + 3 and 4i + respectively.

---

The only non-zero elements of row - are located at positions i + 1 and n - i + 1, and have values 4i and 4i, respectively.
Observation 3.4. The maximum value of A is 2n 2 and is located at the entry (2 +1). 1).
Proposition 3.5. For any non-zero element in the matrix A, there is at most one non-zero element that greater and at most one non-zero element that smaller in the same column or row.
Proof. By Observation 3.3 each row and column of matrix A contains at most two non-zero elements that are necessarily different to each other. Thus. if (i.j) is non-zero element of A, there can be at most two additional non zero elements in row and column j combined. Moreover, at most one of these elements can be greater and at most one can be smaller.
One of the central components of the main theorem is presented below. Lemma 3.6 establishes that in an identical payoff game with matrix A, any approximate Nash equilibrium must distribute the majority of its probability The proof of this theorem is based solely on the structural properties presented in Observation 3.3 and is provided in the Appendix.
the maximum element in A, which located the entry (5 2 +1).
Lemma 3.6 (Unique e²-NE). Let O (1t)) and consider an e2 E-approximate Nash Equilibrium
(xx" .y"). Then the following hold,
21 ne and V 2 72
Lemma 3.6 not only establishes that the only approximate Nash equilibrium of the ceentical-payoff game with matrix A corresponds to the strategies (H. , but it also implics that this is the only exact Nash equilibrium (i.e., 0). This observation follows from Observation 3.4 which states that the entry (5) z + 1) corresponds to a maximum value A and hence it is Nash equilibrium as it dominates both the row and the column that it belongs to. We can formally state this observation as follows.
Corollary 3.7 (Unique pure NE). In an identical payyof game with payoff matrix A, there exists a unique pure Nash equilibrium at ( 22
3.2 Lower Bound for Fictitious Play in a Game with Matrix
In this subsection, we present the proof of Theorem 3.1
To achieve this, we first prove that fictitious
play requires super-exponential time before placing a positive amount of mass in entry ( , 2 + 1). This result is established by our main technical contribution of the subsection, which is Lemma 3.8
Lemma 3.8. Let an clentical-payonn game with payoff matrix A and a fictitious play sequence (())),))) a round T such that:
)(.)),.... (g(t), j(0)),. with (i(1), (())) = (n, 1). Then, for all f = {0.... n 1] there exists
1. the agents play the strategies (n - l, for the first time,
2. all rows [f+ - 8 1] admit 0 cumulative utility, R(Tr) = 0,
3. all columns E [E 2, admit O cumulative utility, ((T)) O.
Moreover for é 22 2, the cumulative utility of row n - at round T is greater than
(Tx)) 2
-) -
(T-1) while
(TT) 24
(2)
Using Lemma 3.8 we are able to establish that for very long period of time the row player has never played row a and that the column player has never played column 2 + 1.
2
Lemma 3.9 (Exponential Lower Bound). Let an identical-payae game with matrix and a ficti- tious play sequence (i(2), (((2),(() j(),.. .,(().,,) ( with (i(1), (()), (n, 1). case (iT)) j(()) 1) then T > ((12 -))

---

j
i'
i
i'
Figure 2: This figure shows the spiral trajectory generated by the fictitious play dynamic in a game with matrix A. The starting point is the lower-left element, and as the dynamic progresses, it visits all non-zero elements in ascending order of value.
we can guarantee the existence of round T == n when the players choose the strategy profile (2 + 1, 2. for the first time. In addition, round T*, holds that R 0 and c(T")
Proof. Based on Lemma 3.8
(T") = 0. The latter condition ensures that the strategy profile
(2. + 1) has not been played up to time T
As indicated by Observation 3.3 row has non-zero entries at columns 3/2 and + 1. Therefore, if the cumulative utilities R/ at time T zero, this implies that neither of these columns has been chosen up to that point. By the same reasoning, column 2 + 1 has non-zero entry only at row 2
indicating that this row has not been chosen as well.
In order to continue, we require an estimate of the duration during which the strategy profile + 2) will be played. Observation 3.3 guarantees that the utility vector of the player is the following.
Ae = (0, 0. 2n 2. 2n - 3. S.O......)
7+1
We can combine this information with the fact that R RTT) n/2+1 # O, R(T") = 0, and that the respective entries in the payoff vector 33) of the row player differ by exactly one. This allows us conclude that will take at least (((T") iterations for the cumulative utilities to become equal, i.e Rg = Rg Therefore, the lower bound on the number of iterations holds regardless of the tie-breaking rule.
Now, if at any time the agents play the strategy profile (((T),(TT) (2 2 + 1). we can conclude
that T' R Using Equation of Lemma 3.8 we obtain:
T> R!T!
2
16
(e 1) 11)
((T)) 2 Ω 4th (6 22))
t=2
Now that we have established the necessary technical result in Lemma 3.9 we are ready to present the proof of Theorem 3.1
Proof of Theorem 3.1 Let T 2 denote the first time at which ((0))(0) = - + +1). For any
1 < T 1, it holds that ((() 1 0. Thus, Lemma 3.6 implies that (a(()) ((0) is not an approximate NE. On the other hand, at each round / 2 T* we are ensured that (1) (2)
97 converges
to 1 with rate 1/t. Applying Lemma 3.6 for e Ve we get that if (a(t) (())) is an e-NE then evident that, even with uniformly random
t 2 T' nipe 2 Ω (4 (n/2- 2)!) nye" initialization, the probability of selecting (n, 1) as the starting point for fictitious play is 1/n2 and so the claim of the theorem follows.
1.

---

As previously hinted, the structure of the payoff matrix dictates the sequence of strategy profiles chosen by fictitious play. The sequence of strategy switches alternates between rows and columns. Continuing with the example from the previous paragraph, let us assume that the row player made 16+2 16+3
16+2
1643
11+2
1443
16+2
1--3
1144
16+4
1144
11-1
1
48
4i+1
44
4i+1 48
16+1
4i
(a) E [TP: TH)
(b) t E [T7, T?)
(c) E (T?, 7
(d) E (TY, 7;4)
Figure 3: The figure illustrates the active row and column player for each time period, with the played strategy highlighted in purple and the corresponding payoff vectors of the row and column player highlighted in green. Additionally, the time period of each played strategy is indicated for clarity.
3.3 Strategy Switches and Proof of Lemma 3.8
This subsection is dedicated to presenting the proof of Lemma 3.8 However, before delving into the proof, we first provide additional statements that serve to shed light on the sequence of strategy profiles generated by fictitious play.
According to Proposition 3.5 if the strategy (i, is chosen by fictitious play, then either in row i or in column j. there at most one element greater than Agj. Therefore, in a subsequent round, fictitious play will necessarily choose this element as its strategy. Let i' be the row where the element of greater value is located. Intuitively, we can imagine that as fictitious play continues to play the same strategy (é. j). the payoff vector Ae, is repeatedly added to the cumulative vector of the row player. Since this vector has a greater value at coordinate i' than at coordinate i, a strategy switch will eventually occur. We state this observation in Proposition 3.10 and defer the proof to the Appendix.
Proposition 3.10 (Strategy Switch). Let (()),)()) be a strategy selected by fictitious play at round t, and (9) + ( 2). Then, in a subsequent round, fictitious play will choose the strategy of greater value that is either on row i(t) or column jit).
the most recent strategy switch from (i, to (i', .).. This implies that the element Arr is greater than Asj. as otherwise a strategy switch would not have taken place, as established in Proposition 3.10 Moreover, by Proposition 3.5 we know that there must be an element of greater value in either row i' or column j. Since Ar is greater than Aty. any element of greater value must be located in row The same reasoning applies for the case where the column player can summarize this observation by stating that if one player is the last to switch, then the other player must switch next. We formally state this in Corollary 3.11 and defer the proof to the Appendix.
the last to switch strategies. We
Corollary 3.11 (Successive Strategy Switches). Lett be round in which player changes their strategy. Then exactly one of the following statements is true:
1. If the row player changes their strategy at round t, i.e. j(t) + ((t-1), then the column player can only make the next strategy switch.
2. If the column player changes their strategy at round t, i.e. jot & j(t-1), then the row player can only make the next strategy switch.
Applying the same concept, we can observe that starting from the lower-left corner, fictitious play follows a spiral trajectory. The resulting spiral is illustrated in Figure We now proceed with the main result of this section, Lemma 3.8
Proof. Since (z(1) (2) (n,, 1) all the above claims trivially for To 1. We assume that the claim holds for and will now establish it inductively for + 1.
By the induction hypothesis, agents play strategies (n - i, + 1) at round T := T,. Furthermore, row n admits cumulative utility of R! while row i + 1 admits cumulative utility of R!TT) 0. According to Observation 3.3 the payoff vectors of the row and column agent are highlighted in
Figure 3a By combining these facts, we can establish the following.
8

---

Proposition 3.12 (Abridged; Full Version in Proposition B.3). There exists a round T; > T at which the strategy profile (i (i+1,i+ 1) for the first time, column 1 admits cumulative utility (TT))
+ +1), and C O. (4i + (R. i+1
C+1
By Proposition 3.12 at round Ti', the agents play strategies (i+1,i+1). Furthermore, the cumulative utility of column equals C 0. According Observation 3.3 the payoff vectors of the row and column agent are highlighted Figure 3b Combining these facts, we get the following:
Proposition 3.13 (Abridged; Full Version in Proposition B.4 There exists a round T? > T at which the strategy profile is (i + 1, for the first time, row i + admits cumulative utility (T.))
((T)) (4i 2)
and R R(T.) R- 0. 141
1+1
By Proposition 3.13 at round T/K the agents play strategies 11+1, i). Furthermore, the cumulative utility of row n - 1 equals to (T(?) 0. According to Observation 3.3, the payoff vectors of the row and column agent are highlighted Figure 3e By combining these facts, we get the following:
Proposition 3.14 (Abridged; Full Version in Proposition B.5 There exists round T T? at which the strategy profile is (n - (i + 1), i) for the first time, R 0.
By Proposition 3.14 at round 7, the agents play strategies (n 1, n i). the cumulative of column + 2 equals to R (2²) 0. According to Observation 3.3 the payoff vectors of the and column agent are highlighted Figure 3d By combining these facts, we can establish the following.
Proposition 3.15 (Abridged; Full Version in Proposition B.6 There exists a round T TP at which the strategy profile is (n (n-(1 (i++1) for the first time, row n i admits cumulative utility (T?) (+++1 Z (4i + 4) n-1
(TP) all rows k E [[i 1) + 1,n (i 1) - 1] admit RE(T)) 0
and all columns & [ + 1) 2, (i 1)] admit C(T:))
Proposition 3.15 establishes that there exits round T:41 T at which the strategy profile
(n (i + 1), (1
1) + is played for the first time. Furthermore, Proposition
3.15 confirms that all
admit RT[T: admit c( 0. We still need verify the the recursive relation Equation 2 By combining
rows ls E (i++))++++++1 mi+
0 and all columns {(i+1) 1 +2, n neenn-iiita (i+1))
Proposition 3.12
3.13
3.14 and33.15 we can deduce
R (T+1)
R-i-1 2 (4i 4)(4i + 3) + 2) 1)R
4 Experiments
In this section, we aim to experimentally validate our findings on a 4 x 4 payoff matrix. Our analysis focuses three key aspects: the round in which throughout the game, and the empirical strategy employed by the x player. We present the plot from the row player's perspective, which is identical to that of the column player.
strategy switch occurs, the Nash gap
In Figure 4a we provide the time steps of all strategy switches. As expected from the analysis, fictitious play visits all strategies, specifically in increasing order of their utility, to reach the pure Nash equilibrium. Moreover, Figure 4b) we observe a recurring pattern the Nash gap diagram, where the gap increases after the selection of new strategy with a higher utility and decreases until the next strategy switch. However, this pattern stops after the pure Nash equilibrium reached, which is the unique approximate Nash equilibrium in accordance with Lemma 3.8

---

Rist gno
t
player
from
to
4
11
54-
38
174
990
11
(a) Table of transitions
(b) Nash Gap
(c) Empirical strategy of player
Figure 4: The figure displays the three aspects that were analyzed in the experiments. To preserve the crucial qualitative features both diagrams, the r-axis was logarithmic scale.
5
Conclusion
summary, this paper has provided a thorough examination of the convergence rate of fictitious play within specific subset of potential games. Our research has yielded recursive rule for constructing payoff matrices, demonstrating that fictitious play, regardless of the tie-breaking rule employed, may require super exponential time to reach a Nash equilibrium even in two-player identical payoff games. This contribution to the literature differs from previous studies and sheds new light on the limitations of fictitious play in the particular class of potential games.
Limitations and Broader Impacts: Our work is theoretical nature, and we do not identify any limitations negative ethical or societal implications.
Acknowledgments
Ioannis Panageas would like acknowledge start-up grant and SF50818. This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 200021_205011, 11, by Hasler Foundation Program: Hasler Responsible AI (project number 21043) and Innovation project supported by Innosuisse (contract agreement 100.960 IP-ICT).
References
[1] D. Abernethy, K. A. Lai, and Wibisono. Fast convergence of fictitious play for diagonal payoff matrices. In D. Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 13, 2021, pages 1387- 1404. SIAM, 2021. doi: 11113//197811111766633 9781611976465.88
https:/t:://do. org arg/10.1137/1 1137/1
[2] L. Baudin and R. Laraki. Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvári, G. Niu, and S. Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 1664 1690. PMLR, 2022. UtL/ /tlpitttp///rroeeddnggs mlr. ptt.sp/eess/// baudin22a. html
[3] L. Baudin and R. Laraki. Smooth fictitious play in stochastic games with perturbed payoff's and unknown transitions. Advances in Neural Information Processing Systems, 35:20243-20256. 2022.
[4] G. W. Brown. Some notes on computation of games solutions. Technical report, RAND CORP SANTA MONICA CA, 1949.
[5] G. W. Brown. Iterative solution games by fictitious play. Act. Anal. Prod Allocation, 13(1):
374, 1951.
[6] O. Candogan, A. E. Ozdaglar, and P. A. Parrilo. Dynamics in near-potential games. Games Econ. Behav. 82:66-90 90, 2013. doi: 10. 10.10016/geeh.221..77.. htt/stts::///// :/ttops:///i.... //tp::/oo.oooo/0////////// 1016/ geb. 2013. 00.
10

---

[7] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006. ISBN 978-0-521-84108-5. doi: 10.001//3307705515566111 URL https //doi.org//a 1017 0411///009785515445559
[8] Y. Chen, X. Deng, C. Li, D. Mguni, J. Wang, X. Yan, and Y. Yang. On the convergence of fictitious play: decomposition approach. In L. D. Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 179-185, orgai.org, 2022. doi: 00.24963/jccii URL https://áos erg/10../// 104963/ijcaii. 20222/6
[9] C. Daskalakis and Q. Pan. A counter-example to karlin's strong conjecture for fictitious play. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 11 11-20. IEEE Computer Society, 2014. doi: 10.1 D0.100//OCS.200 2014.10.. URI.ttps:: http:://ddoooorrpp//
1109/FOCS. 2014.
[10] J. C. Harsanyi. Oddness of the number of equilibrium points: a new proof. International Journal of Game Theory, 2:235-250, 1973.
[11] Heinrich, M. Lanctot, and D. Silver. Fictitious self-play in extensive-form games. In F. R. Bach and D. M. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 805-813, JMLR.org, 2015. URL BtLphttp/ppprcceeding mlr press/v37/heing iew.n html
[12] J. Hofbauer and W. H. Sandholm. On the global convergence of stochastic fictitious play. Econometrica, 2066):2265-2294, 2002.
[13] S. Karlin. Mathematical Methods and Theory in Games, Programming & Economics. Addison- Wesley Professional, 1959.
[14] W.-C. Ma, D.-A. Huang. N. Lee, and K. M. Kitani. Forecasting interactive dynamics of pedestrians with fictitious play. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, pages 774-782, 2017.
[15] J. R. Marden, G. Arslan, and J. S. Shamma. Joint strategy fictitious play with inertia for potential games. IEEE Transactions on Automatic Control, 54(2):208-22) 220, 2009.
[16] K. Miyasawa. On the convergence of the learning process in a 2 non-zero-sum two-person game. Princeton University Princeton, 1961.
[17] D. Monderer and A. Sela. A2x 2game without the fictitious play property. Games and Economic Behavior, 14(1): :::::)444 1::1441444 1996.
[18] D. Monderer and L. Shapley. Fictitious play property for games with identical interests. Journal of economic theory, 68(1):258-22) 1996.
[19] D. Monderer and L. S. Shapley. Potential games. Games and economic behavior, 14(1): 124-143, 1996.
[20] P. Muller, S. Omidshafiei, M. Rowland, K. Tuyls, J. Pérolat, S. Liu, D. Hennes, L. Marris, M. Lanctot, E. Hughes, Z. Wang, G. Lever, N. Heess, T. Graepel, and R. Munos. A generalized training approach for multiagent learning. In 8th International Conference on Learning Repre- sentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https://openreviev..n
[21] G. Ostrovski and S. van Strien. Payoff performance of fictitious play. CoRR, abs/1308.40499 2013. URRLLatpp//arxiv..rr/aaa///////
[22] Robinson. An iterative method of solving a game. Annals of Mathematies, 54(2):296-301,
1951. ISSN 0003486X. URL http::tttp:..t.. jstor arg/staabee/1995550
[23] M. O. Sayin, F. Parise, and A. E. Ozdaglar. Fictitious play in zero-sum stochastic games. SIAM Control. Optim., 60(4):2095-21 14, 2022. doi: 10. 11.7137/211 m 426675.. URL httpss
//doi orgorr//// /00 1137/21mm4265511

---

[24] L. Shapley. Some topics in two-person games. Advances in game theory, 52:1-29, 1964.
[25] B. Swenson and S. Kar. On the exponential rate of convergence of fictitious play in potential games. In 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017, Monticello, II, USA, October 3-6, 2017, pages 275-279. IEEE, 2017. doi: 10.1 /ttp:ALLERRTON211.2222222222 8262748
URL htttp:://daat http:///oooorg//////// 111111109/AAAA ALLERTON 2017
[26] Y. Yang J. Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. CoRR, abs/201 1.00583, 2020. URL BRRLhhtps::/ h/aps:///rxxvv.. httpaaawwv./g..aaa//a//.. arggabss/011 .05883
12

---

Appendix
A Proof of Lemma 3.6
In this section, we present a comprehensive proof of Lemma 3.6 This lemma establishes a fundamen- tal property of recursive construction, defined in Definition 3.2 the only ca-aproximmaee Nash equilibrium is located at the maximum value element. Consequently, the fictitious play dynamics fail reach even approximate Nash equilibrium (within the specified degree of approximation) unless the strategy ( + 1) has been played for a sufficient duration. Our theoretical findings are further supported by our experiments. As shown in Figure 4b] the Nash gap does not vanish before the final strategy switch occurs. To provide precise definition of the Nash gap, we present it below.
Definition A.1 (Nash Gap for Identical Payoff). The Nash gap at round for a two-player identical payoff games is
max [Ay ) Tay(t) (a)) AA3 - (I) TAy (E
jE
To establish Lemma 3.6 we employ similar approach as in the other proofs presented in this work. Specifically, we heavily rely on the structure of our payoff matrix and utilize an induction technique to demonstrate that the majority of the probability mass must be concentrated in the maximum element. The induction argument starts from the outermost elements the matrix, namely row n column 1, and row column 1. By successive induction steps, we establish that until the maximum element reached, none of the elements those rows or columns can possess a significant probability mass.
Lemma A.2 (Proof of Lemma 3.6). Let 1056/)) and (a* y²) an e2NNE. Then for each i E [0, n2/2 2}.
क S e and an S
Vi+1 S and y c.
Proof. We will prove the claim by induction. First, assume that for all E [0, 1]. we have:
x att1 S and - S 6.
03+1 S and セū= S c.
2 1/41:1 6. We demonstrate these inequalities the exact order as presented, as their proof relies on underlying structure of the matrix. It is important to note that there are interdependencies between these inequalities, which will address accordingly.
Next, we proceed to establish the inequalities -; 1..1
Case 1: x; Se
Let assume that - and we will reach contradiction. From Observation 3.3 the utility of row n equals
notice that
[Ay*]n-: (4i + 1)yf+1 1 + 4iy2-141
(4)
At the same time the utility of row i equals
[Ay*]i+1 (4i 2)4(41 + (4i + 3)y
As result, by taking the difference on the utilities of row i and we get,
[Ay*]+ [Ay" (4i 2)yi+1 + (4i +3)++ (4i + 1) 4iy
= Vi-1 + (4i + 3) 4ky
Vi-1 :ー 4ic
where the last inequality follows by the fact that 1 S (Inductive Hypothesis). As result, we conclude that
13

---

[Ay]k+ - [Ay"I 2 vo+1 + vi+1 4ic
In case vi+1 + y 2 (42 + 1)c then [Ay*];+1 [Ay" 2 c. Hence if the row player puts 2 z probability mass row + by transferring the probability mass from increases its payoff by 2 ([Ay"[[A"+++ - [Ay"]n-<) > e The latter contradicts with the assumption that (x* .y") is an e2NNE Thus, we conclude in the following two statements.
i row i + 1 then
V7+1 + - S (4i + 1)c and [Ay"h-i S 2(4i 1)
where the last inequality is obtained by combining the first inequality with Equation (4). Now consider the sum of the utilities of rows & [i+ 2, - 1]. By the construction of the payoff matrix A we can easily establish the following claim.
Proposition A.3. The sum of utilities of rows & E li n, i 1] satisfies the inequality,
n R-i-1
n-i-1
Σ k=++2
[Ay 2
Σ k=i+2
9/4
By Proposition A.3
we are ensured that
[Ay*Ja Jk
Σ
yk
k=1+
k=i+2
i+1
Σ yi
=
Uk
1=1
A==
(vh+1 v#-s)
Vk
uk
k=n k=n-i+1
IV IV
(4i + 1)e ne
(5n + 1)e
where the second incquality follows by the fact that 0 + Uカ= S (4i + 1)e and the fact that yÿ S
for all & [1, U [n - 1, n] (Inductive Hypothesis).
Due to the fact that
Σ R=1+2
[A 2 1 (5n + 1)e
we are ensured that there exists a row 1s' E + 2, n - i 1] with utility [Ay]]s Ja- 2 1-(b++1e Now consider the difference between the utility of row h= and the row
[Ay*]a- [Ay*] - (5n + 1)c
1 1- (5n + 1)e
2(4i 1)2e
2(4n + 1)
n
where the last inequality holds for s 1/56n.. Hence if the row player puts -; probability mass to row k* then it increases its payoff by =" [Ay*].-:) > c². The latter contradicts with the assumption that (x*,"") is an 2-NE. Thus we have reached to final contradiction that -h > 6.
Case 2: vi+1 S
Similar to the previous case, we assume that 8.+1 > and proceed to derive contradiction. From Observation 3.3 we notice that the utility of column + is given by:
[(**)TART A] (4i + 2)x741 + (4i 1)
14

---

At the same time the utility of column n equals
[<=)) A]n- = (4i + 3) + (4i + 4)
As result, by taking the difference on the utilities of columns and i we get,
[(**) -|== - -=a=t=(a"aaaaa AJe+1 (4i + 3)x + (4i 4)--7--11 (4i + 2) - (4i + 1)
Ftt + (4i + - (4i + 1)2
2 2 + p (4i 1)c
where the last inequality follows by the fact - S (Inductive Step Case 1). As result, we conclude that
[(x*))AR
Als+1 2 - + x - - (4i + 1)E
In case ri+1 + - 2 (4i+ 2) then [<=')AARR=2 A|R-
[ A|1+1 2 e. Hence if the column player puts v4+1 probability mass to column - then it increases its payoff by v4+1(((x)) A]n-== [(**] T Al(+1) > e². The latter contradicts with the assumption that (a*, .v") is an ---NE Thus conclude in the following two statements:
2 + zn S (4i + 2)c and (A S 2(4i 2)
Now consider the sum of the utilities of columns k: E [ 2, n2 i - 1]. By the construction of the payoff matrix A we can easily establish the following claim.
Proposition A.4. The sum of utilities of columns E [i + 2, n
1] satisfies the inequality,
n-i-1
n-i-1
Σ ( T Ale 2 R=-2
Σ
x
k=i+2
By Proposition A.4 we are ensured that
Σ
[(*t) (A)x
>
k=1+
k=i+2
i+1
=
zjj
k=1
k=n-i
(x/+1
x
x
x
Smn-itt
2 ((4) 2)c
2i
+
1=1
k=n-i+1
N 1 (5n + 3)
where the second to last inequality follows by the facts: r + - < (4i + 2) and so #f+1 S (4i + 2)c, and the Inductive Step Case 1, x S c. Moreover, the last inequality holds by the Inductive Hypothesis: z < e for all & [1, U I - 1,n.).
Due to the fact that
n-i-1
(
Alk 2 (5n 3)c
we are ensured that there exists a column ks E 2 - i i with utility [(=*)TA] A]e. 2 1-(5++3)e Now consider the difference between the utility of column 4- and the column + 1.
15

---

1 (5m + 3)e 2(4i 2)
1 (5n + 33e
[(x")TAl A]a- - A 2
22(4n + +)) 2
where the last inequality follows by the fact that S 1/56n2. Hence if the column player puts Vi4 probability mass to column k* then it increases its payoff by V4+1 ([(=*)T AAa= ([==))+[++]] > e The latter contradicts with the assumption that (x* y² is an e2-NE. Thus we have reached final contradiction that Vi+1 > c.
Case 3: 21+1 S
Let assume that xi-1 > and will reach a contradiction. From Observation 3.3 we notice that the utility of row i I equals,
[Ay])4z (4i 2)y(+1 + (4i + 3)y
Next, we examine the row n n- (i+ in the inner submatrix. If this row is not well-defined, implies that the inductive step has reached the 2 x submatrix. this case, the proof of Lemma 3.6 has already been completed. Otherwise, the utility of row n - (i + 1) equals
[Ay"I-(041) = (4(i+1) - 1) 1)(44)441 + (4(i + 1))0 ((+1)4+1 2 (4i + 4)yi
As result, by taking the difference on the utilities of row i 1 and (i+ 1) we get,
[Av"In((41)) [Ay*]++ = (4i + 4) - (4i + 2) (4i + +33
Un- (4i + 2)
Vー (4i + 2)
where the last inequality follows by the fact that vi+1 S 6 (Inductive Step Case 2). As a result, we conclude that
[Ay") In-1n-(it1>
(i+1) - [Ay 2 vh-1 (4i + 2)
In case vー=; 2 (4i + 3)c then [Ay")a (ny"n=-0++n - 1141 2 c. Hence, if the row player puts x;4 probability mass to row n- (i+1) then it increases its payoff by ([Ay"((A")ss) (noA:)"--(++11-010 (Ay*)+++))))))) > e The latter contradicts with the assumption that (z*, y²) is an 22-NE. Thus, we conclude the following two statements:
- (4i 3)c and [Ay*l4+1 2(4i - 3)
Now consider the sum of the utilities of rows & E (i + 2, - i - 1]. From Proposition A.3
n-1-1
n-i-1
#+1
i+1
Σ [A
Σ vi =1
Σ
Uk
Σ
yi
2 Vn
Σ
y
Vk
k=
k=
-=n-
++
2 1 - (4i + +3) NE
(5n + 3)c
Thus, we ensured that there exists a row 1e + 2, n 1] with utility [Ay]]e+ 1 1-nt++3)e Now consider the difference between the utility of row ls* and the row m -t.
1 - (5n + 3)c
(5n + 3)c
[Ay*) - [Ay*]++1 2
2(4i + +3)
2(4n + +33 2
where the last inequality follows by the fact that S 1/56n². Hence if the row player puts x probability mass to k* then it increases its payoff by 2;41 ([Ay][] [Ay*)+1) > é. The
16

---

latter contradicts with the assumption that (x",y") is an eN-NE. Thus we have reached to final contradiction that 21+1 >
Case 4: V 6
Let assume that v > and we will reach a contradiction. From Observation 3.3 we notice that utility of column i equals,
"en))Aln=+- (4i 3) + (4i 44)
Now, we consider the column (i+ 1+++++1 + in the inner submatrix. In case this column is not well- defined, it means that the inductive step j has reached the 2 2 submatrix and so the proof of the Lemma 3.6 has already been completed. Otherwise, the utility of column (i + 1) + equals
[(x*) (((+))) 11 As result, by taking the difference on the utilities of columns i and (i 1) we get,
(1 2) + (4(1 + 1) + 1) (1+1)+++111111111 2 (4i + 5)z
(o7))A)(tDHH) [x=)T A]n-; (4i + 5) (4i + 3)m(41 (4i + 4) 4)z
zn (4i 3)
2 zn (4i 3)c
where the last inequality follows by the fact that x,41 S (Inductive Step Case 3). As result, conclude that
[x*)] Ak(+4)4 [(=))] T
Aln-i 2 20 - (4i + 3)c
In case -; 2 (4i 4)c then [(=*) ( A) T AAn- 2 c. Hence if the column player puts
-n-s probability mass column (i + 1) + then it increases its payoff by ((xx)((="" Al(+1)-1 ((a*)TAln=)) Alm-i) 2 The latter contradicts with the assumption that (a*,y") an e2-NB. Thus conclude in the following two statements:
[(**)] T
a S (4i + 4)e and [(x*) S 2(4i + 4)
Now consider the sum the utilities of columns & E [i 11+ n 1). From Proposition A.4
n-i-1
n-i-1
Σ [at) Ale
Σ x =1
k=1+2
k=n-i
1 x
k=n ++1
W (4i + 4)c ne
(5n + 4)c
Thus, we are ensured that there exists a column As E [ + 2, n - i 1] with utility [(x*)] A]k+ 2
1- (5n-4)c Now consider the difference between the utility of column A and the column n - i.
[xxt) A/a- - T A] 1 - (5n 4)e 2(4i + 2)
(5n + 4)e 2(4n + 4) 2
n
where the last inequality follows by the fact that e S 11/56m3. Hence if the column player puts Vi probability mass to column is then it increases its payoff by yi ([(x+)T TA]k- [T=)T A|m-i) [<=')AApm>) >
2 The latter contradicts with the assumption that (x* y²) is 2-N.. Thus have reached to final contradiction that yi > e.
17

---

A.1
Proof of Theorem A.3
Proposition A.5. The sum of utilities of rows & li 2,
admits,
n-i-1
n-i-1
AAyl
Σ
yk
R=
k=
Proof. By Observation 3.3 we derive the following equation.
[Ay*]++ = [Ay*)041)+1 = (4i +2)((114411 + (4i 3)1 2 ((+1)++1
n-i-1
n-i-1
The claim can be immediately derived from the inequality given above,
Σ
[Ay*]a | 2 Σ Ve.
h=i+2
kmi+2
A.2 Proof of Theorem A.4
Proposition A.6. The sum of utilities of columns k E Ei [i -
1] admits,
カーf-1 (C)) T
n-i-1
Σ
x
k=i+2
Proof. By Observation 3.3 we derive the following equation.
[(*')TA] Ali+=
((x') (] 2 (4i 2)z + (4i (4i+3))n-(++)) (i+1)) 2 3(1+1)+1
n-i-1
カ-i-1
The claim can be immediately derived from the inequality given above,
Σ
Alk 2
Σ o
k=it2
k=1+2
L
B Proof of Lemma 3.8
B.1 Omitted Proofs Section 3.3
Proposition B.1 (Proof of Proposition 3.10 Let (()))()) be a strategy selected by fictitious play round and (i(0) j(0) + ( 2) Then, in subsequent round, fictitious play will choose the strategy of greater value that either on row z(t) or column j(t)
Proof. To establish the claim, we employ the concept of a cumulative utility vector, as defined in Definition 2.7 According to Proposition 3.5 the row z(() and column j(t) combined have three distinct non-zero elements. Without loss of generality, let's assume that the greater element is in column j(0) but in a different row, denoted as ''.
Firstly, observe that any subsequent strategy will involve only those three elements. This is because in the cumulative utility vector, which determines the strategy to be played in each round, only the coordinates corresponding to those elements are updated as long as the strategy (z(9), ((() is being played.
Moreover, we can demonstrate that among these elements, the one with the greater value will be played next, and this transition is deterninistic. This means that the row player will choose the strategy associated with the greater element. We note that this decision is implicitly affected by the strategy of column player.
18

---

Let's first exclude the case where the next strategy switch involves the column player. We initially assumed that the greatest element is in column j(() but on a different row. Consequently, the only non-zero element a different column than j(t) must have a smaller utility compared to the element ((0),)(0) Therefore, there is no incentive to switch a strategy with lower utility. This confirms that the column player will not opt for different strategy, ensuring that the next strategy switch, if it occurs, will necessarily involve the row player.
Regarding the row player, we aim to prove that there will be round where they will change to a different strategy, and consequently, to a different row. To analyze this, let's examine how the cumulative utility vector of the row player changes from round to round.
h-1 Σ Aegin
i == ;=) E arginax iE(n)
Therefore, as long as the column player continues to use the same strategy, the row Aejto will repeatedly be added to the cumulative vector, reinforeing the coordinate of row i' However, this cannot happen indefinitely, as the cumulative utility vector is bounded. After certain number of rounds, the row player will eventually choose the strategy associated with row i'. This proves that claim for the case of the row player.
Similarly, if the greater element is located in the same row but different column, similar argument can be made to prove that the column player will switch strategies next.
Let be round in which a player changes their strategy. Then exactly one of the following statements is true:
Corollary B.2 (Proof of Corollary 3.11
1. If the row player changes their strategy at round t, i.e. i(t) f ((t-1), then the column player can only make the next strategy switch.
2. If the column player changes their strategy at round 1, iee. j(0) + j((-1), then the row player can only make the next strategy switch.
Proof. This corollary is simple application of Proposition 3.10 We will only prove the first claim. Let be the round when the row player changes their strategy, i.e., j(t) * f(t-1). According to Proposition 3.5 there are three non-zero elements combined in (()) Since the row player changes their strategy, it follows from Proposition 3.10 that the other element column j(() but not in row j(t) must necessarily have a smaller value than (z(0), Therefore, the element with the greater value must necessarily be in different column. Hence, by applying Proposition 3.10 conclude that the column player can only make the next strategy switch. This proves the claim.
B.2 Auxiliary Propositions for Lemma 3.6
In this subsection, we provide the full version of the proposition used establish the proof Lemma 3.6 Proposition B.3. There exists a round TV! T at which
(i) the strategy profile is (i + 1, + for the first time,
(ii) for all rounds t (TP: Ti -1, the strategy profile is (n i, 1),
(iii) column i+ 1 admits cumulative utility (TT)) 2 (4i + 1) (T( + +1),
(iv) all rows E [[i [ 1) I, -i-1 admit R (TTT 0 and all columns [i ( 2, admit C (T.) =0.
Proof. The proposition composed of multiple parts, each of which is proven separately. To begin with, must establish that the new strategy profile chosen by fictitious play will be (i + 1, 1).
19

---

According to the inductive hypothesis in Theorem 3.1 we know that the strategy (n - i, 1) was
played at round T for the first time, while any strategy involving row [i 1, n- (i 1)] has not been played until that point. Additionally, the inductive hypothesis also states that the strategy played before time 7 was (n i, n i + 1). Therefore, according to Corollary 3.11 it is guaranteed that the next strategy switch will be initiated by the row player.
In other words, as long as the column player continues play their current strategy, strategy
(n i, 1) will be played in every subsequent round, which establishes Item (ii) This implies that the row player's 's cumulative utility will increase by Aes+1. As per Observation 3.3 only has non-zero elements in positions i + and n i.
column + 1
Ae 10..... 4i 4++20 2.200
O, 4i 1.0....
1+1
n-
Since strategy i + 1 has higher value, strategy switch in later time step is certain. Consequently, there will be round T in which the strategy (i+1,i+1)) will be played for the first time, establishing Item
We must determine the point at which the strategy switch to (i + 1, 1) will take place. According greater than the value of strategy n i.
to Equation (5), the value of strategy + 1 is exactly From the inductive hypothesis, we know that row + 1 has a cumulative utility of zero, whereas
row n has a cumulative utility of R(ZT- Therefore, it will take precisely R(T steps for those strategies to have equal cumulative utility values. Consequently, the strategy switch will either occur that round or the immediate next, as the cumulative utility row i + 1 will have surpassed that of row n i.
(iii) we compute the updated cumulative utility of column (i + 1). As shown in Equation (5). column has value of (4i + 1) at position i. Thus, if row i has
In order to proceed with Item
been played for a minimum of (T(?)) rounds, then the cumulative utility of column + 1 is greater than (4i 1)- (T.) Given that row i has also been played previously (inductive hypothesis), it reasonable to conclude that:
(1 (R +1)
Lastly, according to Observation 3.4 there exists non-zero element in row i + 1+10 at position i 1. Due to the fact that column i ++1 has already been played (according to Item (ii) we can conclude that the cumulative utility of row i i+ 1 must be non-zero. Combining this with inductive hypothesis, concludes the proof of Item (iv)
B.2.1 Proof of Theorem 3.13
Proposition B.4, There exists a round T? > T!! at which
(i) the strategy profile is (i + 1, - i) for the first time,
(ii for all rounds t [T), T? - 1), the strategy profile is (i 1,1+
(iil) row + 1 admits cumulative utiity n!TT)) 2 (4i + 2) (T))
(iv) all rows k [(i+1)+ n- -i i- admit (T( and all columns k E 2. (i+1)] admit C (T?)
=0
Proof. We repeat the same reasoning in the proof of Proposition 3.12 To begin with, must establish that the new strategy profile chosen by fictitious play will be (i + nn i).
We can infer from both Items (i) and in Proposition 3.12 that the most recent strategy switch was made by the row player. Therefore, based on Corollary we are certain that the next strategy switch will be initiated by the column player.
20

---

In other words, as long as the row player continues to play their current strategy, strategy (1+1,i+ i will be played in every subsequent round, which establishes Item (ii This implies that the column
player's cumulative utility will increase by e A. As per Observation 3.3 row + only has non-zero elements at positions i + and i.
e A [0,
2.0,
0, 44
3. 0,
(6)
Since strategy n - has higher value, a strategy switch a later time step certain. Consequently, there will be round T?? in which the strategy n--) will be played for the first time, establishing Item
We must determine the point at which the strategy switch to (i - 1, i) will take place. According to Equation (6). the value of strategy n is exactly one greater than the value of strategy i + 1. i has cumulative utility of zero, whereas
From the Proposition 3.12 we know that column
column i+ has cumulative utility of C:T:)) Therefore, it will take precisely c steps for those strategies have equal cumulative utility values. Consequently, the strategy switch will either occur in that round or the immediate next, as the cumulative utility of column n - i will have surpassed that of column +
In order to proceed with Item (ii)) we compute the updated cumulative utility of row (i + 1). As shown in Equation (6), row i +I has value of (4i 2) position i + 1. Thus, if column + 1
(T!))
has been played for minimum of C+1 rounds, then the cumulative utility of row i + satisfies
R (4i +4i+21 2) C+11
(T.) -)
Lastly, according to Observation 3.4 there exists a non-zers element column n - i at position i+ 1. Due to the fact that row i+ I has already been played (according to Item (i)), can conclude that the cumulative utility of column n must be non-zero. Combining this with Proposition 3. 12 it concludes the proof of Item (iv)
B.2.2 Proof of Theorem 3.14
Proposition B.S. There exists a round TV >> T at which
(i) the strategy profile is (n (i + 1), n for the first time,
(ii) for all rounds t [T?: T - 1], the strategy profile is (i + 1, n - i).
(iii) column admits cumulative utility (T?)) (4i 3) R
(T.))
(iv) all rows k E [[i 1) 1,n (i + 1) 1] admit R (T+) i 2, n (i + 1)] admit (T.) 0.
0 and all columns k
Proof. We repeat the same reasoning as in the proof of Proposition 3.12 To begin with, we must establish that the strategy profile chosen by fictitious play will be (n
1, n. i).
We can infer from both Items (i) and iii in Proposition 3.13 that the most recent strategy switch was made by the column player. Therefore, based on Corollary 3.11 we are certain that the next strategy switch will be initiated by the row player.
In other words, as long as the column player continues to play their current strategy, strategy (i+ 1, - i) will be played in every subsequent round, which establishes Item (ii) This implies that the row player's cumulative utility will increase by Aen-j. As per Observation 3.3 column
only has non-zero elements at positions + 1 and n (i + 1).
4i 1 3,0, O, 0, 4i + 0, Ae 10...,
2+1
n-(++)
21

---

Since strategy (i + 1) has a higher value, strategy switch in later time step is certain. Consequently, there will be round T in which the strategy (n (n-i 1, 10-0 i) will be played for the first time, establishing Item
We must determine the point which the strategy switch (n - 1,n i) will take place.
According to Equation (7). the value of strategy n- (i + 1) is exactly one greater than the value of strategy From the Proposition 3.13 we know that row n - (i+ 1) has a cumulative utility of
zero, whereas row i has cumulative utility of ( Therefore, it will take precisely R ((T?) steps for those strategies to have equal cumulative utility values. Consequently, the strategy switch will either occur in that round or the immediate next, as the cumulative utility of row - (i + 1) will have surpassed that of row i +..
In order to proceed with Item shown in Equation (7). column 72 has a value of (4i + 3) at position + 1. Thus, row + has
we compute the updated cumulative utility of column n i. As
been played for minimum of rounds, then the cumulative utility of column n satisfies
c (4i + 3) R(TT)
Lastly, according to Observation 3.4 there exists a non-zero element in row n (i + 1) at position
i. Combining this with the Proposition [313 and the fact that column n i has already been
played (according Item (ii),, we can conclude that the cumulative utility of row n 1) must be non-zero. This concludes the proof of Item (iv)
B.2.3 Proof of Theorem 3.15
Proposition B.6. There exists a round T: >> T at which
(i) the strategy profile is (n (i + 1), (i++1) 1) for the first time,
(ii) for all rounds t [TY T - 11. the strategy profile is (n (i + 1), n i),
(iil) row n - i-11 1 admits cumulative utility R(TT) n-((+1) 2 (4i + 4) ((T.)
(iv) all rows & E [(i + 1) + 1, - +i+ 1) 1] admit R (Tt) = and all columns k E 1)++1)2217 n - (i + 1)] admit C = 0.
Proof. We repeat the same reasoning in the proof of Proposition 3.12 To begin with, must
establish that the new strategy profile chosen by fictitious play will be (n (i + 1), (2 + + 1).
We can infer from both Items (1) and (11) in Proposition 3.14 the most recent strategy switch was made by the row player. Therefore, based on Corollary 3.1 we are certain that the next strategy switch will be initiated by the column player.
In other words, as long as the row player continues play their current strategy, strategy (n (i 1), i) will be played in every subsequent round, which establishes Item (ii This implies that the column player's cumulative utility will increase by eT (i+11+)) A. As per Observation 3.3 row (i+1) 1) only has non-zero elements positions (i + 1) + 1 and n (i+1). 1).
T en (1-1) A [0,............. 4i 4,.0 (++1)+1
O, 4i 4 ......]
(8)
n- (1+1)-1
Since strategy (1 + 1) + 1 has a higher value, a strategy switch in a later time step is certain. Consequently, there will be round 77 in which the strategy (n (i (i+1) 1), (i 1) + 1) will be played for the first time, establishing Item (i)
We must determine the point which the strategy switch (n - (i + 1), (i + 1) will take place.
According to Equation (8), the value of strategy (i + 1) + 1 is exactly one greater than the value of strategy i. From the Proposition 3.14 we know that column (i + 1) 1 has cumulative utility Therefore, it will take precisely
of zero, whereas column has cumulative utility of (T?))
22

---

CLEi steps for those strategies to have equal cumulative utility values. Consequently, the strategy switch will either occur in that round or the immediate next, as the cumulative utility of column (n 1), (i + 1) + 1) will have surpassed that of column n i.
In order to proceed with Item iiii)
we compute the updated cumulative utility of row n - (i+ 1). As 1) has value of (4i + 4) at position
shown in Equation (). row 71
Thus, if column
has been played for minimum of ( C rounds, then the cumulative utility of row (2 + 1)
satisfies R (T7) (-(++1) 2 (4i 44) (!P))
Lastly, according to Observation 3.4 there exists a non-zero element column (i+1) + at position
(i 1). Combining this with the Proposition 3.14 and the fact that row n - (i + 1) has already been played (according to Item (ii) we can conclude that the cumulative utility of column (i + 1)
must be non-zero. This concludes the proof of Item (iv)
23


Reviews:
[{"review_id": "HKBPeuAagY", "reviewer": "Reviewer_TVCP", "summary": "This paper studies the convergence rate of Fictitious Play (FP) in potential games. While prior work shows that FP asymptotically converges to a NE in the case of $N$-player potential games, the current paper proves that FP can take exponential time to do so. Specifically, the paper recursively constructs a two-player coordination game with identical interests and a unique pure NE. The paper shows that FP requires super-exponential time before placing positive probability in the unique NE, even with an arbitrary tie-breaking rule. The paper also contains simulations to validate the shown learning dynamics. ", "questions": "Line 58 - 60: I believe [1] is only for diagonal games?\n\nLine 100 - 101: The latter A should be B. ", "limitations": "N/A.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper provides a complete answer to an important problem (convergence rate of FP in potential games). \n2. The paper is very well-written and easy to follow. Related works are discussed extensively. Technical results are delivered in a clear way. \n3. The paper also provides simulations to validate findings and provide intuition. ", "weaknesses": "1. It might be better to include more background information on FP and potential games, e.g., some concrete examples of potential games in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer of all the work. We sincerely appreciate the reviewer's valuable comments. Related to reviewer's questions/concerns: \n\n1. $[1]$ is for diagonal zero-sum games and moreover the tie-breaking rule is fixed in advance (not adversarial as in [2]). \n\n2. Indeed, $A$ should have been $B$; thank you for pointing it out.\n\n3. We will incorporate an example of a potential game in the preliminaries section and expand our references. Potential games are notably important in capturing routing games (also known as congestion games [3,4]).\n\n[1] Fast Convergence of Fictitious Play for Diagonal Payoff Matrices, Abernethy et al.\n\n[2] A Counter-Example to Karlin's Strong Conjecture for Fictitious Play, Daskalakis et al.\n\n[3] A class of games possessing pure-strategy Nash equilibria, Rosenthal.\n\n[4] Potential games, Monderer et al."}, {"review_id": "M9GCJpesZT", "reviewer": "Reviewer_hanH", "summary": "This paper constructs a common-payoff two-player game for which fictitious play must take a number of iterations exponential in the number of actions to converge to an $\\epsilon$-equilibrium.  The paper closes with some empirical demonstrations of the behavior of fictitious play on the game.", "questions": "1. What is $z$ for in the construction of the game?  Once $K_n(z)$ has been defined, we only ever think about $A=K_n(0)$ for the rest of the paper.\n\n\n#### Minor issues (did not affect my evaluation)\n- on p.3, $x^\\top A(y') - x^\\top Ay = \\Phi(x,y') - \\Phi(x,y)$ should be $x^\\top B(y') - x^\\top By = \\Phi(x,y') - \\Phi(x,y)$\n- on p.7, \"Applying Lemma 3.6 for $\\epsilon := \\sqrt\\epsilon$...\": This is needlessly confusing", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The construction of $A$ is very clever, and the description of why this guarantees an exponential lower bound does an excellent job of delivering the important aspects without getting bogged down in the arithmetic details.\n\nFictitious play is an extremely well-studied and widely-used algorithm.  The structural simplicity of the constructed example gives an excellent intuition about a class of scenarios in which we should expect FP to perform poorly.", "weaknesses": "My only concern about this work is that it might have limited impact; a link to the structural properties of games that FP is commonly applied to might have helped.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your work and your feedback on our paper. We appreciate your valuable comments.\n\n1. Indeed, A should have been B; thank you for pointing it out.\n\n2. The equality sign does indeed get confusing for the reader; we will change it to either $\\coloneqq$ or $\\rightarrow$ to signify assignment rather than equality.\n\n3. $z$ is just a positive real number defining the matrix $K_n(z)$, see Figure 1a. In Definition~3.2 $K^n(z)$ is recursively defined and the construction of our game corresponds to $A = K_n(0)$. \n\nRegarding the potential limited impact of our work: Our study contributes to the existing literature by investigating the convergence rate of Fictitious Play in potential games. Fictitious Play (FP) is a fundamental concept in understanding learning dynamics within strategic interactions, originally introduced by Brown in 1951 [1]. While previous work by Robinson [2] established convergence in zero-sum games, it didn't provide a precise rate of convergence (Karlin conjectured that the rate of FP in zero-sum games is of order $O(1/\\sqrt{T})$). FP possesses not only an intuitive game theoretic interpretation but also other attractive properties, such as its simplicity with no need for a step-size parameter. These traits have contributed to FP's status as a pivotal topic of study, leading to numerous works aiming to establish convergence in broader settings [8, 9, 10, 11].\n\nFurthermore, it's essential to emphasize that FP, in conjunction with Blackwell's approachability theorem [6], laid the groundwork for the development of no-regret learning algorithms [15, 21], a thriving area of research. Additionally, the stochastic version introduced by Hofbauer and Sandholm [12] inspired the well-established Follow the Perturbed Leader (FTPL) dynamics [13]. \n\nThe relevance of theoretical investigations into the convergence of FP has been amplified in recent years. Notably, Daskalakis et al. [3] and Abernethy et al. [4] addressed Karlin's conjecture, a long-standing problem dating back to 1959 [5]. Similarly, Monderer et al.'s foundational work [7] demonstrated FP's convergence in potential games, yet without providing a specific rate of convergence. It was this particular gap in knowledge that sparked our investigation. This work builds upon these preceding studies and addresses a specific aspect that remained unexplored.\n\nThere are also many works in the literature published in different venues such as ML/AI [20, 22, 23, 24], theoretical computer science [1, 2, 3, 4, 10, 11, 21], and control theory  [16, 17, 18, 19]. DeepMind used an algorithm called Prioritized Fictitious Self Play as part of the training for their AlphaStar program for playing competitive Starcraft [14].\n\nIn light of this, our research contributes to this lineage of ideas, providing insights into the convergence behavior of Fictitious Play in potential games and augmenting the broader landscape of game theory research. We believe our work has meaningful implications for understanding learning dynamics and strategic interactions, and we hope the reviewer finds our perspective on its potential impact clearer in light of these connections.\n\n[1] Iterative solution of games by fictitious play, Brown et al.\n\n[2] An iterative method of solving a games, Robinson et al.\n\n[3]  A Counter-Example to Karlin's Strong Conjecture for Fictitious Play, Daskalakis et al.\n\n[4] Fast Convergence of Fictitious Play for Diagonal Payoff Matrices, Abernethy et al.\n\n[5] Mathematical Methods and Theory in Games, Programming, and Economics, Karlin\n\n[6] An analog of the minimax theorem for vector payoffs, Blackwell \n\n[7] Fictitious Play Property for Games with Identical Interests, Monderer et al.\n\n[8] On the convergence of the learning process in a 2 x 2 non-zero-sum two-person game, Miyasawa et al. \n\n[9] Some topics in two-person games, Shapley et al.\n\n[10] A 2 × 2 game without the fictitious play property, Monderer et al.\n\n[11] On the rate of convergence of fictitious play, Brandt et al.\n\n[12] On the Global Convergence of Stochastic Fictitious Play, Hofbauer et al.\n\n[13] Efficient algorithms for online decision problems, Kalai et al. \n\n[14] Grandmaster level in StarCraft II using multi-agent reinforcement learning, Vinyals et al. \n\n[15] Prediction,learning, and games, Cesa-Bianchi et al.\n\n[16] Joint strategy fictitious play with inertia for potential games, Marden et al.\n\n[17] Forecasting interactive dynamics of pedestrians with fictitious play,  Wei-Chiu et al.\n\n[18] Fictitious play in zero-sum stochastic games, Sayin et al.\n\n[19] Approximation guarantees for fictitious play, Conitzer et al.\n\n[20] Smooth Fictitious Play in Stochastic Games with Perturbed Payoffs and Unknown Transitions, Baudin et al.\n\n[21] No-regret dynamics and fictitious play, Viossat et al.\n\n[22] Fictitious play for mean field games: Continuous time analysis and applications, Perrin et al. \n\n[23] Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games, Baudin et al.\n\n[24] Provably efficient fictitious play policy optimization for zero-sum Markov games with structured transitions,  Qiu et al.\n"}, {"review_id": "Qin8GsHUEk", "reviewer": "Reviewer_nmF9", "summary": "This paper examines the convergence rate of Fictitious Play (FP) in potential games. The paper proves that FP for potential games can take exponential time to reach a Nash equilibrium. The research has yielded a recursive rule for constructing payoff matrices, demonstrating that fictitious play, regardless of the tie-breaking rule employed, may require exponential time to reach a Nash equilibrium even in two-player identical payoff games. The same theorem holds for general N-player potential games. ", "questions": "I want to clarify the issues of the weakness section. If this is well-addressed, I am down to re-evaluate this paper.\n\n", "limitations": "The authors adequately addressed the limitation and potential negative societal impact on their work.\n\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "They have provided a concrete example to illustrate the exponential lower bound with figures, which greatly enhances the clarity and understanding of the paper. Furthermore, I am satisfied with the overall readability of the paper. The writing style is approachable, making it easier for readers to engage with the content. One aspect that I particularly enjoyed is the authors' explanation of intuition to construct counterexamples of learning dynamics. This approach helps readers grasp the underlying concepts more effectively, enhancing the overall learning experience. The proof idea is simple and intuitive.\nThe paper is well-written, provides clear explanations through intuitive examples, and offers an enjoyable reading experience.", "weaknesses": "I have some concerns regarding this paper that I would like the authors to address.\n\n1. In reference [1], it is mentioned that if certain regularity conditions are met, FP dynamics achieve an exponential rate. Can the authors provide more details on these regularity conditions and their implications? Like why this game is not in the regularity conditions. [1] are saying that almost every potential game are regular game. \n\n2. For FP dynamics, this paper proves that finding NE using fictitious play potential games has exponentially lower bounds. Does this exponential lower bound also hold for stochastic fictitious play? For example, if people have some exploration in each turn,  is it possible to break the exponential lower bound? \n\n3. I am curious about the upper-bound of the convergence rate in the case where the conditions of regularity are not satisfied. I guess that the example that this paper gave does not satisfy the regularity condition. Is there a specific upper-bound that can be established? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your work and the valuable comments. We would like to address comment 1 and 3 together, as they are closely related. Additionally, we want to clarify that when referring to [1], we assume the paper the Reviewer nmF9 mentioned is titled \"On the Exponential Rate of Convergence of Fictitious Play in Potential Games\". In comparison to that work, our research presents several important qualitative differences.\n\nWe remark that our constructed lower bound *does* satisfy the regularity conditions of [1]. There are two key reasons that [1] and our work are not contradictory. First of all [1] consider the *continuous-time* version of fictitious-play while we consider the *discrete-time* version, thus our lower bound is not necessarily applicable. Secondly and most importantly, [1] establish exponential convergence only in the asymptotic sense. Let us take a closer look to their main theorem.\n\nTheorem 8. Let $\\Gamma$ be a regular potential game. Then for almost every initial condition $x_0 \\in X$, there exists a constant $c = c(\\Gamma, x_0 )$ such that if $x$ is an FP process associated with $\\Gamma$ and $x(0)=x_0$ , then $d(x(t), NE) \\leq c e^{-t}$.\n\nNotice that $c$ is not a universal constant in fact it is not even polynomially bounded by the size of the game. Meaning that $c$ can have super-exponential dependence on $n$ - for example $c = O(2^{2^{n}})$ or $c = O(4^n((n/2-2)!)^4)$. \n\nIn simpler words, [1] establish that for *continuous* fictitious-play there exist a time-step $T^\\star$ after which exponential convergence occurs, however $T^\\star$ can be super-exponentially large! The latter is totally aligned with our take-way message for the discrete case.\n\n*Comment 2*\n\nExtending our lower bound construction for stochastic fictitious play in an interesting research direction that however remained outside the scope of this work. To this end, we have experimentally studied the convergence properties of stochastic fictitious play in the provided lower bounded construction of this work. Our experimental evaluations are included in the uploaded pdf and suggest that a more fine-grained analysis can be extend our lower bound to stochastic FP.\n"}, {"review_id": "s2SEi03CXQ", "reviewer": "Reviewer_a6So", "summary": "This paper studies fictitious play in potential games and in particular, two-player identical payoff games. It is shown that fictitious play, under arbitrary tie-breaking, needs super-exponential time with respect to the number of actions to find an approximate Nash equilibrium. The lower bound is proved through recursive construction of a hard game in which fictitious play spirals slowly and takes super exponential time to reach the unique pure Nash equilibrium.", "questions": "A couple of minor questions:\n\n- Line 221: In Eq (2), should the last term be $R^{T_{l-1}}_{n-l+1}$ instead?\n\n- Line 247: To evoke Lemma 3.6, wouldn't one need $n\\sqrt{\\epsilon}<1$? I can't seem to find where this is assumed.\n\n- Line 248: \"On the other hand, at each round $t\\ge T^*$, ..., with rate $1/t$\". Where is result statement proven?", "limitations": "This work is of theoretical nature and there is no foreseeable negative ethical, societal implication.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- This paper makes significant progress on a fundamental problem, namely the convergent behavior of fictitious play in potential games. While Monderer et al. proved an asymptotic $O(1/t)$ rate, no finite-time guarantee is known before to my knowledge; this paper shows that any finite-time guarantee for classes of games that include identical-payoff games has to be super-exponential in the number of actions. It suggests that fictitious play in potential games, while asymptotically convergent, would have a burn-in period that is super-exponentially long.\n\n- The paper is remarkably well written. The results are presented clearly and the construction is clean and easy to follow.", "weaknesses": "- The asymptotic part of the lower bound translates to $\\Omega(1/(n^2t^2))$, which I believe is not tight in light of the $O(1/t)$ upper bound.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all its effort, the insightful comments and the carefully reading of our work. We start by answering the reviewer's questions.\n\n*Questions*\n \n1. Thanks for spotting the typo.\n2. The reviewer is right we missed the assumption in Theorem 3.1. In fact Lemma 3.6 requires $\\epsilon \\in O(1/n^3)$. Since in the proof of Theorem 3.1, Lemma 3.6 is applied for accuracy $\\sqrt{\\epsilon}$, we need to take $\\epsilon < O(1/n^6)$. We will add the latter in the Theorem 3.1.\n3. Notice that once $(i(t),j(t)) = (n/2,n/2+1)$ for $t = T^\\star$ then $(i(t),j(t)) = (n/2,n/2+1)$ for all $t \\geq T^\\star$ since $(n/2,n/2+1)$ is the maximum entry of the matrix $A$ and thus $n/2$ is the action with most cumulative payoff for agent $x$ (resp. $n/2+1$ for agent $y$). We will add the above explanation in the revised version. \n\n$$ $$\nConcerning the reviewer's major point, we want to remark that our results imply exponential lower bounds even for the $1/t$ case. More precisely, let us assume that an upper bound of the form $p_1(n) + p_2(n)/\\epsilon$ could be established. By taking $\\epsilon = O(1/n^6)$, Theorem~3.1 applies and thus \n$$ p_1(n) + O(n^6 p_2(n)) \\geq 4^n ((n/2-2)!)^4$$\n\nmeaning that either $p_1(n)$ or $p_2(n)$ is super-exponential. We will add the above discussion in the revised version of our work."}]

Author rebuttal:
We thank the reviewers for their hard work. We have attached a pdf with experimental evaluations on the stochastic version of fictitious play, to address a question asked by reviewer nmF9 (what happens in our constructed game if each agent has some exploration). The experiments suggest that a more fine-grained analysis can extend our lower bound to stochastic FP. 

Meta-review: After some discussion, all reviewers agreed that the paper should be accepted. The authors should incorporate their replies to the reviewers about related work into the main body of the paper, which will help clarify the significance of their theorem.
Decision: Accept (poster)