Networks and distributed operation [Elektronische Ressource] : the price of anarchy in non-atomic routing and network formation / Lasse Kliemann

Lasse Kliemann

Sujets

• Mathematics

Informations

• Publié par: christian-albrechts-universitat_zu_kiel
• Publié le: 01 janvier 2009
• Nombre de lectures: 10
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

Networks and Distributed Operation
THE PRICE OF ANARCHY
in Non-Atomic Routing and Network Formation
Dissertation
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
(Dr. rer. nat.)
der Technischen Fakultät
der Christian-Albrechts-Universität zu Kiel
Dipl.-Math. Lasse Kliemann
Kiel
20091. Gutachter: Prof. Dr. Anand Srivastav
Christian-Albrechts-Universität Kiel
2. Gutachter: Prof. Dr. Klaus Jansen
Christian-Albr Kiel
3. Gutachter: Prof. Dr. Matthias Müller-Hannemann
Martin-Luther-Universität Halle-Wittenberg
Datum der mündlichen Prüfung: 11. Januar 2010Networks and Distributed Operation
THE PRICE OF ANARCHY
in Non-Atomic Routing and Network Formation
Lasse KliemannErrata and revised versions can be found via
http://lasse-kliemann.name
or by using the permanent ID.
Permanent ID of this document:
d811d50d-931a-4413-bffe-1cd6a2e1d84c
This version is dated 2010-10-20.
To search for (newer versions of) this document, use the search string:
Permanent ID of this document: d811d50d-931a-4413-bffe-1cd6a2e1d84c
When citing this document, please use the document ID in the following form:
“Document ID: d811d50d-931a-4413-bffe-1cd6a2e1d84c”. You can also use the
date to refer to a particular version of this document.
Please do not use the phrase “Permanent ID of this document” when citing,
since that would make it impractical to find this document using the search
string given above.Contents
Introduction xiii
I Distributed Non-Atomic Routing in Networks 1
1 Non-Atomic Congestion Games 3
1.1 Selfish Unicast Routing . . . . . . . . . . . . . . . . . . . 4
1.2 Non-Atomic Congestion Games . . . . . . . . . . . . . . 7
1.3 Formal Subtleties – Matrix Notation . . . . . . . . . . . 10
1.4 Equilibrium Concept . . . . . . . . . . . . 12
1.4.1 Basic Concept . . . . . . . . . . . . . . . . . . . . 12
1.4.2 Non-Atomic Games and Variational Inequality
Formulation . . . . . . . . . . . . . . . . . . . . . 13
1.5 Uniqueness of Nash Equilibrium . . . . . . . . . . . . . 15
1.6 Computation and Potential Function . . . . . . . . . . . 16
1.7 Bounding the Price of Anarchy . . . . . . . . . . . . . . 21
1.7.1 The Anarchy Value . . . . . . . . . . . . . . . . . 21
1.7.2 Theb Parameter . . . . . . . . . . . . . . . . . . 25
1.7.3 Jacobian Approach . . . . . . . . . . . . . . . . . 29
1.8 Reasons for Inefficiency . . . . . . . . . . . . . . . . . . 32
1.9 Bibliographic Overview . . . . . . . . . . . . . . . . . . 34
2 NCRCG 37
2.1 Selfish Multicast Routing . . . . . . . . . . . . . . . . . . 38
2.2 Non-Uniqueness of Equilibrium and Lower Bound . . 40
2.3 Modeling as NCGs . . . . . . . . . . . . . . . . . . . . . 45
2.4 Non-Atomic Consumption-Relevance Cong. Games . . 46viii Contents
2.5 New Parameters and Global Measures . . . . . . . . . . 49
2.6 Modeling Multicast Routing . . . . . . . . . . . . . . . . 50
2.7 Reducingg by Scaling . . . . . . . . . . . . . . . . . . . 52
2.8 General Lower Bound on the Price of Anarchy . . . . . 54
2.9 Upper Bound on the Price of Anarchy . . . . . . . . . . 57
2.10 Bicriteria Bound . . . . . . . . . . . . . . . . . . . . . . . 62
2.11 Computation . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.11.1 Convexity and Non-Convexity ofSC and Com-
putation of Optima . . . . . . . . . . . . . . . . . 65
2.11.2 Computation of Nash Equilibria . . . . . . . . . 69
2.11.3 Extreme Nash Equilibria . . . . . . . . . . . . . . 71
2.12 Bibliographic Remarks . . . . . . . . . . . . . . . . . . . 73
2.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3 Experimental Studies and Conjecture 75
3.1 Computational Procedure . . . . . . . . . . . . . . . . . 76
3.2 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . 79
3.3 Random Model and Data Sets . . . . . . . . . . . . . . . 81
3.4 Qualitative Observations . . . . . . . . . . . . . . . . . . 83
3.5 Hexagonal Binning Plots . . . . . . . . . . . . . . . . . . 84
3.6 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.7 Comparison with Perakis’ Bound . . . . . . . . . . . . . 87
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Conclusion and Future Directions 89
II Distributed Network Formation 91
4 Network Formation 93
4.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.2 Model Framework . . . . . . . . . . . . . . . . . . . . . 95
4.2.1 Strategy Profile, Final Graph, Cost . . . . . . . . 95
4.2.2 Graph-Related Notions . . . . . . . . . . . . . . 98
4.2.3 Nash Equilibrium and Price of Anarchy . . . . . 101
4.3 A Concrete Model: Sum of Distances . . . . . . . . . . . 103
4.4 More on the Bilateral Case . . . . . . . . . . . . . . . . . 111Contents ix
4.4.1 Bilateral Equilibrium Concepts . . . . . . . . . . 112
4.4.2 Lower Bound for Bilateral Sum-Distance Model 118
4.4.3 Transformations . . . . . . . . . . . . . . . . . . 122
4.5 Bibliographic Overview . . . . . . . . . . . . . . . . . . 124
4.5.1 Sum-Distance Model . . . . . . . . . . . . . . . . 124
4.5.2 Equilibrium Concepts and Further Models . . . 125
5 Distributed Network Formation Against an Adversary 129
5.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.1.1 Simplified Notation . . . . . . . . . . . . . . . . 131
5.1.2 Illustration . . . . . . . . . . . . . . . . . . . . . . 132
5.2 Previous Work and Comparison . . . . . . . . . . . . . 133
5.3 General Bounds and the Bridge Tree . . . . . . . . . . . 135
5.4 Simple-Minded Adversary . . . . . . . . . . . . . . . . . 138
5.4.1 Optima, Equilibria, and the Price of Stability . . 139
5.4.2 Bounding the Price of Anarchy . . . . . . . . . . 144
5.5 Smart Adversary . . . . . . . . . . . . . . . . . . . . . . 148
5.5.1 Optima, Equilibria, and the Price of Stability . . 149
5.5.2 Bounding the Price of Anarchy . . . . . . . . . . 152
5.6 Bilateral Case . . . . . . . . . . . . . . . . . . . . . . . . 156
5.6.1 Bounding the Price of Anarchy . . . . . . . . . . 157
5.6.2 Convexity and Non-Convexity of Cost . . . . . 161
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Conclusion and Future Directions 165
A Basic Terminology and Notation 167
A.1 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . 167
A.2 Graphs and Networks . . . . . . . . . . . . . . . . . . . 168
B Experimental Results 171
B.1 Hexagonal Binning Plots . . . . . . . . . . . . . . . . . . 172
B.2 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
B.2.1 Detailed Tables for p= 1 . . . . . . . . . . . . . 179
B.2.2 TRx Values for p2 1, 2, 3 . . . . . . . . . . . . 187f g
B.3 Comparison with Perakis’ Bound . . . . . . . . . . . . . 212