Price of Anarchy Bounds for Network Pricing Games 

We study a game theoretic model of competing network service providers that strategically price their service in the presence of elastic user demand. Demand is elastic in that it diminishes both with higher prices and latency, which in turn grows linearly with a network's usage. The model we study is based on a model first proposed and studied by Acemoglu and Ozdaglar and later extended by Hayrapetyan, Tardos, and Wexler to consider elastic user demand. We consider the Price of Anarchy (PoA), which we define as the ratio of the social welfare of the system when a social planner chooses link prices versus the social welfare attained when link owners choose the link prices selfishly. We make an analogy between the game and an electric circuit, and in this analogy the slope of each provider's latency function is taken to be the resistance of a circuit branch. Using the analogy, we find a bound on the PoA that depends on the ratio of the conductance of the player with highest conductance to the combined conductance of all the branches. This ratio is a metric of how much of the system's capability is concentrated in one player's network, so our bound measures how efficency loss increases as the capability of the system becomes more concentrated in one player's network.