A Study of System Efficiencies Through Game Theory and Optimization.

摘要

Game theory is a common tool in modeling human decisions and strategies under various decision environments, with the foundation being the fact that a joint decision from all the individuals (we shall adhere to the term players hereafter) will impact on each other's well being. In this thesis, we shall study how the behaviors of the players affect the performance of the whole system, and shall introduce some measurements to quantify the influence on the system performance.;The first part is devoted to the study of the loss of system efficiency caused by selfish behavior of the players. We use the notion of the Price of Anarchy and consider two different but intrinsically related game settings to address the issue. One is to consider the cost incurred to the players due to the usage of some shared resources, modeled as the links of a network. Suppose that there are K players and each of them must achieve a given throughput. Furthermore, the unit cost on each link is affine linear in the total flow. Then the price of anarchy for the game can be upper bounded by (3K + 1)/(2 K + 2). The second model is a generalization of Cournot oligopolistic competition, in which the players utilize some shared resources to produce some commodities to sell. Again, suppose there are K players, and the unit costs of the shared resources and the selling prices of the products are all affine linear functions in the amount of demand and supply respectively. Then the price of anarchy is shown to be lower bounded by 1/K.;In the second part, we turn to the consequence of greediness of the players. In a dynamic decision-making process, system inefficiency may be caused by the unwise use of the resources due to the myopia of the decision makers. The loss of efficiency is measured by a ratio termed the Price of Myopia: the value at the greedy solution divided by the optimal value. A specific setting is studied to illustrate the point. Furthermore, we consider the combined effect of selfishness and myopia under a game framework and introduce a new notion, the Price of Isolation to quantify the matter. Some bounds for the price of isolation are established in a dynamic setting of the previous two models.;In the third part, we investigate the influence of cooperation and altruistic behavior of players. The incentive of the players to cooperate, and the impact of cooperation on the members of the coalition and on the whole system are analyzed. We consider a model of resource competition game and find that the system will benefit from the cooperation of players at the expense of some individual members in the coalition. A measurement termed the Price of Socialism is introduced to characterize how much any individual will need to sacrifice for the social optimum. We obtain a tight bound for the price of socialism for our particular model.