Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions
Authors: Nivasini Ananthakrishnan
Nika Haghtalab
Chara Podimata
Kunhe Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: Information asymmetry
Repeated games
Stackelberg games
Primary area: algorithmic_game_theory

Abstract: When learning in strategic environments, a key question is whether agents can overcome uncertainty about their preferences to achieve outcomes they could have achieved absent any uncertainty. Can they do this solely through interactions with each other? We focus this question on the ability of agents to attain the value of their Stackelberg optimal strategy and study the impact of information asymmetry. We study repeated interactions in fully strategic environments where players' actions are decided based on learning algorithms that take into account their observed histories and knowledge of the game. We study the pure Nash equilibria (PNE) of a meta-game where players choose these algorithms as their actions. We demonstrate that if one player has perfect knowledge about the game, then any initial informational gap persists. That is, while there is always a PNE in which the informed agent achieves her Stackelberg value, there is a game where no PNE of the meta-game allows the partially informed player to achieve her Stackelberg value. On the other hand, if both players start with some uncertainty about the game, the quality of information alone does not determine which agent can achieve her Stackelberg value. In this case, the concept of information asymmetry becomes nuanced and depends on the game's structure. Overall, our findings suggest that repeated strategic interactions alone cannot facilitate learning effectively enough to earn an uninformed player her Stackelberg value.

Is Knowledge Power? On the (Imspossiyility of Learning from Strategic Interactions
Nivasini Ananthakrishnan' Nika Haghtalab', Chara Podimata', and Kunhe Yang'
UC Berkeley, {nivasini, nika, kunbeyang) MIT & Archimedes AI, podimatašmit. edu
Abstract
When learning in strategic environments, key question is whether agents can overcome uncertainty about their preferences to achieve outcomes they could have achieved absent any uncertainty. Can they do this solely through interactions with each other? We focus this question on the ability of agents to attain the value of their Stackelberg optimal strategy and study the impact of information asymmetry. We study repeated interactions in fully strategic environments where players' actions are decided based on learning algorithms that take into account their observed histories and knowledge of the game. We study the pure Nash equilibria (PNE) of a meta- meta-game where players choose these algorithms as their actions. We demonstrate that if one player has perfect knowledge about the game, then any initial informational gap persists. That is, while there is always a PNE which the informed agent achieves her Stackelberg value, there is game where no PNE of the meta-game allows the partially informed player to achieve her Stackelberg value. On the other hand, if both players start with some uncertainty about the game, the quality of information alone does not determine which agent can achieve her Stackelberg value. In this case, the concept of information asymmetry becomes nuanced and depends on the game's 's structure. Overall, our findings suggest that repeated strategic interactions alone cannot facilitate learning effectively enough earn an uninformed player her Stackelberg value.
Introduction
Learning to act in strategic environments is fundamental to the study of decision making under uncertainty in wide range of applications, such as security, economic policy, and market design (e.g., [31, 1,,1,, 8, 19]). In these environments, acting and learning are intimately connected: agents' actions and the reactions they elicit generate payoffs, and help clarify the latent preferences of other agents. A central question is whether, through repeated interactions alone, agents (aka players) can overcome uncertainty about each other's preferences in order achieve outcomes they could have achieved in the absence of uncertainty. An extensive line of work on learning in Stackelberg Games [5, 8, 31, 31,35, 35] has focused on answering this question for achieving the Stackelberg value, which the optimal payoff a player guarantees herself when assuming other players will best respond to her actions. While player who hopes to attain her Stackelberg value a one-shot game must know the game (i.e., know the utilities of all players), this line of work asks whether player who is a-priori uninformed can overcome her lack of knowledge and attain her Stackelberg value through repeated interactions with other players.
By and large, existing works have studied this question by constructing learning algorithms for uninformed players that attain their Stackelberg value, through repeated interactions with other players who myopically best respond. While these results are encouraging for learning about the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

preferences of well-behaved best responding agents', ! they do not provide clear evidence of the ability of uninformed players to learn from strategic interactions alone. Indeed, the two players' different attitudes towards their outcomes - namely, one player planning a long-term strategy to maximize her long-term payoff while the other player responding without considering the impact of her actions on her long-term payoff confounds the overall impact uncertainty may have on how well players learn from strategic interactions; leaving one to wonder whether it was the lack of rational long-term planning on the part of one agent or some genius of the learning algorithm employed by the other agent that enabled her to learn from strategic interactions.
In this paper, we revisit the problem of learning in strategic environments with renewed focus on the impact of information asymmetry between two equally rational players who aim to maximize their total payoff. We ask again: can an uninformed player learn to allain the value of her Stackelberg outcome, through repeated interactions alone? In contrast to the aforementioned results, our findings largely imply that strategic interactions alone cannot facilitate learning effectively enough to earn an uninformed player the value of her optimal strategy.
Our Model and Contributions. To study the impact of informativeness on the ability of players to gain the payoff of their Stackelberg outcome, we study repeated interactions between two rational agents playing repeatedly a one-shot game G ~ D. While the players know D, they may not know the realized game G except perhaps through signals of differing precision about G. For example, one player may know G and another may have access to signal that reveals G with probability 0.5 and is uninformative (i.c., independently drawn from D) otherwise. Each player deploys an algorithm, which specifies her actions at every round, given all that the player has observed so far (e.g.. history of actions and/or utilities experienced) and the information she possesses about G. We consider meta-game where players' actions algorithms that specify agent's strategies in T rounds of interactions and study pairs of algorithms that form pure Nash Equilibria in the meta-game. We use the overall utility attained by pairs of algorithms that form pure Nash Equilibria draw clear separation between the informed and uninformed players' ability to attain the value of their Stackelberg optimal strategies.
In the following, we use Val, to refer to player i's value of her optimal Stackelberg strategy in game G. We summarize our results follows.
In Section 3, we study the full information asymmetry when player 1 (Pi) knows the realized game G and player (P2) only has partial information based imperfect signal. We show full separation in the achievable utilities. In particular, we show in Theorem 3.1 that for every distribution D and realized game G, there is pure Nash Equilibrium (PNE) in the meta game induced between the algorithms' of the two players for which P1 achieves her Stackelberg value, i.e., Stack (G). On the other hand, Theorem 3.2 gives distribution D such that no PNE of the meta game allows P2 to achieve EGLD (Stac (G)]. In other words, for some realized game G and all PNE of the meta-game, P2 cannot achieve the value of her optimal Stackelberg strategy for G.
Taken together, Theorem 3.1 and Theorem 3.2 establish that learning through interactions alone is not sufficient to allow an uninformed player (in this case, P2) to attain the value of her optimal Stackelberg strategy. Does this mean that P2 in unable to learn the game matrix through interac- tions that form a PNE in the gett-gamme? This is not necessarily the case (see Observation A.4) as indeed P2 may be able to learn the underlying game G eventually. What our results imply is that in every PNE, either P2 never learns the game G sufficiently well, or she has enough information identify G but the stability condition for her algorithm to be in PNE does not allow her to extract the value of her optimal Stackelberg strategy. This points to the limitations on what agents can achieve if their only source of learning is through repeated interactions.
In Section 4, we study setting where neither player fully knows the realized game G. Interest- ingly, a separation need not hold in this case. particular, there are distributions DD where the player with a less informative signal about G is able to extract her benchmark EG-D |Stack VG) while the player with the more informative signal cannot achieve her corresponding benchmark. This occurs when the less- ins--nnfrded player is able to learn the identity of G more efficiently,
Beyond myopic restonespnn,,ng, several other types of algorithms for the responding agent have been considered, such as gradient descent [21, 39], no-regret [25, 10]. no-swap regret [10], and responding to calibrated forecasts [28]; none of these focuses on how the other player's is learning dynamics may be affected as the result of the second player's actions.
2

---

possibly due to the structure of D. This is perhaps not surprising, given that less-informed player can become more informed or even perfectly aware of the realized game faster, while the player who started the meta-game with more informative signal continues to remain only partially informed.
On the possibility and impossibility of learning from strategic interactions. We view our work as providing different lens on studying learnability in the presence of strategic interactions that also elucidates the context and subtleties of a vast line of prior work in this space. By and large, prior work in this space [31, 8, 5, 35, 11, 25, 22, 15, 38, 28, 10] has attempted to establish the following message: "An uninformed player can always learn to achieve (even surpass) its Stackelberg value through repeated strategic interactions alone". At a high level, our work demonstrates the opposite, that "In some cases, an uninformed player cannot lear, through repeated interactions alone, to achieve its Stackelberg value". Of course, these messages, while both technically correct, are contrary to each other. So, what accounts for this difference?
One of our takeaways is that prior work's findings (that an uninformed can always overcome her informational disadvantage through repeated strategic interactions) heavily hinges on the lack of rationality of at least one of the agents in those strategic interactions. That is, the dynamics studied in prior work involve pairs of agent algorithms that are not best-responses to each other. On the other hand, our work shows that the inherent uncertainty about the game or more precisely, the informa- tion asymmetry between two equally rational agents - can persists throughout repeated interactions and makes it impossible for an uninformed agent to overcome her informational disadvantage.
The processes of learning and acting based on the learned knowledge are naturally intertwined when dealing with uncertainty in strategic environments. Our work implies that it is precisely because of their intertwined nature that an uninformed agent cannot overcome her informational disadvantage from strategic interactions alone. That is, information disadvantage between a pair of rational agents persists for one of two reasons: Either actions taken by the agents' algorithms do not reveal enough information to identify the game at play, or if they do, the less- ress-informed agents use of the elicited information would have lead the informed agent to deviate to an algorithm that barred her from learning in the first place.
1.1 Related Works
Algorithms and benchmarks for repeated principal-agent interactions. There is a vast literature investigating online algorithms and benchmarks in repeated games with agents under various behav- ioral models such as: 1) myopically best-reppn [31, 5, 8, 38]; 2) optimizing dime-discounted utilities [27, 29, 2, 1]; 3) employing no-regret [9, 17, 22, 25, 10, 26, 18], no-swap-regret [17, 32, 10], no counterfactual -nttuuaall-ttttaaa-- -ntereal-regret algorithms [11, 15], or online calibrated forecasting algorithms [28].
Given a particular model of the agent, what is the optimal algorithm to employ? This has been studied in both the complete and incomplete information setting. In the complete information setting, the static algorithm of playing the optimal Stackelberg strategy is shown to be optimal against no-swap-regret agents [17, 28]. But it is not necessarily optimal against general no-regret algorithms, including common algorithms such as EXP3 [9, 17, 26, 36). Additionally, it is not optimal against no-swap-regres agents in Bayesian games where agents have hidden information but is optimal if [32].
agents satisfy a stronger notion called no polytope-swap--ree
Long-term rationality of agents in the meta-game. Instead of modeling agents as no-regret learners, another line of research treats the repeated game as a meta-game in which players' actions are their choice of algorithms. Towards understanding the PNE of this meta-game, Brown et al. [10] show that no pair of no-swap-regret algorithms can form a PNE unless the stage game has PNE. Previous work discussed above on optimally responding to no-regret agents also has implications on the meta- veta-gamees PNE such as (1) no-swap-regre regret algorithms are supported in meta game PNE for all games G [17], and (2) there are games where no meta-game PNE contains certain common seieet-miniiizing algorithms such as EXP3 [10]. We discuss these implications in Appendix C.
Kolumbus and Nisan [30] study a meta-game where players are restricted to choose no-regret algorithms but have the option to manipulate their private information. They show that non-truthful PNE exists in multiple classes of games. Besides PNE, some previous works also study Stackelberg strategies of meta-games [14, 40]. Recently, Arunachaleswaran al. [3] study the Pareto optimality relative to all possible games instead of exact optimality in particular game.
3

