What modern game theorists describe as fictitious play is not the learning process George W. Brown defined in his 1951 paper. Brown's original version differs in a subtle detail, namely the order of belief updating. In this note we revive Brown's original fictitious play process and demonstrate that this seemingly innocent detail allows for an extremely simple and intuitive proof of convergence in an interesting and large class of games: nondegenerate ordinal potential games.

This dissertation studies multi-agent algorithms for learning Nash equilibrium strategies in games with many players. We focus our study on a set of learning dynamics in which agents seek to myopically optimize their next-stage utility given some forecast of opponent behavior; i.e., players act according to myopic best response dynamics. The prototypical algorithm in this class is the well-known fictitious play (FP) algorithm. FP dynamics are intuitively simple and can be seen as the \natural" learning dynamics associated with the Nash equilibrium concept. Accordingly, FP has received extensive study over the years and has been used in a variety of applications. Our contributions may be divided into two main research areas. First, we study fundamental properties of myopic best response (MBR) dynamics in large-scale games. We have three main contributions in this area. (i) We characterize the robustness of MBR dynamics to a class of perturbations common in real-world applications. (ii) We study FP dynamics in the important class of large-scale games known as potential games. We show that for almost all potential games and for almost all initial conditions, FP converges to a pure-strategy (deterministic) equilibrium. (iii) We develop tools to characterize the rate of convergence of MBR algorithms in potential games. In particular, we show that the rate of convergence of FP is \almost always" exponential in potential games. Our second research focus concerns implementation of MBR learning dynamics in large-scale games. MBR dynamics can be shown, theoretically, to converge to equilibrium strategies in important classes of large-scale games (e.g., potential games). However, despite theoretical convergence guarantees, MBR dynamics can be extremely impractical to implement in large games due to demanding requirements in terms of computational capacity, information overhead, communication infrastructure, and global synchronization. Using the aforementioned robustness result, we study practical methods to mitigate each of these issues. We place a special emphasis on studying algorithms that may be implemented in a network-based setting, i.e., a setting in which inter-agent communication is restricted to a (possibly sparse) overlaid communication graph. Within the network-based setting, we also study the use of so-called \inertia" in MBR algorithms as a tool for learning pure-strategy NE.

This dissertation studies three economic problems plagued by multiple equilibria. Indeterminacy of equilibrium outcome often poses a challenge in deriving robust predictions and policy guidance. The dissertation shows how the utilization of potential game theory can better deal with this challenge. Chapter 1 studies a general contracting problem between one principal and multiple agents. The interdependence of agents’ actions and payoffs creates a coordination problem among them, leading to multiple equilibria. In general, the principal’s optimal contracting scheme varies with how one selects among equilibria. Nevertheless, for a large class of contracting models where agents’ payoffs constitute a weighted potential game, I show that one contracting scheme is optimal for a large class of equilibrium selection criteria. This scheme ranks agents in increasing weight in the weighted potential game and induces them to accept their offers in a dominance-solvable way, starting from the first agent. I also apply the general results to networks and pure/impure public goods/bads. Chapter 2 studies two-sided markets, where two groups of agents interact via platforms. These markets exhibit network effects, i.e., the value of joining a platform increases with the number of users, which in turn lead to multiple equilibria. I show that many two-sided market models are weighted potential games, enabling the selection among equilibria by potential maximization—a refinement of Nash equilibrium justified by many theoretical and experimental studies. Under potential maximization, platforms often charge the side deriving more network benefits and subsidize the other side. Therefore, profit-maximizing platforms are often designed to favor the money side much more than the subsidy side. Chapter 3 studies markets with strong network effects. In these markets, firms compete for the adoption of all consumers rather than the marginal consumer. Therefore, the Spence distortion—a quality distortion driven by competition for the marginal consumer—should be absent, contradicting the findings in the network economics literature. This inconsistency stems from the choice of equilibrium selection criterion. I show that all popular selection criteria in that literature lead to Spence distortions, whereas potential maximization does not. Therefore, network market regulations based on Spence distortion arguments may be misguided.

The objectives of this research are to extend cooperative control methods based on potential games to dynamic environments and to develop an experimental test bed to illustrate theoretical results. Cooperative control concerns coordinating a collective performance of multiple autonomous agents. Possible applications include mobile sensor networks, distributed computation, and unmanned vehicle teams. Prior work has explored game theory, specifically the framework of potential games, as an approach to cooperative control, but has been restricted to static environments. This research shows that potential game based cooperative control also can be applied to dynamic environment problems. The approach is illustrated on three example problems. The first one is a moving target tracking problem using a modified form of the learning algorithm, restrictive log-linear learning. The second example is mobile sensor coverage for an unknown dynamic environment. The last example is multi-agent path optimization using payoff based learning. The performances of the developed systems are studied by simulation. The last part of this thesis develops an experimental moving target tracking system using multiple mobile robots. Finally, the thesis concludes with suggestions for future research directions.

