John Musacchio
04/24/2009 09:00 AM
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. The model we study supposes a topology of service providers connected in parallel and serial combinations. 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 circuit branch 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 branch, so our bound measures how efficiency loss increases as the capability of the system becomes more concentrated in a particular serial combination of players.
