Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions

Authors: nivasini  ananthakrishnan
nika  haghtalab
chara  podimata
kunhe  yang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:32:59

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.

Main paper: 
 introduction: 
 Learning to act in strategic environments is fundamental to the study of decision making under uncertainty in a wide range of applications, such as security, economic policy, and market design (e.g., [31, 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 to achieve outcomes they could have achieved in the absence of uncertainty. An extensive line of work on learning in Stackelberg Games [5, 8, 31, 35] has focused on answering this question for achieving the Stackelberg value, which is the optimal payoff a player guarantees herself when assuming other players will best respond to her actions. While a player who hopes to attain her Stackelberg value in a one-shot game must know the game (i.e., know the utilities of all players), this line of work asks whether a 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 preferences of well-behaved best responding agents1 , 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 a 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 attain 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 a signal that reveals G with probability 0.5 and is uninformative (i.e., 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 a meta-game where players' actions are 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 to draw a clear separation between the informed and uninformed players' ability to attain the value of their Stackelberg optimal strategies.In the following, we use StackVal i (G) to refer to player i's value of her optimal Stackelberg strategy in game G. We summarize our results as follows.• In Section 3, we study the full information asymmetry when player 1 (P 1 ) knows the realized game G and player 2 (P 2 ) only has partial information based on an imperfect signal. We show a 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 a pure Nash Equilibrium (PNE) in the meta game induced between the algorithms' of the two players for which P 1 achieves her Stackelberg value, i.e., StackVal 1 (G). On the other hand, Theorem 3.2 gives a distribution D such that no PNE of the meta game allows P 2 to achieve E G∼D [StackVal 2 (G)]. In other words, for some realized game G and all PNE of the meta-game, P 2 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, P 2 ) to attain the value of her optimal Stackelberg strategy. Does this mean that P 2 in unable to learn the game matrix through interactions that form a PNE in the meta-game? This is not necessarily the case (see Observation A.4) as indeed P 2 may be able to learn the underlying game G eventually. What our results imply is that in every PNE, either P 2 never learns the game G sufficiently well, or she has enough information to identify G but the stability condition for her algorithm to be in a 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 a setting where neither player fully knows the realized game G. Interestingly, a separation need not hold in this case. In particular, there are distributions D where the player with a less informative signal about G is able to extract her benchmark E G∼D [StackVal(G)] while the player with the more informative signal cannot achieve her corresponding benchmark. This occurs when the less-informed player is able to learn the identity of G more efficiently, possibly due to the structure of D. This is perhaps not surprising, given that a 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 a 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 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. 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 learn, 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 information 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-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.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 behavioral models such as: 1) myopically best-responding [31, 5, 8, 38] ; 2) optimizing time-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-internal-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-regret agents in Bayesian games where agents have hidden information but is optimal if agents satisfy a stronger notion called no-polytope-swap-regret [32] .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 a PNE. Previous work discussed above on optimally responding to no-regret agents also has implications on the meta-game's PNE such as (1) no-swap-regret algorithms are supported in a meta-game PNE for all games G [17] , and (2) there are games where no meta-game PNE contains certain common regret-minimizing 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 et al. [3] study the Pareto optimality relative to all possible games instead of exact optimality in a particular game.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 a 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 utility. The higher utility is due to the informed player's ability to shape the learned beliefs of the uninformed player and this power of information is also shown in a recent line of work on follower deception in Stackelberg games [24, 33, 23, 6, 13, 12] .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 in 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 to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