Στην παρούσα διπλωματικής εργασία εφαρμόζουμε τις αρχές της Θεωρίας Παιγνίων, και συγκεκριμένα τις έννοιες των Ισορροπιών Nash και των Παι­γνίου Συμφόρησης, ώστε να αναλύσουμε την επίδραση που έχει στην καθο­λική απόδοση ενός δικτύου και γενικότερα ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Αρχικά ασχολούμαστε με το πρόβλημα της εγωιστικής δρομολόγησης φορ­τίων από μια κοινή πηγή προς έναν κοινό προορισμό σε ένα δίκτυο επικοι­νωνίας. Σε ένα τέτοιο περιβάλλον οι χρήστες επιλέγουν εγωιστικά τις στρα­τηγικές τους, οι οποίες στην περίπτωση μας αντιστοιχούν σε μονοπάτια από την πηγή προς τον προορισμό Όταν οι χρήστες δρομολογούν τα φορτία τους σύμφωνα με τις στρατηγικές που επιλέγουν, έρχονται αντιμέτωποι με μια κα­θυστέρηση που προκαλείται από τα φορτία όλων των χρηστών καθώς διαμοι­ράζονται τις ακμές. Κάθε χρήστης στοχεύει στην ελαχιστοποίηση του εγωι­στικού τον κόστους, που αντιστοιχεί σε αυτήν ακριβώς την καθυστέρηση, γεγονός που συνήθως έρχεται σε αντίθεση με το στόχο της βελτιστοποίησης της καθολικής απόδοσης του δικτύου. Η θεωρία των ισορροπιών Nash μας παρέχει μία σημαντική αρχή επίλυ­σης για τέτοιου είδους καταστάσεις: μια ισορροπία Nash, είναι μια κατάσταση του συστήματος τέτοια ώστε δεν υπάρχει κάποιος χρήστης που να μπορεί να μειώσει το εγωιστικό του κόστος αλλάζοντας μονομερώς τη στρατηγική του. Σε ένα τέτοιο δίκτυο λοιπόν περιμένουμε οι χρήστες να καταλήξουν σε μια ισορροπία Nash. Ωστόσο, ο υπολογισμός μιας τέτοιας ισορροπίας παραμέ­νει ένα πρόβλημα του οποίου η πολυπλοκότητα είναι, στη γενική περίπτωση, άγνωστη. Στα πλαίσια αυτής της διπλωματικής εργασίας δείχνουμε πειραματικά ότι ο υπολογισμός μιας αγνής ισορροπίας Nash σε ένα περιβάλλον εγωιστικής δρομολόγησης, όπου η καθυστέρηση σε κάθε ακμή ισούται με το φορτίο της. μπορεί να γίνει σε πολυωνυμικό χρόνο για μια μεγάλη ποικιλία δικτύων και κατανομών των φορτίων των χρηστών. Επιπλέον, προτείνουμε μια αρχική ανάθεση χρηστών σε μονοπάτια η οποία, όπως δείχνουν οι προσομοιώσεις μας, οδηγεί σε μια αξιοσημείωτη μείωση του συνολικού αριθμού των βημάτων που απαιτούνται ώστε να καταλήξουμε σε μια αγνή ισορροπία Nash. Επίσης αποδεικνύουμε την ύπαρξη αγνών ισορροπιών Nash και για την περίπτωση που η καθυστέρηση σε κάθε ακμή είναι εκθετική συνάρτηση του φορτίου της. Στη συνέχεια προτείνουμε και αναλύουμε ένα νέο μηχανισμό κόστους που θέτει τιμές για την ανταγωνιστική χρησιμοποίηση πόρων από ένα σύνολο χρη­στών. Το βασικό πλεονέκτημα αυτού του μηχανισμού είναι ότι οι πόροι θέ­τουν τα κόστη με έναν ισοδύναμο, δίκαιο τρόπο, και το πλέον σημαντικό είναι ότι κανένας πόρος δεν επωφελείται εις βάρος των χρηστών. Αυτός ο δίκαιος μηχανισμός κόστους επαγάγει ένα μη συνεργατικό παί­γνιο μεταξύ των χρηστών, για το οποίο αναλύουμε τις ισορροπίες Nash. Απο­δεικνύουμε ότι δεν υπάρχουν αγνές ισορροπίες Nash, εκτός από την περί­πτωση όπου όλα τα φορτία είναι ίσα, ενώ δείχνουμε ότι υπάρχει πάντα μία πλήρως μικτή ισορροπία Nash. Επίσης αναλύουμε για το παίγνιο αυτό το Κόστος της Αναρχίας, που εκφράζει την απόκλιση της απόδοσης του συ­στήματος στη χειρότερη ισορροπία Nash από τη βέλτιστη απόδοση. Αποδει­κνύουμε ότι το Κόστος της Αναρχίας στη χειρότερη περίπτωση είναι γραμ­μικό ως προς το πλήθος των χρηστών και ότι το φράγμα αυτό είναι αυστηρό. Ωστόσο προτείνουμε δύο τρόπους για να μετριάσουμε τη δυσάρεστη αυτή διαπίστωση. Καταρχήν, μελετάμε την περίπτωση όπου τα φορτία των χρηστών επιλέ­γονται από μία πολύ ευρεία οικογένεια φραγμένων κατανομών πιθανότητας. Ορίζουμε το Διαχεόμενο Κόστος της Αναρχίας το οποίο λαμβάνει υπόψη την κατανομή πιθανότητας των φορτίων και αποδεικνύουμε ότι Διαχεόμενο Κόστος της Αναρχίας φράσσεται εκ των άνω από μία μικρή σταθερά. Επιπλέον, προτείνουμε έναν υβριδικό μηχανισμό κόστους, ο οποίος επιτυγχάνει ένα ση­μαντικά μικρότερο Κόστος της Αναρχίας, ενώ το κέρδος κάθε πόρου παρα­μένει αμελητέο. / -