---

Information asymmetry in repeated games. The final line of related work is the substantial literature on information asymmetry and repeated interactions including classical work by Aumann et al. [4]. They also study repeated games between player knowing the game and one who does not. For zero-sum games, they show that all PNE of the meta-game yields the same utility to the informed player and this utility can be higher than the informed player's one-shot urility. The higher utility is due to the informed player's s ability to shape the learned beliefs of the uninformed player and this power of information is also shown in recent line of work on follower deception in Stackelberg games [24, 33, 23, 6, 13, 12].
2 Model and Preliminaries
We study games between two players, referred to P1 and Pz. Wlog, we assume that P1 is generally more informed than P2 (to be defined formally below). Although we focus on repeated games, we first provide the setting for one-shot games and then build upon it for repeated games.
Bayesian Games. A game G' is a tuple A2, U1, U2), where A, is P.'s discrete action space, and U, : Ai x Ag + I is Pt's utility function (i E {1,2]). A Bayesian game is described by a family of games G and a distribution D E Ag) over games in this family, where g consists of games sharing the same action space. When P1 plays action x E A and P2 plays action y E A2 then they receive utilities U1 (x, y) and (z, y) respectively. We sometimes overload notation and write U1 (2, y; G), U2 y: G) denote that the utilities of the two players come from a particular game instance G. Instead of pure strategies (i.e., playing discrete actions), the players can also choose to play mixed strategies x E ((Ai) and y E A(A2) for players 1 and respectively. To simplify notation, we sometimes write (x, y) in place of Ex-x.y-- (x, v)] for P,'s 's utility. Unless specified otherwise, we assume that the players are moving simultaneously and they both know the prior distribution D. We also assume that every game G in the support of D has no weakly dominated action for either player. An action Zig E Ai is weakly dominated for P1 in G if there exists A(A1) {zo s.t., U1 (x(x,) y: G) 2 (1 y; G') for every y E A2. The weakly dominance property of actions yo E A2 is defined symmetrically for Pg.
Optimistic Stackelberg Value. The optimistic Stackelberg value of game G for Pt, denoted with (G), is the optimal value of the following optimization problem:
Stack StackVal, (G)
max EA(AA) (x
max
U1(x*,3)
where BRg(x"; G) A argmax, U2(x", y) indicates P2's set of best responses to x*. When there are multiple actions in (x" G). ties are broken optimistically in favor of Pt. We use (x" (G), G() to denote the pair of strategies that achieves the value Stack Val, For P2, the optimistic Stackelberg value VtackVal2 and ( (G)) are defined symmetrically. Finally, we define Stack (D) & EG-D Stack Val,())) to be the expected optimistic Stackelberg value for P; under the prior distribution D (i E (1,2)).
Game Information. We assume that both players know the prior D. After the game G ~ D is realized, each player P, also receives additional information about the realization of G, which is characterized by a signal s; E G. We assume that nature generates both signals $1, 82 independently and with potentially different precision levels P1.P2 E [0, 1]. and each player can only observe their own signal. Fixing a precision Pt, 8 perfectly reveals the true game G with probability pi, and with probability 1 Ps. it provides an independent draw from the prior distribution D. Formally, the conditional distribution of s; given G is defined as follows:
VG, s; E G, Pr, (s: G) = p; 1 (s; - + D(s.).
While each player can only observe their own signal 8;, we assume that the distributions generating both signals are common knowledge, i.e., both players know P1 and P2- Note that when p. = 1, the signal s; perfectly correlates with the realization G, in which case we say that P, is fully-nffood or have perfect knowledge about which game being played. On the other extreme, if p; = O, then the signal 8; reveals no additional information compared to the prior distribution D. In this case, we call P; uninformed. Throughout this paper, we focus on settings with information asymmetry where we always assume P; is more informed than P2, i.c. P1 >> P2.

---

Repeated Games. In this paper, we focus on repeated (Bayesian) games. Initially, nature draws a game G 9 from prior D. The game is then fixed and repeated for T rounds. At each round E [T]. Pi and P2 play strategies x", y' and obtain utilities (x',, y"; G), U2 (x", y"; G) respectively. We call G the stage game of the repeated interaction.
Without loss of generality, we use algorithms to describe both players' adaptive strategies in the repeated game. For E 21, we use Ti denote the algorithm used by P., which is a sequence of mappings (T() that at each round maps from player i's information about the game and historical observations the distribution of mixed strategies from which the next strategy is drawn. Specifically, for each round I, the mapping is defined as T/ (s1; H1, - A(x;), where 8; is the signal received by P; about the realization of G, and Hद¹ is the feedback that P; observed at round r (r E [t - 1)) When both players observe each other's ' realized strategies as well as their own (but not the other's) realized utilities, we have H = (x", y", U,(x", ;))) We call this the full-iffrrmatio feedback setting. We also consider the bandit feedback setting, where the players do not observe the strategies of their opponent, i.c., HJ = (x", Ux"XXX yy;; and H! = (y', U2(x", y":",,";C'" G)).
Trajectories and expected utillities. Consider fixed pair of algorithms (TI, Under every realization of (G,81, 82), algorithms (T), induce a distribution over trajectories of mixed strategy pairs of length T, which we denote with (x', "'yy")eett
TF (Ti, m2; G, 82) A(A)) In particular, the signals s; (i E {1, 2)) are inputs of क,, that specify P 's behavior upon receiving certain feedbacks, whereas G' influences P; is observed utilities, which is part of the feedback and indirectly influences P,'s strategies of the next round.2 We also use T (m, n2; G) to denote the mixture of 7 (Ti, T22 G, 81; 82) as 8; pp, G') for i E (1,
A(A(AI)
When the realized game is G and players use algorithms (TT1, R2) with time horizon T, the expected average utility of P. under G, denoted as Ü3(T1, T2; G), can be expressed as
U. (MI1,T2;))) G2; -
E
E U.''', (( NET
T
We further define U. (T), T2: BGnD U, (m), T2; G') as the expected average utility under D.
Equilibrium in the Meta-Game. We model the rationality of long-tern players by treating the repeated Bayesian game D as meta-game, where each player P, Ps action is an algorithm Ti and the utilities of each pair of action (Iı, π2) are given by (1(T), π2; D). Our analysis focuses on the pure Nash equilibria (PNE) of this meta game applied the asymptotic regime T + cc.
Definition 2.1 (PNE of the Meta-Game), We say that a pair of algorithmss (I n2) form a pure Nash equilibrium (PNE) in the meta- meta-game for all E { and all other algorithms T/e
lumsup (U, (T'; -= D) - U. (T, ( S 0,
T-
where - denotes the algorithm of P, 's opponent.
Finally, we define no-regret and no-swap regret algorithms below.
Definition 2.2 (No-(Swap) Regret Algorithms). An algorithm mi of Pi is called no-regret for all adversarial sequences y I-T E ((A2)* the strategies x output by nı satisfies
Elregreri"1 -
max ax EA11
Σ U1(x .y') - -x(x'' st] E (T)).
LE[T]
Furthermore, ni is called no swap-regret if
E[swap-regrer"] E
max L-
Σ - U, Ux x5)] E E
(E(TT]
where f(x) E ((Ai) denotes the mixed strategy induced by fxx as x ~ x. We define no-(swap)
regret algorithms for P2 symmetrically.
We remark that there exist no-regret and no-swap regret algorithms under both the full-information feedback and bandit feedback setting.
"Our results also hold in an alternative setting where both players can only play pure strategies at each round, i.e., x' x and y ~ y For the feedback H the realized utilities and the observations about opponent's strategy should both be defined in terms of (x", y instead of (x", yY). As result, T(T1, n2; G, $1, $2) becomes a distribution over pure- stre-strategy trajectories (x y')xetr)) instead of mixed strategies (x", y )(e)()
5

---

3 Interactions between fully-informed P and partially-informet P2
In this section, we analyze the setting with a fully-informed Pi - i.e., P1 knows the game G being played - and partially informed Pg. In other words, algorithms т and тT can each take an observable signal as input, where the signals received by Pi and P2 are independently drawn from signal distributions Pp, (-IG) and pppz (-IG) with precision p1 and p2 < respectively. Recall that each P. sees her realized signal S; and knows the precision levels p1 P2 of both players' signals.
Our main takeaway is that there is separation in the benchmarks for achievable cumulative utilities between P1 and P2 in this setting, when P1 and P2 employ algorithms that form a PNE of the meta- game. This is not surprising in the one-shot setting. But in the repeated setting, even with infinite rounds for P2 to learn the game from feedback gained throughout the interaction, we show that there is still a separation in achievable benchmarks.
This separation could be due two factors: 1) P2's inability to learn the game based repeated interactions, and 2) P2's 's failure to achieve the benchmark utility despite successful learning. We discuss this in more detail in Section 3.2 and Appendix A. We show that if P2 was able to learn the game based on external signals, then P2 would be able to achieve the benchmark. This highlights a fundamental difference between learning based on interactions with the other player and learning independently without relying on the other player. In the latter scenario, a utility benchmark is always achievable, whereas in the former, it is sometimes unattainable.
The benchmark that we will show separates P1 from P. is the average Stackelberg value with the player of interest as leader. Recall that Stack (al, EG-D [Stack [StackVal, (G]] for each P.. We will demonstrate the separation by showing that P1 is always able to achieve this benchmark through a PNE of the meta-game, for all D, but there exists some distribution in which no PNE of the meta-game yields P2 her counterpart benchmark.
We will first state the theorems and provide proof sketches later. Our first theorem (Theorem 3.1) asserts that Pi can achieve the benchmark Stack (D) by explicitly constructing a PNE pair of algorithms (Ii, m2) that grants P1 this utility in the asymptotic regime. In the proof of this theorem, we provide the rate of convergence to this utility (Remark B.
Theorem 3.1 (Benchmark achievable by P1 for all D). For every game family G and every distribution D E (g)) supported on it. there exists algorithu pair (11, T22 such that (I1, n2) is PNE of the meta- peeta-game, and VG E GG UT (I1, N2; G) 2 StackVal1(G) (1))).
That is, for every realized game G. the expected average utility of Pı over T rounds tends to of player strategies,
StackVal, (G) as T xc. The expectation is over the trajectories-eequeee and resulting utilities induced by the algorithms nı, T2 and G.
The next theorem completes the separation argument by constructing a specific game distribution where no PNE of the meta-game allows P. asymptotically achieve the benchmark VaackVal, (D).
Val,
Theorem 3.2 (Benchmark unachievable by P2 for some D). For all thresholds p" E [0, 1). there exists a game family G and a distribution D E (G)), s.i., Yp2 < p", all PNE (πI,, of the metu- game where P2's " signal is of precision p2 must suffer BG-D Ug (TI, R2; G) S StackValz(D))
(r((1).
This implies that there is a game G E G such that when G is realized, P2 's expected average utility over T rounds remains strictly bounded below StackVal, (G) even as T + DC.
Theorems 3.1 and 3.2 show that there is a separation in achievable benchmark whenever the less- informed player is at any informational disadvantage, however small, compared to the fully-infor info-minformed player. P2's ss signal could be arbitrarily close to being fully informative (i.c., P2 is arbitrarily close to 1), but there is still barrier between what P2 can achieve compared to P1, when Pj has full knowledge.
3.1 Proof sketches of main theorems
Now we present proof sketches for the two theorems, defering the full proofs to the appendices.
Proof sketch of Theorem 3. Our proof puts together results from previous work [17, 28). We present the proofs of these results for completion. In this proof sketch, we will prove the theorem when every game G in the support of is such that Pa has a unique hest-response y(x*; G) to P, 's optimal Stackelberg strategy x" (G). The full proof is in Appendix B.

---

Let Ti be the algorithm that plays Pi's optimal Stackelberg strategy of the realized game G (i.e.. x²()) at every round. Since P1 has access to signal that fully reveals the realized game G, Pi can compute x (G) and employ this strategy. Let ih be no-swap-regret algorithm in the bandit- feedback setting (the algorithm only based on the utilities received in each round). Such algorithms exist [7, 16, 34] and are deployable by P2 without any knowledge of the game played or P1 's strategies. Note that T2 does not use P3's 's signal s2. Therefore our analysis holds for all levels of precision of s2.
First, let us analyze the expected utility of P3 due to (T1, IT)). The generated trajectories when the game G is realized are of the form (x" (G). ) y)) Since T2 is so-swap-regret algorithm, the regret of this trajectory up to round T is sub-linear in T (o(T)).
Since we assumed that 2R₂ (x"; G) is unique, any round where P2 is not employing this unique best-response (y(x*; G)) causes P2 incur regret. The no-swap-regret property for P2 essentially means that P2's 's strategies in the trajectory (y") (y') become close to y(x"; G). And as a result, P1 's utility per round gets close to U1 (x* (G), G); which is StackVal, (G).
More formally, Pi's cumulative utility over T rounds satisfies EiETTy (x (G), U)) >
StackVal, (G) T ei ExEry llayl - yxxx; G)II,, where y(x*; G) is the one-hot vector encoding of u(x;; G) and a = max (o)x ( (xx G). We bound term Eiepy lly - y(xx; G)] using the no-swap-regret property. Py's swap regret is at least Eierr "2lly* G(x;;))l1. where C2 = U2)x*(G), v(xx;(())))) G))
the minimum differ- ence of P2's utility between playing the best response action G) and any other action in A2. Sub-linear swap regret therefore implies that E Et= lly - y(z G)ll]] o(T) and thus E EL (G), > StackVal, (G) TT T (TT), i.e., P 's expected average utility in T rounds is at least Stack StackVal, (G) - (1).
(G)x)))),))
We have shown that the pair (F1, achieves P1 's benchmark utility. We now show that it is a PNE of the meta-game. Fixing T1, the maximum utility P2 can get is the utility achieved by playing yxx:; G). Vt. P2 does not necessarily know G to play y(x"; G) for all t E [T',, but we have shown that due to T2 being a no-swap- regret algorithm, P2 ends up playing strategies close to y(x"; G) asymptotically. The difference between P2 's cumulative utility between playing 22 against Ti, versus playing per-round best response against и is at most O(Etetry E Ily" ((xx"G)]l which is o(T) by the no-swap-regret property. So P2 has vanishing incentive to deviate from 22 in the meta-game.
Next fixing T2 to be no-swap-regret algorithm, previous work [17, 28] caps Pi 's achievable utility through any algorithm 5ं (Deng al. [17, Theorem 6]). These results show that for every πí. P1 expected average utility induced by (Tí. T2) in T rounds is at most Stack (G) + (1). Since we have shown that (TI, yields at least Val, (G) - (1) for P1, there is vanishing incentive for P1 to deviate.
In Appendix B.I, we extend this proof to the scenario with potential ties in P2's best response, but under the assumption that P2 has no weakly dominated action. Using regret rates of standard swap-regret algorithms, we also provide the rate of convergence to the Stackelberg benchmark. D
Proof sketch of Theorem 3.2. To prove this theorem, we construct a family of two games G1 and G2 (shown in Figure 1) and let the prior distribution D to be uniform over G2 and G2- Note that the maximum value of game parameters depends inversely on A 1-p" I+px, where p" is the maximum precision of the signal received by P2. In this construction, the utility functions in both games are identical for P2 but different for Pt. This implies that P2 cannot gain any additional knowledge about which game is realized from looking at her own utility function.
We first illustrate the high-level idea by considering a hypothetical situation where the trajectory always converges to the Stackelberg equilibrium led by P, for all G. In other words, the trajectory converges to (x(y"; G1),y"(G,)
when G1 is realized and (a(y"; G2). y" (G22) when G2 realized. It is not hard to check that the Stackelberg equilibria turns out to be supported on different pure- strategy pairs: (A, C) in G and (B, D) in G2 (shaded cells Figure 1). Because the Stackelberg strategies differ for G and G2, to converge to the correct equilibrium, P2 must have gained full information about which game G is being played through repeated interactions with P,. However, from P 's perspective, the strategy pair (A, C)- the Stackelberg equilibrium led by P2 in G1-is
7

---

C
D
C
D
A B
16/7.
1
16/%
-32/7
A
1.
0.
-3//7
2,
0
0.
2
B
0.9,
0
0.1,
2
Game Matrix G1
Game Matrix G2
Figure 1: game matrices G1 and Gz. Pi is the row player and Pa is the column player. The values in each cell are (Pi 's utility, P3's s utility). Shaded cells represent the action profiles supported in the Stackelherg equilibria led by the column player. The parameter ry is defined as
I-p' E (0, 1J. where p' is the precision threshold of p2- 14p"
more favorable than the other equilibrium (B, D) in both G1 and G2. Therefore, instead of disclosing information about which G is realized, it would be more beneficial for P1 to conceal this information and always behave as if G were G1. Therefore, any pair of algorithms that give rise to this hypothetical situation cannot be an equilibrium in the space of algorithms.
Our actual proof applies similar ideas to establish a stronger claim: not only impossible for P2 to have the trajectory always converge to their Stackelberg equilibrium, but they cannot recover an average utility of StackValg(D) through any repeated interactions with P1 that are specified by PNE algorithm pairs. To argue this, we will use the notion of correlated strategy profiles (CSP) [3] as a succinct way of analyzing the expected utility of each player. For a distribution T over trajectories of length T,, the CSP induced by T², denoted CSPyr, is correlated distribution in A(A, x A2) which is taken as the empirical average of the mixed-strategy profiles in each time step, ie., CSPyr - Exx. vy: (erem)>>[((///)) Exe(r) X2 & yıl- Since CSPs serve as a sufficient statistics of both players' expected utility (which is a direct consequence of the linearity of utilities), working with them significantly reduces the dimension of the problem.
Special case: full information asymmetry. We start with the full information asymmetry setting, i... Pi 1 and p2 O. For the sake of contradiction, assume that pair of equilibrium algorithms (TI, Ø2) can let P22 achieve the benchmark StackValz = 3/2.. With the CSPs introduced above, we rewrite P2 average expected utility 2/2 CS) U2(2, y: G1)+ CGg.)))CCP, U2 yı G2), where we have used CSP1 and CSP2 to denote the CSPs induced by the distribution over trajectories generated by T 71 m22 G1) and T (T1. T22 G2), respectively.
Similar to the hypothetical situation sketched above, we want to argue that there incentive for P1 to deviate to an algorithm oं that always behaves according to Tı (G1) even when the actual game is G2. other words, we aim to show that P1 expected utility in G2 strictly increases after replacing the induced CSP from CSP2 to CSP,, i..., EysCSP, (T; G2) > Er~CSP, (T; G2). Note that for Pi's utility in G2, cells involving action all have utility close to 1, whereas those involving action D all have utility close to O. Therefore, it suffices to show that cells involving action D take up significant probability mass in CSP₂ but very little in CSP We break these into the following three claims and use the equilibrium condition to establish them in Appendix B.3.
Claim 1. CB, is very small, otherwise P1 would deviate to always playing action A.
Claim 2. CS,, D) is very small, otherwise P2 would deviate to always playing action C.
Claim 3. CSP D) is very large, otherwise P2 cannot achieve benchmark Stack Valy (D).
Towards partial information asymmetry. the remainder of this sketch, we discuss the extension of the above approach to the partial asymmetry setting where p1 1 and 0 S P2 S pp < 1. The fact that P2's 's signal is partially informative introduces extra challenge to our analysis, since P2 belief about the true game depends not only P, 's behavior during the interaction, but also on the information carried by the external signal 82- As a result, if P1 deviates to acting according to G1 when the actual game is G2, it does not trigger the expected CSP when the realized game is G1, but instead causes a "distorted" posterior since the distribution of 82 ~ Ppp (-IG2) does not change.
To illustrate this, consider the four different CSPs introduced by all combinations of the realized signals received by both players. For (i,j) E {1, 21, let CSP,, to denote the CSP induced by TT (MI, T2; 81, 82, G = 81) when 81 = G; and 82 = Gj (we have set G=a 81 because 81 perfectly reveals G). When the realized game is G2, Pi's expected utility before deviation is given by
1- P2
U2(T; G2) + 1+ P2
(TI, T2; G2)
E CS
E
U2(T;G2).
T CSPS
8

---

because the probability of P2 seeing signals 82 G1 and = G2 are 1_p2 and 1+ 2 respectively.
So, for the expected utility after deviation, the coefficients 1- and 1+ remain the same, but the first distribution CSP21 becomes CSP22 and the second distribution changes from CSP22 to CSP 12:
T2; G2) 1- p2 E CSCS
U2(T: G2) + 1+ P2
U1 (2;
E CS
U2(T:
2
However, if the true game were G1, then CSP and CSP12 12 would be realized with swapped probability 2 1+ and 1-f2, not the ones appeared in (m T2; G2)! Hence, even if we can guarantee that action pairs (A, Dj and (B, D) occur very infrequently when the true game is = G1. they L+ times when factoring into the utility after deviation ( T22 G2). Therefore, establishing the benefit of deviation requires much smaller probability of (A, D) and (B, D) under the CSPs induced by G = G1. This is why we need the game parameters to inversely depend on = I4p
may only occur under CSP12 12. whose frequency gets amplified by T-pz
I-p", where p" is an upper bound on P2.
3.2 Difference in learning through repeated interactions and learning independently
In this section, we provide an informal discussion on the reason behind P2's ss failure to recover their Stackelberg value benchmark through repeated interactions, with a more formal treatment deferred to Appendix A. We argue that the failure is not due to the PNE of meta-game always preventing P2 from "learning" the game, but rather because P2 cannot apply her learned knowledge to recover her Stackelberg value in any equilibrium.
At each round, P2 can form a posterior belief about the realized game G based on her observed feedback from the historical interactions and the initial signal 82 received. We say that P2 succesyfully Definition A.2).
learns her posterior belief converges to the point distribution on (formally Interestingly, using the same pair of PNE algorithms designed to show that P1 can achieve their Stackelberg value, we can show that P2 is indeed able to successfully learn G through strategic interactions. This is because P2 's strategy converges to the best response y(x"; G), which perfectly reveals G for some game families G. Thus, successful learning of G through repeated interactions can happen in a PNE of meta-game where Stack cannot be achieved (Observation A.4).
The problem preventing P2 from achieving Stack (al is not an insufficient rate or accuracy of learning, but rather the fact that learning and acting this learned knowledge are intertwined. In fact, if P. 's learning was independent of the repeated interaction, i.e., when P. has access to external signals that become more accurate over time, she can achieve StackValy( (Proposition A.5).
Interactions between two partially-infomme
players
In this section, we consider the setting where neither player is fully informed. That is, the precision of both player's signals P2) are less than one. Even though there may be information asymmetry in the form of different precision levels of player signals, we show that there is no longer a clear separation between players through the average Stackelberg value benchmark.
At a high level, what distinguishes this setting from the previous setting (hence resulting in the lack of separation), is that the identity of the more-informed player can shift throughout the course of the repeated interaction. Due to the structure of D, more information about the realized game may be released to one player compared to the other. In contrast, when the more informed player starts with perfectly knowing the realized game, there is no possibility of her becoming less informed since there no information beyond what she already knows.
Example 4.1. Consider D to be the uniform distribution over the two game matrices defined in the figure below.
C
D
C
D
A
1.
1
-1,
5
A
1.
3
1,
0
B
O.
2
2,
5
B
Game Matrix G1
Game Matrix G2
Figure 2: Example game matrices G = (C1, G2) revealing more information to Pz compared to P.. Here, Pt is the row player and P, is the column player.

---

Note that P2 chooses the pure strategy C. then for any strategy of P2's utility lies in the range [1. 2] if G is realized and the range [3. 7] if G2 is realized. Since both ranges are non-intersecting. P2 can deduce G exactly after single round by choosing the pure strategy B in the first round.
However, since the utilities of Pi for all action profiles are the same in both G1, G2. P1 gains no additional information about the realized game, So even if P1 started off with a more informative signal, after a single round, P2 becomes more informed and in fact perfectly informed.
To show that the average Stackelberg value benchmark does not separate the more- from the less- informed player, we will show that neither player can achieve the average Stackelberg value in all instances. Put another way, for every possible pair of player signals' precision, there is instance such that this player cannot achieve the benchmark value at equilibrium.
Proposition 4.2. For every player signal precision values P2 E [0, 1), for each i (1.2), there exists D such that for every PNE (T1, (2) of the
(TI, (T1, T2: D) s StackVal, (D) (D)-
Proof. The proof of this proposition reduces to the proof of Theorem 3.2. This is due to the following game-revealing property (similar to Example 4.1) of the construction D used in the proof of Theorem 3.2 described by Figure Since the range of the set of attainable utilities in G1, G2 when P1 chooses action A, has no intersection for Pi, regardless of P2 's strategy, Pi can deduce the game exactly after a single round while P2 gains no additional information after a single round.
After the first round, we are in the regime of fully informed P1 and partially informed P2 since P2 < 1. Theorem 3.2 already shows that in this regime, no equilibrium provides P. her average Stackelberg value benchmark. Using distribution D' that is the same as D but with player utilities flipped proves the proposition for Pz.
5 Discussion
In this paper, we study the effects of information asymmetry (codified in terms of signals about the game played) on the achievable benchmarks of two non-myopic players interacting repeatedly over T' rounds. First, we showed that when P1 is fully informed (i.e., knows G') while P2 is not, then there is a separation between the more and the less informed player by way of each player's achievable benchmarks. Next, we showed that when neither player is fully informed (i.e., both pL P2 < 1) then, there is no longer a clear separation between players in terms of benchmarks.
There are several avenues for future research stemming from our work.
Characterizations of algorithms that can be supported in an equilibrium. We should gain a better understanding of what algorithms from natural classes can be in equilibrium. A useful step would be to characterize the necessary and/or sufficient conditions for an algorithm to be supported in the PNE of the cata-game. Our work and previous work provide sufficient conditions such as no-swap-regret algorithms and best-responding per round: an algorithm satisfying either condition can be supported in a PNE of every meta-game if at least one player fully informed. Previous work also implies that no-regret is not sufficient for an algorithm to be part of meta-game PNE (see Appendix C for
more details). Finally, in the case where neither player is fully informed, it would be very useful to characterize the structure of the meea-gamee that causes shift wrt the information advantage.
Other models of how signals are generated. Alleviating some of our modeling assumptions, one could ask how the results would change if nature not assumed to be truthful with respect to the signal reporting but it may strategically modify the signals to achieve its own goals, such as maximizing social welfare. Taking this aspect into account, we can consider information design setting where the nature designs signaling scheme that shapes both agents' beliefs about the state and therefore their algorithms of choice. In addition, we have assumed that nature provides signals cost-free. This is required and natural first step, but an interesting direction would be to understand what happens when the signals are costly and their accuracy positively correlated with their cost.
Computational aspects of meta-game equilibrium. Moreover, it would be very interesting to see how the results about the effects of information asymmetry generalize the case where the players are computationally bounded; note that our current setup provides information-theores could be computationally hard for players to communicate their algorithms to each other, or even verify that two algorithms are equilibrium.
results, but it
10

---

Acknowledgements
This work was supported in part by the National Science Foundation under grant CCF-2145898, by the Office of Naval Research under grant N00014-24-1-2159, C3.A1 Digital Transformation Institute grant, an Alfred P. Sloan fellowship, a Schmidt Science A12050 fellowship, and an Amazon Research Award.
References
[1] Jacob D Abernethy, Rachel Cummings, Bhuvesh Kumar, Sam Taggart, and Jamie Morgen- stern. Learning auctions with robust incentive guarantees. Advances in Neural Information Processing Systems, 32, 2019.
[2] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. In Advances in Neural Information Processing Systems (NeurIPS), volume 26, 2013.
[3] Eshwar Ram Arunachaleswaran, Natalie Collina, and Jon Schneider. Pareto-optimal algorithms for learning games. arXiv preprint arXiv:240.00954, 2024.
[4] Robert Aumann, Michael Maschler, and Richard E Stearns. Repeated games with incomplete information. MIT press, 1995.
[5] Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Commitment without regrets: Online learning in Stackelberg security games. In Proceedings of the 16th ACM Conference on Economics and Computation (EC), pages 61-78, 2015.
[6] Georgios Birmpas, Jiarui Gan, Alexandros Hollender, Francisco Marmolejo, Ninad Rajgopal, and Alexandros Voudouris. Optimally deceiving learning leader in stackelberg games. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 20624-20635. 2020.
[7] Avrim Blum and Yishay Mansour. From external internal regret. Journal of Machine Learning Research, 8(6), 2007.
[8] Avrim Blum, Nika Haghtalab, and Ariel Procaccia. Learning optimal commitment to overcome insecurity. In Advances in Neural Information Processing Systems (NeurIPS), volume 27, pages 1826-1834, 2014.
[9] Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg. Selling to no-regret buyer. Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 523-538, 2018.
[10] William Brown, Jon Schneider, and Kiran Vodrahalli. learning in games good for the learners? Advances in Neural Information Processing Systems (NeurlPS), 36, 2024.
[11] Modibo K Camara, Jason D Hartline, and Aleck Johnsen. Mechanisms for no-regret agent: Beyond the common prior. In Proceedings of the 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 259-270 IEEE, 2020.
[12] Yurong Chen, Xiaotie Deng, and Yuhao Li. Optimal private payoff manipulation against commitment in extensive-form games. arXiv preprint arXiv:2206. 13119, 2022.
[13] Yurong Chen, Xiaotie Deng, Jiarui Gan, and Yuhao Li. Learning to manipulate a commitment optimizer. arXiv preprint 233.v:2302211822 2023.
[14] Natalie Collina. Eshwar Ram Arunachaleswaran. and Michael Kearns. Efficient stackelberg strategies for finitely repeated games. In Proceedings the 2023 International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), AAMAS '23, page 643-651, 2023.
[15] Natalie Collina, Aaron Roth, and Han Shao. Efficient prior-free mechanisms for no-regret agents. arXiv preprint 41X04:231..07754, 2023.

---

[16] Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. From external to swap regret 2.0: An efficient reduction for large action spaces. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1216-1222, 2024.
[17] Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against no-regret learners. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, pages 1579-1587, 2019.
[18] Kate Donahue, Nicole Immorlica, Meena Jagadeesan, Brendan Lucier, and Aleksandrs Slivkins. Impact of decentralized learning on player utilities in stackelberg games. arXiv preprint arXiv:2403.00188, 2024.
[19] Fei Fang, Thanh Nguyen, Benjamin Ford, Nicole Sintov, and Milind Tambe. Introduction to green security games. In International Joint Conference on Artificial Intelligence (IJCAI). 2015.
[20] Julius Farkas. Theorie der einfachen ungleichungen. Journal für die reine und angewandte Mathemarik (Crelles Journal), 1902(124):1-22) 1902.
[21] Tanner Fiez, Benjamin Chasnov, and Lillian J Ratliff. Convergence of learning dynamics in stackelberg games. arXiv preprint 190.011906.01217, 2019.
[22] Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in Stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In International Conference on Machine Learning (ICML), pages 1133-3144, PMLR, 2020.
[23] Jiarui Gan, Qingyu Guo, Long Thann, Bo An, and Michael Wooldridge. Manipulating learning defender and ways to counteract. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
[24] Jiarui Gan, Haifeng Xu, Qingyu Guo, Long Tran-Thanh, Zinovi Rabinovich, and Michael Wooldridge. Imitative follower deception in stackelberg games. In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 639-657) 2019.
[25) Denizalp Goktas, Jiayi Zhao, and Amy Greenwald. Robust no-regret learning in min-max stackelberg games. In Proceedings of the 2022 International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 543-552, 2022.
[26] Guru Guruganesh, Yoav Kolumbus, Jon Schneider, Inbal Talgam-Cohen, Emmanouil-Vasiln Vlatakis- Gkaragkounis, Joshua R Wang, and S Matthew Weinberg. Contracting with learning agent. arXiv preprint vrxiv:2401.66990 2024.
[27] Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, and Alexander Wei. Learning in stackelberg games with mon-myopic agents. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 917-918, 2022.
(28) Nika Haghtalab, Chara Podimata, and Kunhe Yang. Calibrated stackelberg games: Learning optimal commitments against calibrated agents. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2024.
[29] Mohammad Hajiaghayi, Mohammad Mahdavi, Keivan Rezaci, and Suho Shin. Regret analysis of repeated delegated choice. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), volume 38, pages 9757-9764, 2024.
[30] Yoav Kolumbus and Noam Nisan. How and why to manipulate your own agent: On the incentives of users of learning agents. Advances in Neural Information Processing Systems, 35: 2022.
[31] Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In Algorithmic Game Theory, pages 250-262. Springer, 2009.
[32] Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Strategizing against learners in Bayesian games. In Conference on Learning Theory (COL.T), pages 5221- 5252. PMLR, 2022.
12

---

[33] Thanh Nguyen and Haifeng Xu. Imitative attacker deception in stackelberg security games. In International Joint Conference on Artificial Intelligence (LJCAI), pages 528-534, 2019.
[34] Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and applications to approxi- mate correlated equilibria. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages
2024.
[35] Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu. Watch and learn: Optimizing from revealed preferences feedback. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 949-962, 2016.
[36] Aviad Rubinstein and Junyao Zhao. Strategizing against no-regret learners in first-price auctions. arXiv preprint arXiv:2402 2.660770 2024.
[37] Gilles Stoltz and Gábor Lugosi. Internal regret in on-line portfolio selection. Machine Learning, 59:125-159, 2005.
[38] Geng Zhao, Banghua Zhu, Jiantao Jiao, and Michael Jordan. Online learning in stackelberg games with an omniscient follower. In International Conference on Machine Learning, pages 42304-42316. 16. PMLR, 2023.
[39] Tijana Zrnic, Bric Mazumdar, Shankar Sastry, and Michael Jordan. Who leads and who follows in strategic classification? In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 15257-15269, 2021.
[40] Song Zuo and Pingzhong Tang. Optimal machine strategies to commit in two-person repeated games. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 29, 2015.
13

---

A Difference in learning through repeated interactions and learning independently
In this part, we will use Theorem 3.2 to show that there is a difference between learning through repeated interactions and learning independently based on external signals. We will argue that learning independently is more powerful as it allows achieving the average Stackelberg benchmark, whereas learning based on repeated interactions does not always allow this.
Our approach to doing this is to introduce two models of learning: one based on histories generated by the repeated interaction and the other based on external signals. Fixing the same success criterion for both models (to defined soon), we will show that
1. Successful learning by P2 based on repeated interactions is possible at PNE of the meta- game, but still does not yield P/ her average Stackelberg value (Observation A.4).
2. Successful learning by P2 based on external signals makes P2's 's average Stackelberg value achievable at a PNE of the meta-game, for all 'D (Proposition A.5).
We first define both learning models and the success criterion of learning. Later in this section, we state results demonstrating the separation between the two learning models.
Successfully learning realized game G entails forming beliefs over the realized game such that the beliefs asymptotically concentrate on the true realized game G.
Definition A.I (Successful learning criterion). Given a realized game G from a game family G, a belief sequence (B') where B E (9) is a belief (distribution) over G for each t E N, successfully learns G if PIzr~3r1 [GT + G] E (1). That is, the beliefs asymptotically fully
concentrate on the realized game G.
Different models of learning involve different constraints on or power afforded how beliefs of the realized game are generated. The first model of interest is learning based on repeated interactions. Here, the belief at a round is constrained be formed based on the initial signal and the history at round generated during the repeated interaction.
Definition A.2 (Successful learning based on repeated interactions). Given a family of games 9 and player P; (i E {1, 11, a history-based belief function for P; is mapping from the player's 's signal value and a history of repeated interactions to a belief distribution supported on G. Formally, we denote the belief function with h (s;; H + AG)).
Given a distribution D E (G). we say a history-based belief function h, as defined above, success- fully learns based on interactions through the algorithm pair (T1, X2) ifr every realized game G G
and every realized signal $1, $2, the induced beliefs (Bt) where each belief 3 fi(s,, :!:
induced by histories the realized game G (according to Definition A. with probability 1.
H. generated from the distribution (" n2: G, 82). successfully learns
The second form of learning occurs without dependence on the other player's actions and instead based on externaly provided signals.
Definition A.3 (Successful independent learning). Given a distribution of games D, we say that P. can independently Iearn successfully if for every realized game G ~ D, there is sequence of signals (q' ) with q¹ E G. that are generated by a sequence of signaling distributions (Q' y with Q AGG), where the sequence (Q y successfully learns the realized game G (according to Definition A.I).
The signal qf is provided P, round I. So P:'s algorithm ni maps the initial signal 8i, history at each round L (H. ), and g¹ to a strategy taken at round t.
Revisiting Theorem 3.2, which states that the average Stackelberg value is not achievable by P2 for some D, we can question whether some property of 'D and the equilibria of the meta-gan sata-game prevents P2 from successfully learning or if P2 can successfully learn but cannot use this learning to achieve her Stackelberg value. We assert that it is the latter.
Observation A.4. There is a game distribution D, such that there exists a PNE (T,, 12) of the meta-game peet- that allows P2 to successfully learn based repeated interactions (in the sense of
14

---

Definition A.2), but no equilibrium allows P2 to achieve her average Stackelberg value benchmark StackValz (aackVal2()))
D
E
F
A
16/7,
1-c
16/7,
-32/y
16/7.
1 +
B
2.
0
0.
2
2.
C
(16
- -c//,
1tc
16/7,
-32/7
(16 - cl/7,
1 1-c
Game Matrix Gi²
E
F
A
1.
1 1-6
6
0.
-32/7
1. 1 +
B
0.9.
0
0.1,
2
0.9,
C
1+G,
1+c
0,
-22/7
1tc,
1-
Game Matrix G²2
Figure 3: game matrices Cj and G2. Pj is the row player and P2 is the column player. The values in each cell are (Pi 's utility, Pa 's utility). The parameter y is defined as I-p" of p2-
I+p" E (0, 1], where p" is the precision threshold
Proof. Consider the construction of 'D used in Theorem 3.2 (Figure 1). D is a distribution with equal probabilities over two game matrices G1, G2. Theorem 3.2 proves that the average Stackelberg benchmark is unattainable by P2 in any equilibrium.
For this proof, we will consider another construction D' that is equal probability over game matrices G¹, G2 defined in Figure 3. Gj is essentially G1 with an additional row and column, where the additional row is essentially a duplicate of the first row and the additional column is essentially duplicate of the first column. Rather than being an exact duplicate, the new row/column is a small perturbation (given by parameter e) of the original row/column it duplicates. G²2, is obtained from G2 similarly.
Since the new construction is essentially duplicating rows/columns of the old construction, by the same argument as Theorem 3.2, the average Stackelberg benchmark is also unattainable by P2 in any equilibrium of the meta- game of the Bayesian game D
Despite this, we can show there is an equilibrium enabling P2 to successfully learn through repeated interactions. We construct the perturbations to ensure that the Pi-led equilibrium response has a different response for P2 in G compared to G% Our argument is that the meta-game PNE pair results in both players playing the Pidled Stackelberg equilibrium of the realized game. Therefore, based on P2's 's responses generated by the trajectories of the meta-game PNE, P/ can determine the realized game.
Consider the algorithm pair where P1 plays her Stackelberg strategy of the realized game and P2 plays a no-swap-regee weggrtt algorithm. The proof of Theorem 3.1 showed that this pair forms an equilibrium and that Pz 's strategy eventually becomes the best-response of the realized game due to Py's 's no-swap-regret property. Note that the two games G¹, G²2 in the support of D' have different P2 responses in P 's Stackelherg equilibrium. So based on the strategies P2 plays, she will be able to deduce the realized game. Consider the belief function that at round computes the average Yr yr and forms a belief concentrated on G¹2 if lly. - yxx:; Gllll < lly: y(xx; G1 and forms a belief concentrated on G¹2 otherwise, where yxx:; GK) is the one-hot encoding vector of the best response y(x;; G)) in game G. The induced sequence beliefs concentrates on the true realized game and hence satisfies the accuracy criterion for learning the realized game. Therefore, there is an equilibrium of algorithms that allows Pz to successfully learn.
strategy employed thus far: y, 1/(1 1) Ei=ly
The above observation highlighted a limitation of successful learning based on repeated interactions. There could be two reasons driving this limitation. One possibility is that the accuracy criterion for successful learning is not strong enough to always enable achieving the average Stackelberg value benchmark. The other possibility is that the learning process relies on the actions of the other player in the repeated interaction.
15

---

We will now argue that the limitation arises from the second reason and not the first. If the accuracy criterion for successful learning is met through independent learning based on external signals instead of histories of the game dynamics, we will show that the average Stackelberg value benchmark becomes achievable.
The following proposition shows that if P2 can successfully learn independently for every D, then P2 can achieve her average Stackelberg value Stack (aackVal((D)) for every at PNE of the meta-gan game. This extends Theorem 3.1, which stated that this is possible if P2 was fully informed. Essentially, successful independent learning guarantees the same power to a player as being fully informed from the beginning.
Proposition A.5. For every D for which P2 can successfully learn independently (Definition A.3), there is algorithm pair (T1, T2) such that (T1,72) is a PNE of the meta- game and GG E 9, (1 n2; G) 2 Vta) (r)).
Proof sketch. The equilibrium algorithm pair we will show guarantees this utility to P2 is the one where P2 employs the Stackelberg response of the game denoted by the external signal q¹ at round I and P1 employs no-swap-regret algorithm.
We defined successful independent learning as when the less informed player learns the realized game to arbitrarily high precision, based on external signals. the external signals were not quite as powerful, the average Stackelberg benchmark can no longer be always achieved. In particular, if P2 could only learn the realized game to precision bounded away from 1, Theorem 3.2 shows that the average Stackelberg benchmark is not always achievable when P1 is fully informed about the game.
B Missing Proofs
B.1 Proof of Theorem 3.1
Theorem 3.1 is implied by Proposition A.5. Please see the proof of Proposition A.5 in Appendix B.2.
B.2 Proof of Proposition A.5
We will construct algorithm pair (T1, such that when P1 is able successfully learn through an independent sequence of signals (q'),=1, 1. (#1, T2) is an equilibrium pair and guarantees P1 an expected average utility of at least Stack Val, (G) (G)-or (1) in T rounds, for every realized game G. The same proof also holds if P2 is the player able to learn through external signals. Let (x* (G),v(x*; G)) denote P1 's Stackelberg strategy and P2's best response in the game G. Let (x"; G) be the one-hot encoding vector of y(x";G) G).
We choose T2 to be no-swap-regret algorithm with swap-regret rate ( for 1. We will first construct T1 in the setting with a known, finite time horizon T so that P2 achieves average regret Stack Val, (G) (1(1) in T rounds when interacting with P2 employing no-swap-regret algorithm. This is builds on the proof of Theorem 4 by Deng et al. [17]. We will present the argument here for completeness. We will later show how apply the doubling trick to extend this to the setting with infinite time horizon.
Under the assumption that the realized game has no weakly dominated actions, we will show how Pı can choose a strategy x' so that y(x"; is Pa's unique best response and x' is close to x" (G)). Since y(x"; : G)) is not weakly dominated, there is y' E (AA2 \ fu(x*; G))) such that
yz" 2 U2 xx, (x";; G)) for all æ E A₁. By Farkas' lemma [20], there must exist a X E ((Ar) such that U2 G)) Z U2(8. p(x;;(())))))))>> + e for constant >> O. This implies that if P1 plays the strategy X, (1 - 6)x* + 58, then for all values of > 0, Pz's unique best response to x", is G(x To indicate dependence of this strategy on the game G, we will also denote it by (G). Choosing a small á enables P1 to play a strategy close to the Stackelberg strategy while ensuring that P2's 's unique best response is G))
In the each round t E [T], Pi employs x5r((')) where qf is the signal at round t. We will later describe how to choose 5t. Let (x', "x',y") y') be the sequence of strategies generated through the interaction of the above algorithm of P, and P2's no-swap-regret algorithm. Given a 8², let us compute P, 's expected cumulative utility. Let Z' be a random variable indicating if the external signal at round t is the realized game i.e., Zt = (g' = =). In rounds with zt = 1, the immediate regret of P2 at round is clly² y(x:; G)Ll- A lower bound on P 's regret based regret accumulated
16

---

only in rounds with Z" = is Et= 0" c. I' -)lx where e == U2(x', u(xx:G)) U2(x', y).
T 8 c. I''ly' - yx(";
swap-regret
E Elswap-regrei]
8 c. 1Blz Ellly y(x";
(Independence between o and P2's action)
8 oT()) E
lly' ;(*;
(Successful learning criteria)
E[swap-regret] E O(T")
(T2 's swap regret bound)
ly y(xx
00(T))0')
(1)
P1 's cumulative utility satisfies:
T
T E|Z (Ui(x)r ;(xx;));;GG) - Ellly y(x;; + 02
T Σ
U1 (x", y": 0)
E[1 - z4|
1=1
[=1
T
E|Z (Stack Val, (G) -2 Eilly y :) +
E[1 z
1=
where
G1 U1 x(x;))
vEAI)(((r:)) Ux
min
C2 min U1(x,y),
=EAL.EA:
C3 = Stack (G) - U1 (xx y(x G):
Finally, we use Equation (1) and E| = (1) to conclude that
T
IC
Σ Ui(x'' .'))
2 StackVal, T (1ap::00--00000-000000000101-111 -((T),
(2)
In eq. (2), the second term TT comes from playing action X instead of x to induce a unique best response; the third term ei (T comes from the swap regret of Pz, and the last o(T) term comes from eπrоrs in the external signals Z, By choosing 8 - for some 0 < b < a, m yields Stack Val, (G)-T- o(T) utility to P1. In the special case where the last o(T) term zero (e.g., when P1 has perfect knowledge about the game G as in Theorem 3.1), tradeoff by setting
achieve the optimal be Lef which yields a convergence rate O _ to StackVal (G).
The doubling trick to construct Ti that does not rely on the time horizon being known: Initialize maximum horizon T.. Until the round index hits Tm. employ Xsr.. Once t Tm. update T'm + 21',, and employ xST... until the round index exceeds the new max horizon.
Remark B.1 (Rate of convergence to Stackelberg benchmark.). Algorithms that provide swap- regret rates of (2) are known [7, 37]. By setting 1/ and = 2² our proof shows that these algorithms lie in PNE of the meta came that results in ((33/4) convergence rate to P1 Stackelberg benchmark.
B.3 Proof of Theorem 3.2
We prove this theorem for every fixed signal precision P2 = S p*. Before diving into the proof, will first introduce some notations. For (i,j) {1,2) {1,2), we use CSPs, to denote the CSP
17

---

C
D
C
D
A
16/7.
16/%.
-32/7
A
1,
-2/7 0.
B
2,
0
0.
2
B
0.9,
0
0.1,
2
Game Matrix G1
Game Matrix G2
Figure 4: game matrices G1 and G2. Pi is the row player and Pa is the column player. The values in cach cell are (P) 's utility, P3's utility). Shaded cells represent the action profiles supported in the Stackelberg equilibria led by the column player. The parameter ry is defined as I-p" E (0, 1J, where p' is the precision threshold of 14p
induced by T (T1,, 12; = G, 82 = G G.). Note that we have taken 81 and G to both be G; because $1 = G when P1 1. Recall that ( T2; G2. G,, G²) is the distribution over trajectories of length (denoted as 7 (x', xx'y")) (T())) generated by the pair of algorithms (T T2) when takes input signal G; and me takes input signal Gj. Formally, we have
1
iS - CSP (, TMTTMmGGGGGGG.
Σ x 8y: T
1
In addition, for E {1,2}. we use CSP; to denote the CSP generated by the trajectory distribution T (T1, T22 G.). Since 81 perfectly correlates with G, and $2 drawn from the signal distribution
Ppp2 (s| p+ 1 {s- = G} + - 1 (s + G}. can equivalently write CSP1 and CSP2
1 P IS + 1-P P CSP125 12:
CSP
2 CSP₂
1 CSSP21
1 CSP
2
As argued in the proof sketch, we will establish the following three claims about CSP, and CSP2. Claim B.2. If (TI,TT) T2) forms an equilibrium in the algorithm space, then CSP, D) + o1))
Claim B.3. If (M1, n2) forms an equilibrium in the algorithm space, then CSP (A, D) s + (1)
Claim B.4. If Claim B.3 holds and (πI, 12) grants P2 the expected Stackelberg value, i.e.,
inm U2(T1, T2; 3 T-000
then (B, 2 1/2+ ((1.
We will first build the proof of Theorem 3.2 on these claims, and then formally establish these claims in appendix B.4.
Assume that (Ti, R2) is PNE the meta-game that lets P2 achieve the benchmark Stack StackVal(2) Val(D) 3
We show that if (T1, X2) satisfies Claims B.2 through B.4, then P1 gains utility by deviating to an algorithm xf that always plays according G1.
Formally, consider oं defined as follows. For any history time step t > 0 and any history H (r > 0).
(G H A ग. (G1, H|", YG E (G1, G2).
After the deviation, P1 average utility can be expressed
I T
of ( T2) = - UT,, m2; (2) +
1-p
Σ
Un(xx
4
T-T
T
T Σ
1 1+p
E
TTT
T t=1
18

---

Since oं is defined to behave according to #i on observing G1, the above equation can be rewritten
1 1-p
U1(4), T2)
[1,, T2; G1) +
[1 y; G2)]
2
4 (m.))~CSP1
+
E
(1, G2)]
(x.y)~CSP12
Now we define new CSP to be the mixture of CSP and CSP12 but CSP12 is taking up more probability than CSP 11:
CSP & - 1 1
CSP
2
Note that compared with the CSP1 defined before (repeated below)
CSP = + CSP 11 +
1-21 CSP 12:
2
2
conclude that for any action pair (2r E {A, {C, D),
(a, - + P CSP (z.1)
+ D CSP (z. y) 1 CSP (x,y), y), p
7
1-p" Combined with where the second step used p S p* and the last step uses the definition of = 14p= the upper bounds on CSPi(B, D) and CSP (A, from Claim B.2 and Claim B.3, we have
CSP + CSP (A, D) < (CSP) + CSP, (A, D)) < 4 + oT()).
(3)
Finally, we lower bound the increase in P1 's utility after deviating from m to q follows. Since
m2) 0f (T) m2) (c..))
[U1(2, y: G2) (2.g)~C5P,
UU((2 yi G2))
it suffices to lower bound the difference in utility when G2 is realized.
On the one hand, note that (z( yy G2) 2 0.9 as long as (a, 3) + (A, or (B,D), we have
E
U1 y. G2) 2 (1 CSP D) - (B, 0.9
(..p)
(from eq. (3)) On the other hand, since U1 y: Gz) S 0.1 when (x.1) (B, D) and Un (xx y: G2) < otherwise, we have
2 or(1) 0.9 > 0.6 -r)
E
CSP (B, D) 0.1 CSP D))
CSPP
1.1 ool(1) 2
(CSP, D) 2 2 + +T((1) from Claim B.4)
< 0.6 + or(().
As result, after taking their difference, we have that in the asymptotic regime
lim T
(UT T2; UT (2, m2; D)) > 0,
which contradicts with the assumption that (Iı, л2) forms PNE (ef. Definition 2.1) in the meta- game! Therefore, cannot be possible for any PNE (Nı, R2) of the meta game to achieve the benchmark Stack (alp for Pz. The proof is thus complete.
19

---

B.4 Proof of Technical Claims
Proof of Claim B.2. We prove this claim by contradiction. hold, i...
Assume that the above claim does not
lim sup CSP (SPI((B,
7 8
T-+00
will show that Pi gains utility by deviating to another algorithm n.j that always plays action A regardless of the signals and the feedbacks observed. We have
lim inf U. (TT, m2;
T-000
=lim inf
Uf (TI, (TL T2; G1) + _ 07 (TI,
(51, T2: G2)
T-400
2
=lim inf
E U1 G1) 2 (s.P)
E
(1 y; G2)
T-*x
2 (2:D)~CSP,
16
1
< lim inf T-000
(B) 0 (1- CSP.CSSP(BB.)
.1)
?
2
(U G1) s 16 for all (a, + (B, D); (2 yi G2) S 1 for all (z, (),
1
1
7
16
+
1
(assumption that lim supr CSP (SB, D)) > }
2
8
7
2
8
On the other hand, since P1 always plays action A under 71,, which has utility y in G1 regardless of the strategy of P2, we have
limsup 0f (T T2: D) 2 lim sup sup ] of 12; D)
16
2
T-
T- 2
2
Combining the above two inequalities give (21, lim (UT (T', T2; D) 0 ,,;,,;; D)) > 0,
T2;
T-x00
which violates the requirement of PNE in Definition 2.1. Therefore, we have established the claim that CB,, < (1)).
Proof of Claim B.3. Again, assume for the sake of contradiction that CSP D) ] o1) does not hold, which implies
lim sup I 2
T-
We upper bound P2's utility under equilibrium as
lim inf Uh (TI, D2;
T
lim inf T430
(1
E (SP))
(2(2, G1)
1
E (2(2,):
(2.0))CPP,
32
1 2
lim inf T-x
(A,
+
1
CSP1(A, -2
2
(Pz's s utility is -32/y for (A, D) and < 2 for all other cells)
32 7
+ (1
11
(assumption that lim supt CSP (4, D) 7/8.)
16
16
0.
On the other hand, if P2 deviates to an algorithm Th that always plays action C regardless of the signal 82 and the observed feedbacks, then the average utility U2 (m,, m/z D) is always nonnegative. As result, we have
lim (UT ( m/z D) U (m1, T2, D)) > 0,
T
which again violates the condition of (πI, being a PNE in the meta-game, Therefore, we must have CS,, < Or()..
D
20

---

Proof of Claim B.4. Note that U2 is the same under G1 and G2, for which the top-2 2 highest utility values are achieved by (B, D) and (A, C)) respectively. Therefore, we can upper bound P2 expected average utility as
U (2 =
E (2.0)~CPP,
U1) + (2.9)~CSPP
E
U2(1, 9i G2)
(BPI(BB,)) (
+ 1
*2(11 (1-CSS2 D)) 1 CSP D) D)
2
= 1 1+
CSP1 ( (B,
2 (B,
2
1
1 1
CSP (B,, o())
16
2
where the last step uses Claim B.3. On the other hand, from the assumption, (2 T2: D) is lower bounded by 3/2 as oc. Therefore, we obtain
2
lim CBP 21 T-x
8
which proves (BP2(B,D) (11).
C Implications from prior works
In this section, we provide arguments for the following claims about PNE of the meta game that are implied either directly or indirectly by previous works. We say that an algorithm मं of P, is supported in meta-game game PNE if there exists an algorithm ã= such that the pair (T,, m-s) forms a PNE of the meta-game. The claims in this section provide answers to whether common classes of algorithms such as wwwapreeret-mmnimiiz response are always/someimmes/neer supported in a meta-game game PNE.
myopically best-responding, playing Stackelberg
Claim C.1. All no-swap-regrel algorithms are supported in meta-game PNE for all games G. Put another way, being no-swap-rees is sufficient condition for an algorithm to be supported in some meta-gan game PNE.
Proof. This is direct corollary of [17, Theorem 6] which can also be justified by proof of Theorem 3.1. Consider the pair algorithms (T1, T2) in which лı plays strategies close to the Stackelberg optimal strategy (via doubling trick, see Appendix B.2 for the full construction), and m is a no-swap-regret algorithm. We have proved in Appendix B.2 that (Ti, T2) is a PNE in the meta- game because no-swap-regret algorithms are able to cap their opponent's utility the Stackelberg value.
The second claim is stated Theorem 2 by Brown al. [10]. Since most game matrices do not have PNE, this claim effectively states that a pair of no-swap-regret algorithms cannot be PNE the meta-game for most games.
Claim C.2 (Theorem 2, [1O].. Unless the stage game has a PNE, any pair of two no-swap regret algorithms cannot form PNE of the meta-game.
Claim C.3. No-regret is not sufficient condition for an algorithm to be supported in meta- came PNE. For common no-regret algorithms such as EXP3, there is game where no meta-game PNE contains this algorithm.
Proof sketch. This claim can be established by combining two claims in [9]. In their setting, a single seller repeatedly sells single item single buyer for T rounds. We will use two of their results:
1. (Theorem 3.1 of [9]) If the buyer uses EXP3 or other mean-based algorithms, then there exists algorithm for the seller which extracts (almost) full welfare.
2. (Theorem 3.3 of [9] There exists an algorithm for the buyer (no-regret without overbidding), which caps the seller's 's revenue at the Mayerson value.
21

---

Wlog, assume Pi 's algorithm is a mean-basee no-regret algorithm such as EXP3. We will show that for any algorithm Ta of Pz, the pair (Ti, π2) cannot PNE of the meta-game.
Let T/ be the algorithm given by the above result that lets P2 extract full welfare against иj. Let Tं be the algorithm that achieves the property in the above result 2.
On the one hand, if UI (m), x2) S Welfare (D) Q(T"), then P1 will increase utility by deviating to algorithm T1. thus (T1, m2) cannot be a PNE in the meta-game.
On the other hand, if TT is already extracting full welfare against स2 (meaning that P1 is getting asympiotically zero utility), then P1 has the incentive to deviate to algorithm T2. under which she can cap P2's 's utility the Myerson value and therefore guarantee herself nonzero utility, For this reason, (T), T2) cannot be PNE in the meta-game.
Combining the above two cases, conclude that æn cannot be supported in any PNE of the meta-game.
22

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and the introduction clearly state the claims and contributions of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Section 5,
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
23

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide proof for each theoretical result in either the main body or the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided not)?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/ http://udddes/oooSSuuiiiseee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips.co. cttps.ccc/pae aerliiiggiiess/CCe
iesionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
25

---

7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /etp:://neu...eeeeeeee www.rriss.ccppuulpee ct/ppblic////ccccpccccccccccccct /Ethi issuuddelines"
Answer: [Yes]
26

---

The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., . if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
While our work provides commentary and critiques of how interpret previous results on learning in strategic interactions to overcome lack of information, we do not prescribe any new methods.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
27

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
28

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
29


Reviews:
[{"review_id": "eKBSiYLh5j", "reviewer": "Reviewer_CgaS", "summary": "The paper explores the impact of information asymmetry on the ability of agents to achieve their Stackelberg optimal strategy in repeated games. It investigates whether agents can overcome initial uncertainty through strategic interactions alone. The authors propose a meta-game model where players' actions are algorithms that determine their strategies based on observed histories and knowledge of the game. The paper's main findings suggest that while an informed player can always achieve her Stackelberg value, an uninformed player cannot necessarily do so, even with repeated interactions.", "questions": "Could the authors highlight their contributions and discuss the significance of the results?", "limitations": "I did not find any limitations of the paper.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1 The paper presents a clear and novel perspective on information asymmetry in strategic interactions.\n2 The theoretical model and meta-game framework are well-defined and contribute to the understanding of learning in games.\n3 The analysis of pure Nash equilibria provides valuable insights into the limitations of learning through repeated interactions.", "weaknesses": "While the paper discusses the inability of uninformed players to achieve their Stackelberg values, it could provide more insight into the learning dynamics and the rate at which players converge (or fail to converge) to these values.\n\nThe findings of the paper, while theoretically sound, may not offer surprising or counterintuitive insights that significantly advance the field. \n\nThe authors does not clearly articulate how its findings contribute to the existing body of work in the field of game theory and strategic interactions. The paper would benefit from a clearer exposition of how its findings contribute to the existing body of work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions.\n\n> While the paper discusses the inability of uninformed players to achieve their Stackelberg values, it could provide more insight into the learning dynamics and the rate at which players converge (or fail to converge) to these values.\n\nIn our paper, we study the interactions between the informed and uninformed players across a wide range of algorithms, rather than analyzing a specific or parameterized class of algorithms. Because we consider such a broad set of algorithms, we treat the agents’ choices of algorithms as black-boxes. As a result, our primary focus is on determining whether certain benchmarks can be achieved at all, rather than on the learning dynamics or convergence rates. \n\nNonetheless, when it comes to specific types of interactions that our work addresses, we can provide convergence guarantees using the techniques and results from past work. For example, in demonstrating that the more informed agent can always achieve their Stackelberg value at some PNE (Theorem 3.1), we constructed a pair of algorithms where the informed player (P1) plays strategies close to the Stackelberg strategy and the less informed player (P2) uses a no swap regret algorithm. Implicitly in our proof (see line 627), we show that P1’s convergence rate depends on P2’s swap regret.  For example, when P2’s swap regret is of order $\\sqrt{T}$, P1’s convergence rate is $O(T^{3/4})$. On the other hand, our negative results show that in no PNE a sublinear convergence to P2’s Stackelberg value is possible. \n\nWe will clarify this point further in the revision by adding a remark about the convergence rate after Theorem 3.1.\n\n> Main contribution, significance of results, and relation to previous work.\n\nWe view our work as providing a different lens on studying learnability in the presence of strategic interactions that also elucidate the context and subtleties of a vast line of prior work in this space. By and large, prior work in this space has attempted to establish the following message: “An uninformed player can always learn to achieve/surpass its Stackelberg value through repeated strategic interactions alone.” At a high level, our work demonstrates the opposite, that “In some cases, an uninformed player cannot learn, through repeated interactions alone, to achieve its Stackelberg value”. Of course, these messages, while both technically sound, are contrary to each other. So, what accounts for this difference?\n\nOur work elucidates that the results of prior work (i.e., that learning does happen) hinge on an asymmetry in the rationality levels of the two agents that interact with each other. That is, the dynamics that are studied in prior work involve pairs of agent algorithms that are not best-response to each other. This lack of rationality confounds the takeaway message of prior work, leaving one to wonder whether it was the lack of rationality of the second agent or some genius of the first agent’s algorithm that enabled the first player to learn from strategic interactions.\n\nThe starting point of our work is therefore to consider agents that are rational in their choice of algorithm, which we capture by studying the pure Nash Equilibria (PNEs) of the meta-game that is the repeated interactions between two agents. Through this lens, we show that an uninformed agent may not be able to learn to achieve her Stackelberg value (Theorem 3.2), which is what she could have achieved if she was fully informed (Theorem 3.1).\n\nLet us expand on the above by discussing our paper’s takeaways:\n\n**Takeaway 1:** In settings with informational asymmetry, informational advantage can persist throughout repeated interactions. We show this by constructing an instance where no PNE of the meta-game allows the less-informed player to achieve her Stackelberg value. This stands in contrast to results from previous work that show that it is always possible to learn unknown information and achieve the Stackelberg value when interacting with agents from specific classes of algorithms. This difference is due to the pair of algorithms considered in previous work not being a PNE of the meta-game, that is, at least one of the agents was not rational in her choice of the algorithm.\n\nCompared to prior work that also argues that the more-informed player can prevent the less-informed player from realizing her Stackelberg value by misrepresenting her private information, we show this in a stronger sense, without making behavioral assumptions on the more-informed player, and instead analyzing the PNE of the meta-game. Therefore, we show that it is the inherent nature of information asymmetry and not any limit on agent rationality that drives the persistence of the informational advantage throughout repeated interactions. \n\n**Takeaway 2:** The persistence of informational advantage is due to the processes of learning and acting based on the learned knowledge being intertwined. This demonstrates the nuances of why informational advantage persists. We argue that this is not due to the less-informed player being unable to learn the unknown information alone. In fact, in our construction in Theorem 3.2 where the less-informed player is unable to achieve her Stackelberg value, she still does fully learn the game matrix. However, if she deviated to using this learned information to obtain her Stackelberg value, the other player would benefit from deviating to a different algorithm that does not depend on informed player’s knowledge and hence prevents learning the game. \n\nIn this work we used the meta-game’s PNE as a way to reflect on the interpretations of previous work on repeated strategic interactions. We hope this framework will be useful for future work to also shed light on natural algorithms that may be used and how this depends on the structure of the game and the forms of information available to each agent.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GcSxTEXiWg", "reviewer": "Reviewer_bNuD", "summary": "The paper studies two-player repeated games where both players use (no-regret) learning algorithms to choose strategies simultaneously in each stage, which are called meta-games. The authors define the pure Nash equilibria of the meta-games and explored the players' equilibrium utilities based on their initial information  about the game. Specifically, they find that if one player is fully informed of the game while the other is partially informed, the fully informed player can always guarantee its Stackelberg utility at some equilibrium, while the partially informed one cannot. When both players are partially informed, then there are cases that either can fail to obtain her Stackelberg value.", "questions": "1. See weaknesses 2. \n2. Do the agents's set of strategies need to be the same to obtain all the results? \n3. Does the meta-game always admit a pure NE?", "limitations": "1. The related work with on \"Information asymmetry in repeated games\" is missing references. I suggest the authors refer to the \"related work\" section in the paper they cite, \"learning to manipulate a commitment optimizer\", to include all references. Two references that I know are missing are:\n\n    \"\n- Thanh H. Nguyen and Haifeng Xu. Imitative attacker deception in Stackelberg security games. IJCAI'19\n\n- Yurong Chen, Xiaotie Deng, and Yuhao Li. Optimal private payoff manipulation against commitment in\nextensive-form games. WINE'22\n    \"\n\n2. typos:\n    1. line 338: \"that that\" -> \"that\"", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The meta-games where players use learning algorithms to play against each other is natural and important, due to the widespread use of machine learning techniques. The results into how initial information asymmetries influence the utilities players can achieve in equilibrium is interesting.", "weaknesses": "1. The paper can be presented more clearly and rigorously in at least the following ways:\n    1. Beginning with the discussion of Stackelberg games in the introduction is confusing as the paper considers repeated simultaneously games. \n    2. The reason why take Stackelberg value as a benchmark is lacking. \n    3.The statements of the theorems do not mention which learning classes are used (no-regret or no-swap regrets, or hold for both), and whether two players have the same sets of learning algorithms.\n    4. The paper does not mention whether any meta-game holds a pure NE. \n2. The paper lacks a clear explanation of its technical novelty compared to previous work on strategizing no-regret learners?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback.\n\n> Reason for using Stackelberg value as a benchmark\n\nThank you for your question. We agree that more information on choosing Stackelberg value as a benchmark will strengthen the paper. We plan to include more details, as we briefly discuss below.\n\nWe view our work as providing a different lens on studying learnability in the presence of strategic interactions that also elucidates the context and subtleties of a vast line of prior work in this space. Therefore, we use the benchmark that is primarily studied in this line of work, which by and large, uses the one-shot game's Stackelberg value as the benchmark for the repeated game. Stackelberg value of the one-shot game forms a particularly compelling benchmark to study because it is both achievable and the tightest under some assumptions in prior work [Brown et al.; Haghtalab et al.; NeurIPS'23]. \n\nThe Stackelberg value is also unique for general sum games, unlike other equilibria classes (such as NE and CE). Hence, the Stackelberg value provides a clean way to show separation between the benchmarks achievable by informed and less-informed players in the meta-game’s PNE.\n\n> Which learning classes are used?\n\nWe believe there may be a misunderstanding about our setting, as described by the reviewer’s summary. We do not restrict either player to specific learning classes, such as no-regret or no-swap regret algorithms. Instead, we allow both players to choose any algorithm from the entire space of all possible algorithms, as long as they form best responses to each other. In Line 161-163 we define algorithms as sequences of mappings from the player’s information about the game and the historical observations to the (randomized) strategies in the next round. We are intentional in this choice because, as this (see Appendix C) and some prior work show, a pair of no-regret algorithms cannot form an equilibrium with each other. Therefore, to model the long-term behaviors of both agents, we need a much larger and more expressive space of algorithms.\n\n> Do the agents' sets of strategies need to be the same?\n\nWe interpret the “set of strategies” in your question as referring to the strategies in the meta-game, ie., the long-term strategies or algorithms. Indeed, the set of long-term strategies (i.e., algorithms) is semantically the same for both agents, which is the space of all possible algorithms. In Lines 161-163 of our paper, all algorithms can be written as sequences of mappings from the signal $s_i$ and the historical observations to the strategies that the agents want to use in the next round. The only difference between the two agent’s set of algorithms is that their input signals $s_1$ and $s_2$ may carry different amounts of information. \n\nIf your question refers to whether both agents’ sets of pure strategies are the same for all one-shot games G in the support of D, the answer is also yes. This is implicit in our paper, and we will clarify it in future versions.\n\n> Technical novelty compared to previous work on strategizing against no-regret learners\n\nOur main contribution is conceptual, providing a framework for interpreting previous work on strategizing against algorithm classes like no-regret, rather than introducing new tools. Our framework results in the following key takeaways:\n\n**Takeaway 1:** In settings with informational asymmetry, informational advantage can persist throughout repeated interactions. We show this by constructing an instance where no PNE of the meta-game allows the less-informed player to achieve her Stackelberg value. This contrasts previous works that show that it is always possible to learn unknown information and achieve the Stackelberg value when interacting with agents employing specific classes of algorithms. This difference is due to the pair of algorithms considered in previous works not being a PNE of the meta-game and hence having differing levels of rationality.  \n\n**Takeaway 2:** The persistence of informational advantage is because learning and acting based on the learned knowledge are intertwined. We argue that this is not due to the less-informed player being unable to learn the game, but because if she uses this learned information to achieve her Stackelberg value, her opponent would benefit from deviating to a different algorithm that does not reveal knowledge of the game to prevent her from learning. \n\nOn the technical front, in our lower bound construction showing that no PNE allows the less-informed player to achieve her Stackelberg value (Theorem 3.2), we use the concept of correlated strategy profiles (CSP) introduced by [Arunachaleswaran, 2024] as a simple sufficient statistic for the average utilities resulting fromdue to pairs of arbitrary algorithms. By using CSPs, we can greatly simplify the analysis, reducing the complexity of the problem from high-dimensional distributions over trajectories to the lower-dimensional distributions over stage game strategy pairs. This simplification enables us to conduct a careful case analysis of the lower-dimensional distribution, identifying the conditions and structures of distributions that can correspond to PNEs in the meta game. Our results provide further evidence that such techniques can be valuable for understanding the trajectories of strategic repeated interactions.\n\n> Does the meta-game always admit a PNE?\n\nFor the main setting we studied (one player is fully informed), the meta game always admits a PNE. In the proof of Theorem 3.1, we have explicitly constructed a PNE. When both players are partially informed, we suspect that the existence of PNE can be formally established similar to the extensions of the Folk Theorem [Wiseman, Econometrica'05]. We will add a remark to future versions of our paper. \n\n> Missing references\n\nThank you for pointing out these references. We have already cited the first reference, but we will add the second one and any other missing citations to future versions of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1b4VRVLQf6", "reviewer": "Reviewer_LLSw", "summary": "In this paper, the authors study whether players can achieve the Stackelberg value when they have uncertainty about the game. Specifically, the authors consider a two-player setting where players can repeatedly interact with the environment. They consider the pure Nash equilibrium in the meta game where the strategies are long-term algorithms. They demonstrate that (1) when one player is perfectly informed, there exists a PNE where the player can achieve his Stackelberg value, (2) when one player is perfectly informed, there is a game where no PNE allows the other player to achieve his Stackelberg value, and (3) when both players are not perfectly informed, both players may not achieve their Stackelberg value in any PNE.", "questions": "See the weakness part.", "limitations": "See the weakness part.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Studying the results for games with uncertainty is an important and interesting research direction.\n2. The theoretical results are generally sound.\n3. The paper is well-written and easy to follow.", "weaknesses": "I do not have major issues with this paper, but some results need further clarification.\n1. In Section 3.2, the authors explain that learning and acting on this learned knowledge are intertwined. I would expect the authors to provide more details. Intuitively, in my opinion, if the less-informed player could estimate the game correctly, he can then behave as the perfectly informed player. Since the authors study the case when $T \\rightarrow \\infty$, it is possible for the less-informed player to study the game for the first $o(T)$ rounds and then use the same strategy as the perfectly informed player. I expect the authors to explain why this would not work.\n2. Proposition 4.2 demonstrates that when both $p_1$ and $p_2$ are smaller than 1, both players cannot achieve the Stackelberg value in any PNE of the game. However, the result is different as long as one of $p_1$ or $p_2$ is 1. The change in the results when $p_1 = 1$ and $p_1 < 1$ is \"non-smooth,\" and I expect the authors to provide further insight about this.\n3. I found a typo. There are two words \"about\" in Line 162.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the insightful questions.\n\n> further clarification on section 3.2, why cannot thee less-informed player estimate the game for the first o(T) rounds and then use the same strategy as the perfectly informed player for the rest of the rounds\n\nThank you for the question. We believe this is an important note, and we will explain this in more detail in the revision. In particular, let us explain why your proposed algorithm for P2 may not be supported in any PNE. If P2 attempts to estimate the game in the first o(T) rounds, she would need to gather information about the game through repeated interactions with the informed player P1. However, if P2’s Stackelberg strategy as a “perfectly informed player” is not favorable to P1, P1 would have an incentives to deviate to an alternative algorithm that does not reveal any game information to P2 during these o(T) rounds. For example, P1’s alternative algorithm could behave exactly the same regardless of the true game being played. As a result, P2 is no longer able to accurately estimate the game in the first o(T) rounds. This is also the intuition behind our proof of Theorem 3.2, especially those sketched in Line 274-286. \n\nAs a result, for P2’s algorithm to be in equilibrium, either she cannot successfully estimate the game, or, even if she manages to estimate it the first o(T) rounds, she cannot deploy the Stackelberg strategy of the estimated game in the remaining the rounds, as P1 would then deviate. In other words, P2 either cannot learn the game or, if she does, she cannot use her learned knowledge to achieve her Stackelberg value benchmark.\n\n\n> insights into why the change in results from $p_1=1$ to $p_1<1$ is non-smooth\n\nIntuitively, when $p_1=1$, the player P1 already has perfect knowledge about the game, so there is no additional information for P1 to learn through interactions. As a result, whether P2 deviates or not does not impact P1’s ability to implement his Stackelberg strategy. However, when $p_1$ is even slightly smaller than 1, there remains a small amount of information that P1 needs to learn from interactions with P2. In this case, P2 could potentially have (though tiny) incentive to deviate to an alternative algorithm that prevents P1 from learning this remaining information, similar to the scenario described in the previous question. In other words, this non-smoothness is inherently similar to the non-smoothness of Nash equilibria generally, as even minimal incentive to deviate from a strategy can disqualify a pair of strategies from being an equilibrium.\n\nOn a technical level, our lower bound proof (Theorem 3.2) for the case when $p_2\\to1$ relies on constructing game matrices with utilities that scale inversely to $1-p_2$. Specifically, this lower bound construction would no longer be valid if $p_2=1$ because the game needs to be finite.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UOtU3Hm6XA", "reviewer": "Reviewer_r7Rg", "summary": "This paper addresses the theoretical question of whether, through repeated interactions, strategic agents can overcome the uncertainty about the exact payoff structure of the game being played to achieve outcomes they could have achieved in the absence of uncertainty. The authors specifically consider a Stackelberg Game setting, where there are two players, each aiming to maximize their total payoff in the repeated games, with one being more informed about the game structure than the other. The degree of informedness is modeled as a real number $p \\in [0,1]$, representing the precision of the signal. It denotes the player's probability of knowing the exact game structure being played each round in addition to a prior distribution. In this setting, the authors study the pure Nash equilibria (PNE) of a meta-game where players choose their decision-making algorithms as their actions. The results demonstrate that when player $P_1$ knows the game perfectly while player $P_2$ does not, there is a clear separation: $P_1$ can always achieve her Stackelberg value, while $P_2$ sometimes cannot. Conversely, if both players are not perfectly certain about the game being played, such separation is provably gone. Overall, this paper advances the theoretical understanding of learning in strategic environments by showing that repeated strategic interactions alone are not enough for an uninformed player to effectively play a Stackelberg Game.", "questions": "1. Am I correct that each game $G$ in the support of $\\mathcal{D}$ must have the same action spaces for both players? Otherwise, it seems that if a player is not perfectly informed about $G$, it is possible for her to make an invalid action.\n2. If applicable, can you explain the connection of this work with the real world? Feel free to skip this question if you prefer.", "limitations": "I think the authors adequately mentioned the limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The topic being studied in this paper is fundamental and relevant to the NeurIPS community.\n2. The theoretical findings are clean and fundamental. While non-trivial to prove, the statements of results are concise, and they reveal novel theoretical understandings of learning in strategic environments.\n3. The paper is quite well-written, with good typesetting, clear notations, formal statements and proofs, understandable interpretation of results, and proper attribution of them in the introduction.", "weaknesses": "I have no major concerns about this work as a theoretical paper in NeurIPS. \n\nIf I had to mention a weakness, it would be that the theoretical findings of this work are currently somewhat detached from reality, limiting their direct impact on the real world. That being said, I think this is perfectly fine for a theoretical paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback on our work.\n\n> same action spaces for all G in the support of D\n\nYes, we agree with your point. We do require all the games in the support of D to have the same action spaces for both agents to avoid the issue that you proposed. We will make sure to add this clarification to our model section.\n\n> the connection of this work with the real world\n\nWe agree that our work is mainly theoretical. At this stage, our focus is on providing a different lens for the line of work on learning through strategic interactions, rather than immediate applicability to real-world algorithms. However, we believe our work opens the door to many interesting questions about algorithms in the real world. As highlighted in the second paragraph of our discussion section, one interesting open direction is to understand what natural class of algorithms are supported in meta-game PNE, and what benchmarks are achievable when both players are restricted to these classes. In addition, relaxing some modeling assumptions, such as introducing costly signals or considering computationally bounded agents, can further improve the real-world applicability of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies how agents can overcome uncertainty about their utilities through repeated interaction in strategic environments. The main focus of the paper is on the impact of information asymmetry on the ability of agents of reaching their Stackelberg value.

All the Reviewers agree that the problem studied in the paper is interesting and relevant to the NeurIPS community. In particular, the idea of meta-game introduced in this paper to study the dynamics generated by two learning algorithms repeatedly interacting in a strategic environment is novel and natural. Thus, **I recommend the paper to be accepted at NeurIPS.**

There are some minor issues raised by the Reviewers that the Authors are strongly encouraged to fix in the final version of the paper. Specifically: 

1. The reason why the paper considers the Stackelberg value as a benchmark is lacking, additional discussion on this choice should be added to the paper.

2. While the paper discusses the inability of uninformed players to achieve their Stackelberg values, it could provide more insight into the learning dynamics and the rate at which players converge (or fail to converge) to these values.
Decision: Accept (poster)