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.

This thesis deals with factors which are important for making decisions in the game of poker. The goal is to find a way to improve players chances of success in this game. The first two chapters describe the rules of poker and the basics and presumptions of the game theory The following chapters analyze some mathematical models and assumptions for applying these models in the game. These models should find the optimal solution for individuals in decision making situations. It can be considered a static situation, where the behavior of each player is predetermined and the decision maker tries to find an appropriate strategy. It is also can be considered a dynamic situation, when all players react to each other, which heads to equilibrium solution. As a consequence of rising popularity of poker tournaments many strategy books have appeared, as well as analytic software. Nevertheless, it is and probably will remain impossible to solve all decision situations which can occur. A very important factor of success are some gamblers attitude, experience and mental skills. Mathematical knowledge, however, will become more and more important. This thesis will help to understand the basic of mathematic models and their application in poker game.

Participants in deregulated electric power markets compete for financial transmission rights (FTRs) to hedge against losses due to transmission congestion by submitting bids to the independent system operator (ISO). The ISO obtains an FTR allocation, that maximizes sales revenue while satisfying simultaneous feasibility. This FTR allocation remains in place for a length of time during which the participants compete in the energy market to maximize their total payoff from both FTR and energy markets. Energy markets (bi-lateral, day ahead, real time) continue until the the end of the current FTR period, at which time the participants can choose to modify their FTR holdings for the next FTR period. As in any noncooperative game, finding Nash equilibrium bidding strategies is of critical importance to the participants in both FTR and energy markets. In this research, a two-tier matrix game theoretic modeling approach is developed that can be used to obtain equilibrium bidding behavior of the participants in both FTR and energy markets considering the total payoff from FTR and energy. The matrix game model presents a significant deviation from the bilevel optimization approach commonly used to model FTR and energy allocation problems. A reinforcement learning (RL) algorithm is also developed which uses a simulation model and a value maximization approach to obtain the equilibrium bidding strategies in each market. The model and the RL based solution approach allow consideration of multi-dimensional bids (for both FTR and energy markets), network contingencies, varying demands, and many participants. The value iteration based RL algorithm obtains pure strategy Nash equilibrium for FTR and energy allocation. A sample network with three buses and four participants is considered for demonstrating the viability of the game theoretic model for FTR market. A PJM network example with five buses, five generators and three loads is also considered to analyze equilibrium bidding behavior in joint FTR and energy markets. Several numerical experiments on the sample networks are conducted using the approach of statistical design of experiments (DOE) to assess impacts of variations of bid and network parameters on the market outcomes like participant payoffs and equilibrium strategies.

In this study cost-benefits problems concerning the knapsack problem of limited resources is studied and how this relates to an attacker perspective when choosing defense strategies. This is accomplished by adopting a cost-benefit method and merging it with game theory. The cost-benefit method chosen for this study is the Analytical Hierarchy Process and from the field of game theory the Bayesian Nash Equilibrium is used. The Analytical Hierarchy Process allows the user to determine internally comparable weights between elements, and to bring in a security dimension to the Analytical Hierarchy Process a sub category consisting of confidentiality, integrity and availability is used. To determine the attacker strategy and, in effect, determine the best defense strategy the Bayesian Nash Equilibrium is used.

We propose a new classification for multi-agent learning algorithms, with each league of players characterized by both their possible strategies and possible beliefs. Using this classification, we review the optimality of existing algorithms and discuss some insights that can be gained. We propose an incremental improvement to the existing algorithms that seems to achieve average payoffs that are at least the Nash equilibrium payoffs in the long-run against fair opponents. / Singapore-MIT Alliance (SMA)

This thesis considers resource management issues in wireless sensor networks (WSNs), wireless local area networks (WLANs), and cognitive radio (CR) networks. Since energy is a critical resource in WSNs, we consider energy minimization techniques based on explicit node cooperation and distributed source coding (DSC). The explicit node cooperation based on space time block codes (STBC) improves energy efficiency of WSNs, by reducing the energy consumption per bit of each sensor node. The DSC on the other hand exploits the spatial correlation in WSNs, and thus reduces the data generated in a WSN. For the purpose of our analysis, we model the spatial correlation according to a linear Gauss-Markov model. Through our numerical results, we observe that the node cooperation combined with DSC can improve energy efficiency for many cases of interest. A unique aspect of our work is we obtain important structural results using the concepts from monotone comparative statics. These structural results provide insights into the general design of WSNs. Through our numerical results, we also demonstrate that, the cooperation based transmission can achieve better mutual information (MI)-energy tradeoff than the non-cooperation based transmission scheme. From the perspective of WLANs, we propose a price based approach to regulate the channel occupancy of low rate users, which is known to be the primary cause for low overall throughput in WLANs. Owing to the decentralized nature of WLANs we use non-cooperative game theory as a tool for analysis. Specifically, we use supermodular game theory. Through our analysis, we show that an increase in price leads to an increase in rate of WLAN users. We also prove that the best response dynamics indeed converge to the Nash equilibrium of the underlying non-cooperative game. Through our numerical results, we demonstrate that by proper tuning of the price, the proposed price based approach can lead to an improvement in overall throughput of a WLAN. Finally from the perspective of CR networks, we consider the impact of number of channels captured by a secondary user on its transmission control protocol (TCP) throughput. From our simulation results it was found that, there exists a definite optimal number of channels a secondary user needs to capture, to maximize its TCP throughput.