Fictitious Play is the oldest and most studied learning process for games. Since the already classical result for zero-sum games, convergence of beliefs to the set of Nash equilibria has been established for several classes of games, including weighted potential games, supermodular games with diminishing returns, and 3×3 supermodular games. Extending these results, we establish convergence of Continuous-time Fictitious Play for ordinal potential games and quasi-supermodular games with diminishing returns. As a by-product we obtain convergence for 3×m and 4×4 quasi-supermodular games.

Cette thèse se focalise sur les jeux de potentiel et une généralisation d'un jeu d'ordonnancement dans un graphe que nous avons appelé jeu de placement.Dans ce jeu, le coût d'un joueur est impacté par son voisinage.Nous pouvons illustrer cela avec un exemple : le placement de joueurs dans un train, pour lesquels la présence de voisins directs influe sur le bien-être.Les résultats de cette thèse se divisent en deux parties.Tout d'abord, nous étudions ces jeux en considérant l'existence et les propriétés de structure des équilibres.Nous nous posons la question fondamentale de savoir s'il existe des équilibres de Nash dans le jeu de placement.Si tel est le cas, nous tachons de déterminer si ces équilibres sont facilement calculables.Dans le cas où il n'existe pas d'équilibre nous prouvons la NP-complétude du problème.Dans un second temps nous nous intéressons à la notion de calcul distribué d'équilibre de Nash dans des jeux de placement.En particulier nous considérons un jeu basé sur le problème de Max-Cut, qui a été plus étudié en théorie des graphes.Cela nous a permis d'étendre nos travaux à une application aux réseaux mobiles pour la gestion d'interférences dans les réseaux sans fils.Nous avons pu, pour les différents jeux, mettre en place des algorithmes distribués de calcul d'équilibres et étudier leur convergence.Parallèlement, nous avons étendu les travaux de Max-Cut à un problème de sélection d'offre de qualité de service parmi divers fournisseurs d'accès.Nous comparons les performances d'algorithmes de calcul distribué d'équilibres et de minimisation de regret. / This thesis focuses on potential games and a generalized load balancing game in a graph we called placement game.In this game, the cost of a player is affected by its neighbors.We can illustrate this with an example: the placement of players on a train, where the presence of direct neighbors affects their well-being.The results of this thesis are divided into two parts.First, we study these games considering the existence and structural properties of equilibria.We ask ourselves the fundamental question of whether there are Nash equilibria in the placement game.If this is the case we aim to determine if they are easily calculable, if there is no such equilibria we prove the NP-completeness of the problem.Secondly we focus on the concept of distributed algorithms to compute Nash equilibria in placement games.In particular we consider a game based on the Max-Cut problem, which has been more frequently studied.This allowed us to expand our work to a mobile network application for managing interference in wireless networks.We were able, for those different games, to implement distributed algorithms to compute equilibria and study their convergence.Meanwhile, we have expanded the Max-Cut works with a selection of QoS offers problem from various network providers.We compare the performance of distributed algorithms and regret minimization.

