In modern computer games, `bots' - Intelligent realistic agents play a prominent role in success of a game in the market. Typically, bots are modeled using finite-state machine and then programmed via simple conditional statements which are hard-coded in bots logic. Since these bots have become quite predictable to an experienced games' player, a player might lose interest in the game. We propose the use of a game theoretic based learning rule called Fictitious Play for improving behavior of these computer game bots which will make them less predictable and hence, more enjoyable to a game player.

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.

Submitted by Luis Eduardo Craizer (lecraizer@gmail.com) on 2016-09-26T19:40:04Z No. of bitstreams: 1 Dissertação - Versão Final.pdf: 1700556 bytes, checksum: 6dce561cf40774feced5f3a980199830 (MD5) / Approved for entry into archive by Janete de Oliveira Feitosa (janete.feitosa@fgv.br) on 2016-09-27T13:30:15Z (GMT) No. of bitstreams: 1 Dissertação - Versão Final.pdf: 1700556 bytes, checksum: 6dce561cf40774feced5f3a980199830 (MD5) / Approved for entry into archive by Maria Almeida (maria.socorro@fgv.br) on 2016-10-18T11:49:02Z (GMT) No. of bitstreams: 1 Dissertação - Versão Final.pdf: 1700556 bytes, checksum: 6dce561cf40774feced5f3a980199830 (MD5) / Made available in DSpace on 2016-10-18T11:49:53Z (GMT). No. of bitstreams: 1 Dissertação - Versão Final.pdf: 1700556 bytes, checksum: 6dce561cf40774feced5f3a980199830 (MD5) Previous issue date: 2016-03-11 / In an auction, both the good’s seller and the potential buyer desire to maximize their profit. The seller aims to obtain the highest possible value for the good, whereas the buyers want to win the auction paying the less they can for the object. In this scenario, this study suggests an algorithm based on the Fictitious Play, which seeks to simulate the agents’ behavior for the different kinds of auctions. In this simulation, we are also going to embed the risk aversion and try to forecast rational behavior of the agents. The main goal of the work is to make a parallel between the strategy functions, which maximize the agents’ utilities cataloged on books and texts, and the optimal strategies, which are obtained in the simulation through the usage of the proposed algorithm. / Em um leilão, tanto o vendedor quanto os potenciais compradores desejam maximizar suas receitas: no caso do leiloeiro, ele quer obter o maior valor possível pela venda de seu bem; no caso dos agentes participantes, eles desejam pagar o menor valor possível pelo objeto e, ainda assim, vencer o leilão. Tendo como base de estudo o cenário descrito, este trabalho sugere um algoritmo baseado no Fictitious Play que visa simular o comportamento dos agentes perante um certo tipo de leilão específico. Esta simulação pretende também incorporar a aversão ao risco e pretende-se prever o comportamento racional dos agentes participantes perante este cenário. O objetivo principal desta dissertação é realizar uma comparação entre as funções que descrevem as estratégias que maximizam as utilidades dos participantes já catalogadas na literatura e as estratégias ótimas que são obtidas na simulação através do algoritmo proposto.

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.

Les jeux à champ moyen (MFG) sont une classe de jeux différentiels dans lequel chaque agent est infinitésimal et interagit avec une énorme population d'agents. Dans cette thèse, nous soulevons la question de la formation effective de l'équilibre MFG. En effet, le jeu étant très complexe, il est irréaliste de supposer que les agents peuvent réellement calculer la configuration d'équilibre. Cela semble indiquer que si la configuration d'équilibre se présente, c'est parce que les agents ont appris à jouer au jeu. Donc, la question principale est de trouver des procédures d'apprentissage dans les jeux à champ moyen et d'analyser leurs convergences vers un équilibre. Nous nous sommes inspirés par des schémas d'apprentissage dans les jeux statiques et avons essayé de les appliquer à notre modèle dynamique de MFG. Nous nous concentrons particulièrement sur les applications de fictitious play et online mirror descent sur différents types de jeux de champs moyens : Potentiel, Monotone ou Discret. / Mean Field Games (MFG) are a class of differential games in which each agent is infinitesimal and interacts with a huge population of other agents. In this thesis, we raise the question of the actual formation of the MFG equilibrium. Indeed, the game being quite involved, it is unrealistic to assume that the agents can compute the equilibrium configuration. This seems to indicate that, if the equilibrium configuration arises, it is because the agents have learned how to play the game. Hence the main question is to find learning procedures in mean field games and investigating if they converge to an equilibrium. We have inspired from the learning schemes in static games and tried to apply them to our dynamical model of MFG. We especially focus on fictitious play and online mirror descent applications on different types of mean field games; those are either Potential, Monotone or Discrete.

We build a variety of customer booking choice models for a major airline that operates in a very competitive origin-destination market. Some of the models are aimed at incorporating unobserved heterogeneous customer preferences for different departure times. The estimation results show that including these factors into choice models dramatically affects price sensitivity estimates, and therefore matters. We present a stochastic trust region algorithm for estimating ML-type models that involve high-dimensional integrals. The algorithm embeds two sampling processes: (i) a data sampling process and (ii) a Monte Carlo sampling process, and the algorithm dynamically controls sample sizes based on the magnitude of the errors incurred due to the two sampling processes. The first-order convergence is proved based on generalized uniform law of large numbers theories for both the average log-likelihood function and its gradient. The efficiency of the algorithm is tested with real data and compared with existing algorithms. We also study how a specific behavioral phenomenon, called the decoy effect, affects the decisions of sellers in product assortment competition in a duopoly. We propose a discrete choice model to capture decoy effects, and we provide a complete characterization of the Nash equilibria and their dependence on choice model parameters. For the cases in which there are multiple equilibria, we consider dynamical systems models of the sellers responding to their competitors using Cournot adjustment or fictitious play to study the evolution of the assortment competition and the stability of the equilibria. We provide a simple geometric characterization of the dynamics of fictitious play for 2×2 games that is more complete than previous characterizations.

In this technical note we use insights from the theory of projective geometry to provide novel and non-algebraic proofs of convergence of continuous-time fictitious play for a class of games. As a corollary we obtain a kind of equilibrium selection result, whereby continuous-time fictitious play converges to a particular equilibrium contained in a continuum of equivalent equilibria for symmetric 4x4 zero-sum games.

Fictitious play is a classical learning process for games, and games with strategic complementarities are an important class including many economic applications. Knowledge about convergence properties of fictitious play in this class of games is scarce, however. Beyond games with a unique equilibrium, global convergence has only been claimed for games with diminishing returns [V. Krishna, Learning in games with strategic complementarities, HBS Working Paper 92-073, Harvard University, 1992]. This result remained unpublished, and it relies on a specific tie-breaking rule. Here we prove an extension of it by showing that the ordinal version of strategic complementarities suffices. The proof does not rely on tie-breaking rules and provides some intuition for the result.

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.

Approved for public release; distribution in unlimited. / In this thesis, a new fictitious play (FP) procedure is presented to solve two-person zero-sum (TPZS) Blotto games. The FP solution procedure solves TPZS games by assuming that the two players take turns selecting optimal responses to the opponent's strategy observed so far. It is known that FP converges to an optimal solution, and it may be the only realistic approach to solve large games. The algorithm uses dynamic programming (DP) to solve FP subproblems. Efficiency is obtained by limiting the growth of the DP state space. Blotto games are frequently used to solve simple missile defense problems. While it may be unlikely that the models presented in this paper can be used directly to solve realistic offense and defense problems, it is hoped that they will provide insight into the basic structure of optimal and near-optimal solutions to these important, large games, and provide a foundation for solution of more realistic, and more complex, problems. / Captain, Republic of Korea Air Force