The Price of Anarchy of a Network Creation Game with Exponential Payoff
| dc.contributor.author | Baumann, Nadine | |
| dc.contributor.author | Stiller, Sebastian | |
| dc.date.accessioned | 2021-12-17T10:07:34Z | |
| dc.date.available | 2021-12-17T10:07:34Z | |
| dc.date.issued | 2007 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15622 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14395 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | graph process | en |
| dc.subject.other | network analysis | en |
| dc.subject.other | network creation game | en |
| dc.subject.other | price of anarchy | en |
| dc.title | The Price of Anarchy of a Network Creation Game with Exponential Payoff | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2007, 19 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |