direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 19-2007

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
The Price of Anarchy of a Network Creation Game with Exponential Payoff
Authors
Nadine Baumann and Sebastian Stiller
Classification
not available
Keywords
graph process, network analysis, network creation game, price of anarchy
Abstract
Graph processes and network creation games help to understand the structure of real-world networks. Though these tools often fall short of a detailed modeling, their analysis elates by linking a simple and intuitive, creative principle to typical features of huge real-world networks.Several graph process based models have been proposed particularly in an economic context. We consider one which seems fundamental among these. We analyze a graph process (or network creation game) where the vertices as players can establish mutual relations between each other at a fixed price. Each vertex receives income from every other vertex, exponentially decreasing with their distance. To establish an edge, both players have to make a consent. We show that the process has a positive probability to cycle. We reduce the creation rule with payoff functions to graph theoretic criteria. Moreover, these criteria can be evaluated locally. This allows us to thoroughly reveal the structure of all stable states. In addition, the question for the price of anarchy can be reduced to counting the maximum number of edges of a stable graph. This together with a probabilistic argument allows to determine the price of anarchy precisely.
Source
Download as [PDF] [ps]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe