Show simple item record

2014-06-30Dissertation DOI: 10.18452/16991
On selfish network creation
dc.contributor.authorLenzner, Pascal
dc.date.accessioned2017-06-18T13:12:35Z
dc.date.available2017-06-18T13:12:35Z
dc.date.created2014-07-08
dc.date.issued2014-06-30
dc.identifier.urihttp://edoc.hu-berlin.de/18452/17643
dc.description.abstractUntersuchungsgegenstand dieser Arbeit ist ein spieltheoretisches Modell für die dezentrale Erzeugung von Netzwerken durch eigennützige Agenten. Diese Akteure verfolgen das Ziel, ein zusammenhängendes Netzwerk aufzubauen, welches ihre individuelle Verbindungsqualität maximiert. Direktverbindungen im Netzwerk haben Kosten, weshalb die Agenten ihre Ausgaben für das Erstellen von Direktverbindungen und die damit erzielten Kommunikationskosten ausbalancieren müssen. Dieses Modell wurde vor einem Jahrzehnt von Fabrikant, Luthra, Maneva, Papadimitriou und Shenker eingeführt, um reale Netzwerke, welche aus der Interaktion von eigenützigen Parteien entstanden sind, zu verstehen. Zu solchen Netzwerken zählen das Internet und auch soziale Netzwerke. Die vorliegende Arbeit trägt zu diesem Forschungsvorhaben bei, indem die sogenannten Network Creation Games aus drei Perspektiven betrachtet werden. Die erste Sichtweise ist die Approximationsperspektive. Es wird untersucht, welche Netzwerke von sehr einfachen, in ihrer Berechnungsstärke eingeschränkten Agenten erzeugt werden und wie diese im Vergleich mit Netzwerken von Agenten, die beliebige Berechnungsstärke haben, abschneiden. Als zweite Sichtweise wird die Dynamikperspektive betrachtet. Dazu werden sequentielle Versionen des Modells definiert und anhand dieser wird explizit der Prozess der Netzwerkerzeugung untersucht. Die Hauptfragestellung ist, ob unter der natürlichen Annahme, dass Agenten stets ihre Situation verbessern wollen, der Prozess zu einem Gleichgewicht konvergiert und, falls dem so ist, wie dieser Prozess beschleunigt werden kann. Die Abhandlung wird mit der dritten Sichtweise, der Strukturperspektive, abgerundet. Es werden eine Vielfalt neuer Struktureigenschaften für verschiedene Gleichgewichtskonzepte bewiesen und neue Werkzeuge, die bei der Analyse von Gleichgewichtsnetzwerken mit hohen Direktverbindungskosten hilfreich sind, vorgestellt.ger
dc.description.abstractThe subject of study in this thesis is a game-theoretic model for decentralized network creation by selfish agents. These agents aim to create a connected network among themselves which maximizes their individual connection quality. Links in the network are costly and therefore agents try to find a trade-off between their cost spent on creating edges and their cost incurred by communicating within the network. This model was proposed a decade ago by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker with the goal of understanding real networks which emerge from the interaction of selfish entities without explicit central coordination, e.g. the Internet or social networks. We contribute to this research endeavor in many ways by considering these so-called Network Creation Games from three perspectives. Our first point of view on these games is the approximation perspective. We analyze which networks are created by very simple computationally bounded selfish agents and how these networks compare to networks built by agents having unlimited computational resources. The second point of view is the dynamics perspective. We turn the model into a sequential version and focus on the process of selfish network creation. For this, we investigate whether natural dynamics like best response dynamics are guaranteed to converge to an equilibrium of the game and if so, how this convergence process may be sped up. We complete the treatment of Network Creation Games with our third point of view: the structure perspective. We provide new structural insights for several equilibrium concepts and introduce new tools which shed light on the structure of equilibrium networks for high edge-cost.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
dc.rightsNamensnennung - Keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-sa/3.0/de/
dc.subjectAlgorithmische Spieltheorieger
dc.subjectNetzwerkerzeugungsspieleger
dc.subjectApproximative Gleichgewichteger
dc.subjectSpieldynamikenger
dc.subjectNetzwerkdesignger
dc.subjectEigennützige Agentenger
dc.subjectAlgorithmic Game Theoryeng
dc.subjectNetwork Creation Gameseng
dc.subjectApproximate Equilibriaeng
dc.subjectGame Dynamicseng
dc.subjectNetwork Designeng
dc.subjectSelfish Agentseng
dc.subject.ddc004 Informatik
dc.titleOn selfish network creation
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-100219085
dc.identifier.doihttp://dx.doi.org/10.18452/16991
dc.identifier.alephidBV041955323
dc.date.accepted2014-05-30
dc.contributor.refereeAlbers, Susanne
dc.contributor.refereeHarks, Tobias
dc.contributor.refereeSchäfer, Guido
dc.subject.dnb28 Informatik, Datenverarbeitung
dc.subject.rvkST 200
local.edoc.pages176
local.edoc.type-nameDissertation
bua.departmentMathematisch-Naturwissenschaftliche Fakultät II

Show simple item record