Efficiency loss in a resource allocation game: A single link in elastic supply
We consider a resource allocation problem where individual users wish to send data across a single link to maximize their utility, and a cost is incurred dependent on the total flow sent on the link. It has been shown 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 social welfare). Continuing previous efforts to quantify the effects of selfish behavior in network pricing mechanisms, our research considers the possibility that users may anticipate the effect of their actions on the link price. Under the simple assumption that the link's marginal cost function is convex, we establish existence of a Nash equilibrium, and show that the system utility is no worse than a factor of 4/spl radic/2-5 times the optimal system utility; thus, the efficiency loss when users are selfish is no more than approximately 34%.