direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

TKN Technical Report Series

The Impact of Marginal Cost Pricing in Resource Allocation Games
Citation key harks08the_impact_of
Author Harks, Tobias and Miller, Konstantin
Year 2008
Number 032-2008
Month November
Institution Combinatorial Optimization and Graph Algorithms (COGA)Group, Technische Universität 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.
Bibtex Type of Publication OtherTechnicReportsTKN
Link to publication Download Bibtex entry

To top

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

Search Publications