000K utf8 1100 $c2010 1500 eng 2050 urn:nbn:de:gbv:8-diss-55231 3000 Kliemann, Lasse 4000 Networks and distributed operation: the price of anarchy in non-atomic routing and network formation$hChristian-Albrechts-Universität zu Kiel [Kliemann, Lasse] 4000 Netzwerke und verteilte Operation: Der Preis der Anarchie in nicht-atomarem Routing und Netzwerkformierung$hChristian-Albrechts-Universität zu Kiel [Kliemann, Lasse] 4030 Kiel$nChristian-Albrechts-Universität zu Kiel 4209 Der Preis der Anarchie ist ein Maß für den Leistungsverlust dadurch, dass Individuen in verteilter Weise operieren, d.h. dass sie nicht oder nur eingeschränkt koordiniert werden oder nicht oder nur eingeschränkt kooperieren. Im ersten Teil wird ein gegebenes Netzwerk in verteilter Weise genutzt, und zwar für Multicast-Routing, d.h. es möchte jeder Sender eine Mehrzahl Empfänger gleichzeitig erreichen. Wir beweisen nahezu scharfe obere und untere Schranken für den Preis der Anarchie und führen eine experimentelle Studie durch. Im zweiten Teil geht es um die Formierung von Netzwerken. Jeder Knoten des (zu formierenden) Netzwerkes hat die Wahl, in Verbindungen zu investieren. Bei uns findet die Netzwerkformierung unter dem Wissen statt, dass später genau eine Verbindung durch einen Gegner zerstört werden wird. Die Knoten streben an, trotzdem gut verbunden zu bleiben. Wir beweisen scharfe obere und obere Schranken für den Preis der Anarchie für zwei verschiedene Formen von Gegnern. 4209 The price of anarchy is a measure for performance loss due to individuals operating in a distributed manner, i.e., without or with only limited central control or without or with only limited cooperation. In the first part, a network is given and used in a distributed manner, namely for multicast routing, i.e., each sender wishes to transmit a message to multiple receivers simultaneously. We prove almost tight upper and lower bounds on the price of anarchy and conduct an experimental study. In the second part, a network is formed. Each vertex of the (to-be-built) network may invest in the building of links. The formation takes place under the knowledge that an adversary will later delete exactly one link. Vertices wish to maintain good connectivity. We prove tight upper and lower bounds on the price of anarchy for two different adversaries. 4950 https://nbn-resolving.org/urn:nbn:de:gbv:8-diss-55231$xR$3Volltext$534 4961 https://macau.uni-kiel.de/receive/diss_mods_00005523 5051 510 5550 Adversary Model 5550 bilaterale Formierung 5550 Bilateral Link Formation 5550 Distributed Network Formation 5550 Game Theory 5550 Gegnermodell 5550 Multicast Routing 5550 Multicast-Routing 5550 Nash Equilibrium 5550 Nash-Gleichgewicht 5550 Network Creation Game 5550 Netzwerkerzeugungspiele 5550 Nicht-atomare Auslastungspiele 5550 Non-Atomic Congestion Games 5550 paarweises Nash-Gleichgewicht 5550 paarweise Stabilität 5550 Pairwise Nash Equilibrium 5550 Pairwise Stability 5550 Preis der Anarchie 5550 Price of Anarchy 5550 Robustheit 5550 Robustness 5550 Spieltheorie 5550 unilaterale Formierung 5550 Unilateral Link Formation 5550 Verteilte Netzwerkformierung