direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 32-2008

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Efficiency and Stability of Nash Equilibria in Resource Allocation Games
Tobias Harks and Konstantin Miller
not available
game theory, resource allocation, network flow
We study resource allocation games, where users send data along paths and links in the network charge a price equal to marginal cost. When users are price taking, it is known that there exist distributed dynamics that converge towards a fully efficient Nash equilibrium. When users are price anticipating, however, a Nash equilibrium does not maximize total utility in general. In this paper, we explore the inefficiency of Nash equilibria for general networks and semi-convex marginal cost functions. While it is known that for mgeq 2 users, no efficiency guarantee is possible, we prove that an additional differentiability assumption on marginal cost functions implies a bounded efficiency loss of 2/(2m+1). For polynomial marginal cost functions with nonnegative coefficients we precisely characterize the price of anarchy. We also prove that the efficiency of Nash equilibria significantly improves if all users have 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.
Download as [PDF]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe