Arts, Faculty of
Vancouver School of Economics
DSpace
UBCV
Possnig, Clemens
Doctor of Philosophy - PhD
University of British Columbia
This dissertation studies algorithmic agents that interact repeatedly in strategic settings. Chapter 2 provides asymptotic results for a family of reinforcement learning algorithms known as ‘actor-critic learners’. Each such algorithmic agent simultaneously estimates what is called a ‘critic’, such as a value function, and updates its policy, which is referred to as the ‘actor’. The critic is used to indicate directions of improvement for the actor. I establish sufficient conditions for the consistency of each agent’s parametric critic estimator, which enables them to adapt and find optimal responses despite the non-stationarity inherent to multi-agent settings. The conditions depend on the environment, number of observations used in the critic estimation, and policy stepsize. Chapter 3 presents an analytical characterization of the long run policies learned by algorithmic agents in the multi-agent setting. The algorithms studied here form a superset of the family considered in chapter 2. These algorithms update policies, which are maps from observed states to actions. I show that the long run policies correspond to equilibria that are stable points of a tractable differential equation. In chapter 4, I consider algorithmic agents playing a repeated Cournot game of quantity competition. In this situation, learning the stage game Nash equilibrium serves as noncollusive benchmark. I give necessary and sufficient conditions for this Nash equilibrium not to be learned. These conditions are requirements on the state variables of the algorithms, and on the stage game. When algorithms determine actions based only on the past period’s price, the Nash equilibrium can be learned. However, agents may condition their actions on richer types of state variables beyond the past period’s price. In that case, I give sufficient conditions such that the policies converge to a collusive equilibrium with positive probability, while never converging to the Nash equilibrium.
Algorithmic Learning in GamesbyClemens PossnigB.A., Karl Franzens University, 2014M.Sc., Institute for Advanced Studies, Vienna, 2016A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Economics)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)September 2023© Clemens Possnig, 2023The following individuals certify that they have read, and recommend to the Faculty of Grad-uate and Postdoctoral Studies for acceptance, the dissertation titled:Algorithmic Learning in Gamessubmitted by Clemens Possnig in partial fulfillment of the requirements forthe degree of Doctor of Philosophyin EconomicsExamining Committee:Hao Li, Professor, Economics, UBCCo-SupervisorVitor Farinha Luz, Associate Professor, Economics, UBCCo-SupervisorChristopher Thomas Ryan, Associate Professor, Operations and Logistics Division, UBCUniversity ExaminerKevin Song, Professor, Economics, UBCUniversity ExaminerAdditional Supervisory Committee Members:Michael Peters, Professor, Economics, UBCSupervisory Committee MemberiiAbstractThis dissertation studies algorithmic agents that interact repeatedly in strategic settings.Chapter 2 provides asymptotic results for a family of reinforcement learning algorithmsknown as ‘actor-critic learners’. Each such algorithmic agent simultaneously estimates what iscalled a ‘critic’, such as a value function, and updates its policy, which is referred to as the‘actor’. The critic is used to indicate directions of improvement for the actor. I establish suf-ficient conditions for the consistency of each agent’s parametric critic estimator, which enablesthem to adapt and find optimal responses despite the non-stationarity inherent to multi-agentsettings. The conditions depend on the environment, number of observations used in the criticestimation, and policy stepsize.Chapter 3 presents an analytical characterization of the long run policies learned by al-gorithmic agents in the multi-agent setting. The algorithms studied here form a superset ofthe family considered in chapter 2. These algorithms update policies, which are maps fromobserved states to actions. I show that the long run policies correspond to equilibria that arestable points of a tractable differential equation.In chapter 4, I consider algorithmic agents playing a repeated Cournot game of quantitycompetition. In this situation, learning the stage game Nash equilibrium serves as non-collusivebenchmark. I give necessary and sufficient conditions for this Nash equilibrium not to belearned. These conditions are requirements on the state variables of the algorithms, and onthe stage game. When algorithms determine actions based only on the past period’s price,the Nash equilibrium can be learned. However, agents may condition their actions on richertypes of state variables beyond the past period’s price. In that case, I give sufficient conditionssuch that the policies converge to a collusive equilibrium with positive probability, while neverconverging to the Nash equilibrium.iiiLay SummaryWith computation power becoming more and more accessible, many firms have started to usealgorithms in order to optimize sales in real time. For example, online marketplaces providean ideal playground for firms to implement what is known as ‘pricing-bots’, which set pricesaccording to an algorithmic rule. What behaviors can one expect to emerge when multiplefirms compete, not through human managers, but via algorithms? Chapter 2 provides sufficientconditions such that algorithms can learn to play optimal strategies when interacting with oneanother. Chapter 3 shows how one can pin down probabilistically what behaviors can be learnedby algorithms. This method is then used in chapter 4 to provide conditions on algorithms, andthe markets in which they compete, such that collusive behaviors can be learned by them.ivPrefaceThis dissertation is original, unpublished work. Chapter 2 is based on a working paper titled“Consistency of Multi-Agent Batch Reinforcement Learning”. Chapters 3 and 4 are based ona working paper titled “Reinforcement Learning and Collusion”. I am the sole author of thisdissertation.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Learning to Best Reply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Multi-Agent Learning in the Long Run . . . . . . . . . . . . . . . . . . . . . . . 173.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.3 Preliminaries and Running Example . . . . . . . . . . . . . . . . . . . . . . . . . 233.4 Long Run Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 Learning to Collude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33viTable of Contents4.2 Repeated Cournot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.3 Two Special State Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.4 Stable Collusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.5 Numerical Example and Simulations . . . . . . . . . . . . . . . . . . . . . . . . . 484.6 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62AppendicesA Appendix to Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67A.1 Proof of Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67A.2 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69B Appendix to Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75B.1 The Algorithm Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75B.2 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81C Appendix to Chapter 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91C.1 Best Response Dynamics: Stability . . . . . . . . . . . . . . . . . . . . . . . . . 91C.2 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96C.3 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106viiList of Figures4.1 Transition Diagram: SIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2 Transition Diagram: DS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.3 Location of cutoffs xi for piecewise linear h(Q). . . . . . . . . . . . . . . . . . . . . . 494.4 Best Response Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.5 1R-policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.6 S∗-policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.7 S∗-policies, initialized locally . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.8 1R-policies, initialized globally . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.9 S∗-policies, initialized globally . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57viiiAcknowledgmentsI am indebted to my supervisors Hao Li and Vitor Farinha Luz. They have spent more hoursthan I can thank them for, over the years, teaching me how to tackle difficult problems, learningabout new literatures with me, and generally making my early engagement with research apositive experience. I am grateful to Michael Peters, who opened my eyes to the researchdirection which grew into this dissertation, and for his brilliant guidance over the years. I amalso grateful to Kevin Song, for his thoughtful advice and many inspiring conversations. Finally,I wish to thank Wei Li, Sergei Severinov, Vadim Marmer and Jesse Perla; I am thankful fortheir continuous support and advice, and for always having their doors open to me.ixDedicationTo my family and Josephine, with heartfelt appreciation for their constant support and encour-agement.xChapter 1IntroductionMore and more companies are using algorithms to try to optimize sales and increase profits.These algorithms take market data to determine current price or quantity levels, updatingin real-time. Software firms such as solutions.ai and Quicklizard state that a well-performingalgorithm needs to “deliver real-time insights based on market signals, competitive intelligenceand changes in customer preferences (...)” and “trigger repricing of items based on a criteriasuch as (...) competitor price changes (...) ”. How will algorithmic competition affect marketoutcomes?Algorithms can help firms adapt to rapidly changing market environments, and potentiallybetter serve their markets. However, recent empirical and simulation-based studies show thatalgorithms may learn to collude. Studying the German gasoline retail market, Assad et al.[2020] observe that after a critical mass of firms deployed pricing algorithms, profit marginsrose by 28%. Their observations suggest that pricing algorithms learned to punish price cutsby rapidly matching their own price to those of competitors. Klein [2021], Calvano et al. [2021]show that algorithms may learn to play repeated game strategies akin to typical carrot-and-stick type strategies studied in the economic theory literature. This is a concern for consumerwelfare.Moreover, legal systems are not currently adapted to deal with the kind of tacit collusionthat might result from algorithmic competition, where there is no direct communication and noconcept of “intent”. An antitrust regulator would need to understand how competing algorithmsmight lead to inefficient outcomes, depending on the market conditions, the nature of thecompetitive environment, and the details of the algorithms themselves. Both the U.S. FederalTrade Commission (FTC) and European Commission have made official their awareness of theseconcerns.1 Currently, the EU and U.S. are in the process of implementing foundational policiesregarding the use of artificial intelligence (AI), touching on a wide range of AI applications withinternational implications. However, specific regulation regarding the use of AI in price setting1The Antitrust Division of the U.S. Department of Justice (“DOJ”) and the U.S. Federal Trade Commission(“FTC”) note “DAF/COMP/WD(2017)41” submitted as part of the OECD Competition committee on 21-23June 2017. The European Commissioner for Competition M. Vestager, “Algorithms and Competition,” remarksat the Bundeskarellamt 18th Conference on Competition, Berlin, March 16, 2017.1Chapter 1. Introductionand similar areas is not currently mentioned as impending, but is likely to be on the horizon.2This dissertation seeks to shed light on the issue of algorithmic competition from a theoret-ical perspective. Chapter 2 is a technical contribution to the study of asymptotic behaviors ofa family of reinforcement learning algorithms in the multi-agent setting. Commonly, an impor-tant task for an algorithmic agent interacting with others is to find optimal policies that bestrespond to their competitors’ current policy. The challenge such agents face is that they don’tobserve that policy, only being able to see feedback from their own actions, such as realizationsof their payoffs from the past, and transitions of a state variable. Those observations are gen-erated based on the past policies they and their opponents have played. The agents thus needto extract information about their opponents’ current policy based on those past observations.Chapter 2 provides sufficient conditions to guarantee that each agent individually learns toplay optimally according to their own criteria. I study a family of reinforcement learning agentsfor which currently, to my knowledge, no such asymptotic analysis exists. This class is knownas actor-critic batch algorithm (c.f. Busoniu et al. [2017], chapter 3). The term ‘batch’ refers tothe fact that the historical data used for estimating the critic is only a most recent window (thebatch) of past observations, not the full available set of observations. The advantage of such‘forgetfulness’ is that a full set of observations can be contaminated by data realized from pastopponent policies that are very different from the ones used currently, and therefore providea poor source to form a value estimate of the opponents’ current policy. Each agent uses aparametric estimator for their critic function, which commonly is a value function indicatingthe performance of their policy choice. One can formulate the problem of finding an optimalpolicy then as a problem of guaranteeing consistency of the parametric estimator, call it θit foreach agent i at period t, with an unknown true parameter θ∗it . Other than regularity conditions,the main requirement that drives the consistency results in this chapter is as follows:Firstly, policies need to be updated at a slow enough pace. Since policies update only slowly,observations in the batch used for the critic estimation will have been generated by policies thatare similar enough to the current policy. For asymptotic results, the size of the batch needs togrow. The sufficient condition is that the growth rate of the window-size needs to be sufficientlyslow relative to the policy updating speed, so that the batch-based estimator will be consistentand therefore asymptotically correct best responses are computed.Another role of chapter 2 is that its main result is used to show that the family of algorithmsstudied in chapter 3 is nonempty.2Engler, Alex. “The EU and U.S. diverge on AI regulation: A transatlantic comparison and steps to align-ment.” Brookings, April 25 2023, https://www.brookings.edu/research/the-eu-and-us-diverge-on-ai-regulation-a-transatlantic-comparison-and-steps-to-alignment/. Accessed April 30 2023.2Chapter 1. IntroductionChapters 3 and 4 provide a theoretical approach to study the joint behaviors learned byalgorithms in interaction with the markets they are deployed in. This takes a step further fromchapter 2 to ask, once algorithms individually play optimally, what final policy profiles willthey learn in their interaction? More concretely, I address the following questions:1. Given a specific family of algorithms, and details of the market in which they compete,what behaviors are likely to be learned?2. In the example of oligopolistic quantity (“Cournot”) competition, when will algorithmslearn to employ collusive strategies?The algorithms I study learn a policy function to maximize their profits. A policy functionis a decision rule that allows to condition choices on observed information. For example, thealgorithms may observe demand information, such as a previous period’s prices. For everypossible piece of information, the policy maps to an action, such as a quantity to sell in theCournot context.In chapter 3 I provide a characterization of long run policy profiles learned by the algorithms.I show that learnable policy profiles can be approximated by solutions to a deterministic ordi-nary differential equation (ODE). Stability conditions based on this ODE determine whethera profile will be learned with positive probability. Commonly, this ODE is tractable and haseconomic meaning, which allows to study possible long run policies through the lens of stan-dard economic intuitions. This characterization provides a general framework for the study ofcompeting algorithms in many settings other than Cournot.Chapter 4 takes the characterization of chapter 3 and applies it in a repeated oligopolygame. This application both illustrates the benefits of my characterization and allows me tostudy the question of algorithmic collusion more closely. I show that details of the informationthat algorithms observe are essential in determining which behaviors might be learned. Thisinformation can be represented as a state variable that the algorithms keep track of. Onemight expect that a state variable taking many values could facilitate collusion by allowing forcomplex patterns of behavior. However, when it comes to learning collusive behaviors, I showthat properties of the distribution over states are more important than the cardinality of theunderlying state space. I construct a family of binary state variables so that algorithms usingthem will never learn to play the most competitive outcome, but instead learn to collude withpositive probability.This dissertation’s structure is designed to maintain a logical progression across its chapters.In a nutshell, chapter 2 takes a family of algorithms and provides conditions so that these3Chapter 1. Introductionalgorithms, when interacting with each other, will individually learn to satisfy their optimalitycriteria. These algorithms fall into the class of algorithms, the joint behavior of which isstudied in chapter 3. Building upon the preceding chapters, chapter 4 employs this frameworkto examine its application in a Cournot game.For readers more interested in the economic issue of collusion among algorithms, chapter4 can be read independently of the previous chapters. Chapters 2 and 3 cater more towardsreaders seeking comprehensive statistical treatments of algorithmic updating processes.4Chapter 2Learning to Best Reply2.1 IntroductionThis chapter develops asymptotic results for the multi-agent reinforcement learning (MARL)setting, which supports the analysis of behaviors that can be learned by algorithms that interactwith one another.I consider here the setting of actor-critic batch reinforcement learning (RL), which involvesthe mixture of offline (training performance measures on a batch of observations) and online(updating policies during play) approaches (c.f. Busoniu et al. [2017], chapter 3). An actor-critic algorithm iterates over two objects. Firstly, the ‘critic’, a performance measure whichis commonly a value function, is updated every period using observations such as payoff data.Then, the ‘actor’, a policy function, is updated towards directions of improvement of the critic,which inspired the name: one can see the critic as criticizing the actor’s performance.A main challenge in the theoretical analysis of the MARL setting is the inherent non-stationarity of the environment faced by each agent. This comes from the fact that eachagent’s observations are drawn from distributions dependent on the other agents’ policies, whichthemselves are moving over time. At the same time, an agent needs to find an optimal decisionat any given period, where, for optimality, only the current policies of their opponents matter.This introduces the problem commonly referred to as ‘tracking a moving target’: To find a bestresponse, agents need to estimate a value function based on their opponent’s current policy,but can only use data generated from their opponent’s past strategies.The batch-setting studied here allows a useful solution to this issue. Akin to the idea oftwo-timescale approaches, which are well known in the literature (c.f. Borkar [2009], chapter6), it will be true that the batch each agent uses to train their performance measure grows at aspeed that is slower than the convergence rate of each agent’s policy-stepsize. In other words,policies will change at a slower pace than observations are added to the batch. Once that is true,I apply techniques developed and used in econometric theory (see e.g. Newey and McFadden[1994]) to show that tracking the moving target becomes feasible. The Batch-RL setting is incontrast to more commonly known online-only RL schemes, which at every period t incorporate52.1. Introductiononly the new information that has been accrued to adapt their performance measure estimator(see, for example, stochastic gradient descent methods for parametric Q-estimation in Suttonand Barto [2018]). The method of batch-learning is computationally more costly at each period,since a separate optimization routine is run at every period. However, we will see that this canput us at an advantage when it comes to estimation and consistency given non-stationarity.The setting I study is one of discrete state spaces and interval action spaces, motivated bythe oligopoly-competition setting as studied in chapter 4. The interval action setting implies therequirement of using function approximation in the critic estimation step. Results carry overto the finite actions and states case, modulo adjusted notation. No assumptions are imposedon the strategic nature of the interaction each agent faces, i.e. there are no requirements onthe game played to be zero-sum, cooperative or otherwise as is commonly done in the MARLsetting. This chapter focuses on results on a more fundamental level: we are only concernedwith providing conditions for the function approximator of each agent to be well-behaved sothat each agent can individually guarantee to play optimally according to their own criteria.Once this can be verified, other techniques such as stochastic approximation can be appliedto paint a full picture of the asymptotic behavior of the policy-profile process implied by theMARL updating scheme. In chapter 3, I give such an analysis for Markov games of discretestates and interval actions under the assumption that function approximators are well-behavedin the sense developed in this chapter.Related LiteratureTo the best of my knowledge, this is the first study providing asymptotic consistency analysisfor the actor-critic batch RL agents as considered here. Two-timescale approaches as definedin Borkar [2009], chapter 6 have a connection to this paper along the intuitions used to tacklenon-stationarity. Perolat et al. [2018] construct a stochastic approximation result for the two-timescale actor-critic scheme in the discrete state-action setting, while Perkins and Leslie [2013]consider asynchronous two-timescale schemes allowing for multivalued updates. For a morethorough discussion on recent advancements in the MARL literature, consider Zhang et al.[2021].The technique of using the advantages of ‘forgetfulness’ (i.e. a small batch of recent obser-vations to be used in estimation) in the face of non-stationarity is not novel in this chapter. Theliterature on multi-armed bandit learning under non-stationarity using this idea has seen mul-tiple recent advancements, e.g. Cheung et al. [2020], which consider finite single agent settingsand focus on regret bounds. Zhou et al. [2020] provide a regret bound analysis of an RL withlinear function approximation in non-stationary environments. Khetarpal et al. [2022] give a62.2. Consistencythorough survey on the literature of reinforcement learning approaches to non-stationarity.This chapter is organized as follows: Section 2.2 gives the main result, theorem 1, in fullgenerality. Section 2.3 shows how the result applies to common learning rules such as actor-criticQ learning and gradient learning. All proofs are found in appendix A .2.2 ConsistencyFirst, I give a general consistency result on the estimation-step for batch-RL algorithms. Thereare n algorithmic agents, a finite state space S, and a compact interval action space Ai ⊂ R.Action profiles are written as a ∈ A = ×iAi. Agents have a payoff function ui : A × S 7→ R.Define the state transition probability to bePss′ [a] = P[st+1 = s′ | st = s, a]for all a ∈ A and s, s′ ∈ S, where throughout I will maintain an assumption of irreducibilitystated below.Each agent i follows a batch-RL algorithm to update their policies ρit : S 7→ Ai over time.Let the resulting policy profile space be called Γ, which is compact by compactness of Ai.Assumption 1. For all ρ ∈ Γ, the Markov chain induced by Pss′ [ρ(s)] is irreducible andaperiodic.3This assumption is maintained throughout the chapter. It is a commonly made assumptionin the literature on Markov Decision Problems (MDPs). This is also the setting each agentindividually is faced with here, with the added challenge that other agents’ actions affect theMDP of each agent. The assumption ensures the existence of a unique stationary distributionover states conditional on a fixed profile ρ ∈ Γ as introduced later on, as well as the possibilityto learn about every state, which will become clear in section 2.3.The updates to ρit are done using a parametric estimator of an underlying performancemeasure; this can be e.g. aQ-value function as discussed in Section 2.3. For now, the algorithmicupdating rule and critic will be given in general terms, agnostic to the exact definition of theperformance measure. All we need is that the parametric estimator can be expressed as theminimizer of a loss function, which will be introduced later on.Call the parametric function estimator F i(ρi, θi), where parameters θ are the object ofestimation. I assume that F i is continuous in both arguments for all i, and that parametersθ ∈ Θ for a compact set Θ ⊂ Rm.3For definitions, see e.g. appendix A in Puterman [2014]72.2. ConsistencyThe consistency result this chapter establishes is of the following form: each agent will usedata generated from interactions with each other over time to estimate their parameter vectorθi, while ρit are being updated concurrently. There is an unknown (‘true’) population parameterθi∗t that moves with time also, generating a moving-target problem. We will then prove that,under suitable assumptions, each agent’s estimated θit behaves in the following way:∥θit − θi∗t ∥ →P 0,as t→∞, where →P signifies convergence in probability. This result is desirable as RL agentscommonly face an issue of computing policies optimal with respect to the current distributionalenvironment they face, but have only access to data generated from past distributional envi-ronments. The issue of changing distributional environments and moving targets is absent inthe single-agent stationary MDP setting but salient in the multi-agent learning setting of focushere.The algorithmic agents use samples from their interactions to for critic estimates. LetZ ⊂ Rd be a space of observations used in the construction of the loss function Lt : Θ 7→ R+.Each period, a realization Zt ∈ Z is generated after each algorithm chooses their actions.Throughout, Z ∈ Z’s distribution is parametrized by (ρ, s). That is, given current period’sρt, st, the distribution of Zt is pinned down and Zt is only non-stationary if ρt, st is. Sinceestimation is required by reinforcement learners, a stochastic element in choosing actions eachperiod is necessary to generate enough data. Commonly, actions are chosen randomly but undera distribution parametrized by the policy ρit. A basic example is ε-greedy action selection: witha small probability ε, actions are sampled uniformly, while with probability 1 − ε, policy ρit isfollowed. A common example of observations then is Zit = (st, ait, uit, st+1), a tuple of currentstate st, current action realization, payoff realization, and next state observed at the end ofeach period by a model-free4 algorithm. From this example it is clear how given ρt, st, thedistribution of Zit is fixed and only time-varying if ρt is time-varying, which will be translatedinto assumption 2 (1).Given compact set U ⊂ R, define a bounded function ℓ : Z ×Θ 7→ U . ℓ is Lipschitz in botharguments, the realizations of which the loss function will average over, as specified below.5Each algorithm uses only a batch of the most recent observations to construct their loss4Model-free algorithms estimate their performance measure (the critic) without a model of their environment,i.e. without assumptions about a functional form for their payoffs and transition probabilities, and withoutassumptions about their opponents existence and behavior. See e.g. Sutton and Barto [2018], chapter 6.5In general ℓ can be specific to individuals i, in which case the assumptions made here would have to hold forall i.82.2. Consistencyfunction. Define a sequence 0 < Kt < t with Kt ∈ N such that Kt →∞ with t, and letWt = {k : t−Kt + 1 ≤ k ≤ t},be the batch of periods used. Define W t = t−Kt + 1 as the first period of the batch. ThenLt(θ) =1Kt∑k∈Wtℓ(Zk, θ),is the empirical loss. The estimator is defined asθt ∈ argminθ∈ΘLt(θ),the empirical parametric minimizer. This formulation is quite general, allowing for many para-metric function estimators to be described. Examples of approximation methods supportedhere include polynomial, sinusoidal, and spline approximations (for an overview see e.g. Hansen[2010] section 20.). Let ρt = {ρk}W t≤k≤t denote batch-sequences of policies, with st definedanalogously for states. Our first assumption is on the smoothness of the loss function and thebehavior of its conditional expectation:Assumption 2. There exists a real-valued function ϕ(ρ, s, θ), Lipschitz in the first and thirdarguments where1. One can write:E[ℓ(Zt, θ) | ρt, st] = ϕ(ρt, st, θ),i.e. the expectation of ℓ(Zt, θ) conditional on a history of policies and states from periodsin Wt depends on time only through the current period’s realization (ρt, st).2. The following Lipschitz bounds apply:limt→∞1Kt∑k∈WtEC1(Zk) <∞,limt→∞1Kt∑k∈WtEC2(ρk, sk) <∞,supθ∈Θmaxs∈SC3(θ, s) <∞,Where C1(Z), C2(ρ, s), C3(θ, s) are bounded, non-negative functions that exist by the Lipschitz92.2. Consistencyproperties of ℓ, ϕ so that:|ℓ(Z, θ)− ℓ(Z, θ′)| ≤ C1(Z)∥θ − θ′∥,|ϕ(ρ, s, θ)− ϕ(ρ, s, θ′)| ≤ C2(ρ, s)∥θ − θ′∥,|ϕ(ρ, s, θ)− ϕ(ρ′, s, θ)| ≤ C3(θ, s)∥ρ− ρ′∥.In assumption 2 (1), expectations are taken over the distribution of Zt. In keeping with theexample of Zt = (st, ait, uit, st+1), this conditional expectation integrates over random actionsdue to exploration, possible randomness in the payoff realization, and the next state realization.As discussed previously in the introduction of observation space Z, if Zt is Markov given currentpolicy profile ρt and state st, and e.g. if the derivatives of ℓ are uniformly integrable, assumption2 (1) holds.6 Point (2) can be made to hold e.g. if ℓ has bounded derivatives almost everywhere.The following definition states the algorithmic updating rule studied in this chapter ingeneral terms:Definition 1. For each agent, ρit is updated in the following way:ρit+1 = ρit + αt[F i(ρit, θit) +Mit+1],where F i(ρit, θit) is the bounded parametric function estimator, αt ≥ 0 is a decreasing stepsizesequence satisfying the Robbins-Monro condition:αt → 0 with ∞∑t=0αt =∞;∞∑t=0α2t <∞,and M it+1 is an almost surely bounded martingale-difference noise based on an increasing se-quence of sigma algebras Gt.7Many updating rules can be written in the form above. The iteration can be interpreted as6This setting is considered in Section 2.3. For a concrete example, let |S| = L, and Ai = [0, 1]. Suppose atevery t, algorithms choose actions ε greedily: for a fixed 0 < ε < 1, with probability 1 − ε, ρit(st) is realized,while with probability ε, actions are sampled uniformly from Ai. Let ui = u be the same payoff function for alli, and Zt = (st, u(ρt(st), st), st+1), so that Z = u(A,S)× S. Then for any Borel set B ⊆ ZP(B | ρt, st, t)= P(B | ρt, st),since a current period’s action and state realization only depend on the current period’s policy profile, and sincestates transition according to their Markov property as given by assumption 1.7Notice that throughout, many important objects are functions of ρ. Note also that ρt is random due to itsgeneration through a stochastic difference equation. With some abuse of notation, I will use ρ to both specify aparameter when needed, and the realized value of the random variable generated according to definition 1.102.2. Consistencya variant of a Robbins-Monro scheme (Robbins and Monro [1951], for a discussion, see Borkar[2009]). The sequence of sigma algebras Gt can be interpreted as the information available tothe algorithm at each period, e.g. histories of past policies, observations, and shocks M it . Adiscussion and definition can be found in appendix B.1. This specification allows for a largevariety of algorithms, F i being what most distinguishes updating rules from each other. Thecritic mapping F i can e.g. be a gradient, or a maximizer of a value function. Specific examplesare discussed in Section 2.3.The next assumption encapsulates the two-timescale property of the algorithms analyzedhere, as mentioned in the introduction. This assumption is the essential driving force in theresults of this chapter, ensuring that the data used by the loss functions appropriately adjustsfor the fact that a moving target has to be followed.Assumption 3. Assume thatKtαt−Kt → 0,as t→∞.Define µρt(s) ∈ (0, 1) for every s as the unique invariant state distribution if policy profileρt were played forever, which exists by our irreducibility assumption 1. Further, define ρW t:k ={ρj}W t≤j≤k as a truncated sequence of policy profiles. Then letλk(s,ρW t:k, sW t) = P(sk = s | ρW t:k, sW t),be the likelihood of reaching state s in period k ∈Wt, if over periods W t, ..., k, ρt is the policyprofile sequence played, and sW t is the initial state in the first batch-period. Also let λk(s, ρ, st)be the counterpart where ρt = ρ in all periods W t, ..., k. The next assumption is a furtherstrengthening of assumption 1.Assumption 4. hh1. Assume for all t, k > t, that λk(s, ρ, st) and µρ are Lipschitz in ρ with Lipschitz constantsbounded uniformly over S.2. There exist cP > 0 and 1 ≤ k <∞ such that for all s′, s ∈ SP[sk = s′ | s0 = s, ρ] ≥ cP ,where the bound cP does not depend on ρ.112.2. ConsistencyAssumption 4 (1) ensures that the underlying state distributions are smooth, so thatstraightforward uniform convergence theorems can be applied later on. (2) is slightly strongerthan the initial irreducibility assumption on the Markov chain over s. It ensures that in theasymptotic analysis one can safely assume λk(s, ρ, st) > 0 for k > s with t large enough.Next, defineΛt(s,ρt, sW t) =1Kt∑k∈Wtλk(s,ρW t:k, sW t),as the average probability of reaching state s during time window Wt, if sW t is the initial stateand ρt, is the sequence of policy profiles played. To save notation, let ℓ(Zk, θ)s = ℓ(Zk, θ)1{sk =s} for all s ∈ S.The unknown target that Lt(θ) estimates, commonly called ‘population loss’, is then definedasL∗t (θ,ρt) =∑s∈SΛt(s,ρt, sW t)1Kt∑k∈Wt E[ℓ(Zk, θ)s | ρk]Λt(s,ρt, sW t),where, as in assumption 2, expectations in the numerator are taken with respect to the ran-domness in Zk. Next, defineL∗t (θ, ρt) =∑s∈SΛt(s, ρt, sW t)1Kt∑k∈Wt E[ℓ(Zk, θ)s | ρt]Λt(s, ρt, sW t),as the population loss in the case where in all periods k ∈Wt, ρt is the policy profile played.The t-limit of this loss function will play an important role in our results. Its derivationfollows from irreducibility and aperiodicity of the Markov Chain over states and smoothnessassumptions (assumptions 1, 2 and 4).Lemma 1. Suppose assumptions 1, 2, and 4 hold. Thenlimt→∞ supθ∈Θ,ρ∈Γ∥∥∥L∗t (θ, ρ)−∑s∈Sµρ(s)ϕ(ρ, s, θ)∥∥∥ = 0.Proof. All proofs can be found in the appendix.122.2. ConsistencyFrom now on, define this limiting population loss asL∗∞(θ, ρt) =∑s∈Sµρt(s)ϕ(ρt, s, θ),andθ∗(ρt) = argminθ∈ΘL∗∞(θ, ρt),as the optimal population parameter. Notice that θ∗ is a random variable, given that ρt is arandom variable.The next assumption ensures that for any trajectory ρt, there is a unique minimizer θ∗. Thisis a standard assumption common also to the analysis of extremum estimators in econometrics,see e.g. Hansen [2010] chapter 22. Define B(x, ε) as the ε-ball centered at x.Assumption 5 (Identification). For any ρ, and any ε > 0 there exists δ > 0 such that for allθ /∈ B(θ∗(ρ), ε):L∗∞(θ, ρ) ≥ L∗∞(θ∗(ρ), ρ) + δ.We can now state the main result of this paper:Theorem 1. Impose assumptions 1 - 5. Then for any sequence ρt satisfying Definition 1, andfor any ε > 0,P(∥θt − θ∗(ρt)∥ > ε)→ 0,as t→∞.This result is useful in the following sense: in general, the function approximation parametervector θt will depend on the whole policy profile trajectory ρt. Given that the opponent’s policiesare moving over time, this can result in a quite hard to interpret estimator and can lead tobad performance of the iteration ρit. However, the assumptions taken in the theorem ensurethat in fact, θt will, for large enough t, depend on the trajectory of policy profiles only throughthe most current period t. Thus, the resulting loss function behaves as if each agent knewtheir opponent’s current policy, and sampled observations from that policy to estimate theirloss function.Furthermore, the limiting population loss L∗∞ can represent desirable population loss func-tions commonly used in the literature, as will be shown in the next section. This will allow for132.3. Applicationsmore accurate predictions about future behavior of opponents, and therefore better performanceof the algorithm, as will be seen in Section 2.3.2.3 ApplicationsThis section provides an example of a performance measure, and examples of critic mappingsF i that would fit in the framework developed above.Given the setup defined in the previous section, a valid performance measure would be basedon the commonly employed action-value function Q∗i : S × Ai 7→ R. Given a payoff functionui : Ai × S 7→ R, and a discount factor δ ∈ (0, 1), it is defined implicitly asQ∗i (s, a) = ui(a, s) + δE[maxa′∈AQ∗i (s′, a′) | a, s]. (2.1)One of the reasons for the popularity of this function in Reinforcement Learning is the factthat it is a sufficient statistic to finding an optimal policy, simply by maximizing Q∗i . Considerthe value function of the problem of maximizing expected future discounted payoffs, definedvia the Bellman equation:V i(s) = maxa∈Ai{ui(a, s) + δE[V i(s′)| a, s]}.Q∗i is connected to Vi via the identity V i(s) = maxa∈Ai Q∗i (s, a), and thus can be used tofind optimal policies. A more thorough discussion of reinforcement learners involving Q∗i can befound in chapter 3. In what follows, to ease notation, the i-identifier will be dropped wheneverpossible.An extensive literature of reinforcement learning theory has focused on estimating thisfunction. In the single agent setting, where states evolve according to a controlled Markovchain, many convergence results exist for estimators of Q∗, starting with the seminal resultsin Watkins [1989]. Q∗ is a useful function to approximate in Markov Decision Problems since,under appropriate stationarity conditions, an optimal policy can be found straightforwardly bymaximizing Q∗. See Sutton and Barto [2018] for a thorough exposition of learning algorithmsrelated to Q∗.Q-learning algorithms are used to estimate Q∗, and compute an optimal policy based on it.A class of algorithms fitting our Batch-RL framework would be versions of Fitted Q-Iteration(FQI), (Ernst et al. [2005], and Busoniu et al. [2017] chapter 3 for a general discussion) as142.3. Applicationswill be introduced below. A parametric function estimator for Q∗ can be defined as a functionQ : S ×A×Θ 7→ R. As in Section 2.2, θ is the parameter to be estimated within the compactset Θ. An example of a common loss function is then called the squared Bellman-loss:ℓ(Zt, θ) =[ut + δmaxa′Q(st+1, a′, θ)−Q(st, at, θ)]2, (2.2)where we let Zt = ⟨st, at, ut, st+1⟩. It is important to note that this loss does not feature adistance to Q∗, since realizations of this target cannot be observed in practice. The hope isthat the true population minimizer of this loss function is close to Q∗, even if that target itselfis not an element of the family of functions Q parametrized by θ.Due to the necessity of generating data for estimation as mentioned in the previous section,suppose that each agent samples actions using a randomized policy ρ¯it based on their iterationpolicy ρit. Assume for simplicity here that Eρ¯it = ρit, with full support on Ai for all states. Inthat case, we haveE[ℓ(Zt, θ) | ρt, st]= E[ℓ(Zt, θ) | ρt, st],by the Markov property, and thus assumption 2 (1) is satisfied. Following the definition inassumption 2, we have thatϕ(ρt, st, θ) = E[[ut + δmaxa′Q(st+1, a′, θ)−Q(st, at, θ)]2 ∣∣∣ ρt, st].Then, imposing assumptions 1- 5, we can apply theorem 1. As defined in Section 2.2, weget that θt approaches, in probability,θ∗(ρt) ∈ argminθ∈ΘL∗∞(θ, ρt),where L∗∞(θ, ρt) evaluates to the mean-squared Bellman loss:∑s∈Sµρt(s)E[(ut + δmaxa′Q(st+1, a′, θ)−Q(st, at, θ))2 | ρt, st = s]. (2.3)The mean-squared Bellman loss represents a desirable population loss commonly studied in theliterature (see for example Sutton and Barto [2018], e.g. chapters 9, 11).Two important examples of algorithms as defined in Definition 1 based on such a loss152.4. Concluding Remarksfunction are actor-critic Q- learning, for whichF i(ρit, θit) ={argmaxa∈AiQi(s, a, θit)}s∈S , (2.4)and actor-critic gradient learning, where gradient here refers to a gradient in policies:F i(ρit, θit) ={∂Qi(s, a, θit)∂a}s∈S, (2.5)where {}s∈S is to be understood as stacking a vector over s ∈ S. A more general version ofactor-critic Q-learning features as the running example in chapter 3.The results of this chapter can also be used to establish sufficient conditions so that a keyassumption of chapter 3 is satisfied. This discussion can be found in appendix B.1.2.4 Concluding RemarksThis chapter gives sufficient conditions on the payoff structures, state evolution, and hyper-parameters of batch-RL algorithms so that their batch-estimation procedure has a tractableanalytical interpretation. The setting studied here is one of discrete states and interval actionspaces. However, it is likely that an extension can be constructed for more general state spaces,which is subject of further study here.The assumption throughout this paper is that each agent uses parametric function esti-mation in the classical sense, where the number of parameters is finite and smaller than thenumber of observations. This precludes the analysis of Deep RL methods, which by defini-tion overparametrize. However, recent advancements in the convergence analysis of Deep RLfor function approximation (Ramaswamy and Hullermeier [2021]) allow for optimism that anextension to this paper can be made that appropriately applies to Deep RL methods.16Chapter 3Multi-Agent Learning in the LongRun3.1 IntroductionIn this chapter, I introduce a model of reinforcement learning algorithms playing a marketgame such as Cournot quantity competition repeatedly. These algorithms observe a commonstate variable without knowing their payoff function or state transition likelihoods, and adaptby repeatedly experimenting with quantity choices and estimating a value function. I show topin down the long-run behavior of this system, it is enough to find the stable rest points of adifferential equation.The focus of this chapter is actor-critic reinforcement learning. These algorithms keep trackof an estimated performance criterion (the “critic”, essentially a value function) and a policyfunction (the “actor”) that is updated towards the maximizer of the performance criterion.The policy is a mapping from observables (states), such as past prices or other market data,to actions, e.g. prices or quantities. As a result, the class of algorithms studied here havethe ability to learn repeated game strategies (e.g., take the observable to be a summary of thehistory of the interaction), in contrast to the stage game (myopic) strategies more commonlystudied in the literature on learning in games.When policies are updated with a decreasing stepsize8 over time, and the performance cri-terion estimator is well-behaved, I show that the resulting policy iteration can be analyzed asa noisy discretization of a tractable differential equation. Under a well-studied special case inmy class known as actor-critic Q-learning9 (ACQ), this differential equation is a repeated gameversion of best-response dynamics. I obtain these results following the method of stochastic ap-proximation (Borkar [2009]), which I extend to characterize the limiting behavior of competingalgorithms.8Stepsizes signify the impact innovations have on policies in the algorithmic updating rule. They must satisfythe Robbins-Monro condition commonly invoked in the computer science literature. See Borkar [2009], chapter2.9See Dutta and Upreti [2022], Grondman et al. [2012] for relevant surveys.173.1. IntroductionSuppose that after a large enough number of iterations, the performance criterion estimatordiffers from the true criterion at most by a bounded, smooth bias term10. I then show thatattractors of the underlying differential equation will be learned with positive probability, whileunstable points will not be learned11. In the remainder of the chapter, I use ACQ as the runningexample. In that case, if the long run behavior of algorithms converges to a point, that pointmust be a Markov-perfect equilibrium (MPE) of the repeated stage game. The implication ofthis characterization is that it becomes necessary to understand what it means for a given MPEto be stable (i.e. attracting). This is done in chapter 4.Related LiteratureThis chapter makes use of an extensive body of research related to stochastic approximationtheory, which is applied to show that the long run behavior of some families of algorithmicupdating rules can be related to differential systems. See for example Borkar [2009]. The factthat stability properties of the underlying differential system can be applied to make predictionsabout the long run behavior of an algorithm has been shown by foundational works such asBena¨ım et al. [2012], and Hofbauer and Sandholm [2002].Results in this chapter connect also to a growing strand of the computer science literatureestablishing convergence proofs in multi-agent algorithmic environments. The paper in that areaclosest to this one is Mazumdar et al. [2020]. They establish a connection between gradient-based learning algorithms for continuous action games and asymptotic stability of equilibriaof the underlying game. While nested in the family considered here, the updating rules thatMazumdar et al. [2020] study implicitly assume that algorithms observe each other’s per periodpolicies, or at least observe an unbiased estimator of their per-period value function gradient.I argue that this assumption is difficult to satisfy, especially in the case of continuous actiongames. In chapter 2, I give low-level sufficient conditions on independent algorithms so that aweakened version of this assumption goes through. My results suggest that Mazumdar et al.[2020]’s results are robust to the type of bias in the gradient estimation that my RL class allows.Furthermore, this chapter focuses on the possibility of RL to learn history-dependent repeatedgame strategies, which is not the explicit goal of Mazumdar et al. [2020].10The bias term is a modelling decision inspired by the fact that for many real-world performance criterionestimators, bias is unavoidable due to function approximation (Fujimoto et al. [2018]). Also, often convergenceproofs are lacking, in which case the fitness of an algorithm is shown by it doing better at benchmark tasks thanprevious algorithms. C.f. the discussion in chapter 9 of Franc¸ois-Lavet et al. [2018]. My results imply that theanalysis of long run behavior is robust to well-behaved, non-vanishing bias.11An equilibrium of a differential equation is attracting (“stable”) if trajectories of the differential equationthat reach a neighborhood of that equilibrium converge to it. In contrast, an equilibrium is repelling (“unstable”)if trajectories close to that equilibrium can be repelled from it and will not converge to it.183.1. IntroductionBanchio and Mantegazza [2022] also consider a characterization of competing RL algorithmsand apply it to games of economic interest. There are important differences between the classthey consider, and the one considered here. It is unclear whether their analysis can accom-modate actor-critic approaches that are featured here, as such approaches require a separateestimation technique that can introduce dependence of policy parameters on histories of pastobservations. This is important, since the actor-critic feature allows us to consider closelythe learning of repeated game strategies, which is not featured in the focus of Banchio andMantegazza [2022].Other papers related to asymptotic analysis of multi-agent systems commonly focus ondeveloping a specific algorithm that behaves well in some metric, allow communication acrossalgorithms, require information on the primitives of the game, or do not ask about the nature ofthe limiting points. For example, Ramaswamy and Hullermeier [2021] give a thorough analysisof deep learning techniques for Q-functions using gradient updates, without considering stabilityproperties of rest points. Others focus on specific classes of games, for example zero-sum games(Sayin et al. [2021]) and show convergence of multi-agent learning there.There is now a growing area of research situated on the intersection of the theory of learningin games from an economist’s point of view, and the asymptotic theory of algorithmic learningfrom the computer science side. Leslie et al. [2020]’s paper is an example of a paper intendedmore for economists, while applying language also common to the computer science literature.They consider zero-sum Markov games and construct an updating scheme related to best re-sponse dynamics that converges to equilibria of the game. As they also keep track of separatepolicy and value function updates, their scheme falls into the class of actor-critic learning rulesgenerally, while not falling into the class considered in here due to important assumptions onthe updating speed differential between policy and performance criterion used there.Leslie and Collins [2006] introduce what they call “generalized weakened fictitious play”(GWFP), an adaptive learning process the limits of which can be related to classical continuoustime fictitious play (Brown [1951]), or stochastic fictitious play (c.f. Hofbauer and Sandholm[2002]), depending on details of the process. Their framework allows to conclude asymptoticbehavior of learning processes once one has shown that the process is a GWFP process. Theyshow that GWFP converges to Nash equilibria in games that have the fictitious play property.Notably, that class includes zero-sum games, submodular games, and potential games. Onecan interpret results in this chapter as showing that the running example (ACQ) of the RL Iconsider is a GWFP process, in the repeated games sense. Therefore, one can apply Leslie andCollins [2006] to conclude the long run behavior of that process in games with the fictitiousplay property. However, there are many repeated games of interest that do not have this193.2. Reinforcement Learningproperty; notably standard repeated oligopoly (Cournot) games where agents learn repeatedgame strategies. In chapter 4, I analyze the learnability of collusion in oligopoly games moreseriously, and therefore give a more detailed analysis of limiting behavior in a class of games notknown to have the fictitious play property. I do this by taking seriously the fact that GWFPcan in general be defined to learn repeated game strategies, which to the best of my knowledgehas so far only been considered under the restriction of Markov strategies for stochastic games.This chapter is structured as follows: In section 3.2 I give a brief introduction to RL, viathe classical example of single-agent Markov-decision problems (MDPs). In section 3.3 I definethe general economic environment our algorithms will play on, as well as ACQ learning, animportant element of my RL class that will serve as the running example of the chapter. Iprovide the main characterization results in section 3.4.Appendix B.1 characterizes the full algorithm class for which the main results of this chapterhold. Appendix B.2 gives most of the proofs of the results stated in this chapter.3.2 Reinforcement LearningThis section gives a short introduction to reinforcement learning (RL) by ways of the example ofan agent solving a multi-armed bandit problem. For a thorough introduction, consider Suttonand Barto [2018].Consider an agent choosing actions a ∈ X repeatedly. There is a state variable s ∈ S sothat in every possible s, the agent may find it best to choose different a. Given s, the agent’sexpected payoff from choosing a is denoted u(a, s), where expectations are taken over residualrandomness in the environment conditional on state and action. The agent discounts the futurewith δ ∈ (0, 1), and aims to find a policy ρ : S 7→ X that maximizes future expected discountedpayoffsW (s0) = E∑tδtut,where ut is the payoff realization in period t. When the distribution over states and otherrandomness affecting the payoffs is known, the agent can solve the problem of maximizing Wby computing the value functionV (s) = maxa∈X{u(a, s) + δE[V (s′)| a, s]}.In practice, information about u and transition probabilities may be hard to come by. This is203.2. Reinforcement Learningwhere RL methods can be useful.RL algorithms are updating rules meant for the learning of optimal policies or value functionsfor a given problem. Such algorithms are commonly used to solve Markov decision problems(MDPs). In general, RL updating rules move policies towards actions that have performed wellin the past (i.e., such actions are reinforced), and away from actions that perform poorly, basedon some performance criterion, e.g. W .A well-known algorithm the agent could use in this context is Q-learning as introduced byWatkins [1989]. The algorithm estimates a function Q : S ×A 7→ R, which is supposed to findthe target implicitly defined asQ∗(s, a) = u(a, s) + δE[maxa′∈XQ∗(s′, a′)| a, s]. (3.1)This Q- function is related to the value function by V (s) = maxa∈X Q∗(s, a). The Q- functioncan thus be seen as a function evaluating the expected payoff from choosing a in current states and playing optimally afterwards. One may therefore use this function to evaluate one-shot-deviations. Accordingly, Q∗ is a helpful tool for decision makers, since it allows to read-off theoptimal policy ρ∗ simply by maximizing Q∗ in every state.Watkins [1989] then proposed a RL algorithm that estimates Q∗. In the language intro-duced earlier, the algorithm takes estimates of Q∗ as the relevant performance criterion. Thisalgorithm is celebrated due to its simplicity as well as minimal information requirement. Onecan use the algorithm without any knowledge of a payoff function and transition function, thusfalling into the class of ‘model-free’ algorithms.For simplicity let S,A be finite, so Q∗ is a matrix. In the end of each period, the payoffrealization ut, current state st, current action taken at, and the next state st+1 are observed.The algorithm takes some initial value Q0, and then updates the following way:Qt+1(s, a) =Qt(s, a) + βt[ut + δmaxa′∈X Qt(st+1, a′)−Qt(s, a)]if st = s, at = aQt(s, a) otherwise, (3.2)where βt ≥ 0 is a (possibly stochastic) sequence of numbers converging to zero. Importantly,notice that Q-learning does not specify a policy, just a performance criterion. Convergenceresults on Qt give requirements on how often actions are selected over time, but generally theupdating rule is agnostic about how actions at are sampled in every period. As an agent whocares about behaving optimally, a clear exploration-exploitation tradeoff arises in this problem:should one follow the currently-believed optimal action, or try to find actions that may perform213.2. Reinforcement Learningbetter? A common, basic sampling method is known as ε-greedy:Fix a small ε ∈ (0, 1). In every period, the decision maker takes the currently believedoptimal action argmaxa′ Qt(st, a′) with probability 1 − ε. With probability ε, she samplesuniformly from A.For a suitable sequence βt, one can show that Qt converges in probability to Q∗ if statesform a Markov chain controlled by at and actions are sampled ε-greedily (c.f. Watkins andDayan [1992]).12 Stationarity of the state-transitions conditional on a fixed policy ρ is animportant ingredient of the standard convergence proof for Q- learning. If stationarity fails,one can imagine that learning of the correct Q∗ may fail also.The Multi-Agent SettingNow imagine the player described above in fact faces multiple competitors in a market, whichtransforms our MDP into a game. Without any knowledge about their payoff function, statetransitions, and opponents, the player may resort to Q-learning again. What if all players inthe game apply this method to learn their optimal policies?The purpose of this chapter is to characterize a class of algorithms for which it is possible toanalytically describe the limiting policies resulting from agents in that class competing againsteach other. As will be seen in the following sections, this requirement will be an importantpart of the characterization of the class of RL considered here. The class does not contain theabove described simple Q-learning rule, but a common evolution of it, that explicitly adaptsa policy function ρt at the same time as estimating the Q-function, making it an actor-criticQ-learning (ACQ) rule as described in the Introduction. In this section and the main body ofthe chapter, I focus on ACQ for clarity. The general class of algorithms is broader and fullydefined in appendix B.1.In general, I allow the algorithms to be model-free. This translates to a restriction on howperformance criterion estimates are generated. Model-free algorithms maintain estimates oftheir performance criterion without explicitly modeling their own or their opponent behaviorand payoffs. This serves as a minimal-information benchmark, which will be shown to besufficient to lead to the emergence of collusion.13 There are multiple reasons why this is adifficult situation for such agents when it comes to learning a good policy, as discussed inchapter 2, and also in Hernandez-Leal et al. [2017]. I will be abstract about the estimation12This convergence result for single-agent problems has been studied extensively, and it holds generally as longas all actions and states are visited sufficiently often.13Furthermore, model-free algorithms can be thought of as a tool for a firm that recently entered a new,dynamic market. Information on payoffs and market conditions may be hard to come by, so such a firm mayresort to an algorithm that has minimal information requirements.223.3. Preliminaries and Running Exampleof the performance criterion, and introduce a class of algorithms that perform reasonably wellin the function approximation step, up to a well-behaved asymptotic bias term. I believe thatallowing for an asymptotic bias significantly increases the number of learning algorithms thatfall into our class of RL agents, due to the inherent problems these agents face while learning.The results in this chapter are concerned with algorithms that learn to play continuous actionpolicies14. In that case, unbiasedly estimating a value function becomes a difficult task evenwhen stationarity of the environment is satisfied. Commonly in such situations, algorithms usesome form of parametric function approximation to generate an estimate, which can introducebias. Often this involves deep neural networks due to their flexibility and scaleability. I refer toFranc¸ois-Lavet et al. [2018] for a thorough introduction to state-of-the-art RL techniques and adeeper dive into issues of biased estimation of value functions and their gradients. I will showthat the bias I allow in this class does not affect the main results developed in the next section.3.3 Preliminaries and Running ExampleThere are n algorithms indexed by i, each having as action space a compact interval Xi, withprofile space X = ×iXi. A finite state space S with |S| = L comes with a transition probabilityfunction T : S2 × X 7→ (0, 1) where I will maintain throughout the chapter that each statespace considered is irreducible, as specified below.15 Furthermore, after defining its transitionprobability function, I will refer to a state space S keeping implicitly in mind that it comeswith its own transition probability. Each algorithm has a payoff function ui : X × S 7→ R, C2in X, and common discount factor δ ∈ (0, 1).16Algorithms update a policy function ρit : S 7→ Xi, the long-run behavior of which is theobject of our interest. Since states are discrete, policy profile ρt ∈ X¯ = XnL can be representedas a vector in RnL.Assumption 6. For all ρ ∈ X¯, the Markov chain induced by Tss′ [ρ(s)] is irreducible and14This is not as restrictive as might seem. When playing discrete action games, RL algorithms commonly playon the mixed policy space, for example learning to play ’softmax’ strategies of the form P[q| s] = exp(Q(s,q))∑q′ exp(Q(s,q′)).This again falls into our continuous control scenario.15While it may be possible to carry out an analogous characterization of long-run policies under compactinterval domains, the interpretability of the results would likely suffer. RL algorithms commonly used in the caseof interval-state spaces take the policy to be a parametric function of the state, and optimize the parameters ratherthan the policy itself (c.f. Sutton and Barto [2018], chapter 13), which introduces an issue of interpretability. Atthe same time, since this chapter is not concerned with speed of convergence or computational constraints, onecan always take a fine enough discretization of an interval domain and the analysis in this chapter applies.16Let Ci[X,Y ] be the set of functions that are i times continuously differentiable, with domain X and rangeY . When domain and range are clear, I write Ci.233.3. Preliminaries and Running Exampleaperiodic.17In fact, one can view such a policy as a stationary Markov strategy given state space S.Further, define X¯i = XLi , and X¯9i = ×j ̸=iX¯j .Expected future discounted payoffs W i(ρi, ρ9i, s0) can be defined given stationary policyprofiles [ρi, ρ9i] ∈ X¯:W i(ρi, ρ9i, s0) = E∞∑t=0δtui(ρ(st), st), (3.3)where the expectation is taken over the randomness in the stage game payoffs and state variable.Then define BiS(ρ9i) as the optimal policy given a profile ρ9i ∈ X¯9i, chosen from the con-straint set of stationary, S-state policies:BiS(ρ9i) = argmaxρ∈X¯iW i(ρ, ρ9i, s0), (3.4)where due to our assumption on irreducibility of the state space the optimal policy does notdepend on the initial state s0. The optimal policy is indeed optimal over all possible dynamicpolicies since given a Markov stationary opponent profile ρ9i there must be a Markov stationarybest response.Definition 2. Define(i) ES ⊂ X¯ to be the set of Nash equilibria in policy profiles based on payoff functions W i.In other words, ES is the set of profiles ρ∗ s.t. ρ∗i ∈ BiS(ρ∗9i) for all i.(ii) ρ∗ ∈ ES as ’differential Nash equilibrium’ if ρ∗ is interior, first order conditions hold foreach agent at ρ∗, and the Hessian of each agent’s optimization problem at ρ∗ is negativedefinite.By definition, if ρ∗ ∈ ES is a differential Nash equilibrium, then there is an open neighbor-hood Uρ∗ of ρ∗ such that best responses must be single valued for all ρ ∈ Uρ∗ . Let US =⋃ESUρ∗ .Given these definitions of the underlying payoff environment, the following assumption is in-troduced:Assumption 7 (Equilibrium existence and differentiability). hhh(i) Given state space S, stationary equilibrium profiles ρ∗ ∈ X¯ exist. Call the set of suchequilibria ES.17For definitions, see e.g. appendix A in Puterman [2014]243.3. Preliminaries and Running Example(ii) There exist ρ∗ ∈ ES that are differential Nash equilibria.A sufficient condition for both points in assumption 7 to hold is the existence of an interiorstatic Nash equilibrium, given u(a, s) for all s ∈ S. As our analysis of limiting strategies willdepend on a smoothness condition of an underlying differential equation at the given rest point,the second point will prove crucial.Throughout, it is important to keep in mind that I define an environment competed on notby rational agents, but by algorithms constrained to play policies based on a fixed state spacedomain. When an algorithm is defined in our class, it comes with a finite state variable S asa primitive. I will take S as an exogenous object chosen by whoever initialized the algorithm.Importantly, I will assume throughout that the state variable and current state s is a commonobservable to all algorithms competing. The state variable can be interpreted as a model ofwhat kind of information the RL is allowed to condition their policy on.Now to state the running example of RL studied here. Assume that each algorithm usesthe following adaptive rule to update their policy, which is known as actor-critic Q learning(ACQ):1819Definition 3. Each algorithm i updates policies ρit according toρit+1(s) ∈ ρit(s) + αt[argmaxa′∈XQit(s, a′)− ρit(s) +M it+1], (3.5)where αt > 0 is a sequence of stepsizes converging to zero and Mit+1 is an i.i.d, zero-mean,bounded variance noise generated as a means of exploring the policy space, commonly referredto as ‘parameter noise exploration’2021.18I focus on the algorithm in Definition 3 because it forms the basis of many well-behaved real world algorithms,see for example Fujimoto et al. [2018] who introduce an algorithm based on ACQ used in real-world applications.Other algorithms of interest that can be accommodated include gradient-type algorithms. A full exposition canbe found in appendix B.1.19Notice that Definition 3 does not exclude the case in which the function to be approximated is fully known,or there is no bias term. The results thus include the case where agents know their value functions and follow asimple heuristic in updating their payoffs, taking as an input the current strategies of their opponent.20Since our main interest is in algorithms used under incomplete knowledge of the environment, the non-vanishing variance ofMt+1 can be motivated constructively by a need to explore the policy space due to estimationrequirements on the one hand, and residual randomness due to the fact that performance criterion Q∗ is beingestimated. For continuous action problems, various methods of exploration have been suggested, the version ofparameter noise introduced here being one that is adopted frequently in the literature and allows for especiallyclean analytical results (see Plappert et al. [2017], and Yang et al. [2021] for a comprehensive survey).21Notice that I use ’∈’ instead of ’=’ above, since I allow for the possibility of the argmax having multiplevalues. If that is indeed the case, I allow the algorithm to pick arbitrarily, which will not affect the limitingcharacterization in ways that matter, as will be seen in section 3.4.253.3. Preliminaries and Running ExampleQit(s, a) is an estimator ofQi∗(s, a, ρ9it ) = u(a, s) + δE[maxa′∈XQi∗(s′, a′, ρ9it )| a, s],the correct Q∗-function conditional on i’s opponents playing profile ρ9it forever into the future.This Q∗ is related to W through the equationmaxa′∈XiQi∗(s, a′, ρ9i) = maxρ∈X¯iW i(ρ, ρ9i, s).Qit is motivated from stationary MDPs as introduced in Section 3.2. It is important to notethe use of this estimator in the multi-agent case faced here imposes an implicit behavioralassumption on each algorithm. Suppose that Qit(s, a) = Qi∗(s, a, ρ9it ), i.e. the estimator isperfectly correct. Then what the agent computes in their updating step (3.5) is a best responsein stationary strategies, supposing that the opponents hold their current profile ρ9it fixed foreverinto the future. Having read that every algorithm uses (3.5) to update their policies, thissupposition is clearly incorrect. However, firstly as stepsizes for ρit decrease, computing Q∗ canbe seen as an approximation to the true future expected value that would take into accountevolving ρ9it . Secondly, as stated before, this chapter is not looking into a positive theory ofhow an optimal algorithm should behave. Rather, the interest is in developing a model thatis realistic enough while staying analyzable, and forms an informational lower benchmark onalgorithms in the sense that they can be allowed to be model-free. As will be shown in chapter4, the assumptions made here will be sufficient to allow for collusive and other interestingbehavior to emerge.The following assumption ensures that Qit tracks the correct function Qi∗ well when t islarge enough. The classical Q- estimator (3.2) defined to motivate Q-learning will not beenough for this to be true, as it requires discretization of the continuous action space and mayrun into issues due to the underlying non-stationarity of the problem. However, more involvedestimation schemes exist for which Qit can be shown to track Qi∗, as shown e.g. in appendixB.1.Assumption 8. For each i there exists a bounded function gi(s, a, ρ9i), C2 in a, ρ9i such thatwe can defineχit ≡ sup(s,a)∈S×X,∥∥Qit(s, a)−Qi∗(s, a, ρ9it )− gi(s, a, ρ9it )∥∥.263.3. Preliminaries and Running ExampleAssume for each i:(i)χit = OP (t9 12 ),(ii)suptE[(χit)2]<∞.In words, estimators Qit converge uniformly to a biased version of Qi∗. Point (i) bounds theconvergence speed by t912 , and point (ii) ensures that large errors have negligible mass, whichis important in the approximation results established in the next section. For appropriatefunction approximation schemes, the convergence speed can also be shown to satisfy point (i),as is shown in proposition 6.Assumption 8 puts discipline on the limiting difference between Qt and Q∗. Importantly,it is assumed that there exists a well-behaved function g, independent of t, that representsthis limiting difference in expectation in the long run. Furthermore, this limiting difference, orasymptotic bias, is a function of t only through its dependence on the current period’s profileρt. Thus, assumption 8 allows for an asymptotic bias term in the Qt estimation. Results inthe long run characterizations of Section 3.4 impose this bias to be small enough so that limitsof ρt can be inferred via a model in which g = 0. This robustification means it is sufficientfor researchers to verify smoothness and bound a possible asymptotic bias, without needing toknow the specific functional form of g. As stated in the beginning of this section, g is introducedfor the sake of realism and in order to significantly increase the number of RL algorithms thatcan be analyzed in this chapter.Assumption 8 is not trivial, since it sweeps away the issue of non-stationarity when it comesto estimating Qt discussed before. However, firms expecting to compete in a non-stationaryenvironment can be readily assumed to prefer algorithms that can satisfy this assumption overbasic Qt algorithms, as in (3.2). There exist more involved algorithms that can adapt to bothof these issues, as shown in appendix B.1.For the stepsizes αt I maintain the following:Assumption 9. Robbins-Monro Condition on stepsizes:αt → 0 with ∞∑t=0αt =∞;∞∑t=0α2t <∞.273.4. Long Run BehaviorThis assumption takes its name from the celebrated Robbins-Monro algorithm represen-tation (Robbins and Monro [1951]). The assumption constrains the speed of convergence ofαt, needing to balance the averaging out of errors (i.e. be fast enough), versus moving slowlyenough to ensure sufficient exploration of the policy space.Throughout the rest of the chapter, I impose the following assumption on the iteration ρt:Assumption 10. Iterates stay bounded almost surely:supt≥0∥ρt∥ <∞, a.s.Even though commonly made, assumption 10 is often difficult to verify. It is common forauthors to give all their results conditioning on the event that 10 holds, see for example Bena¨ımand Faure [2012]. For a more general discussion of sufficient conditions for bounded iterates,see Borkar [2009], chapter 2.With assumptions 8 and 9 in place, I will show that one can apply results from stochasticapproximation theory (see e.g. Borkar [2009]) to connect the long-run behavior of ρt to limitingsets of solutions to an underlying differential equation. Given assumption 8, one can convinceoneself that this differential equation will have to do with the computation of a best response.This is indeed the case, as will become clear shortly.3.4 Long Run BehaviorThroughout, maintain assumptions 7 - 10.Definition 4. Take the algorithm from Definition 3. The limit set is defined asLS,g =⋂t≥0{ρs |s ≥ t},the set of limits of convergent subsequences ρtk .I write S, g as subscript to underline the dependence of the limiting set on the state space Sand bias function g, both of which are implied by the specification of the algorithms in use. Asthe characterizations introduced here will require properties of a differential equation, I presentnext some useful definitions:Definition 5. Given some ODE ρ˙ = f(ρ), let ρ∗ be a rest point of f(ρ). Let Λ = eigv[Df(ρ∗)]the set of eigenvalues of the linearization of f at ρ∗. For a complex number z, let Re[z] ∈ R bethe real part. ρ∗ is283.4. Long Run Behavior• Hyperbolic if Re[λ] ̸= 0 holds for all λ ∈ Λ.• Asymptotically stable if Re[λ] < 0 holds for all λ ∈ Λ.• Linearly unstable if Re[λ] > 0 holds for at least one λ ∈ Λ.As mentioned in the discussion following assumption 8, I will now show that as long asthe asymptotic bias term g is sufficiently bounded, one can analyze limits LS,g equivalently byanalyzing the special case LS,0, i.e. a situation where g = 0 everywhere. For γ > 0, let Bkγ bethe set of Ck functions with bounded derivatives :Bkγ ={g : X¯ 7→ RnL | supx∈X¯∥g(x)∥+k∑j=1supx∈X¯∥Djg(x)∥ ≤ γ}, (3.6)where Djg represents the j’th derivative.To save notation, define for ρ ∈ X¯FSB(ρ) = B¯S(ρ)− ρ, (3.7)as the state dependent best response dynamics, where I take B¯S(ρ) to be the stacked versionof BiS(ρ9i) over i.Proposition 1. Let ρ∗ ∈ US be asymptotically stable for FSB . Then for all γ small enough andall g ∈ B1γ there is a profile ρg such that1. supg∈B1γ |ρg − ρ∗| → 0 as γ → 0.2. P[LS,g = {ρg}] > 0.Proof Sketch of proposition 1The full proof for this and the following propositions can be found in appendix B.2. Firstly,I make a general connection between the recursion in (3.5) and the differential inclusion FSB .This follows from celebrated results in stochastic approximation theory. One can relate a time-interpolated version of the recursion ρt to solutions of the differential inclusionρ˙ ∈ Fg(ρ(t)) ≡ conv[FSB(ρ(t))] + g(ρ(t)),where for any set B, conv[B] represents the convex closure.Since the best-response may be multivalued, solutions to this inclusion are not guaranteed.However, assumptions on the regularity of FSB (which comes down to a linear growth condition)allow us to show that there is a global solution in the sense of Filipov [1988].293.4. Long Run BehaviorWhen considering that the updating rate αt converges to zero, one may convince oneselfthat the recursion in (3.5) looks similar to a discrete time approximation to a time-derivative.The idea then is to show that the time-interpolated version of ρt indeed must stay close, withprobability one, to solutions of an underlying differential inclusion. The limiting behavior of ρtcan then be deduced from a subset of the limiting behaviors of the differential inclusion above.The proof of the proposition then establishes a firm connection between ρ∗ and ρg. I use amore general version of the inverse function theorem to show that since g(ρ) is a well-behaved,differentiable bias term, for every ρ∗ there is a unique rest point ρg. Further, stability of ρ∗must carry over to stability of ρg. Once it is established that ρt tracks solutions to the aboveinclusion over time, it makes sense that attracting points of the differential system will alsoattract ρt over time.Since I allow for the estimation of performance criterion Q∗ used by each algorithm to bebiased, when considering the long run of ρt one may only see ε-equilibria of the game, definedbelow:Definition 6. A profile ρ is an ε-equilibrium if for all players i, all individual profiles ρ′ ∈ X¯,and states s ∈ SW i(ρ, s) ≥W i(ρ′, ρ9i, s)− ε.Corollary 1. Let ρ∗ ∈ E be asymptotically stable for FSB . Then for all γ small enough and allg ∈ B1γ there is a ε¯ > 0 and a profile ρg such that1. ρg is an ε-equilibrium for all ε ≥ ε¯.2. supg∈B1γ |ρg − ρ∗| → 0 as γ → 0.3. P[LS,g = {ρg}] > 0.Notice that the stability property of an equilibrium depends on the performance criterionFSB used by the underlying algorithm, and is not affected by the bias term g as long as it iswell-behaved, i.e. g ∈ B1γ . The stability of ρ∗ itself depends further on the state space observedby the algorithms. I therefore emphasize this dependence by writing FSB as the best responsedynamics defined on state space S.Proposition 2. Let ρ∗ ∈ US be linearly unstable for FSB . Then for all γ small enough and allg ∈ B1γ there is an open neighborhood Uγ with ρ∗ ∈ Uγ such thatP[LS,g ∈ Uγ ] = 0.303.5. Concluding RemarksProof Sketch of proposition 2Firstly, as in the proof of proposition 1, I establish a one-to-one relationship between the stabilityproperties of ρ∗ and the rest points ρg. ρg being unstable hyperbolic implies that there existsan unstable manifold that ρg lies on, which acts as a repeller to the differential inclusion Fg. Igo on to show that due to the instability of ρg and nonvanishing variance of Mt+1, no matterhow close the algorithm updates come to ρg, and no matter how large t is, there is always ahigh probability that ρt lands on the unstable manifold and therefore must move away fromρg. Finally, I show the existence of a neighborhood Uγ . I show that due to the hyperbolicityof ρ∗, ρg, there is a neighborhood U around ρg with ρ∗ ∈ U such that ρg is the only internallychain transitive set within U . Recall that ρ∗ is not internally chain transitive for the perturbedsystem Fg, and the result follows.Corollary 1 and proposition 2 show the full potential of our characterization. Asymptoticallystable equilibria are equilibria that can be limiting points of the RL learning procedure, whileunstable equilibria are not. The intuition is related to how RL learn to play: since such agentsmake errors due to estimation and also to explore their action space, opponent’s strategy profilesare constantly perturbed. In other words, out of the view of a fixed agent i, the other agentsare frequently deviating to policies nearby in the policy space. Now suppose the current profileρt is close to an equilibrium ρ∗. Since i’s updating rule tracks FSB , their policy will only stayclose to ρ∗ if the dynamics of FSB are somehow robust to deviations. This robustness is impliedby asymptotic stability, and broken by unstable equilibria.There is a caveat here, however: Corollary 1 does not state that all limiting points in LS,gwill be equilibria of the game. Depending on details of the environment, one may or may notbe able to rule out the case where algorithm updates get trapped in a cycle, or other morecomplex behavior not involving rest points (see Papadimitriou and Piliouras [2018]). I do notinclude cycles in the above definition, however it is straightforward to extend proposition 1 tothe case of attracting cycles as in Faure and Roth [2010], and there exist results consideringlinearly unstable cycles (Bena¨ım and Faure [2012]) that suggest one may extend proposition 2to such linearly unstable cycles also.223.5 Concluding RemarksThis chapter presents a characterization of long run learning in the multi-agent setting for afamily of algorithms that, to the best of my knowledge, has not been analyzed through this lens22The inclusion of an analysis of limit cycles is an interesting avenue of further research, but would be beyondthe scope of this investigation.313.5. Concluding Remarksbefore. The actor-critic family studied here can be considered a fundamental class of algorithmsused by firms in practice; a firm will need an algorithm to find a policy function (the actor),since it is prudent to have a decision rule that adjusts actions to information at hand. Atthe same time, a firm will need to be able to evaluate the performance of its choices, whichrepresents the need for a measure such as the critic in the family studied here.The results stated in this chapter can distinguish whether a given equilibrium will be learnedwith positive, or with zero probability. This is the current state of the art of the stochastic ap-proximation approach applied here; in the future, it will be interesting to look into an approachthat allows to evaluate the relative likelihood of observing one equilibrium versus another. Suchan improved characterization will allow for the study of a meta-game. In such a meta-game,firms will choose algorithms (say, the state variable used by the algorithm, the stepsize sequence,or other details of the updating rule). Using this improved characterization, firms can evaluatetheir expected profits from a given algorithm profile. That way, it will be possible to employ aNash equilibrium analysis of a meta-game of choosing algorithms.32Chapter 4Learning to Collude4.1 IntroductionIn this chapter, I study a repeated Cournot game played by RL algorithms falling into thefamily of ACQ learners, as introduced in the previous chapter. The characterization providedin chapter 3 allows to analyze the long run behavior of ACQ learners playing this game. As anon-collusive benchmark, and to introduce intuitions, I ask when the static Nash equilibrium(Cournot equilibrium) can be learned. It turns out that the answer depends on what statevariables these algorithms keep track of, and how these states evolve as a function of pastprices and quantities. For instance, in the case where the state variable is the past period’sprice only, learning the static Nash equilibrium comes down to a condition on the stage gamepayoff function alone. In contrast, I construct a richer state variable under which the staticNash equilibrium may not be learned, even if payoffs satisfy the previous requirement.This richer state variable supports symmetric binary-state equilibria that in one state playcollusive, low quantities, and high punishment quantities in the other. I provide sufficientconditions so that such equilibria will be learned with positive probability.Through an approximation exercise, I show that these collusive equilibria are closely relatedto optimal imperfect monitoring equilibria of the bang-bang kind, as characterized in Abreuet al. [1986].Finally, I provide a numerical example featuring the above properties: there is an attracting,collusive equilibrium as well as a unique stage game Nash equilibrium that is unstable. I verifyin a simulation that ACQ learners initialized in a neighborhood of the collusive equilibrium willindeed converge to it. I also simulate these algorithms initialized close to the stage game Nashequilibrium, and show how they not only do not converge to that equilibrium, but instead moveto a neighborhood of the collusive equilibrium.Related LiteratureBroadly speaking, this project speaks to results in the fast-growing literature on algorithmiccollusion, and the theory of learning in games.334.2. Repeated CournotFirstly, the literature on algorithmic collusion has received increasing attention in recentyears. Assad et al. [2020] provide an empirical study supporting the hypothesis that algorithmsmay learn to play collusively, while there are many simulation studies suggesting the same, ofwhich Calvano et al. [2020], Calvano et al. [2021], and Klein [2021] are important examples.A paper close in spirit to this study is Banchio and Mantegazza [2022]. They consider afluid approximation technique related to the stochastic approximation approach applied here,and recover interesting phenomena regarding the learning of cooperation for a class of RLalgorithms. Important recent work in the area of algorithmic collusion includes Lamba andZhuk [2022], Brown and MacKay [2021], Johnson et al. [2020], and Salcedo [2015]. Thesepapers feature stylized models of algorithmic competition, abstracting away from issues oflearning and estimation, which are an important aspect of my analysis. Their relation to thiswork is discussed more thoroughly in Section 4.6.Secondly, this chapter connects to a long history of the theory of learning in games. Classi-cally, this literature has been concerned with the ability of agents to learn a Nash equilibrium ofthe stage game when following a given learning rule (e.g. Milgrom and Roberts [1991], Fuden-berg and Kreps [1993]). More recent results concern learning in stochastic games (e.g. Leslieet al. [2020]), where the state variable is taken as an exogenous object. The class of RL I studyhas the ability to learn repeated game strategies, i.e. strategies that condition on summaries ofthe history of the game. The games that can be studied here therefore contain stochastic gamesas a special case, but also allow for the case where the state that agents observe represents afinite history of the repeated interaction.This chapter is structured as follows: In section 4.2 I introduce the repeated game of quantitycompetition to which RL are applied. Section 4.3 provides two binary state variables and studieswhat RL in the ACQ family can learn given either of those. I provide an analysis of collusiveequilibria and conditions for such behaviors to be learned in section 4.4. Section 4.5 givesa numerical example and a simulation study to illustrate the theoretical results. Section 4.6concludes and discusses related literature more thoroughly.Appendix C.1 gives technical results regarding asymptotic stability of equilibria under ACQlearning, appendix C.2 provides generalizations to the results presented in this chapter, whileappendix C.3 hosts most of the proofs.4.2 Repeated CournotRecall that in chapter 3, I established a link between state dependent best-response dynamicsFSB as defined in (3.7), and long-run behavior of ACQ learners. In chapter 3 (corollary 1 and344.2. Repeated Cournotproposition 2), I show the following:“A given Markov perfect equilibrium profile will be learned by ACQ learners with positiveprobability if it is attracting under FSB , and with zero probability if it is unstable under FSB .”Therefore, this chapter will consider the existence and stability of equilibria under FSB in arepeated Cournot game more closely. This game can be shown to satisfy assumptions 6 and 7as a consequence of the model setup and lemma 2. It follows that whenever an ACQ algorithmsatisfies assumptions 8 and 9, the long run characterizations of chapter 3 apply.The game is set up as follows:• 2 agents i ∈ {1, 2}.• Stochastic binary price outcome Y ∈ Y = {PL, PH}.• Quantity choice q ∈ X = [0,M ] for some large M > 0, with aggregate quantity Q.• Probability of PL given Q:P[Y = PL|Q] = h(Q),with h′(Q) ≥ 0.• Expected price conditional on Q:Y (Q) = PLh(Q) + PH(1− h(Q)).• Twice differentiable cost function c(q).• Stage game payoff for i ∈ {1, 2}ui(q1, q2) = Y (Q)qi − c(qi),with Q = q1 + q2.Throughout, let S0 = {1} be the trivial state space. FS0B then simplifies to the classicalstage game strategy based best response dynamics, which I sometimes refer to as ‘myopic’ bestresponse dynamics, given the repeated nature of the interaction at hand. Under FS0B , it iswell known that under general conditions on Y (Q), there is a unique Nash equilibrium that isglobally attracting (Milgrom and Roberts [1990]).354.2. Repeated CournotFirstly, I will derive the objects relevant for stability analysis given a general commonlyobserved binary state variable S = {A,B}. Define for any s ∈ S, and qi ∈ X:PsB(q1, q2) = P[s′ = B| s; q1, q2],the transition probability to move to state B given current state s and quantity choices qi instate s. Throughout, I maintain assumption 6 as done in previous chapter. Also assume thatPsB(q1, q2) = P[s′ = B| s; q1 + q2],for all s, qi, i.e. transition probabilities only depend on aggregate quantities. I will thereforesometimes write Pss′(q1, q2) = Pss′(Q) with Q = q1 + q2.Throughout, let ρi : S 7→ X be each player’s policy, and recalling the definition of W i in(3.3), note that in the binary case one can deriveW i(ρ,A) = ω−1[(1− δPBB(ρ))ui(ρi(A), ρ9i(A))+ δPAB(ρ)ui(ρi(B), ρ9i(B))],W i(ρ,B) = ω−1[δ(1− PBB(ρ))ui(ρi(A), ρ9i(A))+ (1− δ(1− PAB))ui(ρi(B), ρ9i(B))],(4.1)whereω =[1 + δ(PAB(ρ)− PBB(ρ))].Thus, W i is a convex combination of stage game payoffs ui over the two states, with weightsbeing a function of transition probabilities. Notably, as δ → 1, these weights will converge tothe unique23 stationary distribution over states given the policy profile ρ.In what follows I will eventually focus on symmetric equilibria, and therefore drop the i-superscript for all objects, fixing our attention on player 1’s payoffs. Suppose ρ∗1 is an interiorbest response to ρ2 (i.e. ρ∗1 ∈ BR1S(ρ2), as defined in (3.4)) for which local optimality conditionshold with a negative definite Hessian. One can then use the implicit function theorem to findthe derivative of 1’s best response with respect to ρ2, which will be an essential building blockin finding stability conditions of an equilibrium. Since policies are vectors in X2, from now onI will use the conventions ρi(s) = ρis ∈ X for all i, s.23Uniqueness is implied by our irreducibility assumption 6.364.2. Repeated CournotJ(ρ∗1, ρ2) =∂ρ∗1A∂ρ2A∂ρ∗1A∂ρ2B∂ρ∗1B∂ρ2A∂ρ∗1B∂ρ2B . (4.2)In the following, to further ease notation, I will adopt the following conventions:• us = u(ρs, ρs), for s ∈ S.• usi =∂us∂qiand usij =∂usi∂qj, for i, j = 1, 2, s ∈ S.• P ′sB =∂PsB∂q1= ∂PsB∂q2 for all s and analogously for P′′sB where the equality comes from thefact that PsB only depends on aggregate quantities.More explicitly, one can then write∂ρ∗1A∂ρ2A= −1 + ω−1δP ′AB(uA2 − uA1 ) + uA11 − uA12ω−1δP ′′AB(uB − uA) + uA11,∂ρ∗1A∂ρ2B=ω−1δP ′AB(uB1 − uB2 )ω−1δP ′′AB(uB − uA) + uA11,∂ρ∗1B∂ρ2A=ω−1δP ′BB(uA2 − uA1 )ω−1δP ′′BB(uB − uA) + uB11,∂ρ∗1B∂ρ2B= −1 + ω−1δP ′BB(uB1 − uB2 ) + uB11 − uB12ω−1δP ′′BB(uB − uA) + uB11.(4.3)Now I introduce more structure to the Cournot payoff function that is natural and will bemaintained throughout the chapter.Definition 7. Say that the payoff function u(q1, q2) is regular if(i) u1(0, 0) > 0.(ii) c(0) = 0, c′(0) > 0, c′′(q) ≥ 0 for all q ∈ X.(iii) Y ′(2q) < 0 for all q < M .(iv) There exists K ∈ (0,M) with u1(0, 2K) < 0 and such thatmaxq≤2K,q′≤2K−qY ′(q + q′) + qY ′′(q + q′) ≤ 0.374.2. Repeated CournotDefinition 7 is slightly weaker than standard assumptions made for the Cournot game.Points (i-iii) are standard assumptions to be expected from a Cournot game. Point (i) makesthe problem interesting, point (ii) is a natural assumption on the cost function, point (iii)a natural assumption on the inverse demand. Point (iv) represents a small deviation fromthe norm only in that I allow for the quantity representing the second derivative of marginalrevenue to be positive for large quantities in X, which will give us flexibility to later on supporta simple, symmetric binary-state collusive equilibrium. At the same time it is enough to have ube quasi-concave as will be shown below. The assumption is weaker than the commonly madeassumption “Y ′(Q) + qY ′′(Q) ≤ 0” for all q,Q (e.g. Hahn [1962]).Lemma 2. Suppose u is regular. Then under a boundary restriction there exists a unique Nashequilibrium qN , which is symmetric and statically stable.As stated before, when u is regular, the unique Nash equilibrium is globally attracting undermyopic best-response dynamics, and therefore if RL played on the trivial state space S0, theywould converge to qN with probability 1. I show next that even though that is true, binarystate variables exist so that when RL condition their policies on them, they will not learn thestatically stable Nash equilibrium:First, consider the matrix of best-response derivatives under a binary state variable whenthe static Nash equilibrium is played: ρis = qN for both i, s. I call this policy ρN .JN =BR′N +δP ′AB(ρN )ωNuN2uN11− δP ′AB(ρN )ωNuN2uN11− δP ′BA(ρN )ωNuN2uN11BR′N +δP ′BA(ρN )ωNuN2uN11 ,where ωN signifies evaluation of ω at ρN and I use that BR′N = −uN12uN11. Thus, one can readoff the tradeoffs faced by an agent who, starting at the static Nash equilibrium ρN , adjustsbest responses to a deviation by the opponent. The agent has a tradeoff between followingincentives about payoffs today (static incentives), represented by BR′N , and dynamic incentivesconsidering effects on continuation payoffs, represented byJN−BR′NI2. The dynamic incentivesallow for additional interpretation:Note thatδP ′AB(ρN )ωN=∂ ln(1− δ + δ(PAB(ρN ) + PBA(ρN )))∂ρA;δP ′BA(ρN )ωN=∂ ln(1− δ + δ(PAB(ρN ) + PBA(ρN )))∂ρB,384.2. Repeated Cournotthus the factor multiplyinguN2uN11can be interpreted as the sensitivity of the sum of transitionprobabilities PAB(ρN ) + PBA(ρN ) with respect to policy ρ. In what follows, I write thesedynamic incentives more compactly asDA = DPADuA =δP ′AB(ρN )ωNuN2uN11; DB = DPBDuB =δP ′BA(ρN )ωNuN2uN11,so that the dynamic incentives can be split into a factor originating from the above describedsensitivity of transition probabilities DPs , multiplying the weighted effect of a perturbation tofuture payoffs DuA = DuB = Du.As noted before, as δ → 1, ω−1N (1 − δPBB) → µA(ρN ) = PBA(ρN )PAB(ρN )+PBA(ρN ) , the stationaryprobability of visiting A ∈ S when ρN is played forever. On the other side, DPA = DPB = 0 whenδ = 0. Stability of the static Nash equilibrium is impacted by this quantity in a straightforwardmanner:Proposition 3. Let u be regular and consider arbitrary transition probabilities Pss′ for a binarystate variable. Then ρN is dynamically unstable (i.e. unstable w.r.t. FSB) if and only if∣∣∣BR′N +DA +DB∣∣∣ > 1.Proof. As discussed in appendix C.1, one needs to linearize best responses at ρN to determinethe stability of that profile. We need to characterize the eigenvalues λ1,2 of JN . We have thatλ1,2 =tr(JN )2±√tr(JN )24− det(JN ),where tr(·), det(·) represent trace and determinant. Thus, λ1 = BR′N , and λ2 = BR′N +DA + DB. Regularity gives that |λ1| < 1, so that |λ2| > 1 appears as the condition in theproposition.Proposition 3 uncovers the channels through which the static Nash equilibrium can bedestabilized, and eventually through which algorithms in my class will learn to avoid this Nashequilibrium. On the one side, market conditions matter through the size of the slope of thestatic best response BR′N today and the weighted effect that an opponent’s deviation has onstage game payoffs u in the future. On the other side, fixing the market conditions, statevariables matter: DPA + DPB is the total sensitivity of transition probabilities with respect topolicy ρ. In words, this quantity represents the aggregate effect of a marginal change in policyρ on transition probabilities, which in turn control the correlation structure over states. For394.3. Two Special State Variablesalgorithms to avoid the static Nash equilibrium, only the magnitude of this sensitivity matters:For any payoff function u of bounded derivatives, there is a threshold so that once |DPA +DPB |surpasses that threshold, static Nash will not be learned. The set of state variables that canrender a static Nash equilibrium unstable is therefore quite large. This intuition then allows toseparate two factors that determine whether the RL will learn to play static Nash: propertiesof stage game payoffs u, and properties of the state variable’s distribution, governed by Pss′ .Corollary 2. Let u be regular. There exists a pair z∗1 < 0 < z∗2 so that ρN is dynamically stableif and only ifDPA +DPB ∈ (z∗1 , z∗2),wherez∗1 = −1 +BR′NDu; z∗2 =1−BR′NDu,andDPA +DPB = δP ′BA + P′AB1− δ + δ(PAB(ρN ) + PBA(ρN )) .Recall that regularity of u implies that BR′N ∈ (−1, 0). Therefore, the following forces areat work in stabilizing the equilibrium: Firstly, the more negative BR′N , the smaller is |z∗1 |, andthe easier is it for negative DPA + DPB to be below z∗1 so that Nash is unstable. This followssince BR′N is negative from the start, and so if dynamic incentives work in tandem with thestatic incentive, perturbations can accumulate easily. This force must be seen as relative toDu; even if transition probabilities are very sensitive (|DPA +DPB | is large), they only matter forbest responses if they lead to a sizeable payoff effect relative to static incentives. Analogously,z∗2 is smaller the closer BR′N is to zero, since positively sensitive transition probabilities mustsurpass the static incentive which works in the opposite direction.Note that proposition 3 and the above corollary can be generalized to Nash equilibria ofpayoff functions u unrelated to the Cournot game studied here, given twice differentiability ofu at the equilibrium.4.3 Two Special State VariablesSo far, state variable S has been allowed to exist without any connection to the underlyingstage game u other than through its correlation to aggregate quantities Q. In what follows, I404.3. Two Special State Variablesintroduce two state variables that correlate to Q through the channel of price outcome Y , andlead to two extreme results. In the first case, static Nash will be dynamically stable for anystate variable falling in that general family; in the second case, static Nash can be dynamicallyunstable, and the existence of collusive equilibria that are attracting is possible.First, consider the state variable where st = Yt−1, the past period’s price realization.Definition 8. A public 1R-policy can be defined as policy ρ : {PL, PH} 7→ X, so that statesare price realizations representing last period’s observed price. This can equivalently be definedas having state realizations Y with transition function T (s, P ) ∈ Y such that T (s, P ) = P forall s ∈ Y, and all price observations P ∈ Y.For this family of policies, one can show the following:Corollary 3. Let ρN be the 1R-policy that plays stage game Nash quantity qN in every state.Then ρN is dynamically stable if and only if qN is statically stable.This result follows from corollary 2, since under 1R-policies at ρN , DPA +DPB = 0 follows.24Note that under 1R-policies, PAB = 1− PBA = P[PH ]. Thus, P ′AB(ρN ) + P ′BA(ρN )=0. In fact,for any policy that plays the same quantity in all states, when the state is past period’s price itmust be that DPA +DPB = 0. In general, this comes from the fact that, for every given currentstate, conditional distributions over future states are the same. I call this quality of a statevariable ‘state-independent transitions’ (SIT).Transitions of a state variable can readily be depicted in a transition diagram. Figure4.1 depicts the underlying transition diagram when st = Yt−1, with state A corresponding toYt−1 = PL, and state B corresponding to Yt−1 = PH .24The result holds more generally in the case of finitely many prices (more than 2), see proposition 8 inappendix C.2.414.3. Two Special State VariablesFigure 4.1: Transition Diagram: SITIn contrast, figure 4.2 shows a state variable under a more involved transition profile, whichI denote direction-switching (DS):Figure 4.2: Transition Diagram: DSA realized price PL represents a switch-signal, while realizing PH represents a remain-signal.Thus, states evolve from s to s′ according to transition probability functionPAB(Q) = P[PL | Q] = PBA(Q).More generally, one can define policies following state variables with transition probabilitieshaving the above property:424.3. Two Special State VariablesDefinition 9. Say a binary state policy is a DS-policy (’DS’ for direction-switching) if theunderlying state transitions are irreducible and PAB(Q) = PBA(Q) holds for all Q. Denote theDS- state space as S∗.In words, the probability of reaching any state s conditional on being in A is complementaryto the probability of reaching s conditional on being in B. Notice that this affects dynamicincentives in an interesting manner: for a given quantity Q, marginal deviations affect expectedcontinuations in the opposite direction, depending on the current state. This fact introducesan essential difference in how states A,B are interpreted, even when ρA = ρB is played. Noticethat in this case, DPA = DPB , so thatDA +DB = 2δP ′AB(ρA)ωNDu,with P ′AB(ρA) = h′(2ρA). Let ζN be the DS-policy playing qN in all states (call it ζN , todifferentiate from ρN under 1R policies). It follows from corollary 2 that there should existconditional price distributions h(Q) so that ζN will be dynamically unstable and thereforenot learned by our RL. However, the issue is not immediate, since h(Q) plays a role both inconstruction of u and transition probabilities Pss′(Q). In the following, I show that there is a setof regular payoff functions such that ζN is indeed statically stable, but dynamically unstable.Moreover, this family of regular payoff functions will also allow for the existence of collusiveequilibria.25For the sake of analytical tractability, I introduce a global shape restriction on h so thatthe resulting payoffs are regular, but together with S∗, will allow for a collusive equilibrium toexist. To this end, impose for h (and therefore Y (Q)) to take a S-shaped form:Definition 10. Fix M > 0. Let Go be the space of monotone increasing, twice differentiablefunctions h : [0,M ] 7→ [0, 1], s.t. h′′ = minQ∈[0,M ] h′′(Q) ∈ (−∞, 0). Define a space of S-shapedfunctions with lower bounded second derivative asG ={h ∈ Go s.t. ∃τ ∈ (0, M2) : h′′(0) > −h′′, h′′(2τ) = 0h′′(Q) > 0 ∀Q ∈ [0, 2τ), h′′(Q) < 0∀Q ∈ (2τ,M ],−h′′ < h′(2τ)τ}.25This result holds under more general state-and price spaces which are non-binary, as established in appendixC.2 .434.4. Stable CollusionProposition 4. There exists h ∈ G, PH > PL ≥ 0 and a convex c(q) such that resulting u isregular, ζN is dynamically unstable and there exists a symmetric equilibrium σ with 0 < σA <qN < σB.The intuition for how S∗ can support a simple collusive scheme as σ can be found by thinkingthrough incentives to deviate at the equilibrium: in state A, quantities lower than qN are tobe played. Statically, by the strategic-substitutes nature of the Cournot game, one wants todeviate upwards. However, increasing quantities in state A increases the likelihood of realizingPL, which in turn would lead the system to move to state B, which is undesirable. In state B,punishingly high quantities are to be played. Here, a player statically would want to deviateto lower quantities. However, that would increase the likelihood of realizing PH , which wouldlead to a repetition of state B in the following period; again an undesirable outcome. Thus,collusion is reinforced.Notice that by construction, S∗ is symmetric in the sense that for both states A,B, observingPH leads to staying in the given state, whereas observing PL implies leaving the state. It isthen no surprise that given that payoffs are also symmetric, proposition 4 also implies thatthere exists another symmetric collusive equilibrium σ′, satisfying σ′A = σB, σ′B = σA.We see from the above and the following subsection that SIT-state variables and DS-statevariables lead to starkly different outcomes. In the former, static Nash will always be learnedwith positive probability while in the latter, static Nash may never be learned, while collusioncan be learned with positive probability. More intuitions about the differences of FSB dynamicsunder these two state variables can be found in appendix C.1. Furthermore, payoff functionsresulting in collusive equilibria under DS-state can be such that the static Nash equilibrium isthe unique symmetric equilibrium under 1R-state variables:Corollary 4. Suppose h ∈ G, PH > PL ≥ 0 and c(q) are such that the conditions of proposition4 hold. Then ρN is the unique symmetric equilibrium under 1R-policies.4.4 Stable CollusionThe stability of the collusive equilibrium is determined by local conditions at the equilibrium.The dynamic instability of the Nash equilibrium is sufficient for the existence of collusion, butneither necessary for the existence, nor is it sufficient for stability of the collusive equilibrium.However, stability depends on quantities related to growth rates of transition probabilities andthe stage game in manners analogous to the stability analysis of the static Nash equilibrium.To see this, let Π(q1, q2) = Y (Q)−c′(q1) be the marginal profit as computed by a price-taker.444.4. Stable CollusionNotice that by construction of the Cournot-payoff function, u1(q1, q2) − u2(q1, q2) = Π(q1, q2),which is true for all q and therefore also true for Π′(q1, q2) ≡ ∂Π(q1,q2)∂q1 . This definition allowsone to write, for any interior equilibrium profile σ as constructed in proposition 4,∂ρ∗1A∂ρ2A= −1 + ϕ−1A[Π′A − ω−1δP ′ABΠA],∂ρ∗1A∂ρ2B= ϕ−1A ω−1δP ′ABΠB,∂ρ∗1B∂ρ2A= ϕ−1B ω−1δP ′BAΠA,∂ρ∗1B∂ρ2B= −1 + ϕ−1B[Π′B − ω−1δP ′BAΠB],(4.4)where as before, s-subscripts denote evaluation at qs, andϕA = ω−1δP ′′AB(uB − uA) + uA11;ϕB = ω−1δP ′′BB(uB − uA) + uB11,Some tedious algebra then allows re-writing determinant and trace of J(σ, σ) using (4.4)under the assumption that Π′(q1, q2) < 0 for all qi ∈ X. First, define for s, s′ ∈ S:Rs =δP ′ss′ωΠsΠ′s,which can be interpreted as a ratio of elasticities of ω versus Πs with respect to qs. To savenotation, write J∗ = J(σ, σ). Then:tr(J∗)= −2 + Π′AϕA[1−RA]+Π′BϕB[1−RB];det(J∗)=[1− Π′AϕAΠ′BϕB]− Π′AϕA[1−RA][1− Π′BϕB]− Π′BϕB[1−RB][1− Π′AϕA].(4.5)Notice that for the stage game as constructed in Proposition 4, ϕs < us11 holds, and thereforeΠ′sϕs∈ (0, 1) can be guaranteed as long as us12 ≤ 0, since Π′s = us11 − us12. Sign and magnitudeof Rs depend on local conditions of both transition probabilities and the stage game quantityΠ(q1, q2). It is clear from (4.5) that both trace and determinant depend crucially on the454.4. Stable Collusionquantities Rs. Indeed, if RA, RB are not too negative, stability of σ follows:Lemma 3. Consider an interior, symmetric equilibrium under a binary state variable, σ =(qA, qB) with qA < qB as constructed in Proposition 4. SupposeΠ′sϕs∈ (0, 1) for both s. Then if0 ≤ min{RA, RB}, and RA +RB ≤ 1,σ is asymptotically stable.Proof. Firstly, as shown in appendix C.1, stability of σ is equivalent to∣∣tr(J∗)∣∣− det(J∗) < 1. (4.6)Then, note from (4.5) that by the condition of the Proposition,tr(J∗)< −RA −RBand so for RA, RB not too negative, we must have that tr(J∗) ≤ 0. Next note that we canwritedet(J∗)= −tr(J∗)− 1 + Π′AϕAΠ′BϕB[1−RA −RB].Thus, for RA, RB bigger than 0, the trace drops out in the condition in (4.6). The last equationthen determines stability through the term[1−RA −RB].Relationship to the Best EquilibriumOne might wonder about the relationship between a binary-state collusive equilibrium as con-structed in proposition 4 and the best possible payoff a player can achieve in a repeated gameof imperfect public monitoring. Using the insights of Abreu et al. [1990] (henceforth APS),a useful link can be made between best equilibria and binary-state policies, as defined in theprevious discussions.First, let Γ = ⟨u1, u2⟩ be the stage game as defined in the beginning of the chapter. Thenone can define Γ∞(δ) as the infinite repetition of Γ where players discount expected long termpayoffs by δ ∈ (0, 1). For any 0 < t, define bt = {Ys}0<s<t to be a public history of the game,with Bt = Yt the set of possible public histories up to time t. Then let bit = {qsi }0<s<t be theprivate memory of a player’s own actions, and define Bit = Xt as the set of those at period t.Now, a strategy of player i at period t can be written as map σit : Bt ×Bit 7→ X. A strategy is464.4. Stable Collusionthen a sequence σi = {σit}t>0, with the set of such sequences denoted Σ. In keeping with APS,we can define strongly symmetric sequential equilibria (SSE) of Γ∞ as profiles σ = {σ1t , σ2t )}t>0with σ1t (bt, b1t ) = σ2t (bt, b2t ) whenever b1t = b2t , that are individually unimprovable for each player,with respect to their expected future discounted payoffs:U i(σ) = (1− δ)E∑t>0δtui(σt) ≥ U i(σ′, σ9i) = (1− δ)E∑t>0δtui(σ′t, σ9it ),for any σ′ ∈ Σ. APS provide a result stating that the best SE can be supported by a bang-bangsolution, under their setting. Their setting differs from the one of this chapter on two counts:APS requires uncountable signals under an absolutely continuous distribution, and finite (butarbitrarily many) actions.By allowing for public randomization in the definition of the strategies in Σ, the uncount-able signal requirement can be satisfied. An approximation argument can then be made toapproximate the best SSE of Γ∞ by a sequence of best SSEs of repeated games with a finite,increasing number of actions.Define the restricted action set XK = {x1, ..., xK} ⊂ X such that max0<k,k′≤K{|xk−xk′ |} ≤1K , and such that qN ∈ XK for all K > 0. Let the restricted game Γ∞K be the repeated gamewhere players are constrained to choose actions from Xk. Let E,EK be the sets of SSEs ofΓ∞,Γ∞K respectively. The restriction that qN ∈ XK ensures that EK is nonempty for all K > 0.Define V = {U(σ) : σ ∈ E}. Let VK = {U(σK) : σK ∈ EK}. For Γ∞K , allowing for publicrandomization means that APS’ results can be applied, which specifically gives us that VK iscompact and can be implemented by a bang-bang strategy that only ever plays two actions inXK .Let σ¯K ∈ EK be such that U(σ¯K) = V K = maxVK . By APS, σ¯K can always be chosen tobe a bang-bang profile. Note that any such σ¯K ∈ EK is a ε-equilibrium of Γ∞:Proposition 5. For any ε > 0 there exists Kε > 0 such that for all K ≥ Kε,(i) σ¯K ∈ EK is an ε-equilibrium of Γ∞,(ii) σ¯K ∈ EK satisfies U(σ¯K) = V K ,(iii) There exists a binary state Variable SK = {A,B} with transition probability functionsPKss′(q1, q2) so that policies ρiK : SK 7→ XK constitute an ε-equilibrium of W i(ρ, s) asdefined in (4.1).474.5. Numerical Example and SimulationsProposition 5 tells us that at the very least there exist binary state variables such that, whenalgorithms condition their policies on those (as set up in the beginning of this chapter), and areconstraint to choose quantities in finite set XK , the best equilibrium of the repeated game isa candidate for possible long run behaviors of the algorithms. Whether it can be learned withpositive probability or not would then depend on its stability properties. Of course, the caveathere is that a continuum of actions X is necessary for the stability approach applied in thispaper to go through (differentiability in actions being the necessary requirement). It remainsan open question whether the best SSE payoff supV of Γ∞ can be approximated by a sequenceof V K , which would go beyond the scope of this chapter. If such an approximation result wereto hold, one can argue that indeed also for the unrestricted choice case (actions in X), thereexist binary state variables that support the best payoff and therefore may be learned by theRL agents defined here.To provide a visualization of the results discussed so far, the following section shows sim-ulation results which can be interpreted using the theory developed in this and the previouschapter.4.5 Numerical Example and SimulationsI construct a piecewise-linear version of h(Q), prices PL, PH and a convex cost function c(q)for which there exists a unique stage game Nash equilibrium qN that is statically stable, butdynamically unstable, and there exists a stable symmetric collusive equilibrium. The followingis an overview of a numerical example for which these properties are satisfied.Fix a discount factor δ = 0.98. All numbers given in the example are rounded to twodecimal points. Given domain X = [0,M ], derivative parameters 0 < h′A, h′B < h′N , and cutoffsx = [x1, x2, x3, x4] > 0, I define the set of piecewise linear functions Gˆ so that h ∈ Gˆ if and onlyif one can writeh(Q) =h(Q) Q ∈ [0, x1)h(x1) + h′A(Q− x1) Q ∈ [x1, x2)h(x2) + h′N (Q− x2) Q ∈ [x2, x3)h(x3) + h′B(Q− x3) Q ∈ [x3, x4)h(Q) Q ∈ [x4,M ],where h ∈ [0, 1) is strictly increasing, with h′(0) = 0, h′(x1) = h′A, h′(x4) = h′B and h′′(Q) > 0for all Q ∈ [0, x1], and h ∈ [0, 1) is strictly increasing, with h′(M) = 0, h′′(x4) = 0 and484.5. Numerical Example and Simulationsh′′(Q) < 0 for all Q ∈ (x4,M). Elements of Gˆ are therefore piecewise-linear versions of elementsof G. The idea is that this construction facilitates a numerical example, while still allowing forthe existence of a collusive equilibrium using similar intuition as in proposition 4. Figure 4.3plots the piecewise-linear function h(·) used in the simulations throughout.Figure 4.3: Location of cutoffs xi for piecewise linear h(Q).Given h(Q), prices, and a cost function for which the properties stated in the beginning ofthis subsection are satisfied, one can plot the stage game best response and its inverse to verifythe uniqueness of the static Nash equilibrium:494.5. Numerical Example and SimulationsFigure 4.4: Best Response IntersectionFigure 4.4 shows the unique intersection of static best-response functions in the numericalexample, where qN = 1.58. Best responses jump upwards at a value larger than qN . This isdue to the non-concavity introduced by the requirement h′B < h′N , which enforces the S-shapeof the piecewise-linear h(Q) function. Best responses jump to zero at a large quantity, wherethe interior local maximum has a negative value.One can verify numerically that under this example,−uN12uN11= −0.5; DA +DB = 2.28,which implies from proposition 3 that the Nash equilibirum is statically stable but indeeddynamically unstable. At the same time, this numerical example supports a pair of symmetric,collusive equilibria σ, σ′ with σA = 1.52 < σB = 1.94 (rounded to two decimal points) andthe quantities flipped for σ′. (see the discussion after proposition 4. As laid out in detail in504.5. Numerical Example and Simulationsappendix C.1, the stability of this equilibrium is verified by checking the eigenvalues of thelinearized system FS∗B at the equilibrium. In this case, the largest eigenvalue is −0.5, implyingthat all eigenvalues are strictly negative, implying the stability of the collusive equilibrium.I finish by providing a simulation study to visualize these results. This simulation studyshould be seen as a device to get intuitions about the system dynamics after many iterationsof the algorithm have passed. The characterization of long-run behavior given in Section 3.4 isused here: instead of simulating the estimation part of Qt of the algorithm given in Definition3, I take assumption 8 seriously, set bias term gi = 0 for all i, and simulate iteration (3.5) inthe following way:For i ∈ {1, 2} and all s,ρit+1(s) ∈ ρit(s) + αt[argmaxq′∈XQi∗(s, q′, ρ9it )− ρit(s) +M it+1], (4.7)where αt = t−0.6 satisfies the Robbins-Monro assumption 9, and M it+1 ∼ N(0, .25) is an i.i.dmean-zero Normal noise variable with variance 0.25. Notice that (4.7) replaces Qt given in(3.5) by its estimation target Q∗. Thus, this iteration represents a noisy discretization of FS∗Brather than a simulation of a feasible model-free algorithm. As the results in Section 3.4 tellus, for algorithms in the class studied in this chapter this simulation will give us an equivalentrepresentation of long-run trajectories of ρt to a full simulation of (3.5) when t is large. Runninga more in-depth simulation experiment including the estimation part of Qt will be an insightfulobject of further investigation.Note that the long-run characterizations given in Section 3.4 are local in nature: if theiteration ρt at some point t enters a basin of attraction for a given stable equilibrium ρ∗, thenthe iteration will converge to that equilibrium with large probability.26 One can not hope hereto compute the exact basins of attraction for each equilibrium, as such an exercise would gobeyond the scope of this chapter. However, any basin of attraction for a stable equilibriummust at the very least contain a small neighborhood of that equilibrium. I will use such a smallneighborhood to initialize our simulations in this experiment.In each simulation exercise, I run 96 separate simulations, and each for 25, 000 periods.Thus, simulations are potentially stopped before they’ve noticeably converged to a point. Theidea is to take the following figures as relative to each other: each exercise was done for the same26In fact, approximations of this probability can be made given the neighborhood of ρ∗ the iteration findsitself in, see for example Thoppe and Borkar [2019]. This leads to an interesting avenue of future research,which will allow a study of the distribution of outcomes possible given a set of competing algorithms in theclass developed in this chapter. Once a distribution over outcomes can be characterized, modeling a strategicinteraction involving choosing algorithms will become feasible.514.5. Numerical Example and Simulationsnumber of iterations, but the results differ starkly across exercises. As will be seen, dependingon the state variables of the algorithms involved, iterations move closer to the equilibrium theneighborhood of which they started at, or move away from it, confirming the theory developedin this chapter.First, I consider the result given in corollary 3. Since in this example, the Nash equilibriumis statically stable, its repetition under 1R-policies ρN is also stable. Thus, one would expectthat once algorithms using 1R-state variables come close to the Nash equilibrium, they shouldstay close to it forever, and in the long run converge to it. This is what is evidenced by Figure4.5. Since the state space is binary, the two algorithms’ policies can be represented as pointsin the X2-plane. I now plot simulation outcomes in this plane, so that each simulation run isrepresented by two points in the plane spanned by ρ(A), ρ(B).Figure 4.5: 1R-policiesThe final policy profiles of 96 simulation runs of 25, 000 iterations each are shown in Figure4.5. Simulations are started in a circular neighborhood of ρN , with a radius of .025∥ρN∥. One524.5. Numerical Example and Simulationsred and one orange dot represent a policy profile at the end of a simulation run. σ, σ′ signifythe collusive equilibria, which in this case have not been approached. All simulations remainedin the neighborhood, as should be expected given the stability of ρN .Now contrast this result with an analogous study given DS-policies for a state variableevolving as shown in Figure 4.6. Even though the neighborhood of starting values used in thisscenario is the same as under 1R-policies, the picture is starkly different:Recall that I denote the repetition of qN under S∗ as ζN . Since qN is dynamically unstableunder S∗-policies, no matter how close the starting values of the iteration are, the iterationmust be pushed away from ζN as shown in the proof of proposition 2. However, in the caseof this example, it is not only true that the iteration is pushed away, but also that it is pulledtowards the collusive equilibrium σ. This indicates that the basin of attraction for the collusiveequilibrium in this example is not confined to a small neighborhood of the equilibrium but infact quite large. This scenario also underlines the weight of consideration that should be given tothe analysis of policy spaces given two competing algorithms. Even if one forced algorithms toinitialize very close to a Cournot equilibrium, they can, given the right state variable, approacha collusive equilibrium instead. As this example supports a pair of collusive equilibria, theresulting figure shows how roughly half the simulation runs end up in the North-West of theplane, while the other half approached the South-East.534.5. Numerical Example and SimulationsFigure 4.6: S∗-policiesThe final policy profiles of 96 simulation runs of 25, 000 iterations each are shown in Figure4.6. Simulations are started in a circular neighborhood of ζN , with a radius of .025∥ζN∥. Onered and one orange dot represent a policy profile at the end of a simulation run. All simulationsleft the neighborhood of starting values, with most conglomerating at one of the two collusiveequilibria σ, σ′. To see that outcomes indeed approached σ, σ′, two dots connected by a linerepresent a single simulation outcome. The black circles represent neighborhoods of σ, σ′ withradius .25∥σ∥.With a similar exercise, it can be seen that the collusive equilibria indeed attract the al-gorithm iterations if starting values are analogously defined as for the two above discussedsimulations:Figure 4.7 shows how after starting in a neighborhood of the collusive equilibrium σ, iter-ations stayed there for the course of the simulation. An analogous picture can be generatedwhen initializing in a neighborhood of σ′.544.5. Numerical Example and SimulationsFigure 4.7: S∗-policies, initialized locallyThe final policy profiles of 96 simulation runs of 25, 000 iterations each are shown in Figure4.7. One red and one orange dot represent a policy profile at the end of a simulation run.Simulations are started in a circular neighborhood of σ, with a radius of .025∥σ∥. All simulationsremained in the neighborhood, as should be expected given the stability of σ.Finally, one might wonder about the global properties of the dynamical system generatedfrom this numerical example. It happens to be the case that, when simulations are initializedat a radius of .95qN , i.e. from values approaching the boundary of the action set X, theabove results are unaffected: under 1R-policies, all simulation runs converge to the static Nashequilibrium ρN , while under S∗-policies, none of the simulation runs converge to ρN ; all of themconglomerating at either σ or σ′.554.5. Numerical Example and SimulationsFigure 4.8: 1R-policies, initialized globallyThe final policy profiles of 96 simulation runs of 25, 000 iterations each are shown in Figure4.8. Simulations are started in a circular neighborhood of ρN , with a radius of .95∥ρN∥. Onered and one orange dot represent a policy profile at the end of a simulation run. σ, σ′ signifythe collusive equilibria, which in this case have not been approached. All simulation runsconglomerated at ρN .564.6. Concluding RemarksFigure 4.9: S∗-policies, initialized globallyThe final policy profiles of 96 simulation runs of 25, 000 iterations each are shown in Figure4.9. Simulations are started in a circular neighborhood of ζN , with a radius of .95∥ζN∥. Onered and one orange dot represent a policy profile at the end of a simulation run. All simu-lations conglomerated at one of the two collusive equilibria σ, σ′. The black circles representneighborhoods of σ, σ′ with radius .25∥σ∥.4.6 Concluding RemarksThis chapter takes the characterization of long run behaviors established in chapter 3, andapplies it in a study of collusion in repeated games. This exemplifies the usefulness of chapter3’s framework: it allows researchers to how the long-run learning behavior of RL is affected bydetails of the game and algorithms.Since the algorithms in the class considered require a fixed state variable to condition actions574.6. Concluding Remarkson, this project generates an interesting comparative statics exercise regarding state variables.It can be seen as a first step in categorizing state distributions with regard to the extent withwhich they allow the emergence of cooperative behavior. I introduce the categories 1-recall-policies and direction-switching (DS) states as a first step in this endeavor. I also introducethe terms static and dynamic stability, in order to analyze the ability of RL to learn repeatedgame equilibria in the context of the state variable used by the algorithms. This categorizationof state variables is an interesting area of future research.My results potentially allow empirical researchers and industry regulators to understandwhat conditions of the market and features of algorithms lead to a greater likelihood of collusivebehavior when competing firms use learning algorithms. My characterization implies that onceone knows the state variables of the algorithms, and the payoff environment of the game, onecan determine whether any MPE in the policy space will be learned with positive probabilityby checking its stability property.Discussion of related LiteratureThere is a recent theoretical literature on stylized models of algorithmic competition. Lambaand Zhuk [2022] study how algorithms may learn to collude. They look at a stylized modelof algorithmic competition, in which an algorithm is represented by a policy mapping fromopponent actions to actions, which can be revised less frequently than actions are taken. Theyshow that no equilibrium of that game is fully competitive. Salcedo [2015] goes along a sim-ilar direction, with an algorithm being an automaton strategy that can only be revised lessfrequently than actions can be taken.Another paper of stylized algorithmic competition is Brown and MacKay [2021]. Theyfocus on the frequency with which algorithms can update prices, and let algorithms of differ-ent adjustment speeds compete against each other. When frequency abilities are asymmetricamong algorithms, equilibrium outcomes can be collusive. Interestingly, when firms can choosealgorithms (i.e. their adjustment frequency), the equilibrium features asymmetric frequencies.The works mentioned above focus on different aspects of frequency of adjustment as astylized feature of algorithmic updates. This chapter shows a channel that has not been exploredmuch in this literature: the role of state variables in the ability of algorithms to learn collusion.This could be an interesting new starting point for a study of stylized algorithms. Moreover,the works above abstract away from issues of learning and estimation, which is in contrastto this chapter. An interesting aspect of learning present here is the importance of stabilityof equilibria in determining what can be learned. Stability of equilibria is tightly connectedto dynamic reactions to imprecisions and mistakes (perturbations), which are present when584.6. Concluding Remarkslearning and estimation are part of algorithmic updates.Johnson et al. [2020] look into platform design under algorithmic sellers. They investigatediffering policies implemented by a platform designer wishing to promote competition or raisetheir own profits. They include a simulation study of Q-learning algorithms under differentpolicy designs; clearly, results in this chapter can be applied to study related RL algorithmsunder any given platform policy. Once a more tight characterization of the distribution overoutcomes supported by a profile of algorithms is in place, one can go a step further and attemptto find the optimal platform policy for any given algorithm profile in my class.In connection to the theory of learning in games, this chapter speaks to the learning ofrepeated game strategies by making an important connection: I shed light on the ability ofbehavioral players to learn to play equilibria of a repeated game other than the static equilibriumof the underlying stage game. Since the players I consider learn policies on a fixed policyspace, one may recast their payoffs as expected discounted payoffs based on stationary policyprofiles that have to live in that policy space. See the definition of best response under a givenstate variable (3.4). Taking that view, one can say that algorithms in my class learn to playNash equilibria of a repeated stage game with multidimensional continuous actions (which areprecisely the policies in the policy space). In this sense, my analysis ties neatly into classicalanalysis of the theory of learning in games with minimal information requirements.59Chapter 5ConclusionThis dissertation is concerned with the asymptotic analysis of reinforcement learning algorithmsin the multi-agent setting.The insights of chapter 2 have important implications for the design and analysis of rein-forcement learners in multi-agent settings generally. Moreover, the results can be re-cast in thesetting of single-agent learning under non-stationarity. In this interpretation, I show how analgorithm can be designed that learns an optimal policy when sufficient information about theevolution of the non-stationarity of the environment is known.An interesting avenue of further research will extend this chapter 2’s asymptotic resultsto a finite-time concentration inequality. This will allow evaluating, at any given number ofinteractions, how closely an agent’s best response estimator will be concentrated around thecorrect best response.Chapter 3 provides a characterization of long-run behaviors that can be learned by a fam-ily of competing algorithms. This characterization serves as a methodology that can allowresearches to pick a given interaction of interest, e.g. an auction, a stock market, or multilat-eral platform, then pick a class of algorithms within the family allowed, and evaluate long-runoutcomes in the chosen setting.Main results about long run policies in chapter 3 are restricted to distinguish between“positive probability” and “zero probability”. An important extension of this line of researchwill aim to provide distributional results, allowing to compare the likelihood of different possiblelong run policy profiles.Chapter 4 studies collusion in a repeated Cournot game played by algorithms. I provideconditions for a simple binary-action collusive scheme to be learned, and show an approximativerelationship between this equilibrium and the best equilibrium in the sense of Abreu et al. [1986].What this study does not address is the following issue: the best equilibrium payoff may beachieved by multiple equilibria, one of them being the binary scheme. Thus, the answer to thequestion of whether the best payoff can be learned is complicated by the issue of implementation.An important area of further study will be an alternative model of oligopolistic competitionunder which Abreu et al. [1990]’s necessary conditions hold (theorem 7). In that case, the best60Chapter 5. Conclusionequilibrium can only be achieved by a binary scheme.The aforementioned issue of only being able to distinguish between positive and zero proba-bility in the characterization of chapter 3 constrains interpretations of results in chapter 4. Onecan argue that state variables are a strategic choice. A distributional result as mentioned beforewill allow for the study of a meta-game to the interaction considered in chapters 3 and 4: inthis meta-game, firms choose algorithms, state variables, and then the interaction commences.61BibliographyDilip Abreu, David Pearce, and Ennio Stacchetti. Optimal cartel equilibria with imperfectmonitoring. Journal of Economic Theory, 39(1):251–269, 1986.Dilip Abreu, David Pearce, and Ennio Stacchetti. Toward a theory of discounted repeatedgames with imperfect monitoring. Econometrica: Journal of the Econometric Society, pages1041–1063, 1990.Stephanie Assad, Robert Clark, Daniel Ershov, and Lei Xu. Algorithmic pricing and competi-tion: Empirical evidence from the german retail gasoline market. 2020.Martino Banchio and Giacomo Mantegazza. Games of artificial intelligence: A continuous-timeapproach. arXiv preprint arXiv:2202.05946, 2022.M Bena¨ım. Dynamics of stochastic approximation, le seminaire de probabilite’, springer lecturenotes in mathematics. 1999.Michel Bena¨ım and Mathieu Faure. Stochastic approximation, cooperative dynamics and su-permodular games. The Annals of Applied Probability, 22(5):2133–2164, 2012.Michel Bena¨ım, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differentialinclusions. SIAM Journal on Control and Optimization, 44(1):328–348, 2005.Michel Bena¨ım, Josef Hofbauer, and Sylvain Sorin. Perturbations of set-valued dynamicalsystems, with applications to game theory. Dynamic Games and Applications, 2(2):195–205,2012.Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48.Springer, 2009.George W Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374, 1951.62BibliographyZach Y Brown and Alexander MacKay. Competition in pricing algorithms. Technical report,National Bureau of Economic Research, 2021.Lucian Busoniu, Robert Babuska, Bart De Schutter, and Damien Ernst. Reinforcement learningand dynamic programming using function approximators. CRC press, 2017.Emilio Calvano, Giacomo Calzolari, Vincenzo Denicolo, and Sergio Pastorello. Artificial in-telligence, algorithmic pricing, and collusion. American Economic Review, 110(10):3267–97,2020.Emilio Calvano, Giacomo Calzolari, Vincenzo Denicolo´, and Sergio Pastorello. Algorithmiccollusion with imperfect monitoring. International journal of industrial organization, 79:102712, 2021.Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism. In InternationalConference on Machine Learning, pages 1843–1854. PMLR, 2020.Carmen Chicone. Ordinary differential equations with applications, volume 34. Springer Science& Business Media, 2006.Debaprasad Dutta and Simant R Upreti. A survey and comparative evaluation of actor-criticmethods in process control. The Canadian Journal of Chemical Engineering, 2022.Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcementlearning. Journal of Machine Learning Research, 6:503–556, 2005.Mathieu Faure and Gregory Roth. Stochastic approximations of set-valued dynamical systems:Convergence with positive probability to an attractor. Mathematics of Operations Research,35(3):624–640, 2010.Aleksei Fedorovich Filipov. Differential equations with discontinuous right-hand side. In Amer.Math. Soc, pages 191–231, 1988.Vincent Franc¸ois-Lavet, Peter Henderson, Riashat Islam, Marc G Bellemare, Joelle Pineau,et al. An introduction to deep reinforcement learning. Foundations and Trends® in MachineLearning, 11(3-4):219–354, 2018.Ari Freedman. Convergence theorem for finite markov chains. Proc. REU, 2017.63BibliographyDrew Fudenberg and David M Kreps. Learning mixed equilibria. Games and economic behavior,5(3):320–367, 1993.Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation errorin actor-critic methods. In Jennifer Dy and Andreas Krause, editors, Proceedings of the35th International Conference on Machine Learning, volume 80 of Proceedings of MachineLearning Research, pages 1587–1596. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/fujimoto18a.html.Ivo Grondman, Lucian Busoniu, Gabriel AD Lopes, and Robert Babuska. A survey of actor-critic reinforcement learning: Standard and natural policy gradients. IEEE Transactions onSystems, Man, and Cybernetics, Part C (Applications and Reviews), 42(6):1291–1307, 2012.Frank H Hahn. The stability of the cournot oligopoly solution. The Review of EconomicStudies, 29(4):329–331, 1962.Bruce E Hansen. Econometrics. university of wisconsin, 2010.Pablo Hernandez-Leal, Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. A sur-vey of learning in multiagent environments: Dealing with non-stationarity. arXiv preprintarXiv:1707.09183, 2017.Josef Hofbauer and William H Sandholm. On the global convergence of stochastic fictitiousplay. Econometrica, 70(6):2265–2294, 2002.Justin Johnson, Andrew Rhodes, and Matthijs R Wildenbeest. Platform design when sellersuse pricing algorithms. Available at SSRN 3753903, 2020.Khimya Khetarpal, Matthew Riemer, Irina Rish, and Doina Precup. Towards continual rein-forcement learning: A review and perspectives. Journal of Artificial Intelligence Research,75:1401–1476, 2022.Timo Klein. Autonomous algorithmic collusion: Q-learning under sequential pricing. TheRAND Journal of Economics, 52(3):538–558, 2021.Rohit Lamba and Sergey Zhuk. Pricing with algorithms. arXiv preprint arXiv:2205.04661,2022.David S Leslie and Edmund J Collins. Generalised weakened fictitious play. Games andEconomic Behavior, 56(2):285–298, 2006.64BibliographyDavid S Leslie, Steven Perkins, and Zibo Xu. Best-response dynamics in zero-sum stochasticgames. Journal of Economic Theory, 189:105095, 2020.Eric Mazumdar, Lillian J Ratliff, and S Shankar Sastry. On gradient-based learning in contin-uous games. SIAM Journal on Mathematics of Data Science, 2(1):103–131, 2020.Paul Milgrom and John Roberts. Rationalizability, learning, and equilibrium in games withstrategic complementarities. Econometrica: Journal of the Econometric Society, pages 1255–1277, 1990.Paul Milgrom and John Roberts. Adaptive and sophisticated learning in normal form games.Games and economic Behavior, 3(1):82–100, 1991.Whitney K Newey and Daniel McFadden. Large sample estimation and hypothesis testing.Handbook of econometrics, 4:2111–2245, 1994.J Palis Jr, W de Melo, et al. Geometric theory of dynamical systems. 1982.Christos Papadimitriou and Georgios Piliouras. From nash equilibria to chain recurrent sets:An algorithmic solution concept for game theory. Entropy, 20(10):782, 2018.Steven Perkins and David S Leslie. Asynchronous stochastic approximation with differentialinclusions. Stochastic Systems, 2(2):409–446, 2013.Julien Perolat, Bilal Piot, and Olivier Pietquin. Actor-critic fictitious play in simultaneousmove multistage games. In International Conference on Artificial Intelligence and Statistics,pages 919–928. PMLR, 2018.Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y Chen,Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noisefor exploration. arXiv preprint arXiv:1706.01905, 2017.Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming.John Wiley & Sons, 2014.Arunselvan Ramaswamy and Eyke Hullermeier. Deep q-learning: Theoretical insights from anasymptotic analysis. IEEE Transactions on Artificial Intelligence, 2021.Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals ofmathematical statistics, pages 400–407, 1951.65Bruno Salcedo. Pricing algorithms and tacit collusion. Manuscript, Pennsylvania StateUniversity, 2015.Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar. Decen-tralized q-learning in zero-sum markov games. Advances in Neural Information ProcessingSystems, 34, 2021.Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press,2018.Gugan Thoppe and Vivek Borkar. A concentration bound for stochastic approximation viaalekseev’s formula. Stochastic Systems, 9(1):1–26, 2019.Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):279–292, 1992.Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. 1989.Tianpei Yang, Hongyao Tang, Chenjia Bai, Jinyi Liu, Jianye Hao, Zhaopeng Meng, Peng Liu,and Zhen Wang. Exploration in deep reinforcement learning: a comprehensive survey. arXivpreprint arXiv:2109.06668, 2021.Kaiqing Zhang, Zhuoran Yang, and Tamer Bas¸ar. Multi-agent reinforcement learning: A selec-tive overview of theories and algorithms. Handbook of Reinforcement Learning and Control,pages 321–384, 2021.Huozhi Zhou, Jinglin Chen, Lav R Varshney, and Ashish Jagmohan. Nonstationary reinforce-ment learning with linear function approximation. arXiv preprint arXiv:2010.04244, 2020.66Appendix AAppendix to Chapter 2A.1 Proof of Lemma 1We can write∥L∗t (θ, ρt)−∑s∈Sµρt(s)ϕ(ρt, s, θ)∥≤∑s∈S∥∥∥Λt(s, ρt, sW t)− µρt(s)∥∥∥∥∥∥∥∥1Kt∑k∈Wt E[ℓ(Zk, θ)s | ρt]Λt(s, ρt, sW t)∥∥∥∥∥+∑s∈Sµρt(s)∥∥∥∥∥1Kt∑k∈Wt E[ℓ(Zk, θ)s | ρt]Λt(s, ρt, sW t)− ϕ(ρt, s, θ)∥∥∥∥∥≤∑s∈SR1,s,ρt,t∥∥∥∥∥1Kt∑k∈Wt E[ℓ(Zk, θ)s | ρt]Λt(s, ρt, sW t)∥∥∥∥∥+maxs∈S R2,s,ρt,t ,whereR1,s,ρt,t =∥∥∥Λt(s, ρt, sW t)− µρt(s)∥∥∥,R2,s,ρt,t =∥∥∥∥∥1Kt∑k∈Wt E[ℓ(Zk, θ)s | ρt]Λt(s, ρt, sW t)− ϕ(ρt, s, θ)∥∥∥∥∥.First note that for all fixed ρ ∈ Γ,|Λt(s, ρ, sW t)− µρ(s)| → 0as t→∞, and independently of initial state sW t , which follows from irreducibility (c.f. Freed-man [2017], theorem 4.9). Now to prove uniform convergence in ρ. Firstly, ρt ∈ Γ compact. Sofor any fixed δ > 0, we can find an open cover of Γ of cardinality Jδ, using δ-balls centered at67A.1. Proof of Lemma 1θj with 1 ≤ j ≤ Jδ. Now write for all s ∈ SHt(ρ, s) =1Kt∑k∈Wtλk(s, ρ, sW t)− µρ(s).Thensupρ∈Γ|Ht(ρ, s)| ≤ max1≤j≤Jδsupρ∈B(ρj ,δ){|Ht(ρ, s)−Ht(ρj , s)|+ |Ht(ρj , s)|}≤ supρ∈Γsupρ1∈B(ρ,δ)|Ht(ρ, s)−Ht(ρ1, s)|+ max1≤j≤Jδ|Ht(ρj , s)|= At +Bt,whereAt = supρ∈Γsupρ1∈B(ρ,δ)|Ht(ρ, s)−Ht(ρ1, s)|,Bt = max1≤j≤Jδ|Ht(ρj , s)|.Pointwise convergence of Ht(ρ, s) implies that Bt → 0 as t→∞. Then,At ≤ supρ∈Γsupρ1∈B(ρ,δ)1Kt∑k∈Wt|λk(s, ρ, sW t)− λk(s, ρ1, sW t)|+ supρ∈Γsupρ1∈B(ρ,δ)|µρ(s)− µρ1(s)|≤ supρ∈Γsupρ1∈B(ρ,δ)D11Kt∑k∈Wt∥ρ− ρ1∥+ supρ∈Γsupρ1∈B(ρ,δ)D2∥ρ− ρ1∥≤ δ(D1 +D2),where 0 < D1, D2 < ∞ are the Lipschitz constants existing by assumption 4. Thus, for allt ≥ 1, At → 0 as δ → 0 (and recall that δ is picked arbitrarily), and the result follows:supρ∈Γ|R1,s,ρ,t| → 0,as t→∞.Next, note thatϕ(ρt, s, θ) =E[ℓ(Zk, θ)s|ρt]P (sk = s, ρt),68A.2. Proof of Theorem 1with P (sk = s, ρt) =∑s′∈S µρt(s′)λk(s, ρt, s′) is the stationary expected value of λk over initialstates s′. By assumption 1, for all fixed ρ, limk→∞ λk(s, ρ, s′) = limk→∞ P (sk = s, ρ) = µρ(s).Then we getR2,s,ρt,t ≤∥∥E[ℓ(Zt, θ)s | ρt]∥∥∥∥∥ 1Λt(s, ρt, sW t)− 1P (sk = s, ρt)∥∥∥ (A.1)≤ D3D4∥Λt(s, ρt, sW t)− P (sk = s, ρt)∥, (A.2)where 0 < D3 < ∞ is an upper bound on ∥ϕ(ρt, s, θ)∥ following from the boundedness of theloss function, and 0 < D4 < ∞ is an upper bound on 1Λt(s,ρt,sWt )1P (sk=s,ρt)which follows fromirreducibility and assumption 4, which implies that both fractions cannot diverge. Finally,the last term in (A.1) converges to zero uniformly over ρ by an argument analogous to theconvergence of Ht(ρ, s).Finally, since ∥∥∥∥∥1Kt∑k∈Wt E[ℓ(Zk, θ)s | ρt]Λt(s, ρt, sW t)∥∥∥∥∥ ≤ D3D4,where the last bound is independent of θ, convergence of ∥L∗t (θ, ρt)−∑s∈S µρt(s)ϕ(ρt, s, θ)∥ isuniform over θ ∈ Θ and ρ ∈ Γ.■A.2 Proof of Theorem 1The following lemma will help prove the result. From now on, we drop the i-superscriptwhenever possible.Lemma 4. Impose assumptions 1, 2, and 4.For all ε > 0,P(supθ∈Θ∥Lt(θ)− L∗t (θ,ρt))∥ > ε)→ 0,as t→∞.Proof. We first show pointwise convergence of ∥Lt(θ)− L∗t (θ,ρt)∥.69A.2. Proof of Theorem 1We can writeLt(θ) =∑s∈Snt(s)Kt∑k∈Wt ℓ(Zk, θ)1{sk = s}nt(s),wherent(s) =∑k∈Wt1{sk = s}.First we show, for all s ∈ S ∣∣∣nt(s)Kt− Λt(s,ρt, sW t)∣∣∣→P 0,as t→∞. For this, defineV1,t = E[(nt(s)Kt− Λt(s,ρt, sW t))2],and let dt = 1{sk = s} − λk(s,ρW t:k, sW t).V1,t =1K2t∑k∈WtE[d2k]+1K2t∑k,k′∈Wt|k ̸=k′E[dkdk′],where the second term1K2t∑k,k′∈Wt|k ̸=k′E[dkdk′]=1K2tE∑k,k′∈Wt|k ̸=k′E[dkdk′ | Zk∨k′ ,ρW t:(k∧k′), sk∧k′]= 0,since by definition of dt and assumption 1, states form a controlled Markov chain, and thusE[E[dkdk′ | Zk∨k′ ,ρW t:(k∧k′), sk∧k′]]= E[dk∨k′E[dk∧k′ | Zk∨k′ ,ρW t:(k∧k′), sk∧k′]]= E[dk∨k′E[dk∧k′ | ρk∧k′ , sk∧k′]]= 0.It follows that V1,t → 0 as Kt → ∞. We can then apply Chebyshev’s inequality, and the firstresult follows: ∣∣∣nt(s)Kt− Λt(s,ρt, sW t)∣∣∣ = oP (1).70A.2. Proof of Theorem 1Similarly, let ht(θ, s) = ℓ(Zt, θ)1{st = s} − E[ℓ(Zt, θ)s|ρt]. DefineV2,t,s = E[( 1Kt∑k∈Wthk(θ, s))2],then by an argument analogous to above, using assumption 2 and boundedness of l we canconclude that V2,t,s → 0 as t → ∞ for all s. By assumption 4 we have that nt(s)Kt > 0 withprobability approaching 1 with t. Thus, we can apply the continuous mapping theorem to arriveat the result: for all θ ∈ Θ,∥Lt(θ)− L∗t (θ,ρt)∥ = oP (1).The rest of the proof is based on Newey and McFadden [1994]’s proof of their theorem 2.1,but we have to adapt to the fact that we face a random population objective L∗ due to therandomness of ρt.The proof follows a similar logic as the proof of lemma 1. First defineHt(θ,ρt) =1Kt∑k∈Wthk(θ),where we drop the dependence on state s since the statement holds for any s and there arefinitely many.Take any ε > 0 and any δ > 0. Let B(x, δ) denote the δ ball centered at x. Then bycompactness of Θ, we can construct a finite open cover of Θ with cardinality Jδ < ∞ usingopen balls B(θj , δ). Now note thatP(supθ∈Θ∥Ht(θ,ρt)∥ > 2ε)≤ P(max1≤j≤Jδsupθ∈B(θj ,δ){∥Ht(θ,ρt)−Ht(θj ,ρt)∥+ ∥Ht(θj ,ρt)∥} > 2ε)≤ P(supθ∈Θsupθ1∈B(θ,δ)∥Ht(θ,ρt)−Ht(θ1,ρt)∥+ max1≤j≤Jδ∥Ht(θj ,ρt)∥ > 2ε)≤ At +Bt,71A.2. Proof of Theorem 1whereAt = P(supθ∈Θsupθ1∈B(θ,δ)∥Ht(θ,ρt)−Ht(θ1,ρt)∥ > ε),Bt = P(max1≤j≤Jδ∥Ht(θj ,ρt)∥ > ε).The second term must converge to zero by pointwise convergence as proved before, sinceBt ≤∑1≤j≤JδP(∥Ht(θj ,ρt)∥ > ε)→ 0as t→∞. Now defineYδ = supθ∈Θsupθ1∈B(θ,δ)1Kt∑k∈Wt∥ℓ(Zk, θ)− ℓ(Zk, θ1)∥,andY˜δ = supθ∈Θsupθ1∈B(θ,δ)1Kt∑k∈Wt∥E[(ℓ(Zk, θ)− ℓ(Zk, θ1)) | ρk]∥.Then note thatAt ≤ P(Yδ + Y˜δ > ε) ≤ 1εE[Yδ + Y˜δ], (A.3)by Markov’s inequality. Finally, note thatEYδ ≤ 1Kt∑k∈WtE supθ∈Θsupθ1∈B(θ,δ)∥ℓ(Zk, θ)− ℓ(Zk, θ1)∥≤ 1Kt∑k∈WtE supθ∈Θsupθ1∈B(θ,δ)C1(Zk)∥θ − θ1∥ ≤ 1Kt∑k∈WtEC1(Zk)δ,where the second to last inequality follows from assumption 2 and the Lipschitz property ofℓ(Z, θ). Thus, we getlimt→∞EYδ ≤ limt→∞1Kt∑k∈WtEC1(Zk)δ,where the right hand side vanishes as δ → 0 by assumption 2. We can make an analogousargument to show that limt→∞ EY˜δ → 0 as δ → 0. It follows that At → 0 as t→∞ and δ → 072A.2. Proof of Theorem 1by the bound given in (A.3). The result follows, since Ht(θ) is the only factor in Lt(θ)−L∗t (θ,ρt)that depends on θ:We can write∥Lt(θ)− L∗t (θ,ρt)∥≤∑s∈S∥∥∥nt(s)Kt− Λt(s,ρt, sW t)∥∥∥∥∥∥ Ktnt(s)1Kt∑k∈Wtℓ(Zk, θ)s∥∥∥+maxs∈S∥∥∥ Ktnt(s)− 1Λt(s,ρt, sW t)∥∥∥∥∥∥ 1Kt∑k∈Wtℓ(Zk, θ)s∥∥∥+maxs∈S∥∥∥ 1Λt(s,ρt, sW t)1Kt∑k∈Wthk(θ, s)∥∥∥.The first two terms converge uniformly in θ to zero by our first arguments in this proof, due tothe boundedness assumption on l and assumption 4. Only the last term depends on ht(θ, s),the uniform convergence of which has been shown above.Lemma 5. Impose assumptions 1 - 4. Then for all ε > 0P(supθ∈Θ∥∥L∗t (θ,ρt)− L∗t (θ, ρt)∥∥ > ε)→ 0,as t→∞.Proof. For any θ ∈ Θ we can writeYt(θ,ρt) ≡ ∥L∗t (θ,ρt)− L∗t (θ, ρt)∥ ≤1Kt∑k∈Wt∥E[ℓ(Zk, θ) | ρk]− E[ℓ(Zk, θ) | ρt]]∥≤ C4 1Kt∑k∈Wt∥ρk − ρt∥ ≤ C4C5 1Kt∑k∈Wtt∑l=kαl,with 0 < C4 < ∞ being the bound on C3 given by assumption 2 and 0 < C5 < ∞ being thebound resulting from F (ρt, θt) +Mt+1 being almost surely bounded given Gt for all t. Since αtis decreasing, we have1Kt∑k∈Dtt∑l=kαl ≤ Ktαt−Kt ,and the last term vanishes by assumption 3. Since the last term is independent of θ, we can73A.2. Proof of Theorem 1use Markov’s inequality withE[supθ∈ΘYt(θ,ρt)] ≤ C4C5Ktαt−Kt ,and the conclusion follows.Using lemmas 1, 4, and 5, we conclude that, for all ε > 0,P(supθ∈Θ∥∥Lt(θ)− L∗∞(θ, ρt))∥∥ > ε)→ 0,as t→∞.As a last step, we can prove the convergence of θt. By assumption 5,P(θt /∈ B(θ∗(ρt), ε)) ≤ P(L∗∞(θt,ρt)− L∗∞(θ∗(ρt), ρt) ≥ δ)= P(L∗∞(θt, ρt)− Lt(θt) + Lt(θt)− L∗∞(θ∗(ρt), ρt) ≥ δ)≤ P(L∗∞(θt, ρt)− Lt(θt) + Lt(θ∗(ρt))− L∗∞(θ∗(ρt), ρt) ≥ δ)≤ P(2 supθ∈Θ∥Lt(θ)− L∗∞(θ, ρt)∥ ≥ δ),where the second-to-last inequality follows from assumption 5. The result follows. It followsthat we can write F (ρt, θt) = F (ρt, θ∗(ρt))+ oP (1) as a function approximator that depends onpolicy profiles only through the current period’s profile ρt, and not some weighted average ofpast profiles. ■74Appendix BAppendix to Chapter 3B.1 The Algorithm ClassIn this section, I provide the general reinforcement learning family the analysis of chapter 3applies to. Assume there are N algorithmic agents. Agents observe states on some fixed, finitestate space S with |S| = L, and make per period choices (actions) in compact interval Xi. LetX¯i = XLi , with policy profile space X¯ = ×i∈IX¯i. Agents then follow a fixed rule (algorithm) toupdate their strategy profiles over time.Definition 11. Each agent updates their policy according to the following adaptive procedure:ρit+1 ∈ ρit + αt[F i(ρt) +Bit],where αt > 0 is a decreasing stepsize sequence, F (ρt) is a (possibly multivalued) mapping, andBit represents a (possibly multivalued) error term.I stack the above iteration over i to get to the representation of study:ρt+1 ∈ ρt + αt [F (ρt) +Bt] . (B.1)I write ’∈’ instead of ‘=’ above to allow for multivalued mappings as can be the case whenF i represents an argmax, which corresponds to Q-iterations as in definition 3. The class ofRL algorithms studied here is determined by restrictions on F (ρ) and Bit. Whenever there ismultivaluedness, I allow the algorithm to pick arbitrarily. In our limiting characterization, thiswill show up as possibility of multiple solutions, which will not affect the limiting statementsas shown in section 3.4. Throughout, impose assumptions 9 and 10. The following are twoimportant examples of what behavior Bt can be allowed to take:1. Bt = 0 and F (ρ) is a Lipschitz-continuous function, we are in the familiar territory ofRobbins-Monro algorithms for which the asymptotic behavior is well known (see chapter2 in Borkar [2009]).75B.1. The Algorithm Class2. Bt is a martingale-difference noise with respect to some filtration Ft, with bounded secondmoment. This error term could be the result from an estimation method to estimatingF (ρ) consistently. This scenario can again be readily analyzed using the methods devel-oped in Borkar [2009], chapter 2.Considering the iteration (B.1), we can see that F (ρt) features importantly as a mappingthat provides the reinforcement of the iteration profile ρt. In many scenarios, F (ρ) representsa performance criterion based on market and opponent conditions that are not known to thealgorithm designer and must be estimated. F (ρ) thus becomes an estimation target, and Bt canthen be seen as the resulting error term. If F (ρ) were fully known, as is allowed by definition,one can set Bt = 0 for all t.First, I introduce the class of performance criteria F (ρ), and what kinds of approximationmethods can be considered here:Definition 12 (Candidate performance criteria). Define the set M1 of (possibly multivalued)maps G with domain X ⊆ Rk and range P[R] for R ⊆ Rk s.t.• G(x) ⊂ R is convex, compact valued.• There exists c > 0 such that sup{∥y∥ : y ∈ G(x)} ≤ c(1 + ∥x∥) for all x ∈ X, i.e. lineargrowth.• There is a union of connected sets Ck ⊆ X of positive measure, US =⋃k Ck, such thatG(x) is single-valued and C1 for x ∈ US.Remark 1. I allow for multivaluedness in order for the common learning scheme of actor-critic Q-learning to be covered, which maintains estimates of the argmax of a value function asintroduced in Section 3.3. Note however that, with some abuse of notation, C1 ⊂M1.Now, define the distance between points x and sets A asd(x,A) = infx′∈A∥x− x′∥.We are ready to consider the definition of function approximators to which this analysis applies.Definition 13 (C1 Approximation). hhhLet Y be some space of observations (datasets) Dt to be used to approximate a mapping. Givenγ > 0, say that a function approximation operator Ag :M1 × Y 7→ M1 is a C1 Approximationof a performance criterion F ∈ M1 if there is a bias function g ∈ B1γ and an integer N > 0such that one can write for all t ≥ N :76B.1. The Algorithm Class(i) For all ρ ∈ X,Ag[F,Dt](ρ) = Fg(ρ) + δt,where Fg(ρ) ∈M1 such thatsupz∈Fg(ρ)d(z, F (ρ))< γ,(ii) For all ρ ∈ US,Ag[F,Dt](ρ) = F (ρ) + g(ρ) + δt,with g ∈ B1γ,(iii)δt = OP (t9 12 ),(iv)suptE[∥δt∥2] <∞.One can interpret g(ρ) as representing the bias part of the function approximation, and δt asa random variable such that E[∥δt∥2] represents the variance part. Points (iii) and (iv) boundthe speed of convergence and variance of the error term δt to ensure that our characterizationtechnique used in propositions 1 and 2 goes through.In the case of classical model-free Q learning as in Section 3.2, Dt only needs to consist of(sk, ak, rk, sk+1)tk=1, i.e. past observations of states, actions, payoffs, state transitions, and theinitial Q0.Generally, one can think of Ag[F,Dt](·) as a parametric or non-parametric function approxi-mation to the performance criterion of interest F , with bounded errors that can be approximatedby a small C1 function after enough data (large n) has been accumulated. Sufficient conditionsfor the existence of such function approximators are given in appendix B.1. Fix small γ > 0and observation spaces Y i. We can now state the following assumption that, together withdefinitions 12 and 13 characterizes the algorithm class that can be studied here.Assumption 11. hh(i) Let the bias functions gi ∈ B1γ.77B.1. The Algorithm Class(ii) Let Dit ∈ Y i be a sequence of datasets.(iii)Bit = Aigi [F i, Dit](ρt)− F i(ρt) +M it+1,where Ag[F,Dt] is a C1 Approximation of performance criterion F (ρ) ∈M1. Notice that,accordingly, Bit can be a point or a compact convex set.(iv) Stacked version of Bit:Bt = Ag[F,Dt](ρt)− F (ρt) +Mt+1.(v) Ft is the σ-field generated by {ρt, Dt,Mt, ρt−1, Dt−1,Mt−1..., ρ0, D0,M0}, i.e. all the in-formation available to the updating rule at a given period t.(vi) Mt+1 is a Martingale-difference noise. There is 0 < M¯ <∞, q ≥ 2 such that for all tE[Mt+1 |Ft] = 0; E[∥Mt+1∥q |Ft] < M¯ a.s.(vii) Whenever ρt ∈ US,Ωt ≡ E[Mt+1M ′t+1 |Ft],where Ωt is symmetric positive definite for all t.Gradient-type AlgorithmsHere, I give a brief overview of the kind of gradient-type algorithms that are included in ourclass. First, few definitions are in order to properly understand this class:For any i ∈ I, let X¯9i = ×j ̸=iX¯j . Recall that expected future discounted payoffsW i(ρi, ρ9i, s0)given stationary strategy profiles [ρi, ρ9i] ∈ X¯ are defined as:W i(ρi, ρ9i, s0) = E∞∑t=0δtui(ρ(st), st), (B.2)where the expectation is made over the state transitions.Then define▽W i(ρi, ρ9i, s0) ∈ Rk,78B.1. The Algorithm Classas the gradient with regard to policies of agent i’s long term payoff evaluated at [ρi, ρ9i]. Byabuse of notation, write ▽W (ρ) as the stacked gradients of all agents, where without muchloss one can suppress the dependence on initial states due to our assumption on irreducibility6. It is without much loss since stability properties of any differential Nash equilibrium will beindependent of the initial state under irreducibility, and those properties are the focus of therest of the paper.Now define for ρ ∈ X¯FSD(ρ) = ▽W (ρ), (B.3)as the state dependent gradient dynamics. Take an iteration ρt and its respective functionestimation target F as denoted in (B.1). If F = FSD, we will call the RL iteration ’GradientEquivalent’.For Gradient Equivalent iterations, if there is no asymptotic bias in the estimation of thegradient (g = 0), my results match the results in Mazumdar et al. [2020], but note that westudy the possibility of repeated game strategies, which is not explicitly done there. Further,as noted in the introduction, my results extend Mazumdar et al. [2020] to the more commonlyobserved situation of non-vanishing biased function estimators.Remark 2 (A note on the case Bit = 0). hhhAs stated in the discussion below Definition 11, we do allow for deterministic updates represent-ing the case where everything is known to the algorithm, i.e. Bit = 0. By definition, this impliesthat the nonvanishing variance condition of Mt+1 mentioned above cannot hold. However, itis then possible to prove a similar result as proposition 2 by measuring the set of initial valuesρi0 that would allow for the process ρt to converge to an unstable rest point ρ∗. By definitionof instability, the paths that could attract ρt to ρ∗, if they exist, must be a lower-dimensionalsubspace of profile space X¯. The statement one can then make is that the probability that arandomly chosen starting profile ρ0 will converge to unstable ρ∗ must equal 0, since any lowerdimensional subspace of X¯ has measure zero.Sufficient Conditions for Assumption 8Here, I verify that the result given in theorem 1 can be applied to show that a given algorithmfalls into the class developed in chapter 3. For a fixed opponent profile ρ9it , defineQ∗i (s, a, ρ9it ) = ui(a, ρ9it (s), s) + δE[maxa′∈AQ∗i (s′, a′, ρ9it ) | a, s, ρ9it (s)],79B.1. The Algorithm Classthe action-value function in a repeated game, supposing opponents fix their policy profileto ρ9it forever. The next result will show that for the sufficient conditions given in this paper,assumption 8 of chapter 3 holds. Then, theorem 1 allows us to conclude that, under someadditional regularity restrictions, assumption 8 can be satisfied by a large family of algorithms.Proposition 6. Suppose assumptions 1 - 5 are satisfied, and algorithms update according toDefinition 1. Writegi(s, a, ρt) = Q∗i (s, a, ρ9it )−Qi(s, a, θ∗(ρt)).Assume that, for all ρt and i1. ui(a, s) is bounded below and above.2. Qi(s, a, θ) is twice differentiable in θ for all s, a.3. Li∗∞(θ, ρt) is twice differentiable in θ on a neighborhood N of θi∗(ρt),4. ∂∂θLit(θi∗(ρt)) = OP (t912 ),5.supθ∈Θ∥∥∥∥∥ ∂2∂θ∂θ′Lit(θ)−Bi(θ)∥∥∥∥∥ = oP (1),for some non-stochastic matrix Bi(θ) such that Bi() is continuous and positive definiteat θi∗(ρt).Then for each i, defineχit ≡ sup(s,a)∈S×X,∥∥Qit(s, a)−Qi∗(s, a, ρ9it )− gi(s, a, ρ9it )∥∥.It follows that for each iχit = OP (t9 12 ),withsuptE[(χit)2]<∞,80B.2. ProofsIn other words, assumption 8 in chapter 3 is satisfied.B.2 ProofsProof of Proposition 1The proofs are given in terms of the general algorithm class treated in this paper, introducedin appendix B.1. Throughout we pick a sequence αt s.t. assumption 9 holds and αt ≤ ζt holdsfor all t ≥ 0. Under assumption 8, it is quick to check that the ACQ iteration in Definition 3falls into our class. First, we prove the following result that employs known techniques fromstochastic approximation theory.First, a few definitions are in order. Take a correspondence G(x) ∈ M1, where we recallthe domain being X ⊆ Rk for some k ≥ 1. The following Definition can be found in Bena¨ımet al. [2005]:Definition 14. hh1. Given a set A ∈ X and x, y ∈ A, we write x ↪→A y if for every ε > 0 and T > 0, thereexists an integer n ∈ N, solutions x1, ..., xn to x˙ ∈ G(x), and real numbers t1, ..., tn greaterthan T such that:27a) xi(s) ∈ A for all 0 ≤ x ≤ ti, and for all i = 1, ..., n,b) ∥xi(ti)− xi+1(0)∥ ≤ ε for all i = 1, ..., n− 1,c) ∥x1(0)− x∥ ≤ ε and ∥xn(tn)− y∥ ≤ ε.2. A set A ∈ X is said to be internally chain transitive (ICT) if A is compact and x ↪→A yholds for all x, y ∈ A.Importantly, these sets include rest points and limit cycles (if they exist). Consider Pa-padimitriou and Piliouras [2018] for an intuitive discussion. The following result shows whythese sets are of importance in our analysis:Proposition 7. With probability one, LS,g is an ICT set of the differential inclusionρ˙ ∈ Fg(ρ(t)),27Recall that G(x) is an inclusion, so uniqueness of solutions cannot be guaranteed.81B.2. Proofswhere Fg(ρ(t)) ∈M1 s.t. supz∈Fg(ρ) d(z, F (ρ)) < γ holds for all ρ, and particularlyFg(ρ(t)) = F (ρ(t)) + g(ρ(t))whenever ρ(t) ∈ US .Proof. The algorithm (B.1) can be written asρn+1 = ρn + αn [Fg(ρn) + δn +Mn+1] , (B.4)where δn = Ag[F,Dn](ρn)− Fg(ρn).We can now show first that iteration B.4 is a perturbed solution to ρ˙ ∈ Fg(ρ(t)) as definedin Definition II in Bena¨ım et al. [2005]. Following the proof of their proposition 1.3, we onlyneed to take care of the additional term δn present in iteration B.4.Following the notation in Hofbauer and Sandholm [2002], introduce:τ0 = 0; τn =n∑i=1αi; m(t) = sup{k ≥ 0 : t ≥ τk}.Define for k > n:Ψkn =∥∥∥∥∥k−1∑i=nαi+1δi+1∥∥∥∥∥.Then for proposition 1.3 in Hofbauer and Sandholm [2002] to hold, it suffices to show that, forall T > 0supn≤k≤m(τn+T )−1Ψkn →P 0, (B.5)as n→∞. First, note thatΨkn ≤k−1∑i=nαi+1∥∥δi+1∥∥,82B.2. Proofsand the right hand side is increasing in k, so thatsupn≤k≤m(τn+T )−1Ψkn ≤m(τn+T )−1∑i=nαi+1∥∥δi+1∥∥.Now we get that, for any ε > 0,P(supn≤k≤m(τn+T )−1Ψkn > ε)≤ P(m(τn+T )−1∑i=nαi+1∥∥δi+1∥∥ > ε).Next, recall from definition 13 that ∥δn∥ = OP (n9 12 ). Fix ε′ > 0. By definition there existsMε′ > 0 and N > 0 such that for all n > N :P(∥δn∥ > Mε′n912)< ε′.Define1n = 1{∥δn∥ > Mε′n912}.Thus,∥δn∥ ≤Mε′n912 + 1n∥δn∥.So we can write:P(m(τn+T )−1∑i=nαi+1∥∥δi+1∥∥ > ε) ≤ P(m(τn+T )−1∑i=nαi+11i+1∥∥δi+1∥∥+ Jn > ε),whereJn =Mε′m(τn+T )−1∑i=nαi+1(i+ 1)9 12 .Notice that Jn → 0 as n→∞, as long as αnn912→ 0, which is in line with assumption 9. We canthus take n large enough to have ε > Jn, and then write83B.2. ProofsP(m(τn+T )−1∑i=nαi+11i+1∥∥δi+1∥∥+ Jn > ε) ≤ 1ε− JnE[m(τn+T )−1∑i=nαi+11i+1∥∥δi+1∥∥]≤ ε′ε− Jnm(τn+T )−1∑i=nαi+1E[∥∥δi+1∥∥2] 12≤ ε′ε− JnCδT,where the first inequality follows from Markov’s inequality, and the second one from Cauchy-Schwarz. Since δi are square-integrable by definition 13, there exists 0 < Cδ < ∞ so that thelast inequality follows from the definition of τn. Since ε′ is arbitrary, it can be made arbitrarilysmall, and we have that indeed (B.5) holds.Thus, ρn is a perturbed solution to ρ˙ ∈ Fg(ρ(t)) as defined in Definition II in Hofbauer andSandholm [2002]. The result then follows from theorem 3.6 in Hofbauer and Sandholm [2002].Since payoffs are differentiable around ρ∗, point 1 follows as long as ρg and ρ∗ are close. Forpoint 2, we will prove something more general: as long as ρ∗ is hyperbolic (c.f. Definition 5),point 2 holds.This follows because when ρ∗ is hyperbolic, there is a neighborhood U around 0 such thatF has a differentiable inverse on U . Next, note that ρg solvesF (ρg) + g(ρg) = 0.Since ∥g∥1 ≤ γ, for γ small enough, F (ρg) ∈ U must hold. Then there is some LF−1 > 0 suchthat∥ρg − ρ∗∥ = ∥F−1(F (ρg))− F−1(0)∥≤ LF−1∥F (ρg)∥ ≤ LF−1γ,where the first inequality follows because F−1 is differentiable and F (ρ∗) = 0, and the secondby the definition of F (ρg). Since the right hand side is independent of g, the bound is uniform.For point 3, we first need to verify that all ρg close enough to ρ∗ must also be asymptoticallystable. The next lemma gives a more general result:84B.2. ProofsLemma 6. Suppose ρ∗ is hyperbolic. Then the eigenvalues of DFg(ρg) converge to the eigen-values of DF (ρ∗) uniformly over g ∈ B1γ as γ → 0. Thus, for small enough γ, ρg has the samestability properties as ρ∗.Proof. I will show that eigenvalues of a hyperbolic matrix DF (ρ∗) vary continuously in C1perturbations g to F .Proposition 2.18 in Palis Jr et al. [1982] shows that eigenvalues vary continuously for anymatrix A. Thus, if ∥DF (ρ∗) −DFg(ρg)∥ is small enough, the eigenvalues of the two matricesmust be close to each other. Now write∥DF (ρ∗)−DFg(ρg)∥ = ∥DF (ρ∗)−DF (ρg)∥+ ∥Dg(ρg)∥≤ ∥DF (ρ∗)−DF (ρg)∥+ γ,where the equality follows from the definition of Fg. Since DF is continuous, and ρg → ρ∗uniformly for g ∈ B1γ as γ → 0 (see above proof of point 2), we get thatsupg∈B1γ∥DF (ρ∗)−DFg(ρg)∥ → 0as γ → 0. Then applying proposition 2.18 in Palis Jr et al. [1982] finishes the result.Since we know that all ρg must be asymptotically stable for γ small enough, one can applyFaure and Roth [2010] (Thm 2.8). It suffices to verify that our process satisfies their attainabilitycondition:Definition 15. A point p is attainable if, for any n > 0 and any neighborhood U of pP[∃s ≥ n : ρs ∈ U ] > 0.Let Att(X) be the set of attainable points for algorithm (B.1). Then we need that the basinof attraction of an attractor has nonempty intersection with Att(X). This can be verified:Lemma 7. Let B be a basin of attraction of an attractor A for Fg. Suppose ρt ∈ X¯ \B. Thenthere exists s > n such that ρs ∈ B with positive probability.Proof. Since t is finite, to show existence we construct s = n + 1: For any z ∈ B, one can pindown the necessary shock Mz to reach it:Mz ∈ z − ρtαt− Fg(ρt),85B.2. Proofssince Fg might be multivalued.Since z ∈ int(E) by definition, Mz is in the support of Mt+1 for every t. For any ball Bzaround z, defineMz = {Mx′ : x′ ∈ Bz}.Mz must have positive measure for all finite t, since it is in the support of Mt+1. (if we allows > n+ 1, we may be able to increase the measure, but we only need it to be positive.)All other conditions that are sufficient for the algorithm B.1 to converge to the attractorhold by assumption 11.■Proof of Proposition 2Notice first that the following analysis is local to the rest points in ES , which by assumptionon US is also where F, Fg are single valued. Solution curves are unique whenever they intersectUS .The proof will use the Hartman-Grobman theorem (c.f.Chicone [2006], theorem 4.8), whichconnects the flow of a nonlinear ODE in the neighborhood of a hyperbolic rest point to the flowof a linearized ODE. Since it works fully locally, our analysis only requires that F (ρ) be singlevalued and C1 in Uρ∗ , and we can allow F (ρ) to be multivalued otherwise.First, define invariant sets for given differential equations:Definition 16. Let z(t, z0) be the solution so some given differential equation z˙ = f(z) withinitial value z0. Then a set S• is invariant for f , if z(t, z0) ∈ S holds for all t ∈ R and all z0 ∈ S.• isolated invariant for f if there is an open set N such that S ⊂ N andS = {z′ : z(t, z′) ∈ N ∀t ∈ R}.Given a g ∈ B1γ , we know from proposition 7 that only ICT sets (recall Definition 14)subset of a neighborhood of ρg are candidates to being limiting points of the algorithm (B.1).The singleton {ρg} is an ICT set, and we show first that this cannot be a limiting set of thealgorithm. Then we go on to show that for small enough γ, no other ICT sets can exist in aneighborhood around ρ∗, which finishes the proof.1) {ρg} cannot be a limiting set.86B.2. ProofsNote that by lemma 6, there are γ > 0 small enough such that all ρg are linearly unstablejust as ρ∗. We can thus apply Bena¨ım and Faure [2012], theorem 3.12 to prove P[LS,g = ρg] = 0first:We can show that the sufficient conditions for this hold by definition of our algorithm underassumption 11. First, we need that Hypothesis 2.2 and 3.6 of Bena¨ım and Faure [2012] hold.It is quick to check that if it were the case that µn ≡ E[δn] = 0 for all n, these hypotheseswould hold true.28 In our case, point (v) of Definition 13 is required additionally. To see this,following the arguments in Bena¨ım and Faure [2012] one needs to boundP(suph∈[0,T ]∥X(τn + h)− ϕh(X(τn))∥ ≥ ε | Ft)(B.6)where X(τn) is the linear interpolation of ρn and ϕh(x) is the flow of ρ˙ ∈ Fg(ρ) starting at x,carried forward by h periods. τn is as defined in the proof of proposition 7. By following anargument analogous to the proof of proposition 4.1 in Bena¨ım [1999], bounding the randomvariable inside the above measure leads to all terms present there, with one additional termowing to the presence of µn. This additional term is bounded byKn = sup{∥∥∥∥∥k−1∑i=nαi+1µi+1∥∥∥∥∥ : k = n+ 1, ...,m(τn + T )},with m(·) as defined in the proof of proposition 7. However, this term is deterministic - and bypoint (v) of Definition 13 must vanish with large n. Thus, one can writeP(suph∈[0,T ]∥X(τn + h)− ϕh(X(τn)) ≥ ε | Ft)≤ P(suph∈[0,T ]∥X(τn + h)− ϕh(X(τn)) ≥ ε−Kn | Ft),where Kn vanishes, so the bounding function as required in Hypothesis 2.2 and 3.6 of Bena¨ımand Faure [2012] can be found e.g. by applying proposition 2.16 of Faure and Roth [2010].Finally, note that the conditions and analysis sufficient for the proof of Bena¨ım and Faure[2012]’s theorem 3.12 are local with respect to ρg. Thus, the fact that Fg is globally potentiallymultivalued is of no importance, since in a small enough neighborhood around ρg it must besingle-valued and C1.2) No other ICT sets exist in a neighborhood of ρ∗ and ρg.28For example, by applying proposition 2.16 of Faure and Roth [2010]87B.2. ProofsWe will prove that there are no other invariant sets in such a neighborhood. Since ICT setsare subsets of invariant sets, this will complete the proof.We can use Hartman-Grobman to show that there are open neighborhoods Ng, N0 withρ∗ ∈ N0, ρg ∈ Ng such that ρ∗, ρg are isolated invariant sets in their respective neighborhoods.These neighborhoods are nontrivial for all γ small enough, which follows from both ρ∗, ρg beinghyperbolic:By Hartman-Grobman and hyperbolicity there exists a homeomorphism H on a neighbor-hood N ⊆ Uρ∗ of ρ∗ with H(ρ∗) = ρ∗ such thatH(ϕ(t, ρ)) = ψ(t,H(ρ)),where ϕ(t, ·) is a solution (flow) to the differential inclusion ρ˙ ∈ conv[F (ρ)], and ψ(t, ·) is thesolution to the ODE y˙ = DF (ρ∗)(y − ρ∗). Given a neighborhood U ⊆ N of ρ∗, defineinv(U) = {ρ ∈ U : ϕ(t, ρ) ∈ U ∀t ∈ R}.We will show that ρ∗ = inv(U), and therefore, it is isolated invariant.Notice that inv(U) can be rewritten asinv(U) = {y ∈ H(U) : H−1(ψ(t, y)) ∈ U ∀t ∈ R} = {y ∈ H(U) : ψ(t, y) ∈ H(U)∀t ∈ R},since H is bijective. We know that ρ∗ is an isolated invariant set for the linear ODE solutionψ(t, y) = CetDF (ρ∗)y + ρ∗. Thus, we must also have thatinv(U) = ρ∗,and ρ∗ is isolated invariant set for ϕ(t, ρ).Since ρg are hyperbolic for γ small enough, an analogous argument gives us that ρg areisolated invariant also. Let Ng be the neighborhood on which the homeomorphism is definedthat connects flows of Fg to flows of the linearized system DFg(ρg). By definition, ρg ∈ Ng,and we know that ρg is isolated invariant in Ng. We are left to show that for γ small enough,for all g ∈ B1γ , ρ∗ ∈ Ng:To prove this, we will argue that each Ng contains a ball Bgz (ρg), for which the radius z > 0can be lower bounded by a number that depends only on the eigenvalues of DF (ρ∗) and γ.First, we need an auxiliary lemma to show how eigenvalues of DFg(ρg) vary continuously in γ.First, some more notation:88B.2. ProofsFor small enough γ, all ρg are hyperbolic when g ∈ B1γ . Fix such a g. Define ρl > 0 to bethe smallest positive eigenvalue of DFg(ρg), and ρu < 0 be the largest negative eigenvalue ofDFg(ρg). Now let ag ∈ (0, 1) be any number such thatmax {eρu , e−ρl} < ag < 1.For the original system DF (ρ∗), let a0 ∈ (0, 1) be any such number.Lemma 8. For any δ > 0 with a0 < 1− δ there exists γ > 0 such that for all γ ∈ (0, γ], thereis a set of {ag}g∈B1γ as defined above withsupg∈B1γ|ag − a0| < δ.Proof. Apply lemma 6. Since there is a one-to-one mapping between eigenvalues and {eρu , e−ρl},one can find numbers ag. The result follows.Given this continuity in eigenvalues, we can prove the following lemma to finish our result:Lemma 9. Suppose ρ∗ is hyperbolic for F . Fix a small z > 0. Then there is γ¯ such that forall γ ≤ γ¯, and all g ∈ B1γ, there is Bgz (ρg) ⊆ Ng with z ≥ z.Proof. For small enough γ, all ρg are hyperbolic when g ∈ B1γ . Fix such a g. Given some ε > 0,let rε be defined assup{r > 0 : ∥ρ− ρg∥ < r; ∥DFg(ρ)−DFg(ρg)∥ < ε}.Since DFg is continuous, rε > 0 must hold. Pick ag ∈ (0, 1) as defined previously.Then defineεg =1− agag> 0.By lemmas 4.3 and 4.4 of Palis Jr et al. [1982], Brε(ρg) ⊆ Ng, if ε < εg.We are left to show that rε can be made to depend only on the eigenvalues of DF (ρ∗) andγ. Notice that small enough z > 0 pins down the δ > 0 referred to in lemma 8: Letzˆ(γ) = infγ∈(0,γ]infg∈B1γεg.For δ > 0 small enough, choose γ > 0 such that lemma 8 holds. It follows from the lemma thatzˆ(γ) > 0. Then any z < zˆ(γ) satisfies our conditions and the conclusion follows.89B.2. ProofsNow recall that by the proof of proposition 1 point 2, ρg → ρ∗ uniformly over g ∈ B1γ asγ → 0. Thus, there is γ small enough for which supg∈B1γ |ρg − ρ∗| < z and therefore ρ∗ ∈ Ng forall g ∈ B1γ . Let Uγ = ∩g∈B1γNg. Since ρg for g ∈ B1γ are isolated invariant in Uγ by construction,the result follows.■Proof of Proposition 6Firstly, one can prove χt →P 0 as t→∞ given that θt →P θ∗(ρt), using arguments analogousto the proof of lemma 1, given point (2). This can be done with the following argument:From points (1)-(2), we get that there exists 0 < C <∞ such thatχt ≤ C∥θt − θ∗(ρt)∥,Convergence in probability of χt follows, with also the rate of convergence of χt being boundedby the convergence rate of θt.Assumptions (3)-(5) are classical assumptions used in the asymptotic analysis of extremumestimators in econometric theory, usually to determine asymptotic normality. In this case,these assumptions give us that ∥θt− θ∗(ρt)∥ = OP (t9 12 ), via the standard Taylor approximationargument applied to Lt(θt) (see e.g. Hansen [2010], section 22.6).Finally, square-integrability of χt follows from boundedness of Q,Q∗, which in turn followsfrom boundedness of u (point 1).90Appendix CAppendix to Chapter 4C.1 Best Response Dynamics: StabilityI give here detailed results that allow the stability analysis for binary state profiles given twoplayers, as outlined in chapter 4. I assume notation and nomenclature developed in that chapter.Let S = {A,B} be any binary state space. For a given policy-profile α, β ∈ X2, writebest replies as b1(β) = (bA1 , bB1 )⊤ ∈ BR1S(β), and b2(α) = (bA2 , bB2 )⊤ ∈ BR2S(α). I consider thestability of rest points for the state-dependent best response dynamics under S, FSB (see (3.7)),given the stacked policies σ ∈ X4:σ˙t = FSB(σt) =[b1(σt,3, σt,4)b2(σt,1, σt,2)]− σt. (C.1)Suppose σ∗ is an interior rest point ∈ US . Then asymptotic stability of σ∗ can be determinedby linearizing the system and showing that all its eigenvalues have negative real parts. LetX(σ∗) be the linearized system:X(σ∗) =[−I2x2 J1(σ∗)J2(σ∗) −I2x2,](C.2)where I2 is the 2-dimensional identity matrix andJi(σ∗) =∂bXi∂βA∂bXi∂βB∂bBi∂βA∂bBi∂βB ,for i ∈ {1, 2}.This linearization has a special structure one can exploit:91C.1. Best Response Dynamics: StabilityRemark 3. Suppose A,B,C,D are square matrices of same dimension, s.t. CD = DC. LetT =[A BC D].Then one can showdet(T ) = det(AD −BC).We can use this the following way: consider the characteristic equation of X(σ∗):ch(λ) = det(X(σ∗)− λI4x4).Then all eigenvalues are characterized as the zeros of ch(λ). Remark 3 tells us thatch(λ) = det(J1J2 − (1 + λ)2I2x2).That is, if µ is an eigenvalue of J1J2, then ±√µ− 1 is an eigenvalue of X(σ∗).Note: J1J2 is the matrix of derivatives one gets when considering the derivatives of an iteratedapplication of best responses:b1(b2(σ1, σ2))− (σ1, σ2)⊤ (C.3)with respect to σ. We can then interpret stability graphically as a scenario in which (C.3)doesn’t grow above the 45-degree line. This can be translated to eigenvalues being less than 1,which from the above is equivalent to considering asymptotic stability of X(σ∗).When considering symmetric equilibria, one can go even further:Remark 4. Suppose A,B are square matrices of the same dimension. LetT =[A BB A].Then one can showdet(T ) = det(A−B)det(A+B).Now, in a symmetric equilibrium σ∗, we have b1(σ∗) = b2(σ∗). Further, since we havesymmetric payoff functions, we have J1 = J2 = J as the matrix of derivatives of the best replyfunction. We can then apply Remark 4 to our system and arrive at the conclusion.Firstly, given square matrix A, define Λ as the set of eigenvalues of the A. Then defineκ = max{|λ| : λ ∈ Λ},92C.1. Best Response Dynamics: Stabilityas the spectral radius of A.Lemma 10. Suppose α∗ = β∗ = σ∗ is an interior, symmetric equilibrium. Let κ¯ be the realpart of the spectral radius of M . Then σ∗ is asymptotically stable if κ¯ < 1, and unstable ifκ¯ > 1.Proof. Using Remark 4, we get thatch(λ) = det(M − (1 + λ)I2)det(M + (1 + λ)I2).Thus, if µ is an eigenvalue of M , then ±µ − 1 is an eigenvalue of X(σ∗), and the conclusionfollows, since asymptotic stability requires that all eigenvalues of X(σ∗) have negative realparts.The Role of TransitionsThis subsection provides intuitions about how properties of binary state variables such as 1Rand DS-states affect flows under state-dependent best response dynamics. I employ notationas developed in chapter 4.Compare the best response derivatives in the case of S∗ and SIT- state variables (morespecifically, 1R-strategies), for a fixed regular stage game u. Thus, qN is a constant quantity,and only state variables are varied. For DS-policies, recall that DPA = DPB , so write from nowon DA = DB = D. Then one can writeJ∗N = BR′NI2 +D[1 −1−1 1]= BR′NI2 +DK∗, (C.4)where I2 denotes the 2-dimensional identity matrix and K∗ =[1 −1−1 1].In comparison, take 1R-strategies. At the static Nash policy ρN , we have that DPA = −DPB ,but since the stage game is the same as before, and 1R-strategies transition based on priceobservations just as S∗ does, we have that the resulting best response derivative can be writtenin terms of D again:J1RN = BR′NI2 +DK1R, (C.5)93C.1. Best Response Dynamics: Stabilitywhere K1R =[1 −11 −1].The only difference between these two cases is due to the difference between K∗ and K1R.One can read these matrices as encoding how a perturbation in an opponent’s strategy dynam-ically affects the best response. Firstly, each column c represents how for a perturbation inopponent’s strategy in state c, both state’s best response quantities will be changed. Impor-tantly, note that K1R tells us that for a given perturbation in state c, one reacts optimally inthe same direction no matter which state’s optimal quantity is considered. This is preciselydue to the fact that K1R is constructed based on the 1R-transition function. No matter whatstate it is, the likelihood of moving to another state conditional on a fixed quantity has to bethe same. In contrast, the transitions due to DS strategy ζN give a change in direction foreach state: each column of K∗ has alternating signs. Thus, for a perturbation in a given statec, K∗ implies differential optimal responses across states. This is the essence of the differencebetween 1R and S∗-strategies. Due to its sign-structure, K1R is a nil-potent matrix, meaningthat (K1R)2 = 0. As a result, the aggregate dynamic incentive DA + DB cancels out in theeigenvalue calculation of J1RN , while K∗’s sign structure is such that the aggregate dynamicincentive DA + DB is reinforced, leading to the second eigenvalue of J∗N being different fromBR′N .Furthermore, the nil-potency of K1R renders J1RN defective; meaning that it has a repeateigenvalue λ1 = λ2 = BR′N , but a unique eigenvector v0 = (1, 1)′. As further explainedbelow, this fact implies that applying F 1RB to any perturbation around ρN will lead solutionsto approach to a perturbation along v0. The following thought experiment explains why thisis important: Suppose at ρN , player 2 perturbs their policy along v0. This represents the oneperturbation in 2-dimensional policy space for which the optimization problem faced by player1 is equivalent to the static problem, as they are starting from ρN , and seeing a perturbationequal in both states. It is then natural that when the equilibrium is statically stable, this typeof perturbation can not break its stability, and players will not escape the Nash equilibrium.To elaborate how this result emerges, one needs to consider the role of eigenvalues and eigen-vectors in characterizing the behavior of solutions to ordinary differential equations (ODEs)close to an equilibrium. The celebrated Hartman-Grobman theorem (c.f. Chicone [2006], theo-rem 4.8) connects the flow of a nonlinear ODE in the neighborhood of a hyperbolic equilibrium(see Definition 5) to the flow of a linearized ODE at the equilibrium. In our case, as discussedabove, linearizing the relevant ODE comes down to finding the best-response derivatives atthe equilibrium. Our relevant ODE is then a 4-dimensional system, as the policy profile is4-dimensional. However, due to the symmetry of payoffs and the equilibrium, it is enough to94C.1. Best Response Dynamics: Stabilityget intuitions based on a single agent’s 2-dimensional best response derivative matrix at thestatic Nash equilibrium, JN .First, let 2-dimensional matrix M be diagonalizable, and consider the problem of findingsolutions to linear ODEx˙ =Mx. (C.6)Let v1, v2 and λ1, λ2 be eigenvectors and eigenvalues of M. Then solutions to (C.6) can bewritten as linear combinationsx(t) = c1eλ1tv1 + c2eλ2tv2, (C.7)for any scalar c1, c2. I take the zero-vector as equilibrium without loss, as any linear ODE canbe shifted by a constant vector. Then λj < 0 for both j implies that 0 is a global attractor,while if λj > 0 for at least one j, there is a direction that repels from 0. This is the image oneshould have in mind in case of DS-policy ζN , since J∗N is not defective, having a 2-dimensionaleigenspace that spans the whole plane. As a result, J∗N can have a repelling eigenvalue whenaggregate dynamic incentive DA +DB is important enough (see corollary 2).Now, recall that J1RN is a defective matrix, with unique eigenvector v0 = (1, 1)′. Solutions tolinear 2-dimensional ODEs based on a defective matrix take a different form from (C.7). It canbe shown that there must exist a generalized eigenvector v1, linearly independent of v0 (that isof course not an actual eigenvector to the defective matrix), so that one can write the generalsolutionx(t) = eλt[c1v0 + c2(v1 + tv0)].Now suppose (as in our case of J1RN ) that λ < 0. 0 is attracting as expected, however thesolutions now can be split into a fast direction v1, and a slow direction v0, meaning that anysolution will first approach the slow direction v0 and then approach 0. In other words, theunique eigenvector can be seen as the essential direction of flow close to the equilibrium, sincefor large t the fast direction represented by the generalized eigenvector v1 will factor into x(t)less and less relative to the slow direction. The intuition given in the beginning of this discussionthen follows: all perturbations must approach the trivial perturbations along v0.When considering the full 4-dimensional system, analogous intuitions can be derived, withthe slight complication being that the 4-dimensional system has 2 unique eigenvectors; thereforestill being defective. The two eigenvectors in that system are the unit vector corresponding to95C.2. Extensionsv0 above, and a vector v1 = (1, 1,−1,−1)′, which correspond to perturbations in which bothagents change their policy the same way in each state, but in opposite directions. Thus, theintuition that only myopic incentives matter is not affected.C.2 ExtensionsIn this and the following section, we will show how to connect our insights on stability of thestatic Nash equilibrium and collusive equilibrium defined for the binary price game to gameswith more general state spaces and many possible price outcomes.Consider the general situation in which S = {s1, ..., sK}, and given aggregate quantitiesQ define transition probabilities between states sk, sk′ as Pkk′(Q), assuming throughout thatPkk′(Q) > 0 for all Q, sk, sk′ ∈ S. Let ρ : S 7→ X be a policy with S-domain.For long term payoffs, define implicitly using the Bellman equation, for all si ∈ S:W (ρ, γ, si) = (1− δ)u(ρ(si), γ(si))+ δK∑k=1Pkk′(ρ(si) + γ(si))W (ρ, γ, sk),the discounted expected payoff from playing ρ if the opponent plays γ.Fixing the profile ρ, γ, one can also use the vector formW =[W (ρ, γ, s1), ...,W (ρ, γ, sK)]⊤,U =[u(ρ(s1), γ(s1)), ..., u(ρ(sK), γ(sK))]⊤,to writeW = (1− δ)U + δTW ⇐⇒W = [IK − δT ]−1 (1− δ)U,where T = (Pkk′)k,k′∈{1,...,K} is the Markov transition matrix given a fixed profile ρ, γ.Remark 5. The inverse of IK − δT exists and has all elements non-negative for all δ < 1,since it is an M−matrix.96C.2. ExtensionsCorollary 5. The derivatives of vector W can be written as, for i ≤ K < j:Wi = [IK − δT ]−1 δ ∂T∂ρiW + [IK − δT ]−1 (1− δ)∂U∂ρiWj = [IK − δT ]−1 δ ∂T∂γj−KW + [IK − δT ]−1 (1− δ) ∂U∂γj−KWii = [IK − δT ]−1 δ ∂2T(∂ρi)2W + [IK − δT ]−1 (1− δ) ∂2U(∂ρi)2− 2 [IK − δT ]−1 δ ∂T∂ρiWiWij = [IK − δT ]−1 δ ∂2T∂ρi∂γj−KW + [IK − δT ]−1 (1− δ) ∂2U∂ρi∂γj−K+ [IK − δT ]−1 δ ∂T∂γj−KWi + [IK − δT ]−1 δ ∂T∂ρiWj .Proof. This follows from some matrix algebra, importantly using the following fact:For a matrix function X of variable y, let ∂X be the partial derivative of X with respect to y.Then ∂(X−1) = −(X−1)(∂X)(X−1).If Wi = 0, one can further simplify this, using the fact that T depends only on aggregatequantities in each state.Wj = [IK − δT ]−1 (1− δ)[ ∂U∂γj−K− ∂U∂ρj−K]Wii = [IK − δT ]−1 δ ∂2T(∂ρi)2W + [IK − δT ]−1 (1− δ) ∂2U(∂ρi)2Wij = [IK − δT ]−1 δ ∂2T∂ρi∂γj−KW + [IK − δT ]−1 (1− δ) ∂2U∂ρi∂γj−K+ [IK − δT ]−1 δ ∂T∂ρiWj .(C.8)We can now prove some results for the asymptotic stability of specific types of strategyprofiles, for specific types of general state spaces. To do this, we need auxiliary results on thecharacterization of eigenvalues for general state spaces. The following lemmas will help withthis:Lemma 11. Suppose we have a square matrix A ∈ Rn×n that can be written as A = aIn +B,for some a ∈ R, whereB =[b1ιn, ..., bnιn],97C.2. Extensionswhere ιn is a vector of n ones, so that B is a matrix of columns of constants b1, ..., bn.Then the eigenvalues of A area with algebraic multiplicity n− 1;a+n∑k=1bk with algebraic multiplicity 1.Proof. Firstly, write A = aIn + ιnb⊤, where b⊤ = (b1, ..., bn), with superscript ⊤ denoting thetranspose. By the matrix determinant lemma, for any λ ∈ R writedet(A− λIn)= det((a− λ)In)+ v⊤adj((a− λ)In)ιn,where adj(A) is the adjoint of matrix A. Using that by definition, Aadj(A) = det(A)In, we getthatdet(A− λIn)=(a− λ)n + v⊤(a− λ)n−1ιn=(a− λ)n−1[a− λ+ n∑k=1bk],and the result follows.Lemma 12. Suppose M ∈ Rn×n s.t.M =[M1 M2M3 M4]is a matrix consisting of blocks Mi. For m, k s.t. m+ k = n, suppose we can write those blocksasM1 = a1Im + ιma⊤2 ; M2 =ιmb⊤M3 = ιkc⊤; M4 =d1Ik + ιkd⊤2 .We assume a1, d1 are nonzero scalars, and a2, c vectors in Rm, and d2, b vectors in Rk.98C.2. ExtensionsThen the set of eigenvalues of M , eig(M) = {λ1, ..., λK}, is s.t.λ1 = a1 with algebraic multiplicity: m− 1,λ2 = d1 with algebraic multiplicity: k − 1,λ3,4 =p2±√p24− q,wherep = a1 + d1 + a⊤2 ιm + d⊤2 ιk;q =(b⊤ιk)(c⊤ιm).Proof. For λ /∈ eig(M4), one can use the Schur-complement to write the characteristic equationof M asdet[M − λIn] = det[M4 − λIk]det[M1 − λIm −M2(M4 − λIk)−1M3]. (C.9)Then use the special form of all these blocks. First, note that one can apply the matrix-determinant lemma to getdet(M4 − λIk)= (d1 − λ)k + d⊤2 (d1 − λ)k−1Ikιk= (d1 − λ)k−1[d1 − λ+ d⊤2 ιk].Then one can apply the Sherman-Morrison formula to get(M4 − λIk)−1= (d1 − λ)−1Ik − (d1 − λ)−2ιkd⊤21 + (d1 − λ)−1d⊤2 ιk= (d1 − λ)−1[Ik − ιkd⊤2(d1 − λ+ d⊤2 ιk)−1].So we getM2(M4 − λIk)−1M3 = (d1 − λ)−1[ιmb⊤ιkc⊤ −M2ιkd⊤2M3(d1 − λ+ d⊤2 ιk)−1]=b⊤ιkd1 − λ+ d⊤2 ιkιmc⊤.99C.2. ExtensionsIt follows that one can write, by the matrix determinant lemma,det[M1 − λIm −M2(M4 − λIk)−1M3]= (a1 − λ)m +[a⊤2 −b⊤ιkd1 − λ+ d⊤2 ιkc⊤](a1 − λ)m−1Imιm= (a1 − λ)m−1[a1 − λ+ a⊤2 ιm −(b⊤ιk)(c⊤ιm)d1 − λ+ d⊤2 ιk].Plugging these results into (C.9), we getdet[M − λIn] = (a1 − λ)m−1(d1 − λ)k−1[(a1 − λ+ a⊤2 ιm)(d1 − λ+ d⊤2 ιk)− (b⊤ιk)(c⊤ιm)].The result then follows from finding all roots λ of the above.One-Recall with Many PricesNow consider public one-recall strategies in a game with arbitrarily many prices. First recall theexample game with binary prices and quantity choice q in interval X, with the usual expectedCournot payoffs, given some cost function c. For the resulting payoff functions ui(qi, q9i) andset of players N , call this game Γ∗ = ⟨ui, N⟩.Now consider an enlarged game with K ≥ 2 possible price outcomes, Y ∈ P = {P1, ..., PK},quantity choice q in interval X. Let the cost function c be the same as in Γ∗. For the resultingpayoff functions ui(qi, q9i) and set of players N , call this the enlarged game ΓE = ⟨ui, N⟩, whereenlargement happened only with respect to the possible set of price observations. Throughout,we assume hk(Q) = P[P = Pk |Q] > 0 for all k,Q.In our enlarged Cournot game ΓE , a public one-recall strategy (1R - strategy) can be definedas policy ρ : P 7→ X, so that states are price realizations representing last period’s observedprice. See Definition 8. We show in the following that the insight of corollary 3 can be madein the enlarged game of arbitrarily many price outcomes.Proposition 8. Take ΓE and let ρN be the 1R-policy that plays stage game Nash quantity qNin every state. Then ρN is asymptotically stable if and only if qN is.Proof. To determine the stability of ρN , we need to compute the eigenvalues of the linearizedP -state-dependent best-response dynamics (FPB ) at ρN . As shown in lemma 10, one can equiv-alently consider the eigenvalues of the gradient of the best response in P-statespace at ρN .100C.2. ExtensionsSince by assumption, states are irreducible (i.e. for every aggregate quantity Q, every pricehas positive probability of occurring after finite time), one can fix an arbitrary initial state s1(which in the case of this 1R-policy corresponds to an arbitrary price in P) when computingfirst order conditions to compute best responses. The implicit function theorem and (C.8) canthen be used to find this gradient of the best response.First, write Wij = Wij(s1) for all i ≤ K, j ≤ 2K. Then one can write the Hessian asH = diag(Wii), the diagonal matrix having the second derivatives Wii,i=1,...,K on the diagonal.H is diagonal by the derivation of Wi: writeWi = [IK − δT ]−1[δ∂T∂ρiW + (1− δ)∂U∂ρi].Then, taking another derivative with respect to a variable j ≤ K :Wij =(∂ [IK − δT ]−1)[IK − δT ]Wi+ [IK − δT ]−1[δ∂2T∂ρi∂ρjW + (1− δ) ∂2U∂ρi∂ρj].Notice that ∂2T∂ρi∂ρj, ∂2U∂ρi∂ρjare matrices of all zeros if i ̸= j and i, j ≤ K. Then plugging in thatWi = 0, we get that indeed Wij = 0 whenever i ̸= j and i, j ≤ K. So H must be diagonal.Now define R = [Wij ]i≤K<j as the matrix cross derivatives between an agents own strategyρ(si) and an opponent’s strategy γ(sj−K). Then define, using the implicit function theorem,the best response derivative matrix asM = −H−1R.Since we evaluate this at ρN , one can make multiple observations that will greatly simplifythe structure of M :Firstly, long term payoffs W = UN, since ρN prescribes the same action in each state.Secondly, by the nature of qN ,∂U∂ρi= 0 for all i ≤ K.Now note that since by definition each row of T sums to one, and therefore each row of ∂T∂ρiand ∂2T∂ρi∂ρjmust sum to zero. Therefore, at ρN , one can simplify the elements of H,R to101C.2. ExtensionsWii = [IK − δT ]−11 (1− δ)∂2U(∂ρi)2,Wij = [IK − δT ]−11 (1− δ)[∂2U∂ρi∂γj−K+ δ∂T∂ρi[IK − δT ]−1 ∂U∂γj−K],where for any matrix A we write Xi as the i’th row of A. Let ei be the K-vector that isone in entry i, and zero in all others. Using the fact that ρN is constant for all states, one canwrite this down in the more simple formWii = [IK − δT ]−11 (1− δ)uN11ei,Wij = [IK − δT ]−11 (1− δ)[uN12ei + δ∂T∂ρi[IK − δT ]−1 uN2 ei],if i = j −K, andWij = [IK − δT ]−11 (1− δ)[δ∂T∂ρi[IK − δT ]−1 uN2 ej−K],otherwise, following the notation used in chapter 4.Now again since ρN is constant for all states, one can write T = ιKp⊤, where p⊤ =(Pr1, ..., P rK) is a column-vector of the probability of observing each price k = 1, ..,K givenaggregate quantity choice 2qN . In that case, one can use the Sherman-Morrison formula toderive the inverse[IK − δT ]−1 = IK + δ1− δ ιKp⊤,implying that each of row of [IK − δT ]−1 sums to 11−δ .It follows thatWii = δuN11Pri for all 1 < i ≤ K, andW11 = uN11[1−δ+δPr1]. The differencefor index i reflects the fact that we fixed initial state 1. We can thus write the Hessian asH = uN11[(1− δ)e1 + diag(δPri)]. Going step-by-step, we get[IK − δT ]−1 uN2 ej−K = uN2[ej−K +δ1− δPrj−KιK],so that102C.2. Extensions[IK − δT ]−11 (1− δ)δ∂T∂ρi[IK − δT ]−1 uN2 ej−K=δ2uN2 PriPr′j if i > 1δ[1− δ + δPri]uN2 Pr′j otherwise ,again using that (∂p)⊤ιK = 0 by definition. Finally, when taking the ratio H−1R, one cansee that difference for row i = 1 to other rows does not matter since the factors are cancelledcorrectly between H and R, so that we getWijWii=δuN2 Pr′juN11if j −K ̸= i,uN12uN11+δuN2 Pr′juN11otherwise.We can use this to writeM = −uN12uN11IK +B,where B = [b1, ..., bK ] is a matrix of column vectors of constants: bj = − δuN2 Pr′juN11ιK .Finally, one can apply lemma 11 to find the eigenvalues of M . We immediately get n − 1eigenvalues equal −uN12uN11, which equals the eigenvalue of the static Nash equilibrium qN . For thelast eigenvalue, recall (∂p)⊤ιK = 0, so it collapses to −uN12uN11as well, and we are done.Generalizing S∗I show here that the insights one can gain from a binary-price game with collusive equilibriumbased on binary state variable S∗ hold more generally, i.e. do not depend crucially on thebinary restriction.First, recall that we refer to the binary price game as analyzed in chapter 4 Γ∗ = ⟨ui, N⟩.Define the binary state variable S∗ = {A,B} and binary price outcome Y ∈ {PL, PH} as inchapter 4.We say that (qA, qB) is a binary state equilibrium if the policy σ∗ : S∗ 7→ X is such thatσ∗(A) = qA, σ∗(B) = qB (i.e. it is an S∗-policy) and is a best reply to itself, with the objectivebeing long term discounted expected profits. We let H(Qs) = P[PL|Qs] for s ∈ S∗.103C.2. ExtensionsRecall that we refer to the enlarged game as ΓE , where enlargement was done with respectto the number of possible price realizations. Throughout, we assume hk(Q) = P[P = Pk |Q] > 0for all k,Q.Define two binary partitions of P:PA = {PAL , PAH}; PB = {PBL , PBH }.Note that for the sake of our argument, these partitions don’t have to be monotone.Given PA,PB, define the enlarged state space SE = {s1, ..., sL} for L ≥ 2 and give a binarypartition of this state space as SE = SAE ∪ SBE . Let SAE be indexed as {s1, ..., sl}, l < L. Statesin this enlarged state space evolve with the following state transition T : SE ×P 7→ SE :T (s, P ) ∈SAE if s ∈ SAE ∧ P ∈ PAHSAE if s ∈ SBE ∧ P ∈ PALSBE if s ∈ SAE ∧ P ∈ PBLSBE if s ∈ SBE ∧ P ∈ PBH, (C.10)where importantly, the transition within SAE , SBE will not matter for our result, so one can beagnostic about it.Let F (Q, s) = P[s′ ∈ SAE |Q, s] be the probability of transitioning into some state in SAE ,conditional on aggregate quantity Q and current state s.Define policy ρ∗ : SE 7→ X as a policy that plays only two quantities given the enlargedstate space: ρ∗(s) = qA for all s ∈ SAE , and ρ∗(s) = qB for all s ∈ SBE . Generally we call policieson SE-domain SE-policies, and call them binary SE-policies if they are defined as ρ∗ is. We calla profile of them SE-equilibrium if they are best replies to each other, again under the objectiveof long term discounted expected payoffs.Firstly, one should think of states s ∈ SAE as collusive states (low quantity), and others aspunishment states. Going back to the original, binary state and price equilibrium, this is theintuitive connection to S∗.It is interesting to note that for the following reduction result, it does not matter howexactly the state transition maps within SAE , SBE . All that matters is the probability, given acurrent state s, to map into any future state s ∈ SAE .We say that aggregate transition probability F (Q, s) and binary probability function h are104C.2. Extensionsmatching ifF (Q, s) =1−H(Q) if s ∈ SAEH(Q) if s ∈ SBEF ′(Q, si) =−H ′(Q) if s ∈ SAEH ′(Q) if s ∈ SBEF ′′(Q, si) =−H ′′(Q) if s ∈ SAEH ′′(Q) if s ∈ SBEfor all Q, where for any function f(Q), f ′, f ′′ represent first and second derivatives with respectto Q.Finally, to connect payoff functions between Γ∗ and ΓE , we need to verify the followingproperty:Let P (Q) = H(Q)PL + (1 −H(Q))PH and PE(Q) =∑Kk=1 hk(Q)Pk be the expected pricefunctions for the two games respectively. Then if P (Q) = PE(Q), P′(Q) = P ′E(Q), P′′(Q) =P ′′E(Q) holds for all Q, we say that P, PE are matching. Notice that starting from a binary pricegame, one can always find a game with many prices so that P, PE are matching by defininghk(Q) =1Kh(Q) for all k < K, with hK(Q) pinned down as the residual probability. However,there is a restriction from the other direction: given a game of many prices, there may not bea binary pair of prices PL, PH so that P (Q), PE(Q) can match.Proposition 9. hh1. Suppose S∗-policy σ∗ is a binary state equilibrium. For any enlarged state space SEand partitions PA,PB given set of prices P, define the binary SE policy ρ∗. Then ifF (Q, s), H(Q) and P (Q), PE(Q) are matching, ρ∗ is an SE-equilibrium.2. Conversely, take an enlarged state space SE with set of prices P and partitions PA,PB,and binary strategy ρ∗ that is an SE-equilibrium. If one can find h(Q), PL, PH such thatF (Q, s), H(Q) and P (Q), PE(Q) are matching, then S∗-policy σ∗ is an S∗-equilibrium.3. σ∗ is asymptotically stable if ρ∗ is asymptotically stable. If in addition u11(q, q)+u12(q, q) ≤0 for all q ∈ X (concavity along the 45 degree line), then ρ∗ is asymptotically stable if σ∗105C.3. Proofsis asymptotically stable.Corollary 6. Take a pair Γ∗,ΓE with partitions PA,PB and SE so that F (Q, s), H(Q) andP (Q), PE(Q) are matching.1. Then qN is a static Nash equilibrium of Γ∗ if and only if it is a static Nash equilibriumof ΓE.2. qN is statically asymptotically stable for Γ∗ if and only if it is statically asymptoticallystable for ΓE.3. Let σN , ρN be the S∗, SE strategies respectively playing qN in all states. σN is asymptoti-cally stable if and only if ρN is.Proof. Points (1, 2) follow since for determining static equilibria, players only care about ex-pected prices P (Q), and for stability, all we need is matching first and second derivatives at theequilibrium points.Point (3) follows from the proof of proposition 9, point (3).Remark 6. Proposition 9 includes the scenario where P = {PL, PH}, and SE = S∗ × S¯, forany arbitrary finite S¯. Then SAE , SBE can be constructed intuitively and resulting F (Q, s) mustbe matching with H, so the result from proposition 9 applies.C.3 ProofsProof of Lemma 2First, let Q = q1 + q2 and writeu1(q, q2) = P (Q) + P′(Q)q − c′(q);u12(q, q2) = P′(Q) + P ′′(Q)q;u11(q, q2) = 2P′(Q) + P ′′(Q)q − c′′(q) = u12(q, q2) + P ′(Q)− c′′(q).From the above we see that since P ′ < 0, c′′ > 0, we always have u11(q, q2) < u12(q, q2).Definition 7 implies that u1(0, q2) strictly decreases over q2 ∈ X so that there exists uniqueM∗ < 2K with u1(0,M∗) = 0. For q2 ≤ 2K, (iv) implies that u12(q, q2) < 0 for all q ∈[0, 2K − q2]. It follows that u1(0, q2) > 0 for all q2 < M∗ and for all such q2 there mustbe a unique q∗(q2) < 2K − q2 s.t. u1(q∗(q2), q2) = 0. In addition, u1(q, q2) > 0 for q ∈106C.3. Proofs[0, q∗(q2)) and u1(q, q2) < 0 for q ∈ (q∗(q2), 2K − q2]. Also note that u1(q, q2) < 0 for allq ∈ [max{0, 2K − q2},M ] since u1(0, 2K) < 0.We can conclude from this that for all q2 ∈ X there is a unique best response q∗(q2) that ispinned down by first order conditions whenever q2 ≤M∗, and equals zero otherwise.Whenever q2 ≤ M∗, it must be that u11(q∗(q2), q2) < 0 since q∗(q2) + q2 < 2K and byconvexity of c. It follows that we can find the derivative of the best response in q2 for allq2 < M∗ by the implicit function theorem, which allows us to show∂q∗(q2)∂q2= −u12(q∗(q2), q2)u11(q∗(q2), q2)∈ (−1, 0),since 0 > u12(q∗(q2), q2) > u11(q∗(q2), q2) must hold. Finally, for there to be a unique interiorNash equilibrium, we only need the following boundary condition to be satisfied: q∗(0) < M∗.In that case, 0 is not a best response to the monopoly quantity q∗(0). This together with thefact that ∂q∗(q2)∂q2∈ (0,−1) for all q2 < M∗ implies that there must be a unique interior Nashequilibrium (one can see this by imagining the best response and inverse best response plottedin 2D). It must be symmetric, since the payoff functions (and therefore best response functions)are symmetric.Static stability of this equilibrium (i.e. w.r.t. FS0B ) follows from the eigenvalues of thelinearization of FS0B (qN ). A detailed exposition can be found in appendix C.1. The relevantcondition for stability comes down to ∂q∗(q2)∂q2∈ (−1, 0), which we have shown above. Theintuition in the static case is can be exemplified in the following way: suppose 2’s strategy isperturbed from qN by a small amount, and players apply best responses to adjust thereafter.Then the best-response derivative tells us that 1 would react by moving in the opposite direction,but always by an amount smaller than the initial perturbation of 2. Continuing, 2 must reactto 1’s reaction again by moving in the opposite direction, and by a smaller amount than 1. Theresult is the well known cobweb-like path back to the Nash equilibrium.■Proof of Proposition 4First, we prove that given G, u can be regular:Lemma 13. Suppose h ∈ G. Then there exist parameters PH > PL ≥ 0 and a convex costfunction c(q) such that the resulting stage game payoffs u(q1, q2) are regular.Proof. By definition of G, ∃!D ∈ (τ, M2 ) such that −h′′= h′(2D)D . Since h is strictly increasing,107C.3. Proofsthere exist PH > 0 >(PL − PH)such thath(0) <PH−(PL − PH) < h(2D). (C.11)Recall that, for any cost function c(q),u1(q, q) = PH +(PL − PH)h(2q) +(PL − PH)h′(2q)q − c′(q),and therefore the above implies that there exists a c(q) such that u1(0, D) < 0 < u1(0, 0)(pinned down only by c′(0)). Then since u1(0, qˆ) strictly decreases in qˆ ∈ [0,M ], there existsa unique M∗ ∈ (0, 2D) such that u1(0,M∗) = 0. Finally, to check whether Definition 7 (iv)holds, note thatP ′(q + qˆ) + qP ′′(q + qˆ) =(PL − PH)(h′(q + qˆ) + h′′(q + qˆ)q),P ′(q + qˆ) + qP ′′(q + qˆ) ≤ 0 holds for all q + qˆ ≤ 2τ , since h′′(q + qˆ) ≥ 0 then. By definition ofG, we get0 =(h′(2D) + h′′D) ≤ (h′(Q) + h′′(Q)q),holds for all q ∈ [τ,D] and Q ∈ [2τ, 2D], since h′(Q) is decreasing on that interval. The resultfollows.Now we need the following observations based on the definition of W in (3.3):108C.3. ProofsW1 = ω−1(1− δPBB)[ω−1δP ′AB(uB − uA) + uA1],W2 = ω−1(δPAB)[ω−1δP ′BB(uB − uA) + uB1],W11 = −2ω−1δP ′ABW1 + ω−1(1− δPBB)[ω−1δP ′′AB(uB − uA) + uA11],W22 = 2ω−1δP ′BBW2 + ω−1(δPAB)[ω−1δP ′′BB(uB − uA) + uB11],W12 = ω−1δ[P ′AB1− δPBBδPABW2 − P ′BBδPAB1− δPBBW1],W13 =W11 + ω−1(1− δPBB)[ω−1δP ′AB(uA1 − uA2 ) + uA12 − uA11],W24 =W22 + ω−1(δPAB)[ω−1δP ′BB(uB2 − uB1 ) + uB12 − uB11],W14 = −ω−1δP ′BBδPAB1− δPBBW1 + ω−1(1− δPBB)ω−1δP ′AB[ω−1δP ′BB(uB − uA) + uB2]=W12 + ω−1(1− δPBB)ω−1δP ′AB(uB2 − uB1 ),W23 = ω−1δP ′AB1− δPBBδPABW2 − ω−1(δPAB)ω−1δP ′BB[ω−1δP ′AB(uB − uA) + uA2]=W12 + ω−1(δPAB)ω−1δP ′BB(uA1 − uA2 ).(C.12)Then, an optimal, non-degenerate, interior strategy α∗ must satisfyW1(α∗, β) = 0 ⇐⇒ ω−1δP ′AB(uB − uA) + uA1 = 0,W2(α∗, β) = 0 ⇐⇒ ω−1δP ′BB(uB − uA) + uB1 = 0,W11(α∗, β) < 0 ⇐⇒ ω−1δP ′′AB(uB − uA) + uA11 < 0,W22(α∗, β) < 0 ⇐⇒ ω−1δP ′′BB(uB − uA) + uB11 < 0.Notice that for all such α∗, we also have W12(α∗, β) = 0. This follows under irreducibility,since then initial states do not affect the optimal policy choice. If a policy is optimal, it mustbe optimal given any starting state s, and therefore one can characterize it through FOCsequivalently for any starting s.We now prove some helpful lemmas. First, to save notation, let ∆ = PL − PH .Lemma 14. Suppose h ∈ G andh(2τ) + h′(2τ)τ < h(2D).109C.3. ProofsThen for all neighborhoods N of τ there exist PH > 0 > ∆ and a convex c(q) such that qN ∈ N .In particular, there exist PH > 0 > ∆ and a convex c(q) such that qN = τ .Proof. As argued in lemma 13, there exist PH > 0 > ∆ and a convex c(q) such thath(0) < h(2τ) + h′(2τ)τ <PH − c′(0)−∆ < h(2D).Thus the same arguments as in lemma 13 can be applied to see that there is still a uniqueqN Nash equilibrium. We haven’t made any assumptions on c(q) except for convexity and thepossible range of c′(0). If we pick c′(τ) > c′(0) such thath(2τ) + h′(2τ)τ =PH − c′(τ)−∆ ,it follows that u1(τ, τ) = 0, i.e. qN = τ . The result follows.We can use lemma 14 to make our analysis cleaner. As long as h satisfies the condition ofthe lemma, qN can be treated as a primitive of the model, replacing τ .Lemma 15. Suppose h ∈ G and PH > 0 > ∆ and a convex cost function c(q) such that lemma13 holds. Then for all qˆ ∈ [0,M∗] there exists a unique q∗(qˆ) ∈ [0,M∗] such thatu1(q∗(qˆ), qˆ) = 0.If in addition h′(0) = h′(M) = 0 andh(2τ) + h′(2τ)τ < h(2D),and for all q ∈ [D,M ],3∆h′(2q) + 2∆h′′(2q)q ≤ c′′(q),then there exist PH > 0 > ∆ and a convex c(q) that satisfy lemma 13 such that• For all q ∈ (0, qN ] there exists a unique qˆ ∈ [qN ,M) such thatu1(q, q)h′(2q)+u1(qˆ, qˆ)h′(2qˆ)= 0.110C.3. Proofs• For all q, qˆ ∈ (0,M)u1(q, qˆ)h′(q + qˆ)− u1(qˆ, qˆ)h′(2qˆ)has a unique zero at q = qˆ .Proof. For the first claim, recall from the proof of lemma 13 that qˆ ≤ M∗ < 2D implies thatu11(q, qˆ) < 0 for all q ∈ [0, 2D− qˆ] by definition of G. Then, by construction of M∗, u1(0, qˆ) > 0holds for all qˆ ∈ [0,M∗). Additionally, u1(q, qˆ) < 0 holds for all q ∈ [2D − qˆ,M ], and theremust be a unique zero q∗(qˆ) ∈ (0, D − qˆ).For the second claim, recall from lemma 13 that u1(q, q) is strictly decreasing for all q ∈[0, D]. From lemma 14 we get that we can take qN arbitrarily close to τ . First, let us fixPH ,∆, c′(τ) so that qN = τ . We also have that h′(2q) is strictly increasing for q ∈ [0, qN ), andstrictly decreasing for q ∈ (qN ,M ]. Finally, we have that u1(qN , qN ) = 0, so that the fractionmust be strictly decreasing for q ∈ [0, D]. Note that we have so far only imposed two pointconditions on convex c(q), for c′(0), c′(τ). By assumption of the lemma, for all q ∈ [D,M ],3∆h′(2q) + 2∆h′′(2q)q ≤ c′′(q)then we have that u11(q, q)+u12(q, q) ≤ 0 for all q ∈ [0,M ] and the fraction u1(q,q)h′(2q) is monotonein q. Then, recall h′(0) = h′(M) = 0. So for any q > 0, no matter how close to 0, we can findqˆ ∈ (qN ,M) so that the claim holds: increasing qˆ to M would send the fraction to −∞ afterall.For the third claim, consider three cases:Case 1: qˆ ≤ qN .Notice that qˆ < qN implies u1(qˆ, qˆ) > 0, and as shown for the first claim, u1(q, qˆ) is monotonedecreasing on the candidate solutions q ∈ [0, q∗(qˆ)). But by construction,u1(2qN − qˆ, qˆ) = PH +∆h(2qN ) + ∆h′(2qN )(2qN − qˆ)− c′(2qN − qˆ)= ∆h′(2qN )(qN − qˆ) + c′(qN )− c′(2qN − qˆ) < 0,and thus it must be that q∗(qˆ) + qˆ < 2qN . Thus,u1(q,qˆ)h′(q+qˆ) is strictly decreasing on q ∈ (0, q∗(qˆ)).By monotonicity, there can only be one solution, q = qˆ.Case 2: qˆ ∈ (qN , D].Firstly, consider q ∈ [q∗(qˆ), qˆ]. No smaller q is a candidate, since u1 would change sign. Firstly,in case qˆ ≤ QN , u1(q,qˆ)h′(q+qˆ) is strictly decreasing on q ∈ (q∗(qˆ), QN− qˆ]. That is because, for all such111C.3. Proofsq, qˆ, h′′(q + qˆ) ≥ 0 holds. Then take q ∈ (max{0, QN − qˆ}, D]. By definition of D, u11(q, qˆ) < 0for all such q and we get that u1(q,qˆ)h′(q+qˆ) is further strictly decreasing on q ∈ (max{0, QN − qˆ}, D].Now suppose that M∗ > D, and consider q ∈ (D,M∗ − qˆ]. Then, as shown in the proof oflemma 13, u11(q, qˆ) < 0 for all such q, qˆ and the fraction is monotone still.Finally, notice that we can writeu1(q, qˆ)h′(q + qˆ)=PH +∆h(q + qˆ)− c′(q)h′(q + qˆ)+ ∆q. (C.13)Recall by definition of M∗ < 2D, we have PH + ∆h(q + qˆ) − c′(q) < 0 for all q ∈ [0,M ] ifq + qˆ ≥M∗. So we can write∂ u1(q,qˆ)h′(q+qˆ)∂q=[∆h′(q + qˆ)− c′′(q)]h′(q + qˆ)− h′′(q + qˆ)(PH +∆h(q + qˆ)− c′(q))h′(q + qˆ)2+∆,which is negative whenever q + qˆ ≥ M∗. So both in the case where D > M∗, and whenconsidering q ∈ (M∗ − qˆ,M ], we still have that u1(q,qˆ)h′(q+qˆ) is strictly decreasing. All together, itfollows that, for any qˆ ∈ (qN , D], u1(q,qˆ)h′(q+qˆ) is strictly decreasing for q ∈ [q∗(qˆ),M ], as required.Case 3: qˆ ∈ (M∗,M ].Taking equation (C.13) and the above argument together implies that again, u1(q,qˆ)h′(q+qˆ) is strictlydecreasing, for any q ∈ [0,M ], since M∗ > QN holds (i.e. h′′(q + qˆ) ≤ 0). The claim follows.Note that, by assumption, uij , h′′ are continuous for all i, j,∈ {1, 2} in all their arguments.We can therefore find a neighborhood N ′ of τ such that for all PH > 0 > ∆ and a convex c(q)that give qN ∈ N ′, the lemma still goes through.Now for the proof of the proposition:Assume, as in lemma 15, that h′(0) = h′(M) = 0 andh(2τ) + h′(2τ)τ < h(2D).Firstly, note that finding interior σ such that W1(σ) = W2(σ) = 0 is equivalent to finding σsuch thatW1(σ) = 0;uA1h′(QA)+uB1h′(QB)= 0.From now on, to save notation, I write hs to denote evaluation of h() at qs, s ∈ {A,B,N}. By112C.3. Proofslemma 15 we have that for any qA ∈ (0, qN ] there exists a unique qB ∈ [qN ,M) such thatuA1h′(QA)+uB1h′(QB)= 0.We will call such qB = z(qA). By strict monotonicity we can apply the implicit function theoremto getz′(qA) = −h′Bh′AuA11 + uA12 − 2h′′A uA1h′AuB11 + uB12 + 2h′′BuB1h′B. (C.14)It is then not surprising that at qN , z′(qN ) = −1. Now define Ψ(qA) =W1(qA, z(qA), qA, z(qA))as the first order condition of W with respect to qA, substituting in z(qA) so that at every qA,W2(qA, z(qA), qA, z(qA)) = W1(qA, z(qA), qA, z(qA)) must hold. Thus, any zero of Ψ(qA) mustset both first order conditions to zero.Since σN is always a solution, we have that Ψ(qN ) = 0, i.e. one zero always exists. We willnow show that for small q, Ψ(q) > 0 holds, while for large q, Ψ(q) < 0. The sufficient conditionstated in this proposition is then the condition ensuring Ψ′(qN ) > 0, which ensures that theremust be another zero with qA < qN .Firstly, recall that as in lemma 14 we have that, for q > 0 small enough, u1(q, q) > 0 musthold. Now consider Ψ(qA):Ψ(qA) > 0 ⇔ ω−1δh′(2qA)(uB − uA) + uA1 > 0.Then since h′(0) = 0 we get that the first term must be dominated by the second term forqA > 0 small enough, which is positive.Next, and analogously, take qA ∈ (qN ,M) to be large. In that case, we let y(qA) = z−1(qA) <qN be the inverse solution that equalizes first order conditions. Then if qA < M large enough,we get that the first term must be dominated by the second term since h′(M) = 0, and the113C.3. Proofssecond term is negative by definition of D < M . Finally, note thatΨ′(qN ) =WN11 +WN13 +WN14z′(qN ) =WN11 +WN13 −WN14= ω−1(1− δ(1− hN ))[uN11 + uN12 − ω−1δh′NuN2 + ω−1δh′NuN2 z′(qN )]= ω−1(1− δ(1− hN ))[uN11 + uN12 − 2ω−1δh′NuN2]= ω−1(1− δ(1− hN ))uN11[1 +uN12 − 2ω−1δh′NuN2uN11].Since uN11 < 0, we have Ψ′(qN ) > 0 if1 +uN12 − 2ω−1δh′NuN2uN11< 0⇔ 2ω−1δh′NuN2 − uN12 < uN11⇔ 2δh′NuN2 − ωuN12 < ωuN11⇔ 2δh′NuN2 − 2δhNuN12 < 2δhNuN11 + (1− δ)(uN12 + uN11).Thus we can write1 +uN12 − 2ω−1δh′NuN2uN11< 0⇔ h′N∆h′NqN − hN∆h′N < hN[2∆h′N − c′′N]+R1 +R2⇔ ∆h′N[h′NqN − 3hN]< −hNc′′N +R1 +R2,where R1 = 2∆hNqNh′′N vanishes for qN close enough to τ , and R2 =1−δ2δ (uN12 + uN11) vanishesas δ → 1. Then for δ < 1 close enough to 1 and qN close enough to τ , the condition stated inthe proposition is sufficient for Ψ′(qN ) > 0.This, together with Ψ(q) > 0 for q small, Ψ(q) < 0 for q large, allows us to use the intermediatevalue theorem. It gives us that there exists qA < qN < qB such that W1(σ) = W2(σ) = 0 forσ = (qA, qB, qA, qB).We are left to show that this zero is a global maximizer. Firstly, we note that the Hessian atσ must be negative definite: we see from (C.12) that W12 = 0, so the Hessian must be diagonalat σ. A sufficient condition for negative definiteness then is h′′A > 0 > h′′B and uA > uB. The114C.3. Proofsfirst one follows since qA < qN < qB, the second one follows from the first order conditions:W1 = 0 ⇒ uA − uB = ω uA1δh′(QA)> 0.Now we have that σ is a local max, and we can consider one-shot deviations to show that it isglobal. In state A, we need to show that(1− δ)u(qA, qA)+δ[WA + hA(WB −WA)]≥ (1− δ)u(q, qA) + δ[WA + h(q + qA)(WB −WA)],holds for all q ∈ SA. Equivalently, we can show that q = qA is the unique solution to the firstorder condition of this problem with respect to q, and that boundary conditions are satisfiedso that the maximizer can only be interior. Taking derivatives, we getHA(q, qA) = (1− δ)u1(q, qA) + δh′(q + qA)(WB −WA).By construction, HA(qA, qA) = 0.Since the Hessian is negative definite at qA, qA, HA1 (qA, qA) =∂HA(q,qA)∂q∣∣∣q=qA< 0. Recallthat in the proof of lemma 15 we showed that qA is the only solution to HA(q, qA) = 0,but also that u1(q,qA)h′(q+qA) is strictly decreasing over q ∈ [0, q∗(qA)]. Thus, HA(0, qA) > 0 andHA(M/2, qA) < 0 must hold and qA is globally optimal.Now, in state D we do the analogous argument, take derivatives to getHB(q, qB) = (1− δ)u1(q, qB)− δh′(q + qB)(WB −WA).Where again by the negative definite Hessian, we have HB1 (q, qB) < 0. Then in the proof oflemma 15 we show that u1(q,qA)h′(q+qA) is strictly decreasing over q ∈ [q∗(qB),M/2]. The result followsas above: qB is globally optimal.We have shown that playing σ = (qA, qB) is the unique best reply to an opponent playingσ, and thus σ is a symmetric equilibrium as required.■Proof of Corollary 4First, since we are restricting to symmetric equilibria, it is sufficient to consider two cases:uA ≶ uB.115C.3. Proofsi) uA > uB.Recall that state A corresponds to PL. As laid out in the proof of proposition 4, we can writean agent’s FOC for the problem of best responding in the following way:W1 = 0⇔ δh′(QA)ω(uA − uB)+ uA1 = 0;W2 = 0⇔ δh′(QB)ω(uA − uB)+ uB1 = 0,where we plug in the fact that PAB(Q) = 1 − h(Q). For both equations, the leading term isstrictly positive, since h′(Q) > 0 for all interior Q. It follows that us1 < 0 must hold for both s.In the proof of lemma 15 I show that for qN ∼ τ , (which we assume throughout, as inproposition 4), we have that u1(q,q)h′(2q) is strictly decreasing for all q ∈ [0,M ]. At the same time,u(q, q) is strictly decreasing when q ≥ qN , which is necessary for u1(q, q) < 0. Thus, for case (i)it must be that qA > qB, but sinceu1(q,q)h′(2q) is strictly decreasing, there exists no such pair qA, qBto set W1 =W2. It follows that no such pair can be an equilibrium.The case uA < uB follows from an analogous argument.■Proof of Proposition 5For point (i):Using Lipschitz properties implied by the differentiability of price distribution and stagegame payoffs, I will show that profile σK can at most violate incentive constraints of Γ∞ by anamount bounded by 1K .Recall that in this analysis, players are allowed to use a public randomization device tomake APS result’s applicable. Specifically, the public signal ζ used by players must satisfy (A2in APS): ζ ∈ Ω ⊆ Ra, for some a ≥ 1, being absolutely continuously distributed with p.d.fg(·, q), for all q ∈ X2.I will construct a public randomization device (PRD) that allows for players to both condi-tion actions on the realization of the price signal Y ∈ P = {PL, PH}, and the realization of thepublic randomization.Let Ω = [0, 1]. Call the PRD ζ, so that ζ is unconditionally uniform on [0, 1], but conditional116C.3. Proofson price realization, ζ will realize above or below a cutoff:Y = PL ⇒ g(z,Q) = 1Pr[PL | Q]1{z ∈ [0, P r[PL | Q]]}; (C.15)Y = PH ⇒ g(z,Q) = 1Pr[PH | Q]1{z ∈ [Pr[PL | Q], 1]}. (C.16)Thus, given Q, a realization of ζ below or above Pr[PL | Q] allows players to condition con-tinuation values on price realization, as well as conditional public randomizations. ζ satisfiesAPS’s assumptions A2, A3 by construction.Since σ¯K is a bang-bang profile, it is pinned down by two quantities qK , qK , and two binarypartitions of Ω. Pin those partitions down by specifying Ω ⊂ Ω,Ω ⊂ Ω in the following way:Whenever σK specifies to play qK in period t, realizing ζ ∈ Ω implies qK will be playedin t + 1, and whenever σK specifies to play qK in period t, realizing ζ ∈ Ω implies qK will beplayed in t+ 1. In keeping with APS’ construction and notation, let V K , V K be maximal andminimal values of SSEs in EK . Then we can write them asV K = (1− δ)u(qK , qK) + δ[V K +∫Ω(V K − V K)dz],V K = (1− δ)u(qK , qK) + δ[V K +∫Ω(V K − V K)dz].(C.17)We can use this to define incentive constraints through one-shot deviations, using (C.15):V K ≥ (1− δ)u(q′, qK)+ δ(V K − V K)[h(q′ + qK)∫Ω∩[0,h(q′+qK)]1h(q′ + qK)dz]+ δ(V K − V K)[(1− h(q′ + qK)) ∫Ω∩[h(q′+qK),1]11− h(q′ + qK)dz]holds for all q′ ∈ XK since σK ∈ EK . To see that σK is an ε-equilibrium of Γ∞, it suffices toshow that the right hand side above cannot grow too much by allowing for deviation in all ofX. One can bound the following:117C.3. Proofsmaxq′∈Xmaxq′K∈XK∣∣∣∣∣(1− δ)(u(q′, qK)− u(q′K , qK))+ δ(V K − V K)[ ∫Ω∩[0,h(q′+qK)]dz −∫Ω∩[0,h(q′K+qK)]dz]+ δ(V K − V K)[ ∫Ω∩[h(q′+qK),1]dz −∫Ω∩[h(q′K+qK),1]dz]∣∣∣∣∣which is bounded above bymaxq′∈Xmaxq′K∈XK{(1− δ)Lu|q′ − q′K |+ 2δ(V K − V K) ∫[m1,m2]dz}≤(1− δ)Lu 1K+ 2δ(V K − V K)Lh1K,where Lu, Lh are maximal Lipschitz constants for u, h, and with m1 = min{h(q′K + qK), h(q′ +qK)} and m2 = max{h(q′K+ qK), h(q′+ qK)}. The result follows: for any ε > 0, choose K largeenough so that the worst incentive violation can be bounded by ε. An analogous argumentholds for V K , qK .Point (ii) follows by construction of σ¯K .As for point (iii), using the PRD defined with (C.15), one can construct a binary statevariable that supports σ¯K . Define a state variable SK ∈ {A,B} such thatPAB(Q) = Pr[ζ ∈ Ω | Q],PBA(Q) = Pr[ζ ∈{Ω \ Ω} | Q]. (C.18)Then, using this state variable as the binary state underlying a binary policy ρ as in chapter4, it is quick to check that indeed W i(ρ, s) as defined in (4.1) represents long term expecteddiscounted payoffs when players follow a bang-bang strategy with q = ρ(A), q = ρ(B) andpartitions for a PRD support Ω,Ω. Then, when ρ(A), ρ(B) are chosen to equal qK , qK , theresulting profile will be a ε equilibrium of the game with long-run payoffs defined throughW i(ρ, s), by an argument analogous to the one above.■118C.3. ProofsProof of Proposition 9The proof is done for the case of two agents, but it is readily generalizable. For S∗-policies σ, σ′and SE-policies ρ, γ, implicitly defineW (ρ, γ, si) = (1− δ)u(ρ(si), γ(si))+ δL∑k=1P[sk | ρ(si) + γ(si), si]W (ρ, γ, sk),W˜ (σ, σ′, s) = (1− δ)u(σ(s), σ′(s))+ δ ∑s′∈S∗P[s′ |σ(s) + σ′(s), s]W˜ (σ, σ′, s′),as the long term expected payoffs for both repeated games ΓE ,Γ∗ respectively.Let W˜ be the long term payoff in the repeated version of Γ∗, i.e. where S∗- strategies arechosen. We proceed by proving the following lemmas:Lemma 16. Let σ∗, ρ∗ be policies as in the statement of proposition 9. ThenW (ρ∗, ρ∗, si) = W˜ (σ∗, σ∗, A) if i ≤ l,W (ρ∗, ρ∗, si) = W˜ (σ∗, σ∗, B) if i > l.Proof. First we show that W (ρ∗, ρ∗, si) = W (ρ∗, ρ∗, sj) if i, j ≤ l, and also if i, j > l. Bydefinition,W (ρ∗, ρ∗, si)−W (ρ∗, ρ∗, sj)= δL∑k=1(P[sk | ρ∗(si) + ρ∗(si), si]− P[sk | ρ∗(sj) + ρ∗(sj), sj])W (ρ∗, ρ∗, sk) = 0,since by construction ρ∗(si) = ρ∗(sj) if i, j ≤ l, and also if i, j > l, and by definition of T (s,Q).119C.3. ProofsHaving shown this, we can use the fact that F,H are matching to writeW (ρ∗, ρ∗, s1) = (1− δ)u(ρ∗(s1), ρ∗(s1))+ δL∑k=l+1P[sk | ρ∗(s1) + ρ∗(s1), s1]W (ρ∗, ρ∗, s1)+l∑k=1P[sk | ρ∗(s1) + ρ∗(s1), s1]W (ρ∗, ρ∗, sK)= (1− δ)u(ρ∗(s1), ρ∗(s1))+ δP[A |σ∗(A) + σ∗(A), A]W (ρ∗, ρ∗, s1) + δP[B |σ∗(A) + σ∗(A), A]W (ρ∗, ρ∗, sK),where we chose s1, sL arbitrarily due to the first result of this proof. Thus, W (ρ∗, ρ∗, si) fori ≤ l is the result of the same recursion as W˜ (σ, σ′, A), and the same holds for i > l and B.The result follows.Now suppose that σ∗ is an S∗- equilibrium and ρ∗ is the corresponding SE-policy. To showthat ρ∗ is an SE-equilibrium, it is sufficient to show that ρ∗ satisfies all one-shot deviations. Inother words, we need to show that, for all i, q ∈ XW (ρ∗, ρ∗, si) ≥ (1− δ)u(q, ρ∗(si))+ δL∑k=1P[sk | q + ρ∗(si), si]W (ρ∗, ρ∗, sk).By lemma 16, if i ≤ l we can re-write the above asW (ρ∗, ρ∗, si) ≥(1− δ)u(q, ρ∗(si))+δP[A | q + σ∗(A), A]W (ρ∗, ρ∗, s1)+P[B | q + σ∗(A), A]W (ρ∗, ρ∗, sK),⇐⇒ W˜ (σ∗, σ∗, A) ≥(1− δ)u(q, σ∗(A))+δP[A | q + σ∗(A), A]W˜ (σ∗, σ∗, A)+P[B | q + σ∗(A), A]W˜ (σ∗, σ∗, B),(C.19)which must be true since σ∗ is an S∗-equilibrium. Similarly, for i > l. Thus, ρ∗ must be anSE-equilibrium.For the other direction, suppose ρ∗ is an SE-equilibrium, and take σ∗ as the corresponding120C.3. ProofsS∗-policy as constructed in the statement of the proposition. By an argument analogous to theproof of lemma 16, we get that the statement of the lemma still goes through. But then we cando an argument analogous to (C.19) and the claim follows: σ∗ is an S∗-equilibrium.Finally, we will prove the claim about stability of the equilibria.We will continue similarly as in the proof of corollary 3. Recall that we assume throughoutthat P[s′ |Q, s] > 0 for all Q, s, s′. As in the proof of corollary 3, we can use (C.8) and it iswithout loss to consider Wij =Wij(s1) for all i ≤ L, j ≤ 2L when computing the matrix of bestresponse derivatives. We follow the notation in the proof of corollary 3:Now define R = [Wij ]i≤L<j as the matrix cross derivatives between an agent’s own strategyρ(si) and an opponent’s strategy γ(sj−L+1). Then we can define, using the implicit functiontheorem, the best response derivative matrix asM = −H−1R,where H = diag({Wii}i≤L) is the Hessian. We now show that we can apply lemma 12 to M .Definef⊤ =[IL − δT]−11∈ R1×L.Then note that for any matrix A(j) that is zero in all entries except in row j, we have thatf⊤A(j) = fja⊤,where a⊤ ∈ R1×L is the j’th row of A(j). With some abuse of notation, let Ti, Tii, Tij be thei′th rows of∂T∂ρi;∂2T∂ρi∂ρi;∂2T∂ρi∂ρj,respectively. It follows that we can write for all i ≤ LWii = δfiTiiW + (1− δ)fiu11(ρi, γi),And we can write for all i ≤ L < j ≤ 2L121C.3. ProofsWij =δfiTiiW + (1− δ)fiu12(ρi, γi) + δfiTiWj , if i = j − L+ 1;δfiTiWj , otherwise ,where we recall thatWj =[IL − δT]−1(1− δ)[∂U∂γj9L+1− ∂U∂ρj9L+1]= (1− δ)xj9L+1(u2(ρj9L+1, γj9L+1)− u1(ρj9L+1, γj9L+1)),where define xj ∈ RK×1 to be the j’th column of[IL − δT]−1.Now we can write for all i ≤ L < j ≤ 2L:WijWii=[δTiiW + (1− δ)u11(ρi, γi)]−1δTiiW + (1− δ)u12(ρi, γi)+(1− δ)δTixj9L+1(u2(ρj9L+1, γj9L+1)− u1(ρj9L+1, γj9L+1))if i = j 9 L+ 1;(1− δ)δTixj9L+1(u2(ρj9L+1, γj9L+1)−u1(ρj9L+1, γj9L+1))otherwise.Now, recall that by construction of the SE-policy, we have that W (i) = W˜ (σ∗, σ∗, A) for alli ≤ l, and W (i) = W˜ (σ∗, σ∗, A) for all i > l. To save notation, we write Vs = W (σ∗, σ∗, s) fors ∈ {A,B}.Next let us consider xj more closely. We can in fact compute the matrix[IK − δT]−1byusing the Sherman-Morrison formula twice.First, letps =(P[s1| 2qs], ...,P[sL| 2qs]),for s ∈ {A,B}. Then we can writeT =[ιl0m]p⊤A +[0lιm]p⊤B,122C.3. Proofswhere 0k is a k- vector of zeros and m = L− l. Now defineQ = IL − δ[ιl0m]p⊤A.So we can writeIL − δT = Q− δ[0lιm]p⊤B.Then by the Sherman-Morrison formula,Q−1 = IL +δ[ιl0m]p⊤A1− δ(1− hA) ,where we follow the notation of chapter 4 and write hs = h(2qs) for s ∈ {A,B}. and[IK − δT]−1= Q−1 +δQ−1δ[0lιm]p⊤BQ−11− δp⊤BQ−1[0lιm] .Re-writing things multiple times allows us to get to[IK − δT]−1= IL +[ιl0m]a⊤A +[0lιm]a⊤B,whereaA =δ(1− δ)ω[pA(1− δz + δ2hAhB1− δ(1− hA))+ δhApB];aB =δ(1− δ)ω[pAδhB + pB(1− δ(1− hA)),123C.3. Proofswhereω = 1 + δ(hA + hB − 1),z = 1− hB + δhBhA1− δ(1− hA) .Importantly, we have a⊤AιL = a⊤BιL =δ1−δ , so that f⊤ιL = 11−δ .Also notice that following the above representation, xj9L+1(i) = aA,j +1{i = j 9L+1} ∈ Rfor all i ≤ l, and xj9L+1(i) = aB,j + 1{i = j 9 L+ 1} ∈ R for all i > l.Thus,Tixj =∑l≤l PrA′l aA,j +∑l<l≤L PrA′l aB,j + PrA′j if i ≤ l∑l≤l PrB′l aA,j +∑l<l≤L PrB′l aB,j + PrB′j if i > l,where we save notation to write Prs′l =∂P[sj |q+qs]∂q∣∣∣q=qsfor s ∈ {A,B}. Using our informationon transitions for state space SE (C.10), we can further re-write this asTixj =h′(2qA)(aB,j − aA,j)+ PrA′j if i ≤ lh′(2qB)(aA,j − aB,j)+ PrB′j if i > l.Using the transition information, we can also writeTiiW =h′′(2qA)(VB − VA)if i ≤ l−h′′(2qB)(VB − VA)if i > l.Which then allows us to conclude, for i ≤ l:WijWii=[δh′′(2qA)(VB − VA)+ (1− δ)uA11]−1δh′′(2qA)(VB − VA)+ (1− δ)uA12+(1− δ)δ[h′(2qA)(aB,j9L+1 − aA,j9L+1)+ PrA′j9L+1](uA2 − uA1)if i = j 9 L+ 1;(1− δ)δ[h′(2qA)(aB,j9L+1 − aA,j9L+1)+ PrA′j9L+1](uA2 − uA1)otherwise,124C.3. Proofsand if i > l:WijWii=[δh′′(2qB)(VA − VB)+ (1− δ)uB11]−1δh′′(2qB)(VA − VB)+ (1− δ)uB12+(1− δ)δ[h′(2qB)(aA,j9L+1 − aB,j9L+1)+ PrB′j9L+1](uB2 − uB1)if i = j 9 L+ 1;(1− δ)δ[h′(2qB)(aA,j9L+1 − aB,j9L+1)+ PrB′j9L+1](uB2 − uB1)otherwise.Now following the notation in lemma 12 , leta1 = −[δh′′(2qA)(VB − VA)+ (1− δ)uA11]−1[δh′′(2qA)(VB − VA)+ (1− δ)uA12],d1 = −[δh′′(2qB)(VA − VB)+ (1− δ)uB11]−1[δh′′(2qB)(VA − VB)+ (1− δ)uB12].Then we can apply lemma 12 to M . To conclude, we need to compute the quantities givenin the lemma that pin down λ3,4.To do this, we will compute a⊤s ιl, and a⊤s[0lιm], for s ∈ {A,B}.bA = a⊤Aιl =δ(1− δ)ω[(1− hA)(1− δ(1− hA))+ δhAhB]=δ(ω − hA)(1− δ)ω ;bB = a⊤Bιl =δ(1− δ)ω[(1− hA)δhB + hB(1− δ(1− hA))]=δhB(1− δ)ω .Recalling that a⊤AιL = a⊤BιL =δ1−δ , we geta⊤A[0lιm]=δ1− δ − bA =δhA(1− δ)ω ;a⊤B[0lιm]=δ1− δ − bB =δ(ω − hB)(1− δ)ω .125C.3. ProofsIn the notation of lemma 12, we havea⊤2 ιl = −[δh′′(2qA)(VB − VA)+ (1− δ)uA11]−1(1− δ)δ(uA2 − uA1 )h′(2qA)[bB − bA − 1];c⊤ιl =[δh′′(2qB)(VA − VB)+ (1− δ)uB11]−1(1− δ)δ(uA2 − uA1 )h′(2qB)[bB − bA − 1];b⊤ιm =[δh′′(2qA)(VB − VA)+ (1− δ)uA11]−1(1− δ)δ(uB2 − uB1 )h′(2qA)[bB − bA − 1];d⊤2 ιm =[δh′′(2qB)(VA − VB)+ (1− δ)uB11]−1(1− δ)δ(uB2 − uB1 )h′(2qB)[bB − bA − 1].Finally, notice that1 + bA − bB = δ(1− δ)ω(ω − hA − hB)+ 1= ω−1.Recall J1(σ∗), the matrix of best response-derivatives for the S∗-collusive equilibrium σ∗.Take p, q from the definition of λ3,4 in lemma 12. Then putting all the derivation above together,some more re-writing reveals thatp = tr(J1(σ∗)), q = det(J1(σ∗)),where tr, det represent trace and determinant. It follows that λ3,4 equal the two eigenvalues ofJ1(σ∗).Thus, if σ∗ is unstable, ρ∗ must be unstable also. Finally, note that a1 ∈ (−1, 1) alwaysholds by construction of qA and definition of H. That is because qA < qN , and therefore0 ≥ uA12 > uA11.Since uB12 ≥ uB11 must hold, we always have d1 > −1. However, by definition of H it is126C.3. Proofspossible that uB12 ≥ 0, which means we need an additional assumption to ensure d1 < 1:d1 < 1⇔ uB11 − uB12 > 2(ω−1δh′′B(uA − uB)+ uB11)⇔ uB11 + uB12 < −2ω−1δh′′B(uA − uB)which holds if uB11 + uB12 ≤ 0. Thus, if as stated in the proposition u11(q, q) + u12(q, q) ≤ 0 forall q, we are done: d1 ∈ (−1, 1), so it cannot affect conclusions about stability of ρ∗.■127
Thesis/Dissertation
eng
Economics
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Li, Hao
Farinha Luz, Vitor
Algorithmic learning in games
Text