Policy Hill Climbing (PHC) is a reinforcement learning algorithm that extends Q-learning to learn probabilistic policies for multi-agent games. WoLF-PHC extends PHC with the "win or learn fast" principle. A proof that PHC will diverge in self-play when playing Shapley's game is given, and WoLF-PHC is shown empirically to diverge as well. Various WoLF-PHC based modifications were created, evaluated, and compared in an attempt to obtain convergence to the single shot Nash equilibrium when playing Shapley's game in self-play without using more information than WoLF-PHC uses. Partial Commitment WoLF-PHC (PCWoLF-PHC), which performs best on Shapley's game, is tested on other matrix games and shown to produce satisfactory results.

<p> In this thesis, we focus on the rationing polices for the hotel room inventory control problems. Our study begins with a brief overview of revenue management in hotel industry, emphasizing the importance of room inventory control in revenue management problems. Mathematical models for controlling the room inventory in the literature are then reviewed along with recently developed game theoretic applications in revenue management. In game theoretic context, we establish three types of models to solve the hotel room inventory control problem in three different situations: 1) two-player two-fare-class static single-period game with complete information; 2) two-player two-fare-class dynamic multiple-period game with complete information; and 3) two-player two-fare-class single-period game with incomplete information.</p> <p> In the first situation, we find the existence of unique Nash equilibrium and Stackelberg equilibrium in the non-cooperative case. We provide the exact forms for these equilibria and corresponding conditions. Next, under the dynamic game settings, we provide the sufficient conditions for the unique Nash equilibrium. In the last situation, we consider the static single-period games with incomplete information and discuss the optimal strategies for the uninformed case, secret information case, private information case and public information case. The unique Bayesian Nash equilibrium in each case is found. We then analyze the values of different types of information and study their relations in different situations. Under each game theoretic setting, we present the managerial implications of our solutions along with the numerical examples. The thesis is concluded by a discussion of how game theory can is useful in hotel industry, and its relationship to other topics in revenue management.</p> / Thesis / Doctor of Philosophy (PhD)

No description available.

This dissertation builds a model of information exchange, where the information is skills. A two-sided matching market for skills is employed that includes two distinct sides, skilled and unskilled agents, and the matches that connect these agents. The unskilled agents wish to purchase skills from the skilled agents, who each possess one valuable and unique skill. Skilled agents may match with many unskilled agents, while each unskilled agent may match with only one skilled agent. Direct interaction is necessary between the agents to teach and learn the skill. Thus, there must be mutual consent for a match to occur and the skill to be exchanged. In this market for skills, a discrete, simultaneous move game is employed where all agents announce their strategies at once, every skilled agent announcing a price and every unskilled agent announcing the skill she wishes to purchase. First, both Nash equilibria and a correlated equilibrium are determined for an example of this skills market game. Next, comparative statics are employed on this discrete, simultaneous move game through computer simulations. Finally, a continuous, simultaneous move game is studied where all agents announce their strategies at once, every skilled agent announcing a price and every unskilled agent announcing a skill and price pair. For this game, an algorithm is developed that if used by all agents to determine their strategies leads to a strong Nash equilibrium for the game. / Economics

Networks, generically, refer to any application of graph theory in economics. Consider an undirected graph where nodes represent players and links represent relationships between them. Players can both form and delete links by which we mean that they can both form new relationships and terminate existing ones. A stable network is one in which no incentives exist to change the network structure. There can be various forms of stability depending on how many links players are allowed to form or delete at a time. Under strong pairwise stability, each player is allowed to delete any number of links at a time while any pair of players can form one link at a time. We introduce a network-value function, which assigns to each possible network a certain value. The value is allocated according to the component-wise egalitarian allocation rule, which divides the value generated by a component equally among members of the component (where a component refers to a maximally connected subgraph). An efficient network is one that maximizes the network value function. We show that there is an underlying conflict between strong pairwise stability and efficiency. Efficient networks are not necessarily strongly pairwise stable. This conflict can be resolved only if value functions satisfy a certain property called "middlemen-security". We further find that there is a broad class of networks called "middlemen-free networks" for which the above condition is automatically satisfied under all possible value functions. We also look at three network applications. A peering contract is an arrangement between Internet Service Providers under which they exchange traffic with one another free of cost. We analyze incentives for peering contracts among Internet service providers using the notion of pairwise stability. A hierarchy is a directed graph with an explicit top-down structure where each pair of linked agents have a superior-subordinate relationship with each other. We apply the notion of conjunctive permission value to demonstrate the formation of hierarchical firms in a competitive labor market. Comparative or targeted advertising is defined as any form of advertising where a firm directly or indirectly names a competitor. We also examine a model of targeted advertising between oligopolistic firms using non-cooperative game theoretic tools. / Ph. D.