Cette thèse étudie l'interaction technico-économique entre véhicules électriques et réseaux d'électricité. Le développement récent de la mobilité électrique invite en effet à analyser les impacts potentiels de la recharge de ces véhicules sur les réseaux électriques, mais aussi le soutien que ceux-ci pourraient apporter dans les réseaux du futur. Ce travail s'inscrit résolument dans le cadre des réseaux d'électricité intelligents ; la plupart des résultats de cette thèse s'appliquent tout aussi bien à un lave-linge, un chauffe-eau, une télévision tant que l'on leur prête la capacité d'intelligence ! Dès lors que les décisions des consommateurs électriques flexibles interagissent, ce cadre d'étude offre un terrain de jeu propice aux outils de théorie des jeux. Ceux-ci ont un apport direct lorsque le problème considéré a un fondement stratégique, mais leur application permet aussi de proposer des solutions sur des aspects où la théorie des jeux n'est pas forcément attendue : algorithmique, dans l'échange d'information entre acteurs, etc. La description de cet apport est l'objet principal de ce travail de thèse et se décompose en trois parties. En fil rouge, le cas des profils de charge rectangulaires – soutenus par de nombreux arguments pratiques mais souvent délaissés par les chercheurs – est analysé. En premier lieu, des questions algorithmiques se posent pour coordonner la charge de véhicules électriques dans un même périmètre du système électrique. Proposant et étudiant un algorithme de coordination, il est montré comment les propriétés fondamentales de celui-ci - sa convergence, l'efficacité de ses points de convergence – peuvent être déduite d'un jeu auxiliaire sous-jacent. L'analyse de ce jeu est faite en montrant qu'il appartient à la classe des jeux de potentiel, sous des hypothèses physiques et économiques très générales. Sur le plan de l'échange d'information, un modèle est proposé pour réfléchir à la bonne communication entre un opérateur du réseau et un véhicule. Ces deux agents ont intérêt à communiquer pour planifier la charge intelligente du véhicule électrique, mais ont des objectifs distincts. Ce cadre est très proche du Cheap-talk en théorie des jeux, mais aussi de la problématique de la quantification en traitement du signal. Ce travail tisse au passage des liens entre ces sujets. Il propose aussi une méthode pour que l'agent du réseau et le véhicule s'accordent hors-ligne sur un bon mécanisme d'échange d'information. Enfin, la théorie des jeux est appliquée dans un cadre plus habituel, pour analyser le jeu des acteurs. Ceci est fait quand des ensembles de véhicules de taille importante, vus comme des flottes, cohabitent avec des véhicules individuels. Ceci offre un terrain de jeu applicatif aux outils très récents des jeux composites. Dans ces trois directions de recherche, des simulations sont effectuées dans le cadre d'un réseau de distribution d'électricité, maille du système électrique qui pourrait vivre des impacts significatifs si la charge est non-coordonnée. En particulier, elles montrent la robustesse des méthodes proposées face aux incertitudes sur les données lorsque des profils de charge rectangulaires sont considérés. / This thesis studies the technical and economical interaction between electric vehicles and electrical networks. The recent development of electric mobility leads to the analysis of potential impacts of electric vehicle charging on the electrical networks, but also to the possible support that these particular electric consumers could provide in the future smart grids. In this direction, most of the results given in this thesis also apply to a washing machine, a water-heater, a TV, as soon as these equipments are capable of being smart! When the decisions of flexible electric consumers interact, the considered framework naturally offers a unique exercise area for the tools of game-theory. The interpretation is straightforward when the considered problem is strategic by definition, but these tools allow also shedding light on other aspects: algorithmic coordination, information exchange, etc. The description of the benefits of using game-theory in this context is the aim of this work. This is done according to three aspects. In these three directions, a particular attention is drawn to the case of rectangular charging profiles, which are very practical, but often ignored by the literature. First, algorithmic issues arise when coordinating the charging of electric vehicles in a same area of the electrical network. A charging algorithm is proposed and analyzed. This is done by studying an underlying auxiliary game. This game is proved to belong to the class of potential games under very general physical and economic assumptions. In turn, it inherits from the strong properties of this class of games, namely convergence and an efficiency result in the case of a large number of electric vehicles. Considering information exchange, a model is proposed to design a good communication scheme between an operator of the electrical system and an electric vehicle. Both agents have an interest in exchanging information to schedule optimally the charging profile of the electric vehicle but they do not share the same objective. This framework is closely related to Cheap-talk in game theory and to quantization in signal processing. Amongst others, this work explains interesting connections between both topics. Furthermore, a method, which is used offline, is given to obtain a good communication mechanism between both agents. Finally, game theory is used in its traditional form, studying the strategic interaction when groups of a large number of electric vehicles – seen as fleets – coexist with individual vehicles. This allows the application of the very recent concept of composite games. In the three parts of the work, simulations are conducted in a French realistic distribution network, which could be the first part of the electrical system severely impacted by a non-coordinated charging. This highlights the robustness of rectangular charging profiles against forecasting errors on the parameters of the models.

