Efficiency loss in a network resource allocation game: the case of elastic supply

By Ramesh Johari, Shie Mannor, John N. Tsitsiklis. IEEE Transactions on Automatic Control, 2004

618 citations recorded by the source corpus.

We consider a resource allocation problem where individual users wish to send data across a network to maximize their utility, and a cost is incurred at each link that depends on the total rate sent through the link. It is known that as long as users do not anticipate the effect of their actions on prices, a simple proportional pricing mechanism can maximize the sum of users' utilities minus the cost (called aggregate surplus). Continuing previous efforts to quantify the effects of selfish behavior in network pricing mechanisms, we consider the possibility that users anticipate the effect of their actions on link prices. Under the assumption that the links' marginal cost functions are convex, we establish existence of a Nash equilibrium. We show that the aggregate surplus at a Nash equilibrium is no worse than a factor of 4/spl radic/2-5 times the optimal aggregate surplus; thus, the efficiency loss when users are selfish is no more than approximately 34%.

Subfields: Computer Networks and Communications, Management Information Systems, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/d722733dc067f57f0fb4666aad210325a5a7d4b7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Information Systems

In Management Science and Operations Research

Citations in the corpus

Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems (2015, background): “Clearly, x i ∈ Ω i also generalizes previous box constraints in Johari & Tsitsiklis (2004), D’Amico, Sanguinetti & Palomar (2014) and Cherukuri & Cort´es (2014).”
Network Optimization and Control (2008, methodology): “The price of anarchy for strategic users using the Kelly mechanism was computed by Johari and Tsitsiklis in [102].”
Game Theory in Wireless and Communication Networks (2008, background): “Some researchers have focused on developing bounds of efficiency loss in such simple bidding games: Johari and Tsitsiklis [235] show that with a uniform-pricing scheme the Nash equilibrium (NE) of a share auction achieves at least 3/4 of the total utility in a socially optimal solution.”
Selfish routing and the price of anarchy (2005, background): “In theoretical computer science, potential functions have been used to bound the price of anarchy in several applications [3, 36, 73, 74].”
The Price of Fairness (2011, background): “See Johari and Tsitsiklis (2004), Koutsoupias and Papadimitriou (1999), Papadimitriou (2001), Perakis (2007), and Roughgarden and Tardos (2002) for more details.”
Auction-Based Spectrum Sharing (2006, background): “Our approach is similar to a share auction (see [3] [4] [5] [6] [7] [8] and the references therein), or divisible auction, where a perfectly divisible good is split among bidders whose payments depend solely on the bids.”
Advanced Demand Side Management for the Future Smart Grid Using Mechanism Design (2012, methodology): “However, the details of the proof can be found in [35].”
Live Video Analytics at Scale with Approximation and Delay-Tolerance (2017, background): “utility functions, an abstraction used extensively in economics [65, 73] and computer systems [22, 55].”