The Price of Anarchy and Myopia: a Study of System Inefficiencies

Prof. Shouhong Zhang
Industrial and Systems Engineering
University of Minnesota

Abstract:

Lack of coordination and lack of long-term planning can cause the performance of a system to deteriorate. Thus far, the statement is self-evident. The real question is: Can we quantify the deterioration? In this talk, we present a study of system inefficiencies caused by the selfish nature in non-cooperative game models and/or myopic and greedy attitude in dynamic decision-making processes. First we consider a structure whereby the cost for a user (player) is due to the utilization of some shared resources, modeled as the links of a network. The objective of each player is either to minimize the cost, or to maximize the profit (the benefit minus the cost). The game that we consider involves K players. Our first model assumes that the unit cost on each link is affine linear in the total flow, and that each player must achieve a given throughput. In that case, the price of anarchy (PoA) of the game is shown to be upper bounded by (3K+1)/(2K+2). If the players have the same OD and the same desired throughput, then the PoA of the game is upper bounded by 4K^2/(3K^2+2K-1). If the total cost on each link is affine linear in the total flow and each player shares the cost proportional to the usage, then the PoA is upper bounded by K. If each player aims at maximizing the profit by operating a flow on the network (linear benefit function), then we show that the PoA is lower bounded by O(1/K). Then, we turn our attention to a structure whereby K players compete to maximize their profits over a period of T stages. We assume that all the players are not only selfish but also myopic, meaning that they aim at maximizing the profit at the current stage. We show that equilibrium also exists in this situation. Moreover, the Price of Myopia, i.e. the total profit at the equilibrium over the optimal social value, is in the order of 1/(KT).