Please use this identifier to cite or link to this item:
For citation please use:
Main Title: The Price of Anarchy of a Network Creation Game with Exponential Payoff
Author(s): Baumann, Nadine
Stiller, Sebastian
Type: Research Paper
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.
Subject(s): graph process
network analysis
network creation game
price of anarchy
Issue Date: 2007
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2007, 19
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 456.83 kB
DownloadShow Preview
Format: Postscript | Size: 6.46 MB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.