In recent years, game theory has emerged as a promising approach to solving the power control problem in wireless networks. This thesis extends the reach of game-theoretic analysis to embrace link adaptation, thereby constituting a generalization of the power control problem. A realistic and natural problem formulation is attempted, wherein transmitter power and a discrete-valued Adaptable Link Parameter (ALP), e.g. code rate, constitute the action set of a player in this game. The dual goals of maximizing throughput and minimizing power consumption are reflected in the utility function selection, which uses the accurate sigmoid model for approximating throughput. The discrete action space makes it difficult to verify the existence of a Nash Equilibrium (NE) in this game using standard techniques. To circumvent this limitation, a heuristic algorithm is proposed. This algorithm is analytically shown to always converge to a NE. The subsequent results probe its validity and sensitivity. Favorable comparisons are drawn between these game-theoretic results and those arising from parallel systems techniques. A linear programming system optimization that exploits properties of the dominant eigenvalue of the system gain matrix is also presented in a comparative context. / Master of Science

博士（経済学） / 乙第354号 / 112 p. / Hitotsubashi University

This thesis introduces the basic concepts of the game theory. Necessary models and solution concepts are described. Follows the summary of the computational complexity of these concepts and corresponding algorithms. Poker is formalized as one of the game theory game models. State of the art algorithms for the ex- tensive form games are explained with the application to the Poker. The thesis also introduces the Annual Computer Poker Competition and participating pro- grams. Finally, new result about the extensive form games with many actions is presented. Keywords: Game theory, Poker, Nash equilibrium, Extensive form games

Nesse trabalho, aplicando métodos da Topologia Algébrica, nós obtivemos novas versões do teorema de equilíbrio de Nash. Nós definimos um conceito de equilíbrio local para jogos não cooperativos, o chamado equilíbrio local fraco, e demonstramos sua existência quando os espaços de estratégia são variedades diferenciáveis e as funções payoff são continuamente diferenciáveis. Nós demonstramos a ineficiência do equilíbrio local fraco no sentido de Pareto / In this work, applying methods of Algebraic Topology, we obtain new versions of the Nash equilibrium theorem. We define a concept of local equilibrium for non-cooperative games, the socalled weak local equilibrium, and we prove its existence when the spaces of strategies are differentiable manifolds and the payoff functions are continuously differentiable. We prove the ineffciency of weak local equilibrium in the Pareto sense

Neste trabalho demonstram-se os teoremas de ponto fixo de Brouwer e Kakutani com o objetivo de provar a existência do equilíbrio de Nash em jogos finitos em forma normal. No primeiro capítulo apresentam-se as definições de teoria dos jogos, começando com jogos finitos em forma normal e terminando com o conceito de equilíbrio de Nash. Na primeira seção do capítulo dois desenvolve-se a teoria de simplexes, em Rn, e se demonstra o teorema de Brouwer. Na seção seguinte, são relacionadas as propriedades de semi-continuidade superior e gráfico fechado em set functions, para então provar os teoremas de Celina e von Neumann que, em conjunto com o teorema de Brouwer, resultam no teorema de Kakutani no fim da seção. Como último resultado é demonstrado o teorema de existência do equilíbrio de Nash em jogos finitos em forma normal através do teorema de Kakutani, mostrando que o equilíbrio de Nash é um ponto fixo de uma set function. / In this work, the fixed-point theorems of Kakutani and Brouwer are proved with the intention of showing the existence of Nash equilibrium in finite normal-form games. In the first chapter the needed definitions of game theory are shown, starting with finite normal-form games and ending with the concept of Nash equilibrium. In the first section of chapter two, simplex theory in Rn is developed and then the Brouwer fixer point theorem is proved. In the next section, some relations of upper hemi-continuity and closed graph in set functions are shown, then proving the theorems of Celina and von Neumann that, along with Brouwer theorem, result in Kakutani fixed-point theorem in the end of the section. As the last result, the existence of Nash equilibrium in finite normal-form games is proved through Kakutani’s theorem, relating the Nash equilibrium to the fixed-point of a set function.