Existence, convergence and efficiency analysis of nash equilibrium and its applications

• Main Author: Wang, Xuehe
• Other Authors: Xie Lihua
• Format: Theses and Dissertations
• Language: English
• Published: 2016
• Subjects: DRNTU::Science::Mathematics::Applied mathematics::Game theory
• Online Access: https://hdl.handle.net/10356/65997
• Institution: Nanyang Technological University

Game theory deals with strategic interactions among multiple players, where each player tries to maximize/minimize its utility/cost. It has been applied in a broad array of areas such as economics, transportation, engineering, psychology, etc. Nash equilibrium, a fundamental concept in the realm of noncooperative game theory, is defined as the action profile of all players where none of the players can improve its utility/cost by a unilateral move. However, it is widely known that a Nash equilibrium often exhibits a suboptimal behavior compared with the socially optimal assignment. Moreover, in repeated games where each player makes its decision based on the available information at each stage, it is possible that the action profiles of all players fail to converge to a Nash equilibrium. This thesis presents research results on existence, convergence and efficiency analysis of Nash equilibrium in variety classes of games and their applications. First, we discuss a repeated noncooperative multiple choices congestion game in which players have limited information about each other and make their decisions simultaneously. Congestion games are a class of games in game theory, in which the utility of each player depends on the resources each player chooses and the number of players choosing the same resource. At each stage, players can calculate their best choice if they know the number of players choosing each resource. However, in most cases, each player does not know other players' strategies before it makes its decision. Therefore, a player may need to estimate the number of players choosing each resource. We introduce a consensus protocol to estimate the percentage of players selecting each resource. At each stage, each player may exchange information with its neighbors randomly and independently. We show that the congestion game under investigation has at least one pure strategy Nash equilibrium and the almost sure convergence to a pure Nash equilibrium can be ensured after some sort of inertia is adopted. Then, we apply our results to the trip timing and routing problem in traffic congestion control. By introducing different dynamic pricing schemes, the social optimum is achieved and players' choices are spread out, respectively. Simulation results based on the real traffic data of Singapore validate the effectiveness of the designed pricing schemes. Next, we analyze the efficiency loss of Nash equilibrium in a nonatomic congestion game, where there is a continuum of players, each of which is infinitesimally small. A network with one origin-destination pair is formulated, where each edge is assigned a latency function. To characterize the worst-case efficiency loss of all possible Nash flow, price of anarchy (POA), defined as the worst possible ratio between the total latency of Nash flow and that of the socially optimal flow, is adopted. In order to improve the POA, a scaled marginal-cost is designed to affect players' choices. All players in the noncooperative congestion game are divided into groups based on their price sensitivities. For the two groups and two routes case, it is shown that the total latency of the Nash flow can always reach the total latency of the socially optimal flow if the designed scaled marginal-cost is charged on each link. For general case, if certain conditions are satisfied, a scaled marginal-cost can be designed such that the unique Nash flow can achieve the social optimal flow. An algorithm is also proposed to find the price scheme that optimizes the POA for any distribution of price sensitivity and any network with one origin-destination pair. Besides the inefficiency of Nash equilibrium, there is also efficiency loss at each stage in repeated play. Therefore, we study the performance of a sequence of action profiles generated by repeated play in multiple origin-destination networks. To analyze the efficiency of the sequence of action profiles, the price of total anarchy (POTA), defined as the worst-case ratio of the average total latency over a period of time and the total latency of any optimal strategy, is adopted. It is shown that the sequence of action profiles generated by best response principle with inertia possesses almost sure no-regret property. Via smoothness arguments, the upper bound of POTA is identified for both linear and nonlinear latency networks respectively. To reduce the upper bound of POTA, dynamic pricing is implemented for networks with linear latency functions. The influence of the inaccurate parameter information of the latency function on the POTA is also discussed. For the network with heterogeneous players, we show that the upper bound of POTA is the same as that in the network with homogeneous players as time goes to infinity. The results are applied to a traffic routing problem based on the real traffic data of Singapore. At last, we investigate the behavior of large population systems based on mean field games where each agent evolves according to a dynamic equation containing the input average and seeks to minimize its long time average (LTA) cost encompassing a population state average (PSA), which is also known as the mean field term. Due to the informational burden resulting from the PSA coupling to the states of all agents, our idea is to find a deterministic function to estimate it. It is shown that the deterministic function is an approximation of the PSA as the population size goes to infinity. The resulting decentralized mean field control laws lead the system to mean-consensus asymptotically as time goes to infinity and the stability property of the mass behavior is also guaranteed. Furthermore, the optimal controls generate an almost sure asymptotic Nash equilibrium, which implies that the LTA cost of each agent can reach its minimal value as the number of agents increases to infinity. In addition, a nonlinear dynamic system is discussed and the influence of inaccurate mean field information on individual agent is analyzed. Then, we consider the socially optimal case where the objective of each agent is to minimize the social cost as the sum of all agents' LTA costs containing the PSA. In this case, it is shown that the decentralized mean field social control strategies are identical to the mean field Nash controls for infinite population systems.