Coordination is a desirable feature in many multi-agent systems, such as robotic, social and economic networks, allowing the execution of tasks that would be impossible by individual agents. This thesis addresses two problems in stochastic coordination where each agent make decisions strategically, taking into account the decisions of its neighbors over a regular network. In the first problem, we study the coordination in a team of strategic agents choosing to undertake one of the multiple tasks. We adopt a stochastic framework where the agents decide between two distinct tasks whose difficulty is randomly distributed and partially observed. We show that a Nash equilibrium with a simple and intuitive linear structure exists for textit{diffuse} prior distributions on the task difficulties. Additionally, we show that the best response of any agent to an affine strategy profile can be nonlinear when the prior distribution is not diffuse. Then, we state an algorithm that allows us to efficiently compute a data-driven Nash equilibrium within the class of affine policies. In the second problem, we assume that the payoff structure of the coordination game corresponds to a single task allocation scenario whose difficulty is perfectly observed. Since there are multiple Nash equilibria in this game, the agents must use a distributed stochastic algorithm know as textit{log linear learning} to play it multiple times. First, we show that this networked coordination game is a potential game. Moreover, we establish that for regular networks, the convergence to a Nash equilibrium depends on the ratio between the task-difficulty parameter and the connectivity degree according to a threshold rule. We investigate via simulations the interplay between rationality and the degree of connectivity of the network. Our results show counter-intuitive behaviors such as the existence of regimes in which agents in a network with larger connectivity require less rational agents to converge to the Nash equilibrium with high probability. Simultaneously, we examined the characteristics of both regular graphical coordination games and non-regular graphical games using this particular bi-matrix game model. / Master of Science / This thesis focuses on addressing two problems in stochastic coordination among strategic agents in multi-agent systems, such as robotic, social, and economic networks. The first problem studies the coordination among agents when they need to choose between multiple tasks whose difficulties are randomly distributed and partially observed. The thesis shows the existence of a Nash equilibrium with a linear structure for certain prior distributions, and presents an algorithm to efficiently compute a data-driven Nash equilibrium within a specific class of policies. The second problem assumes a single task allocation scenario, whose difficulty is perfectly observed, and investigates the use of a distributed stochastic algorithm known as log-linear learning to converge to a Nash equilibrium. The thesis shows that the convergence to a Nash equilibrium depends on the task-difficulty parameter and the connectivity degree of the network, and explores the influence of rationality of the agents and the connectivity of the network on the learning process. Overall, the thesis provides insights into the challenges and opportunities in achieving coordination among strategic agents in multi-agent systems.

Cognitive radio is frequently touted as a platform for implementing dynamic distributed radio resource management algorithms. In the envisioned scenarios, radios react to measurements of the network state and change their operation according to some goal driven algorithm. Ideally this flexibility and reactivity yields tremendous gains in performance. However, when the adaptations of the radios also change the network state, an interactive decision process is spawned and once desirable algorithms can lead to catastrophic failures when deployed in a network. This document presents techniques for modeling and analyzing the interactions of cognitive radio for the purpose of improving the design of cognitive radio and distributed radio resource management algorithms with particular interest towards characterizing the algorithms' steady-state, convergence, and stability properties. This is accomplished by combining traditional engineering and nonlinear programming analysis techniques with techniques from game to create a powerful model based approach that permits rapid characterization of a cognitive radio algorithm's properties. Insights gleaned from these models are used to establish novel design guidelines for cognitive radio design and powerful low-complexity cognitive radio algorithms. This research led to the creation of a new model of cognitive radio network behavior, an extensive number of new results related to the convergence, stability, and identification of potential and supermodular games, numerous design guidelines, and several novel algorithms related to power control, dynamic frequency selection, interference avoidance, and network formation. It is believed that by applying the analysis techniques and the design guidelines presented in this document, any wireless engineer will be able to quickly develop cognitive radio and distributed radio resource management algorithms that will significantly improve spectral efficiency and network and device performance while removing the need for significant post-deployment site management. / Ph. D.