@techreport{harks08the_impact_of,
Title = {The Impact of Marginal Cost Pricing in Resource Allocation Games},
Author = {Harks, Tobias and Miller, Konstantin},
Year = {2008},
Number = {032-2008},
Month = {November},
Type = {OtherTechnicReportsTKN},
Institution = {Combinatorial Optimization and Graph Algorithms (COGA)Group, Technische Universit\"at Berlin},
Abstract = {We study the impact of marginal cost pricing in resource allocation games on the worst case efficiency of Nash equilibria. Resource allocation games are closely related to congestion games and model the strategic interaction of players competing over a finite set of congestible resources. Examples of resource allocation games are routing and congestion control games in networks. For convex and differentiable marginal cost functions, we prove that marginal cost pricing leads to a worst-case efficiency loss of Nash equilibria of at most 2/(2 n + 1), where n is the number of players. This is the first bound that holds for resource allocation games with arbitrary convex and differentiable marginal cost functions. For polynomial marginal cost functions with non-negative coefficients, we precisely characterize the price of anarchy. We also prove that the efficiency of Nash equilibria significantly improves if all players have the same strategy space and the same utility function. We propose a class of distributed dynamics and prove that whenever a game admits a potential function, these dynamics globally converge to a Nash equilibrium. Finally, we show that in general the only class of marginal cost functions that guarantees the existence of a potential function are affine linear functions.},
Url = {ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Report-032-2008.pdf}
}