Artificial Intelligence Algorithms for Large Economic and Computer Games

Abstract

Contemporary artificial intelligence algorithms (search, graphical models, machine learning, etc.) have achieved great success in a variety of practical domains. This thesis particularly considers their application to the equilibrium analysis of multiagent systems. Specifically, I study the following subject: emph{how a structured combination of modern artificial intelligence methods facilitates strategic reasoning focusing on equilibrium concepts on multiagent systems of diverse domains, especially those without tractable and analytical description}.

After laying out the technical foundations, I present four research works to illustrate the theme. The first three follow the chronological order in which most game theory textbooks are organized: the most basic normal-form games are first studied, then games with incomplete information, and then dynamical games with imperfect information. The difference here, though, is that my approaches are more from a computational perspective using practical AI methods, instead of deriving the exact mathematical solutions. First, I demonstrate how supervised learning and unsupervised learning techniques can be utilized under a model-based structure learning framework to facilitate equilibrium computation in many-player normal-form games. This method can scale to games with hundreds of players. Second, I show how a particular class of policy search algorithms being well-studied in deep reinforcement learning can be employed in generic frameworks to solve many-player games of incomplete information. The pure equilibria computation method can recover classic analytical solutions in simple auction games. And both the pure and mixed equilibria methods scale to games with high-dimensional type space and action space. Third, I develop a general-purpose multi-agent algorithm that combines an AlphaZero-styled tree-search and a population-based RL training loop, for general-sum extensive-form games with large imperfect information. Using this algorithm, a game-playing bot is built and can achieve comparable social welfare with humans as when humans trade with themselves in a class of negotiation game. In the last part, instead of focusing on emph{solving} a particular game, I consider the problem of emph{evaluating} different interactive AI algorithms by using a meta-game analysis framework. A variety of game-theoretic properties of model-free, model-based, self-play, and population-based multi-agent reinforcement learning algorithms are uncovered.