model and preliminaries: 
 We study games between two players, referred to as P 1 and P 2 . Wlog, we assume that P 1 is generally more informed than P 2 (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 (A 1 , A 2 , U 1 , U 2 ), where A i is P i 's discrete action space, and U i :A 1 × A 2 → R is P i 's utility function (i ∈ {1, 2}). A Bayesian game is described by a family of games G and a distribution D ∈ ∆(G) over games in this family, where G consists of games sharing the same action space. When P 1 plays action x ∈ A 1 and P 2 plays action y ∈ A 2 , then they receive utilities U 1 (x, y) and U 2 (x, y) respectively. We sometimes overload notation and write U 1 (x, y; G), U 2 (x, y; G) to 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 ∈ ∆(A 1 ) and y ∈ ∆(A 2 ) for players 1 and 2 respectively.To simplify notation, we sometimes write U i (x, y) in place of E x∼x,y∼y [U i (x, y)] for P i '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 x 0 ∈ A 1 is weakly dominated forP 1 in G if there exists x ∈ ∆(A 1 \ {x 0 }) s.t., U 1 (x, y; G) ≥ U 1 (x 0 , y; G) for every y ∈ A 2 .The weakly dominance property of actions y 0 ∈ A 2 is defined symmetrically for P 2 .Optimistic Stackelberg Value. The optimistic Stackelberg value of a game G for P 1 , denoted with StackVal 1 (G), is the optimal value of the following optimization problem:StackVal 1 (G) ≜ max x ⋆ ∈∆(A1) max y∈BR2(x ⋆ ;G) U 1 (x ⋆ , y),where Game Information. We assume that both players know the prior D. After the game G ∼ D is realized, each player P i also receives additional information about the realization of G, which is characterized by a signal s i ∈ G. We assume that nature generates both signals s 1 , s 2 independently and with potentially different precision levels p 1 , p 2 ∈ [0, 1], and each player can only observe their own signal. Fixing a precision p i , s i perfectly reveals the true game G with probability p i , and with probability 1 -p i , it provides an independent draw from the prior distribution D. Formally, the conditional distribution of s i given G is defined as follows:BR 2 (x ⋆ ; G) ≜ argmax y∈A2 U 2 (x∀G, s i ∈ G, φ pi (s i | G) = p i • 1 {s i = G} + (1 -p i ) • D(s i ).While each player can only observe their own signal s i , we assume that the distributions generating both signals are common knowledge, i.e., both players know p 1 and p 2 . Note that when p i = 1, the signal s i perfectly correlates with the realization G, in which case we say that P i is fully-informed or have perfect knowledge about which game is being played. On the other extreme, if p i = 0, then the signal s i reveals no additional information compared to the prior distribution D. In this case, we call P i uninformed. Throughout this paper, we focus on settings with information asymmetry where we always assume P 1 is more informed than P 2 , i.e., p 1 > p 2 .Repeated Games. In this paper, we focus on repeated (Bayesian) games. Initially, nature draws a game G ∈ G from prior D. The game is then fixed and repeated for T rounds. At each round t ∈ [T ], P 1 and P 2 play strategies x t , y t and obtain utilities U 1 (x t , y t ; G), U 2 (x t , y t ; 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 i ∈ {1, 2}, we use π i to denote the algorithm used by P i , which is a sequence of mappings (π t i ) t∈[T ] that at each round maps from player i's information about the game and historical observations to the distribution of mixed strategies from which the next strategy is drawn. Specifically, for each round t, the mapping is defined as π t i : (s i ;H 1:t-1 i ) → ∆(x t ), where s i is the signal received by P i about the realization of G, and H r i is the feedback that P i observed at round r (r ∈ [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 r i = (x r , y r , U i (x r , y r ; G)). We call this the full-information feedback setting. We also consider the bandit feedback setting, where the players do not observe the strategies of their opponent, i.e., H r 1 = (x r , U 1 (x r , y r ; G)) and H r 2 = (y r , U 2 (x r , y r ; G)). Trajectories and expected utilities. Consider a fixed pair of algorithms (π 1 , π 2 ). Under every realization of (G, s 1 , s 2 ), algorithms (π 1 , π 2 ) induce a distribution over trajectories of mixed strategy pairs of length T , which we denote with(x t , y t ) t∈[T ] ∼ T T (π 1 , π 2 ; G, s 1 , s 2 ) ∈ ∆(∆(A 1 ) T × ∆(A 2 ) T ).In particular, the signals s i (i ∈ {1, 2}) are inputs of π i that specify P i 's behavior upon receiving certain feedbacks, whereas G influences P i 's observed utilities, which is part of the feedback and indirectly influences P i 's strategies of the next round. 2 We also use T T (π 1 , π 2 ; G) to denote the mixture of T T (π 1 , π 2 ; G, s 1 , s 2 ) ass i ∼ φ pi (• | G) for i ∈ {1, 2}.When the realized game is G and players use algorithms (π 1 , π 2 ) with time horizon T , the expected average utility of P i under G, denoted as Ūi (π 1 , π 2 ; G), can be expressed asŪ T i (π 1 , π 2 ; G) ≜ E τ ∼T T (π1,π2;G)   1 T t∈[T ] U i (x t , y t ; G)   .We further define Ū T i (π 1 , π 2 ; D) ≜ E G∼D Ū T i (π 1 , π 2 ; G) as the expected average utility under D. Equilibrium in the Meta-Game. We model the rationality of long-term players by treating the repeated Bayesian game D as a meta-game, where each player P i 's action is an algorithm π i , and the utilities of each pair of action (π 1 , π 2 ) are given by Ūi (π 1 , π 2 ; D). Our analysis focuses on the pure Nash equilibria (PNE) of this meta game applied to the asymptotic regime T → ∞. Definition 2.1 (PNE of the Meta-Game). We say that a pair of algorithms (π 1 , π 2 ) form a pure Nash equilibrium (PNE) in the meta-game if for all i ∈ {1, 2} and all other algorithms π ′ i , lim supT →∞ Ū T i (π ′ i , π -i ; D) -Ū T i (π i , π -i ; D) ≤ 0,where π -i denotes the algorithm of P i 's opponent.Finally, we define no-regret and no-swap regret algorithms below.). An algorithm π 1 of P 1 is called no-regret if for all adversarial sequences y 1:T ∈ ∆(A 2 ) T , the strategies x 1:T output by π 1 satisfiesE[regret T 1 ] ≜ E max x ⋆ ∈A1 t∈[T ] U 1 (x ⋆ , y t ) -U 1 (x t , y t ) ∈ o(T ). Furthermore, π 1 is called no swap-regret if E[swap-regret T 1 ] ≜ E max f :A1→A1 t∈[T ] U 1 (f (x t ), y t ) -U 1 (x t , y t ) ∈ o(T ),where f (x) ∈ ∆(A 1 ) denotes the mixed strategy induced by f (x) as x ∼ x. We define no-(swap) regret algorithms for P 2 symmetrically.We remark that there exist no-regret and no-swap regret algorithms under both the full-information feedback and bandit feedback setting.3 Interactions between fully-informed P 1 and partially-informed P 2In this section, we analyze the setting with a fully-informed P 1 -i.e., P 1 knows the game G being played -and a partially informed P 2 . In other words, algorithms π 1 and π 2 can each take an observable signal as input, where the signals received by P 1 and P 2 are independently drawn from signal distributions φ p1 (•|G) and φ p2 (•|G) with precision p 1 = 1 and p 2 < 1, respectively. Recall that each P i sees her realized signal s i and knows the precision levels p 1 , p 2 of both players' signals.Our main takeaway is that there is a separation in the benchmarks for achievable cumulative utilities between P 1 and P 2 in this setting, when P 1 and P 2 employ algorithms that form a PNE of the metagame. This is not surprising in the one-shot setting. But in the repeated setting, even with infinite rounds for P 2 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 to two factors: 1) P 2 's inability to learn the game based on repeated interactions, and 2) P 2 '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 P 2 was able to learn the game based on external signals, then P 2 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 P 1 from P 2 is the average Stackelberg value with the player of interest as leader. Recall that StackVal i (D) = E G∼D [StackVal i (G)] for each P i . We will demonstrate the separation by showing that P 1 is always able to achieve this benchmark through a PNE of the meta-game, for all D, but there exists some distribution D in which no PNE of the meta-game yields P 2 her counterpart benchmark.We will first state the theorems and provide proof sketches later. Our first theorem (Theorem 3.1) asserts that P 1 can achieve the benchmark StackVal 1 (D) by explicitly constructing a PNE pair of algorithms (π 1 , π 2 ) that grants P 1 this utility in the asymptotic regime. In the proof of this theorem, we provide the rate of convergence to this utility (Remark B.1).Theorem 3.1 (Benchmark achievable by P 1 for all D). For every game family G and every distribution D ∈ ∆(G) supported on it, there exists an algorithm pair (π 1 , π 2 ) such that (π 1 , π 2 ) is a PNE of the meta-game, and∀G ∈ G, Ū T 1 (π 1 , π 2 ; G) ≥ StackVal 1 (G) -o T (1). That is, for every realized game G, the expected average utility of P 1 over T rounds tends to StackVal 1 (G) as T → ∞. The expectation is over the trajectories -sequence of player strategies, and resulting utilities induced by the algorithms π 1 , π 2 and G.The next theorem completes the separation argument by constructing a specific game distribution where no PNE of the meta-game allows P 2 to asymptotically achieve the benchmark StackVal 2 (D). Theorem 3.2 (Benchmark unachievable by P 2 for some D). For all thresholds p ⋆ ∈ [0, 1), there exists a game family G and a distribution D ∈ ∆(G), s.t., ∀p 2 ≤ p ⋆ , all PNE (π 1 , π 2 ) of the meta-game where P 2 's signal is of precisionp 2 must suffer E G∼D Ū T 2 (π 1 , π 2 ; G) ≤ StackVal 2 (D) -Ω T (1). This implies that there is a game G ∈ G such that when G is realized, P 2 's expected average utility over T rounds remains strictly bounded below StackVal 2 (G) even as T → ∞.Theorems 3.1 and 3.2 show that there is a separation in achievable benchmark whenever the lessinformed player is at any informational disadvantage, however small, compared to the fully-informed player. P 2 's signal could be arbitrarily close to being fully informative (i.e., p 2 is arbitrarily close to 1), but there is still a barrier between what P 2 can achieve compared to P 1 , when P 1 has full knowledge.) There exists an algorithm for the buyer (no-regret without overbidding), which caps the seller's revenue at the Mayerson value.Wlog, assume P 1 's algorithm π 1 is a mean-based no-regret algorithm such as EXP3. We will show that for any algorithm π 2 of P 2 , the pair (π 1 , π 2 ) cannot be a PNE of the meta-game.Let π ′ 2 be the algorithm given by the above result 1 that lets P 2 extract full welfare against π 1 . Let π ′ NeurIPS Paper ChecklistQuestion: 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 a separate "Limitations" section in 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 a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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.1. 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 D is such that P 2 has a unique best-response y(x ⋆ ; G) to P 1 's optimal Stackelberg strategy x ⋆ (G). The full proof is in Appendix B.1.Let π 1 be the algorithm that plays P 1 's optimal Stackelberg strategy of the realized game G (i.e., x ⋆ (G)) at every round. Since P 1 has access to a signal that fully reveals the realized game G, P 1 can compute x ⋆ (G) and employ this strategy. Let π 2 be a no-swap-regret algorithm in the banditfeedback setting (the algorithm is only based on the utilities received in each round). Such algorithms exist [7, 16, 34] and are deployable by P 2 without any knowledge of the game played or P 1 's strategies. Note that π 2 does not use P 2 's signal s 2 . Therefore our analysis holds for all levels of precision of s 2 .First, let us analyze the expected utility of P 2 due to (π 1 , π 2 ). The generated trajectories when the game G is realized are of the form (x ⋆ (G), y t ) ∞ t=1 . Since π 2 is a no-swap-regret algorithm, the regret of this trajectory up to round T is sub-linear in T (o(T )).Since we assumed that BR 2 (x ⋆ ; G) is unique, any round where P 2 is not employing this unique best-response (y(x ⋆ ; G)) causes P 2 to incur regret. The no-swap-regret property for P 2 essentially means that P 2 's strategies in the trajectory (y t ) ∞ t=1 become close to y(x ⋆ ; G). And as a result, P 1 's utility per round gets close toU 1 (x ⋆ (G), y(x ⋆ ; G); G) which is StackVal 1 (G).More formally, P 1 's cumulative utility over T rounds satisfies y ) is the minimum difference of P 2 's utility between playing the best response action y(x ⋆ ; G) and any other action in A 2 . Sub-linear swap regret therefore implies thatt∈[T ] U 1 (x ⋆ (G), y t ) ≥ StackVal 1 (G) • T -c 1 t∈[T ] ∥y t -y(x ⋆ ; G)∥ 1 , where y(x ⋆ ; G) is the one-hot vector encoding of y(x ⋆ ; G) and c 1 = max y∈A2\{y(x ⋆ ;G)} U 1 (x ⋆ (G), y; G). We bound term t∈[T ] ∥y t -y(x ⋆ ; G)∥ 1 using the no-swap-regret property. P 2 's swap regret is at least t∈[T ] c 2 ∥y t -y(x ⋆ ; G)∥ 1 , where c 2 = U 2 (x ⋆ (G), y(x ⋆ ; G)) -max y∈A2\{y(x ⋆ ;G)} U 2 (x ⋆ (G),E T t=1 ∥y t -y(x ⋆ ; G)∥ 1 ∈ o(T ) and thus E T t=1 U 1 (x ⋆ (G), y t ) ≥ StackVal 1 (G) • T -o(T ), i.e., P 1 's expected average utility in T rounds is at least StackVal 1 (G) -o T (1).We have shown that the pair (π 1 , π 2 ) achieves P 1 's benchmark utility. We now show that it is a PNE of the meta-game. Fixing π 1 , the maximum utility P 2 can get is the utility achieved by playing y(x ⋆ ; G), ∀t. P 2 does not necessarily know G to play y(x ⋆ ; G) for all t ∈ [T ], but we have shown that due to π 2 being a no-swap-regret algorithm, P 2 ends up playing strategies close to y(x ⋆ ; G) asymptotically. The difference between P 2 's cumulative utility between playing π 2 against π 1 , versus playing per-round best response against π 1 is at most O( t∈[T ] E ∥y ty(x ⋆ ; G)∥ 1 ) which is o(T ) by the no-swap-regret property. So P 2 has vanishing incentive to deviate from π 2 in the meta-game.Next fixing π 2 to be a no-swap-regret algorithm, previous work [17, 28] caps P 1 's achievable utility through any algorithm π ′ 1 (Deng et al. [17, Theorem 6] ). These results show that for every π ′ 1 , P 1 's expected average utility induced by(π ′ 1 , π 2 ) in T rounds is at most StackVal 1 (G) + o T (1). Since we have shown that (π 1 , π 2 ) yields at least StackVal 1 (G) -o T (1) for P 1 , there is vanishing incentive for P 1 to deviate.In Appendix B.1, we extend this proof to the scenario with potential ties in P 2 's best response, but under the assumption that P 2 has no weakly dominated action. Using regret rates of standard swap-regret algorithms, we also provide the rate of convergence to the Stackelberg benchmark.Proof sketch of Theorem 3.2. To prove this theorem, we construct a family of two games G 1 and G 2 (shown in Figure 1 ) and let the prior distribution D to be uniform over G 1 and G 2 . Note that the maximum value of game parameters depends inversely on γ ≜ 1-p ⋆ 1+p ⋆ , where p ⋆ is the maximum precision of the signal received by P 2 . In this construction, the utility functions in both games are identical for P 2 but different for P 1 . This implies that P 2 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 2 for all G. In other words, the trajectory converges to (x(y ⋆ ; G 1 ), y ⋆ (G 1 )) when G 1 is realized and (x(y ⋆ ; G 2 ), y ⋆ (G 2 )) when G 2 is realized. It is not hard to check that the Stackelberg equilibria turns out to be supported on different purestrategy pairs: (A, C) in G 1 and (B, D) in G 2 (shaded cells in Figure 1 ). Because the Stackelberg strategies differ for G 1 and G 2 , to converge to the correct equilibrium, P 2 must have gained full information about which game G is being played through repeated interactions with P 1 . However, from P 1 's perspective, the strategy pair (A, C)-the Stackelberg equilibrium led by more favorable than the other equilibrium (B, D) in both G 1 and G 2 . Therefore, instead of disclosing information about which G is realized, it would be more beneficial for P 1 to conceal this information and always behave as if G were G 1 . Therefore, any pair of algorithms that give rise to this hypothetical situation cannot be an equilibrium in the space of algorithms.P 2 in G 1 -is C D A 16/γ, 1 16/γ, -32/γ B 2, 0 0, 2 Game Matrix G 1 C D A 1, 1 0, -32/γ B 0.9, 0 0.1, 2 Game Matrix G 2Our actual proof applies similar ideas to establish a stronger claim: not only is it impossible for P 2 to have the trajectory always converge to their Stackelberg equilibrium, but they cannot recover an average utility of StackVal 2 (D) through any repeated interactions with P 1 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 T over trajectories of length T , the CSP induced by T T , denoted as CSP T T , is a correlated distribution in ∆(A 1 × A 2 ) which is taken as the empirical average of the mixed-strategy profiles in each time step, i.e., CSPT T ≜ E (xt,yt) t∈[T ] ∼T T [(1/T ) t∈[T ] x t ⊗ y t ].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.e., p 1 = 1 and p 2 = 0. For the sake of contradiction, assume that a pair of equilibrium algorithms (π 1 , π 2 ) can let P 2 achieve the benchmark StackVal 2 (D) = 3/2. With the CSPs introduced above, we can rewrite P 2 's average expected utility as1 2 E (x,y)∼CSP1 U 2 (x, y; G 1 )+ 1 2 E (x,y)∼CSP2 U 2 (x, y; G 2 ), where we have used CSP 1 and CSP 2 to denote the CSPs induced by the distribution over trajectories generated by T T (π 1 , π 2 ; G 1 ) and T T (π 1 , π 2 ; G 2 ), respectively. Similar to the hypothetical situation sketched above, we want to argue that there is incentive for P 1 to deviate to an algorithm π ′ 1 that always behaves according to π 1 (G 1 ) even when the actual game is G 2 . In other words, we aim to show that P 1 's expected utility in G 2 strictly increases after replacing the induced CSP from CSP 2 to CSP 1 , i.e., E τ ∼CSP1 U 1 (τ ; G 2 ) > E τ ∼CSP2 U 1 (τ ; G 2 ). Note that for P 1 's utility in G 2 , cells involving action C all have utility close to 1, whereas those involving action D all have utility close to 0. Therefore, it suffices to show that cells involving action D take up a significant probability mass in CSP 2 but very little in CSP 1 . We break these into the following three claims and use the equilibrium condition to establish them in Appendix B.3.• Claim 1. CSP 1 (B, D) is very small, otherwise P 1 would deviate to always playing action A.• Claim 2. CSP 1 (A, D) is very small, otherwise P 2 would deviate to always playing action C.• Claim 3. CSP 2 (B, D) is very large, otherwise P 2 cannot achieve benchmark StackVal 2 (D).Towards partial information asymmetry. In the remainder of this sketch, we discuss the extension of the above approach to the partial asymmetry setting where p 1 = 1 and 0 ≤ p 2 ≤ p ⋆ < 1. The fact that P 2 's signal is partially informative introduces extra challenge to our analysis, since P 2 's belief about the true game depends not only on P 1 's behavior during the interaction, but also on the information carried by the external signal s 2 . As a result, if P 1 deviates to acting according to G 1 when the actual game is G 2 , it does not trigger the expected CSP when the realized game is G 1 , but instead causes a "distorted" posterior since the distribution of s 2 ∼ φ p2 (•|G 2 ) 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) ∈ {1, 2} 2 , let CSP ij to denote the CSP induced by T T (π 1 , π 2 ; s 1 , s 2 , G = s 1 ) when s 1 = G i and s 2 = G j (we have set G = s 1 because s 1 perfectly reveals G). When the realized game is G 2 , P 1 's expected utility before deviation is given byŪ1 (π 1 , π 2 ; G 2 ) = 1 -p 2 2 E τ ∼CSP21 U 2 (τ ; G 2 ) + 1 + p 2 2 E τ ∼CSP22 U 2 (τ ; G 2 ),because the probability of P 2 seeing signals s 2 = G 1 and s 2 = G 2 are 1-p2 2 and 1+p2 2 , respectively. So, as for the expected utility after deviation, the coefficients Ū1 (π ′ 1 , π 2 ; G 2 ) = 1 -p 2 2 E τ ∼CSP11 U 2 (τ ; G 2 ) + 1 + p 2 2 E τ ∼CSP12 U 2 (τ ; G 2 ),However, if the true game were G 1 , then CSP 11 and CSP 12 would be realized with swapped probability 1+p2 2 and 1-p2 2 , not the ones appeared in Ū (π ′ 1 , π 2 ; G 2 )! Hence, even if we can guarantee that action pairs (A, D) and (B, D) occur very infrequently when the true game is G = G 1 , they may only occur under CSP 12 , whose frequency gets amplified by 1+p2 1-p2 times when factoring into the utility after deviation Ū (π ′ 1 , π 2 ; G 2 ). Therefore, establishing the benefit of deviation requires a much smaller probability of (A, D) and (B, D) under the CSPs induced by G = G 1 . This is why we need the game parameters to inversely depend on γ = 1-p ⋆ 1+p ⋆ , where p ⋆ is an upper bound on p 2 .In this section, we provide an informal discussion on the reason behind P 2 's 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 P 2 from "learning" the game, but rather because P 2 cannot apply her learned knowledge to recover her Stackelberg value in any equilibrium.At each round, P 2 can form a posterior belief about the realized game G based on her observed feedback from the historical interactions and the initial signal s 2 received. We say that P 2 successfully learns G if her posterior belief converges to the point distribution on G (formally in Definition A.2). Interestingly, using the same pair of PNE algorithms designed to show that P 1 can achieve their Stackelberg value, we can show that P 2 is indeed able to successfully learn G through strategic interactions. This is because P 2 '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 a meta-game where StackVal 2 (D) cannot be achieved (Observation A.4).The problem preventing P 2 from achieving StackVal 2 (D) is not an insufficient rate or accuracy of learning, but rather the fact that learning and acting on this learned knowledge are intertwined. In fact, if P 2 's learning was independent of the repeated interaction, i.e., when P 2 has access to external signals that become more accurate over time, she can achieve StackVal 2 (D) (Proposition A.5).Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Justification: We provide a proof for each theoretical result in either the main body or the appendix.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced.• All assumptions should be clearly stated or 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 to provide a 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 or supplemental material.• Theorems and Lemmas that the proof relies upon should be properly referenced. 
interactions between two partially-informed players: 
 In this section, we consider the setting where neither player is fully informed. That is, the precision of both player's signals (p 1 , p 2 ) 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 is 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.EQUATIONGame Matrix G 2 is the row player and P2 is the column player.Note that if P 2 chooses the pure strategy C, then for any strategy of P 1 , P 2 's utility lies in the range [1, 2] if G 1 is realized and in the range [3, 7] if G 2 is realized. Since both ranges are non-intersecting, P 2 can deduce G exactly after a single round by choosing the pure strategy B in the first round.However, since the utilities of P 1 for all action profiles are the same in both G 1 , G 2 , P 1 gains no additional information about the realized game. So even if P 1 started off with a more informative signal, after a single round, P 2 becomes more informed and in fact perfectly informed.To show that the average Stackelberg value benchmark does not separate the more-from the lessinformed 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 an instance such that this player cannot achieve the benchmark value at equilibrium. Proposition 4.2. For every player signal precision values p 1 , p 2 ∈ [0, 1), for each i ∈ {1, 2}, there exists D such that for every PNE (π 1 , π 2 ) of the meta-game,Ū T i (π 1 , π 2 ; D) ≤ StackVal i (D)-Ω T (1).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 1 . Since the range of the set of attainable utilities in G 1 , G 2 when P 1 chooses action A, has no intersection for P 1 , regardless of P 2 's strategy, P 1 can deduce the game exactly after a single round while P 2 gains no additional information after a single round.After the first round, we are in the regime of a fully informed P 1 and a partially informed P 2 since p 2 < 1. Theorem 3.2 already shows that in this regime, no equilibrium provides P 2 her average Stackelberg value benchmark. Using a distribution D ′ that is the same as D but with player utilities flipped proves the proposition for P 2 .Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to 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 be possible for other researchers to have some path to reproducing or verifying the results. 
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 P 1 is fully informed (i.e., knows G) while P 2 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 p 1 , p 2 < 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 meta-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 is fully informed. Previous work also implies that no-regret is not sufficient for an algorithm to be part of a 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 meta-game that causes a 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 was 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 an information design setting where the nature designs a 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 a required and natural first step, but an interesting direction would be to understand what happens when the signals are costly and their accuracy is 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 in the case where the players are computationally bounded; note that our current setup provides information-theoretic results, but it could be computationally hard for players to communicate their algorithms to each other, or even verify that two algorithms are at equilibrium.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 be defined soon), we will show that 1. Successful learning by P 2 based on repeated interactions is possible at a PNE of the metagame, but still does not yield P 2 her average Stackelberg value (Observation A.4). 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 a realized game G entails forming beliefs over the realized game such that the beliefs asymptotically concentrate on the true realized game G.Definition A.1 (Successful learning criterion). Given a realized game G from a game family G,a belief sequence ( βt ) ∞ t=1 , where βt ∈ ∆(G) is a belief (distribution) over G for each t ∈ N, successfully learns G if Pr GT ∼ βT [ GT ̸ = G] ∈ o T (1). That is, the beliefs asymptotically fully concentrate on the realized game G.Different models of learning involve different constraints on or power afforded to 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 t is constrained to be formed based on the initial signal and the history at round t generated during the repeated interaction.Definition A.2 (Successful learning based on repeated interactions). Given a family of games G and a player P i (i ∈ {1, 2}), a history-based belief function for P i is a mapping from the player'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 i ;H 1:t-1 i ) → ∆(G).Given a distribution D ∈ ∆(G), we say a history-based belief function h, as defined above, successfully learns based on interactions through the algorithm pair (π 1 , π 2 ) if for every realized game G ∈ G and every realized signal s 1 , s 2 , the induced beliefsβt i ∞ t=1where each belief βti = h(s i , H 1:t-1 i )is induced by histories H r i generated from the distribution T T (π 1 , π 2 ; G, s 1 , s 2 ), successfully learns the realized game G (according to Definition A.1) with probability 1.The second form of learning occurs without dependence on the other player's actions and instead based on externally provided signals.Definition A.3 (Successful independent learning). Given a distribution of games D, we say that P i can independently learn successfully if for every realized game G ∼ D, there is a sequence of signals (q t ) ∞ t=1 with q t ∈ G, that are generated by a sequence of signaling distributions(Q t ) ∞ t=1 with Q t ∈ ∆(G), where the sequence (Q t ) ∞ t=1 successfully learns the realized game G (according to Definition A.1).The signal q t is provided to P i at round t. So P i 's algorithm π i maps the initial signal s i , history at each round t (H 1:t-1 i ), and q t to a strategy taken at round t.Revisiting Theorem 3.2, which states that the average Stackelberg value is not achievable by P 2 for some D, we can question whether some property of D and the equilibria of the meta-game prevents P 2 from successfully learning or if P 2 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 (π 1 , π 2 ) of the meta-game that allows P 2 to successfully learn based on repeated interactions (in the sense of Definition A.2), but no equilibrium allows P 2 to achieve her average Stackelberg value benchmark StackVal 2 (D).D E F A 16/γ, 1 -ϵ 16/γ, -32/γ 16/γ, 1 + ϵ B 2, 0 0, 2 2, 0 C (16 -ϵ)/γ, 1 + ϵ 16/γ, -32/γ (16 -ϵ)/γ, 1 -ϵ Game Matrix G ′ 1 D E F A 1, 1 -ϵ 0, -32/γ 1, 1 + ϵ B 0.9, 0 0.1, 2 0.9, 0 C 1 + ϵ, 1 + ϵ 0, -32/γ 1 + ϵ, 1 -ϵ Game Matrix G ′ 2 Figure 3: game matrices G ′ 1 and G ′ 2 .P1 is the row player and P2 is the column player. The values in each cell are (P1's utility, P2's utility). The parameter γ is defined as1-p ⋆ 1+p ⋆ ∈ (0, 1], where p ⋆ is the precision threshold of p2.Proof. Consider the construction of D used in Theorem 3.2 (Figure 1 ). D is a distribution with equal probabilities over two game matrices G 1 , G 2 . Theorem 3.2 proves that the average Stackelberg benchmark is unattainable by P 2 in any equilibrium.For this proof, we will consider another construction D ′ that is equal probability over game matrices G ′ 1 , G ′ 2 defined in Figure 3 . G ′ 1 is essentially G 1 with an additional row and column, where the additional row is essentially a duplicate of the first row and the additional column is essentially a duplicate of the first column. Rather than being an exact duplicate, the new row/column is a small perturbation (given by parameter ϵ) of the original row/column it duplicates. G ′ 2 is obtained from G 2 similarly.Since the new construction is essentially duplicating rows/columns of the old construction, by the same argument as is Theorem 3.2, the average Stackelberg benchmark is also unattainable by P 2 in any equilibrium of the meta-game of the Bayesian game D ′ . Despite this, we can show there is an equilibrium enabling P 2 to successfully learn through repeated interactions. We construct the perturbations to ensure that the P 1 -led equilibrium response has a different response forP 2 in G ′ 1 compared to G ′ 2 .Our argument is that the meta-game PNE pair results in both players playing the P 1 -led Stackelberg equilibrium of the realized game. Therefore, based on P 2 's responses generated by the trajectories of the meta-game PNE, P 2 can determine the realized game.Consider the algorithm pair where P 1 plays her Stackelberg strategy of the realized game and P 2 plays a no-swap-regret algorithm. The proof of Theorem 3.1 showed that this pair forms an equilibrium and that P 2 's strategy eventually becomes the best-response of the realized game due to P 2 's no-swap-regret property. Note that the two games G ′ 1 , G ′ 2 in the support of D ′ have different P 2 responses in P 1 's Stackelberg equilibrium. So based on the strategies P 2 plays, she will be able to deduce the realized game. Consider the belief function h that at round t computes the average strategy employed thus far: ȳt = 1/(t -1) t-1 r=1 y r and forms a belief concentrated onG ′ 1 if ∥ȳ t -y(x ⋆ ; G ′ 1 )∥ < ∥ȳ t -y(x ⋆ ; G ′ 2 )∥ and forms a belief concentrated on G ′ 2 otherwise, where y(x ⋆ ; G ′ i ) is the one-hot encoding vector of the best response y(x ⋆ ; G) in game G. The induced sequence of 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 P 2 to successfully learn.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.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 P 2 can successfully learn independently for every D, then P 2 can achieve her average Stackelberg value StackVal 2 (D) for every D at a PNE of the meta-game. This extends Theorem 3.1, which stated that this is possible if P 2 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 P 2 can successfully learn independently (Definition A.3), there is an algorithm pair (π 1 , π 2 ) such that (π 1 , π 2 ) is a PNE of the meta-game and ∀G ∈ G, Ū2 (π 1 , π2 ; G) ≥ StackVal 2 (G) -o T (1).Proof sketch. The equilibrium algorithm pair we will show guarantees this utility to P 2 is the one where P 2 employs the Stackelberg response of the game denoted by the external signal q t at round t and P 1 employs a 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. If the external signals were not quite as powerful, the average Stackelberg benchmark can no longer be always achieved. In particular, if P 2 could only learn the realized game to a precision bounded away from 1, Theorem 3.2 shows that the average Stackelberg benchmark is not always achievable when P 1 is fully informed about the game. We will construct an algorithm pair (π 1 , π 2 ) such that when P 1 is able to successfully learn through an independent sequence of signals (q t ) ∞ t=1 , (π 1 , π 2 ) is an equilibrium pair and guarantees P 1 an expected average utility of at least StackVal 1 (G)-o T (1) in T rounds, for every realized game G. The same proof also holds if P 2 is the player able to learn through external signals. Let (x ⋆ (G), y(x * ; G)) denote P 1 's Stackelberg strategy and P 2 's best response in the game G. Let y(x * ; G) be the one-hot encoding vector of y(x * ; G).We choose π 2 to be a no-swap-regret algorithm with swap-regret rate O(T a ) for a < 1. We will first construct π 1 in the setting with a known, finite time horizon T so that P 1 achieves average regret StackVal 1 (G) -o T (1) in T rounds when interacting with P 2 employing a 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 to 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 1 can choose a strategy x ′ so that y(x ⋆ ; G) is P 2 's unique best response and x ′ is close to x ⋆ (G). Since y(x ⋆ ; G) is not weakly dominated, there is no [20] , there must exist a x ∈ ∆(A 1 ) such that U 2 (x, y(x ⋆ ; G)) ≥ U 2 (x, y(x ⋆ ; G)) + c for a constant c > 0. This implies that if P 1 plays the strategy x ′ δ = (1 -δ)x ⋆ + δx, then for all values of δ > 0, P 2 's unique best response to x ′ δ is y(x ⋆ ; G). To indicate dependence of this strategy on the game G, we will also denote it by x ′ δ (G). Choosing a small δ enables P 1 to play a strategy close to the Stackelberg strategy while ensuring that P 2 's unique best response is y(x ⋆ ; G).y ′ ∈ ∆(A 2 \ {y(x ⋆ ; G)}) such that U 2 (x, y ′ ) ≥ U 2 (x, y(x ⋆ ; G)) for all x ∈ A 1 . By Farkas' lemmaIn the each round t ∈ [T ], P 1 employs x ′ δ T (q t ), where q t is the signal at round t. We will later describe how to choose δ T . Let (x t , y t ) ∞ t=1 be the sequence of strategies generated through the interaction of the above algorithm of P 1 and P 2 's no-swap-regret algorithm. Given a δ T , let us compute P 1 's expected cumulative utility. Let Z t be a random variable indicating if the external signal at round t is the realized game i.e., Z t = 1{q t = G}. In rounds with Z t = 1, the immediate regret of P 2 at round t is c∥y ty(x ⋆ ; G)∥. A lower bound on P 2 's regret based on regret accumulated only in rounds withZ t = 1 is T t=1 δ T c • Z t ∥y t -y(x ⋆ ; G)∥, where c = U 2 (x ′ , y(x ⋆ ; G)) - max y∈A2\{y(x ⋆ ;G)} U 2 (x ′ , y). swap-regret ≥ T t=1 δ T c • Z t ∥y t -y(x ⋆ ; G)∥ E[swap-regret] ≥ T t=1 δ T c • E[Z t ] • E[∥y t -y(x ⋆ ; G)∥](Independence between q t and P 2 's action)EQUATIONP 1 's cumulative utility satisfies:E T t=1 U 1 (x t , y t ; G) ≥ T t=1 E[Z t ] U 1 (x ′ δ T , y(x ⋆ ; G); G) -c 1 E[∥y t -y(x ⋆ ; G)∥ 1 ] + c 2 T t=1 E[1 -Z t ] ≥ T t=1 E[Z t ] StackVal 1 (G) -δ T c 3 -c 1 E[∥y t -y(x ⋆ ; G)∥ 1 ] + c 2 T t=1 E[1 -Z t ],wherec 1 = U 1 (x ′ δ T , y(x ⋆ ; G); G) - min y∈A2\{y(x ⋆ ;G)} U 1 (x ′ δ T , y; G), c 2 = min x∈A1,y∈A2 U 1 (x, y), c 3 = StackVal 1 (G) -U 1 (x, y(x ⋆ ; G); G).Finally, we use Equation ( 1) andEQUATIONIn eq. ( 2), the second term c 3 δ T T comes from playing action x instead of x to induce a unique best response; the third term c 1 O(T a )/δ T comes from the swap regret of P 2 , and the last o(T ) term comes from errors in the external signalsZ t . By choosing δ T = T -b for some 0 < b < 1 -a, π 1 yields StackVal 1 (G) • T -o(T ) utility to P 1 .In the special case where the last o(T ) term is zero (e.g., when P 1 has perfect knowledge about the game G as in Theorem 3.1), we can achieve the optimal tradeoff by setting b to be 1-a 2 , which yields a convergence rate of O(T2 ) to StackVal 1 (G). The doubling trick to construct π 1 that does not rely on the time horizon being known: Initialize a maximum horizon T m . Until the round index t hits T m , employ x ′ δ Tm . Once t = T m , update T m ← 2T m and employ x ′ δ Tm until the round index exceeds the new max horizon. Remark B.1 (Rate of convergence to Stackelberg benchmark.). Algorithms that provide swapregret rates of O(T 1/2 ) are known [7, 37] . By setting a = 1 2 and b = 1-a 2 , our proof shows that these algorithms lie in a PNE of the meta-game that results in a O(T 3/4 ) convergence rate to P 1 's Stackelberg benchmark.We prove this theorem for every fixed signal precision p 2 = p ≤ p ⋆ . Before diving into the proof, we will first introduce some notations. For (i, j) ∈ {1, 2} × {1, 2}, we use CSP ij to denote the CSPC D A 16/γ, 1 16/γ, -32/γ B 2, 0 0, 2 Game Matrix G 1 C D A 1, 1 0, -32/γ B 0.9, 0 0.1, 2 Game Matrix G 2Figure 4 : game matrices G1 and G2. P1 is the row player and P2 is the column player. The values in each cell are (P1's utility, P2's utility). Shaded cells represent the action profiles supported in the Stackelberg equilibria led by the column player. The parameter γ is defined as1-p ⋆ 1+p ⋆ ∈ (0, 1], where p ⋆ is the precision threshold of p2.induced by T T (π 1 , π 2 ;s 1 = G i , s 2 = G j , G = G i ).Note that we have taken s 1 and G to both beG i because s 1 ≡ G when p 1 = 1. Recall that T T (π 1 , π 2 ; G i , G j , G i ) is the distribution over trajectories of length T (denoted as τ = (x t , y t ) t∈[T ]) generated by the pair of algorithms (π 1 , π 2 ) when π 1 takes input signal s 1 = G i and π 2 takes input signal s 2 = G j . Formally, we haveCSP ij ≜ CSP T T (π1,π2;Gi,Gj ,Gi) = E τ ∼T T (π1,π2;Gi,Gj ,Gi) 1 T T t=1x t ⊗ y t .In addition, for i ∈ {1, 2}, we use CSP i to denote the CSP generated by the trajectory distribution T T (π 1 , π 2 ; G i ). Since s 1 perfectly correlates with G, and s 2 is drawn from the signal distributionφ p2 (s|G) = 1+p2 2 • 1 {s = G} + 1-p2 2• 1 {s ̸ = G}, we can equivalently write CSP 1 and CSP 2 asCSP 1 = 1 + p 2 CSP 11 + 1 -p 2 CSP 12 ; CSP 2 = 1 -p 2 CSP 21 + 1 + p 2 CSP 22 .As argued in the proof sketch, we will establish the following three claims about CSP 1 and CSP 2 . 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 (π 1 , π 2 ) is a PNE in the meta-game that lets P 2 achieve the benchmark StackVal(D) = 3 2 . We show that if (π 1 , π 2 ) satisfies Claims B.2 through B.4, then P 1 gains utility by deviating to an algorithm π ′ 1 that always plays according to G 1 . Formally, consider π ′ 1 defined as follows. For any history time step t > 0 and any history H r 1 (r > 0),π ′ 1 (G, H 1:t-1 1 ) ≜ π 1 (G 1 , H 1:t-1 1 ), ∀G ∈ {G 1 , G 2 }.After the deviation, P 1 's average utility can be expressed asŪ T 1 (π ′ 1 , π 2 ) = 1 2 Ū1 (π 1 , π 2 ; G 1 ) + 1 -p 4 E τ ∼T T (π ′ 1 ,π2;G2,G1,G2) 1 T T t=1 U 1 (x t , y t ; G 2 ) + 1 + p 4 E τ ∼T T (π ′ 1 ,π2;G2,G2,G2) 1 T T t=1 U 1 (x t , y t ; G 2 ) .Since π ′ 1 is defined to behave according to π 1 on observing G 1 , the above equation can be rewritten asŪ1 (π ′ 1 , π 2 ) = 1 2 Ū1 (π 1 , π 2 ; G 1 ) + 1 -p 4 E (x,y)∼CSP11 [U 1 (x, y; G 2 )] + 1 + p 4 E (x,y)∼CSP12 [U 1 (x, y; G 2 )] .Now we define a new CSP to be the mixture of CSP 11 and CSP 12 but CSP 12 is taking up more probability mass than CSP 11 :CSP ′ 1 ≜ 1 -p 2 CSP 11 + 1 + p 2 CSP 12 .Note that compared with the CSP 1 defined before (repeated below)CSP 1 = 1 + p 2 CSP 11 + 1 -p 2 CSP 12 ,we can conclude that for any action pair (x, y) ∈ {A, B} × {C, D},CSP ′ 1 (x, y) ≤ 1 + p 1 -p CSP 1 (x, y) ≤ 1 + p ⋆ 1 -p ⋆ CSP 1 (x, y) = 1 γ CSP 1 (x, y),where the second step used p ≤ p ⋆ and the last step uses the definition of γ = 1-p ⋆ 1+p ⋆ . Combined with the upper bounds on CSP 1 (B, D) and CSP 1 (A, D) from Claim B.2 and Claim B.3, we haveEQUATIONFinally, we lower bound the increase in P 1 's utility after deviating from π 1 to π ′ 1 as follows. SinceŪ T 1 (π ′ 1 , π 2 ) -Ū T 1 (π ′ 1 , π 2 ) = 1 2 E (x,y)∼CSP ′ 1 [U 1 (x, y; G 2 )] - E (x,y)∼CSP1 [U 1 (x, y; G 2 )]it suffices to lower bound the difference in utility when G 2 is realized.On the one hand, note that U 1 (x, y; G 2 ) ≥ 0.9 as long as (x, y) ̸ = (A, D) or (B, D), we haveEQUATION(from eq. ( 3))On the other hand, since U 1 (x, y; G 2 ) ≤ 0.1 when (x, y) = (B, D) and U 1 (x, y; G 2 ) ≤ 1 otherwise, we haveE (x,y)∼CSP1 [U 1 (x, y; G 2 )] ≤ CSP 1 (B, D) • 0.1 + (1 -CSP 1 (B, D)) • 1 ≤ 1 2 • 1.1 + o T (1) (CSP 1 (B, D) ≥ 1 2 + o T (1) from Claim B.4) < 0.6 + o T (1).As a result, after taking their difference, we have that in the asymptotic regime lim supT →∞ Ū T 1 (π ′ 1 , π 2 ; D) -Ū T 1 (π ′ 1 , π 2 ; D) > 0,which contradicts with the assumption that (π 1 , π 2 ) forms a PNE (cf. Definition 2.1) in the metagame! Therefore, it cannot be possible for any PNE (π 1 , π 2 ) of the meta game to achieve the benchmark StackVal 2 (D) for P 2 . The proof is thus complete.Proof of Claim B.2. We prove this claim by contradiction. Assume that the above claim does not hold, i.e., lim supT →∞ CSP 1 ((B, D)) > γ 8 ,we will show that P 1 gains utility by deviating to another algorithm π ′ 1 that always plays action A regardless of the signals and the feedbacks observed. We have lim infT →∞ Ū T 1 (π 1 , π 2 ; D) = lim inf T →∞ 1 2 Ū T 1 (π 1 , π 2 ; G 1 ) + 1 2 Ū T 1 (π 1 , π 2 ; G 2 ) = lim inf T →∞ 1 2 E (x,y)∼CSP1 U 1 (x, y; G 1 ) + 1 2 E (x,y)∼CSP2 U 1 (x, y; G 2 ) ≤ lim inf T →∞ 1 2 CSP 1 (B, D) • 0 + (1 -CSP 1 (B, D)) • 16 γ + 1 2 • 1 (U 1 (x, y; G 1 ) ≤ 16 γ for all (x, y) ̸ = (B, D); U 2 (x, y; G 2 ) ≤ 1 for all (x, y)) < 1 2 1 - γ 8 16 γ + 1 2 (assumption that lim sup T →∞ CSP 1 ((B, D)) > γ 8 ) = 8 γ - 1 2 .On the other hand, since P 1 always plays action A under π ′ 1 , which has utility 16 γ in G 1 regardless of the strategy of P 2 , we have lim supT →∞ Ū T 1 (π ′ 1 , π 2 ; D) ≥ lim sup T →∞ 1 2 Ū T 1 (π ′ 1 , π 2 ; D) ≥ 1 2 • 16 γ = 8 γ .Combining the above two inequalities give us lim sup We upper bound P 2 's utility under equilibrium as lim infT →∞ Ū T 1 (π ′ 1 , π 2 ; D) -Ū T 1 (π 1 , π 2 ; D) > 0,EQUATION(P 2 's utility is -32/γ for (A, D) and ≤ 2 for all other cells)EQUATION(assumption that lim sup T →∞ CSP 1 (A, D) > γ/8.) < 0. On the other hand, if P 2 deviates to an algorithm π ′ 2 that always plays action C regardless of the signal s 2 and the observed feedbacks, then the average utility Ū2 (π 1 , π ′ 2 ; D) is always nonnegative. As a result, we have lim supT →∞ Ū T 2 (π 1 , π ′ 2 ; D) -Ū T 2 (π 1 , π 2 , ; D) > 0,which again violates the condition of (π Ū T 2 (π 1 , π 2 ; D) = 1 2 E (x,y)∼CSP1 U 2 (x, y; G 1 ) + 1 2 E (x,y)∼CSP2 U 2 (x, y; G 2 ) ≤ 1 2 (1 -CSP 1 (B, D)) • 1 + CSP 1 (B, D) • 2 + 1 2 (1 -CSP 2 (B, D)) • 1 + CSP 2 (B, D) • 2 = 1 + 1 2 CSP 1 (B, D) + 1 2 CSP 2 (B, D) ≤ 1 + γ 16 + 1 2 CSP 2 (B, D) + o(1),where the last step uses Claim B.3. On the other hand, from the assumption, Ū2 (π 1 , π 2 ; D) is lower bounded by 3/2 as T → ∞. Therefore, we obtainlim T →∞ CSP 2 (B, D) ≥ 1 - γ 8 ≥ 1 2 , which proves CSP 2 (B, D) ≥ 1 2 + o(1).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 π i of P i is supported in a meta-game PNE if there exists an algorithm π -i such that the pair (π i , π -i ) forms a PNE of the meta-game. The claims in this section provide answers to whether common classes of algorithms such as (swap)regret-minimizing, myopically best-responding, playing Stackelberg response are always/sometimes/never supported in a meta-game PNE.Claim C.1. All no-swap-regret algorithms are supported in a meta-game PNE for all games G. Put another way, being no-swap-regret is a sufficient condition for an algorithm to be supported in some meta-game PNE.Proof. This is a direct corollary of [17, Theorem 6] which can also be justified by our proof of Theorem 3.1. Consider the pair of algorithms (π 1 , π 2 ) in which π 1 plays strategies close to the Stackelberg optimal strategy (via a doubling trick, see Appendix B.2 for the full construction), and π 2 is a no-swap-regret algorithm. We have proved in Appendix B.2 that (π 1 , π 2 ) is a PNE in the metagame because no-swap-regret algorithms are able to cap their opponent's utility at the Stackelberg value.The second claim is stated as Theorem 2 by Brown et 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 in the meta-game for most games.Claim C.2 (Theorem 2, [10] ). Unless the stage game G has a PNE, any pair of two no-swap regret algorithms cannot form a PNE of the meta-game.Claim C.3. No-regret is not a sufficient condition for an algorithm to be supported in a meta-game PNE. For common no-regret algorithms such as EXP3, there is a 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 a single item to a 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 an algorithm for the seller which extracts (almost) full welfare.Question: Does the paper provide open access to the data and code, with sufficient instructions 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.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) 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 a subset of experiments are 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 as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?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 in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
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 not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at 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 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not 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 are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to 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 of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes]• Released models that have a 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 not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are 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 is used and, if possible, include a 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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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 not release new assets.• Researchers should communicate the details of 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 was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.38th Conference on Neural Information Processing Systems (NeurIPS 2024).Beyond myopic best-responding, 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 learning dynamics may be affected as the result of the second player's actions.Our results also hold in an alternative setting where both players can only play pure strategies at each round, i.e., x t ∼ x t and y t ∼ y t . For the feedback H r i , the realized utilities and the observations about opponent's strategy should both be defined in terms of (x t , y t ) instead of (x t , y t ). As a result, τ (π1, π2; G, s1, s2) becomes a distribution over pure-strategy trajectories (x t , y t ) t∈[T ] instead of mixed strategies (x t , y t ) t∈[T ] .be the algorithm that achieves the property in the above resultOn the one hand, if Ū T 1 (π 1 , π 2 ) ≤ Welfare(D) -Ω(T ), then P 1 will increase utility by deviating to algorithm π ′ 1 , thus (π 1 , π 2 ) cannot be a PNE in the meta-game. On the other hand, if π 1 is already extracting full welfare against π 2 (meaning that P 1 is getting asymptotically zero utility), then P 1 has the incentive to deviate to algorithm π ′ 2 , under which she can cap P 2 's utility at the Myerson value and therefore guarantee herself nonzero utility. For this reason, (π 1 , π 2 ) cannot be a PNE in the meta-game.Combining the above two cases, we conclude that π 1 cannot be supported in any PNE of the meta-game. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

The findings of the paper, while theoretically sound, may not offer surprising or counterintuitive insights that significantly advance the field. 

The 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.
questions: questions: Could the authors highlight their contributions and discuss the significance of the results?
limitations: limitations: I did not find any limitations of the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The paper can be presented more clearly and rigorously in at least the following ways:
    1. Beginning with the discussion of Stackelberg games in the introduction is confusing as the paper considers repeated simultaneously games. 
    2. The reason why take Stackelberg value as a benchmark is lacking. 
    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.
    4. The paper does not mention whether any meta-game holds a pure NE. 
2. The paper lacks a clear explanation of its technical novelty compared to previous work on strategizing no-regret learners?
questions: questions: 1. See weaknesses 2. 
2. Do the agents's set of strategies need to be the same to obtain all the results? 
3. Does the meta-game always admit a pure NE?
limitations: 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:

    "
- Thanh H. Nguyen and Haifeng Xu. Imitative attacker deception in Stackelberg security games. IJCAI'19

- Yurong Chen, Xiaotie Deng, and Yuhao Li. Optimal private payoff manipulation against commitment in
extensive-form games. WINE'22
    "

2. typos:
    1. line 338: "that that" -> "that"
paper_summary: paper_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.
strength_weakness: strength_weakness: I do not have major issues with this paper, but some results need further clarification.
1. 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.
2. 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.
3. I found a typo. There are two words "about" in Line 162.
questions: questions: See the weakness part.
limitations: limitations: See the weakness part.
paper_summary: paper_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.
strength_weakness: strength_weakness: I have no major concerns about this work as a theoretical paper in NeurIPS. 

If 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.
questions: 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.
2. If applicable, can you explain the connection of this work with the real world? Feel free to skip this question if you prefer.
limitations: limitations: I think the authors adequately mentioned the limitations.

Comments: comment: Thank you for your response. I will maintain my score.
Thanks for addressing all my questions and comments. I would like to raise my score.
Thank you for reading our response and for the further questions. We are glad that you find our takeaways interesting.


> It is interesting to see that PNE always exists in the settings considered in section 3. I have some questions about the definition of PNE (Definition 2.1). Will the limits always exist? Or should the lim actually be limsup?

Note that Thm 3.1 shows the existence of meta-game PNE with the current definition involving lim instead of limsup. As you point out, it is true that the limit of average utility might not exist for every algorithm but limsup would exist. So considering this alternate notion of PNE with limsup instead of limits could be more natural. Our results continue to hold with this limsup based defintion with appropriate replacements of limits in the proofs with limsup or liminf. We can address this and use this alternate definition in the revised version.


> If I replace the Stackelberg value with some other benchmark value, I can possibly obtain similar separations, right?

It may be possible to show separation through some other benchmark. However, as highlighted in the previous response, we choose the Stackelberg value as the benchmark for showing separation because of its clear interpretability, close connection to previous works, and its uniqueness for all games.


> In Theorem 3.1, the benchmark value used is $\text{StackVal}_i(G)$, while in Theorem 3.2 and Proposition 4.2, the value is $\text{StackVal}_i(D)$. Could you explain why these two values are different? Can this still be regarded as a separation? Can Theorem 3.2 and Proposition 4.2 hold for $\text{StackVal}_i(G)$? 

Thank you for the question. This is a subtle yet important difference. Note that achieving $\text{StackVal}_i(G)$ for all G in the support of D is a **stronger condition**, because it requires the player to achieve the Stackelberg value for every realized game. On the other hand, achieving the average Stackelberg value $\text{StackVal}_i(D)$ is a **weaker condition**, as it only requires achieving the benchmark on average across the distribution, not for every realized game. Importantly, if a player can satisfy the stronger condition ($\text{StackVal}_i(G)$ for all G), they automatically satisfy the weaker condition ($\text{StackVal}_i(D)$), but the reverse is not true.

Therefore, to establish a clearer separation, we have shown that P1 satisfies the stronger condition by achieving $\text{StackVal}_i(G)$ for all G, whereas P2 cannot even satisfy the weaker condition of achieving the average $\text{StackVal}_i(D)$. This is also explained in the remarks in Lines 223-225 and 231-232: P1 can always achieve $\text{StackVal}_i(G)$ for every realized game G, whereas P2 fails to achieve $\text{StackVal}_i(G)$ for some game G.


> other comments

Thank you for the suggestions. We will revise the paper accordingly.
I appreciate the authors' response and I will maintain my score.
Thanks for the responses. It seems that I indeed misunderstood the use of no-regret algorithms defined at the end of section 2.  And the takeaways are quite interesting. Here are my further responses and questions:

1. It is interesting to see that PNE always exists in the settings considered in section 3. I have some questions about the definition of PNE (Definition 2.1). Will the limits always exist? Or should the lim actually be limsup?
2. If I replace the Stackelberg value with some other benchmark value, I can possibly obtain similar separations, right?
3. In Theorem 3.1, the benchmark value used is $StackVal_i(G)$, while in Theorem 3.2 and Proposition 4.2, the value is $StackVal_i(\mathcal{D})$. Could you explain why these two values are different? Can this still be regarded as a separation? Can Theorem 3.2 and Proposition 4.2 hold for $StackVal_i(G)$? 

Other minor comments:
1. Could you write the conditions of $p_1=1$ and $p_2$s into the statements of Theorem 3.1 and Theorem 3.2, to make the conditions where the theorems hold clearer? 
2. I think I found another typo: There are two "is that" in line 359. Should the second one be redundant?
Thank you for the response. I have read it and decided to stand by my original positive recommendation.