Selfish network creation: on variants of network creation games

Andreas Cord-Landwehr Selfish Network Creation: On Variants of Network Creation Games Bibliografische Information Der Deutschen Bibliothek Die Deutsche Bibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.ddb.de abrufbar. Band 353 der Verlagsschriftenreihe des Heinz Nixdorf Instituts © Heinz Nixdorf Institut, Universität Paderborn – Paderborn – 2016 ISSN (Print): 2195-5239 ISSN (Online): 2365-4422 ISBN: 978-3-942647-72-4 Das Werk einschließlich seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung der Herausgeber und des Verfassers unzulässig und strafbar. Das gilt insbesondere für Vervielfältigung, Übersetzungen, Mikroverfilmungen, sowie die Einspeicherung und Verarbeitung in elektronischen Systemen. Als elektronische Version frei verfügbar über die Digitalen Sammlungen der Universitätsbibliothek Paderborn. Satz und Gestaltung: Andreas Cord-Landwehr Hersteller: Verlagshaus Monsenstein und Vannerdat OHG Druck Buch Verlag Münster Printed in Germany Dissertation Selfish Network Creation On Variants of Network Creation Games Dr.rer.nat. Andreas Cord-Landwehr Reviewers Prof.Dr. math. Friedhelm Meyer auf der Heide Jun.-Prof.Dr. rer.nat. Alexander Skopalik Paderborn University Faculty for Electrical Engineering, Computer Science, and Mathematics Preface I must admit: Writing this thesis turned out to be more work than I originally anticipated. Writing the following lines, however, turns out to be much more fun than I had expected some months ago. Now, at this point, there are many people I want to thank and for so many things: For exciting discussions, for chats in the coffee room, for critical questions, for encouraging words, for making the time of writing this thesis (and the years before) far from boring, for bearing my little free time during the past months, and for numerous other things. Foremost, I want to thank my supervisor Friedhelm Meyer auf der Heide. It was a great time working in this research group and I am particularly grateful that I had the opportunity to find my research topic on my own. However, filling the topic with interesting content would not have been possible without all the discussions that helped me identify the important questions. While doing this, I had the chance to travel the world to discuss, present, and bring back new inspirational ideas and for this I owe my gratitudes especially to the Collaborative Research Center 901 “On-The-Fly Computing”. The postcards on my office wall are dedicated as a small thank-you for that. Special thanks go to all of my many co-authors: Alex 4 , Barbara, Bastian, Christoph 2 , Daniel 3 , Frederik, Friedhelm, Kamil, Manuel, Marcus, Markus, Martina, Matthias, Pascal, Peter 2 , Sebastian, and Sven. Specifically, I want to thank Martina for pushing my nose into the field of network creation games, back in the days, which then directly gripped my interest and shaped all of my future research. For all the long research discussions in front of some white v Preface board or via phone, I want to specifically thank Sebastian and Pascal. I learned from Peter the art of introduction writing and how to tell even the most boring topics with a fancy motivation – and everyone reading this thesis should be grateful to him. Working in this research group was a great time and it was made a great time by the people I met there. In particular, this holds for my former and current office-roommates Tim, Peter, Sören and Alex. Last but not least, I have to thank all my friends and my family for enduring the last months in which thesis writing was quite in the focus of my activities. All of you, specifically those I missed to name here, thank you! And you know, there is always a box of free cookies on my desk, reserved just for you. Andreas Cord-Landwehr Paderborn, November 2015 vi Contents Preface v 1 Introduction 1 1.1 A Model for Selfish Network Creation . . . . . . . . . . . . . . 3 1.2 Thesis Focus & Overview . . . . . . . . . . . . . . . . . . . . . 4 2 Preliminaries 9 2.1 The Classic Model of Network Creation Games . . . . . . . . . 10 2.2 Notions of Stability, Quality, and Convergence . . . . . . . . . 12 2.2.1 Notions of Stability . . . . . . . . . . . . . . . . . . . . . 12 2.2.2 Quality of Equilibria . . . . . . . . . . . . . . . . . . . . 14 2.2.3 Convergence of Improving-Response Processes . . . . 15 2.3 KnownResults............................ 17 2.3.1 ModelVariants ....................... 18 2.3.2 Relationships of Model Variants . . . . . . . . . . . . . 22 2.4 AlternativeModels......................... 22 3 Loss and Benefit of Friendships 27 3.1 The Friendship Model & Preliminaries . . . . . . . . . . . . . . 29 3.2 Related Work & Contribution . . . . . . . . . . . . . . . . . . . 31 3.3 Worst-Case Friendships in Swap-Games . . . . . . . . . . . . . 33 3.3.1 Private Costs in Max-Swap-Game Tree Equilibria . . . 37 3.3.2 The Price of Anarchy in Max-Swap-Games . . . . . . . 45 3.3.3 The Price of Anarchy in Sum-Swap-Games . . . . . . . 49 3.4 ProcessEquilibria.......................... 51 3.5 Conclusion & Future Work . . . . . . . . . . . . . . . . . . . . . 56 vii Contents 4 The Impact of Choosing Edge Qualities 59 4.1 Model&Notations ......................... 60 4.2 Related Work & Contribution . . . . . . . . . . . . . . . . . . . 64 4.3 Existence of Equilibria . . . . . . . . . . . . . . . . . . . . . . . 65 4.3.1 Equilibria in the Sum-Pricing-Game . . . . . . . . . . . 65 4.3.2 Equilibria in the Max-Pricing-Game . . . . . . . . . . . 70 4.4 Quality of Equilibria in the Sum-Pricing-Game . . . . . . . . . 73 4.4.1 Employing Characteristic Price Functions . . . . . . . . 79 4.5 Quality of Equilibria in the Max-Pricing-Game . . . . . . . . . 80 4.6 Conclusion & Future Work . . . . . . . . . . . . . . . . . . . . . 84 5 Limits of Locality 85 5.1 Model&Notations ......................... 87 5.2 Related Work & Contribution . . . . . . . . . . . . . . . . . . . 89 5.3 Preliminaries............................. 91 5.4 Approximation Quality of Greedy Probing . . . . . . . . . . . 94 5.4.1 Approximation of the k-Local Sum-Game . . . . . . . . 96 5.4.2 Approximation Lower Bound in the Sum-Game . . . . 97 5.4.3 Approximation Upper Bounds in the Sum-Game . . . 104 5.5 Efficiency of Probing Locality . . . . . . . . . . . . . . . . . . . 109 5.5.1 A Clash of Models . . . . . . . . . . . . . . . . . . . . . 109 5.5.2 The Price of Anarchy . . . . . . . . . . . . . . . . . . . . 113 5.6 Conclusion & Future Work . . . . . . . . . . . . . . . . . . . . . 118 6 Multilevel Network Games 121 6.1 Model & Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 123 6.2 Related Work & Contribution . . . . . . . . . . . . . . . . . . . 125 6.3 Bidirectional Gateways . . . . . . . . . . . . . . . . . . . . . . . 126 6.3.1 The Sum-Layer-Game . . . . . . . . . . . . . . . . . . . 127 6.3.2 The Max-Layer-Game . . . . . . . . . . . . . . . . . . . 138 6.4 Unidirectional Gateways . . . . . . . . . . . . . . . . . . . . . . 143 6.4.1 Existence of Equilibria . . . . . . . . . . . . . . . . . . . 144 6.4.2 Quality of Equilibria . . . . . . . . . . . . . . . . . . . . 146 6.5 Conclusion & Future Work . . . . . . . . . . . . . . . . . . . . . 151 Bibliography 153 Index 163 viii CHAPTER 1 Introduction “ The Internet is the first thing that humanity has built that humanity doesn’t understand – the largest experiment in anarchy that we have ever had. ” Eric Schmidt, former CEO Google How are networks formed when their participants are acting selfishly? What is the cost for society by allowing selfish behavior instead of enforcing a central control? And how can we predict the impact of rules that narrow the freedom of decision? – These are the key issues of this thesis, and they are studied for large and dynamic networks. Networks in the context of this thesis are understood as overlay networks. On top of any physical communication layer, they feature connections in the form of logical links among their participants. Specifically, those logical links can be created and adapted almost arbitrarily, while no such modification affects the underlying physical connections. The importance of overlay networks comes from their applications: They are an important technique especially used to create peer-to-peer networks. Popular examples of them are search overlays, like Gnutella or Chord (cf. survey by Androutsellis-Theotokis and Spinellis [AS04]), which provide efficient search mechanisms for large networks by establishing a logical overlay. Still, different examples can be found in other 1 1 Introduction Multilevel Network Games. The last part of my thesis sheds light on the interaction between different network layers. In particular, how selfish agents of a general purpose network utilize a high-speed layer to improve their communication costs. Such high-speed layers ensure that for every communication path in the general purpose layer there is a shorter path in the high-speed layer. Every agent has the minimal strategy set of either connecting or not connecting to the high-speed layer for a fixed price. Connected agents then act as gateways and allow the access to the other layer. Depending on how the high-speed layer is implemented, two different access models for using the high-speed layer are considered: Assuming the high-speed layer is a separated network, it is reasonable that switching between both networks is only possible at specific gateway locations. Otherwise, if the high-speed layer is considered as a logical network layer, then only the access to the high-speed layer is restricted to gateway locations. My model is the first one that analyzes strategic behavior in multilevel networks. The results specifically cover the price of anarchy and show that in general the games are not potential games. The model, analysis, and results presented in this chapter are based on the following publication: 2014 (with S. Abshoff, D. Jung and A. Skopalik). “Multilevel Network Games”. In: Web and Internet Economics – 10th International Conference, WINE 2014, Beijing, China, December 14–17, 2014. Proceedings, cf. [Abs+14]. 8 CHAPTER 2 Preliminaries In this chapter, we present an overview of the different concepts and notions used in the research on network creation games. Thereby, our focus lies on variants derived from the model by Fabrikant et al. [Fab+03], which we will call the classic network creation game models. 1 We start by formally introducing the Sum-Game and the Max-Game as the major model lines, which either model agents who strive for optimizing their average distances or those who strive for optimizing their maximal distances. After that we discuss different solution concepts, measures for network quality, and convergence characteristics for the agents’ operations. Considering these concepts, after that we provide an overview of the results for variants of the classic network creation game. Most notions introduced and used in this section origin from the field of algorithmic game theory. In particular, solution concepts like for example “Nash equilibria” have a long history in algorithmic game theory, and even predating 1 See Section 2.3 for a broader overview and discussion of models derived from the Sum-Game model by Fabrikant et al. [Fab+03]. As discussed in Section 2.4, there is actually a vast amount of literature in economics and mathematics concerning alternative models that predate the model by Fabrikant et al. [Fab+03]. Yet, we see this model as the most relevant one when considering overlay networks and hence refer to it as the classic model in computer science. 9 2 Preliminaries this, in game theory. Instead of discussing them in their full generality, we only introduce and use them in the sense they are required to study the outcome of selfish behavior in network creation games. For a general introduction into algorithmic game theory and discussion of those concepts, we refer to Nisan et al. [Nis+07]. The notions and definitions presented in this chapter form the basis for introducing and discussing the model variants in later chapters. Specifically, the game definition from Section 2.1 and the equilibrium concepts from Section 2.2 are essential for later discussions. 2.1 The Classic Model of Network Creation Games A network creation game consists of a set of agents 𝑉 = {𝑣0,…,𝑣u�−1} (also called peers or players). These agents are interpreted as network nodes that can create edges to other agents. Thereby, each agent can individually decide about the edges she wants to buy in order to minimize her private cost, which is the cost of the bought edges plus the cost for communicating with other agents. In the game introduced by Fabrikant et al., agents strive to minimize the sum of distances to all other agents and are able to perform arbitrary changes of their edges to achieve this goal. In particular, they can exchange any current set of own incident edges with another set of incident edges. Throughout this thesis, we call this game the Sum-Game.2 Stating the Sum-Game in the terms of a strategic game, every agent 𝑢∈𝑉 has a strategy space 𝑆u�≔𝒫(𝑉⧵{𝑢}) , consisting of all possible sets of incident edges as given by the possible edge endpoints. Her current strategy 𝑠u�∈𝑆u� specifies the currently selected edges, i.e., the edges owned by 𝑢 . Then, the combination of all agents’ strategies 𝑆≔(𝑠u�0,…,𝑠u�u�−1)∈𝑆0×…×𝑆u�−1 denotes the strategy profile, which we interpret as a graph 𝐺[𝑆]=(𝑉,𝐸) : Agents are the graph nodes and each strategy 𝑠u�={𝑣1,…,𝑣u�} implies the graph edges {𝑢,𝑣1},…,{𝑢,𝑣u�} . Note that all edges are undirected edges and, moreover, that even though the definition admits multi-edges, throughout this thesis the selfish nature of the agents ensures that no multi-edges will ever be created – creating an already existing edge cannot be a cost-improving operation. Given 2 In the literature, the Sum-Game is also called Buy-Game [Len12; KL13], SumGame (for example, [MS13]), or sometimes simply network creation game, [Fab+03]. 10 2.1 The Classic Model of Network Creation Games a strategy profile 𝑆 and the induced network 𝐺[𝑆] , we denote the length of the shortest path between two agents 𝑢 and 𝑣 as 𝑑u�[u�](𝑢,𝑣) . The length of the longest shortest path, diam(𝐺[𝑆])≔maxu�,u�∈u�𝑑u�[u�](𝑢,𝑣) , gives the diameter of the network. Agents strive for minimizing their private costs, given by a private cost function 𝑐u�(𝑆) . Thereby, the cost of an agent is given only by the current strategy profile. Each edge in an agent’s strategy raises a fixed cost value of 𝛼>0 . There are two variants of private cost functions that yield two different versions of the game: Sum-Game: If the private cost is given by the sum of distances to all other agents plus 𝛼 for every bought edge, we name the game the Sum-Game (introduced by Fabrikant et al. [Fab+03]). Given a strategy profile 𝑆 and an agent 𝑢∈𝑉with strategy 𝑠u�, formally the private cost of 𝑢is: 𝑐u�(𝑆)=𝛼⋅|𝑠u�|+ ∑ u�∈u�𝑑u�[u�](𝑢,𝑣) (2.1) For this cost function, we refer to the first term as edgeu�(𝑆) , called the edge cost of 𝑢, and to the second as distu�(𝑆), called the distance cost of 𝑢. Max-Game: If the private cost is given by the maximum distance to any other agent plus 𝛼 for every bought edge, we name the game the Max-Game (introduced by Demaine et al. [Dem+07]). Given a strategy profile 𝑆 and an agent 𝑢∈𝑉with strategy 𝑠u�, formally the private cost of 𝑢is: 𝑐u�(𝑆)=𝛼⋅|𝑠u�|+max u�∈u� 𝑑u�[u�](𝑢,𝑣) (2.2) For this cost function, we refer to the first term as edgeu�(𝑆) , called the edge cost of 𝑢, and to the second as distu�(𝑆), called the distance cost of 𝑢. Whereas the private cost is a measure of the local cost of an agent, the sum over all agents’ private cost values, cost(𝑆)≔ ∑ u�∈u�𝑐u�(𝑆), (2.3) estimates the overall quality of a network and we refer to it as the social cost. 11 2 Preliminaries 2.2 Notions of Stability, Quality, and Convergence We are interested in the outcome of the selfish actions of the agents. Specifically, how do “stable” states look like in those games? – To answer this, there are different approaches employed in the literature. The most commonly used solution concept for network creation games is that of a (pure) Nash equilibrium, which focuses on network states where no agent can improve her private cost by unilateral strategy changes (cf. Fabrikant et al. [Fab+03]). But there are also different concepts of stability, like the stability of bilateral strategy changes, called pairwise stability (cf. Jackson and Wolinsky [JW96]), which is widespread in economics literature. 2.2.1 Notions of Stability The concept of a Nash equilibrium was introduced by Nash [Nas51] in his seminal work and since then “has emerged as the central solution concept in game theory” (Nisan et al. [Nis+07, p. 12]). We call a state in a game with a strategy profile 𝑆 aNash equilibrium (NE) if no agent can improve her private cost by unilaterally changing her current strategy. 3 Formally, for every agent 𝑣u� and every strategy change 𝑠′u�u�∈𝑆u�u� with the accordingly changed strategy profile 𝑆′≔(𝑠u�0,…,𝑠u�u�−1,𝑠′u�u�,𝑠u�u�+1,…,𝑠u�u�1), it holds that 𝑐u�u�(𝑆)≤𝑐u�u�(𝑆′). Depending on the allowed strategy changes of the agents, we distinguish the following three different Nash equilibria. For each of these equilibrium notions, we further introduce a so-called greedy equilibrium variant that denotes the stability of single-edge changes. Buy Equilibrium (BE): A strategy profile 𝑆 forms a buy equilibrium if the agents are allowed to arbitrarily buy, remove, and swap own incident edges and 𝑆 forms a Nash equilibrium. If no agent can buy one incident edge, remove one own incident edge, or swap one incident edge, 𝑆 forms agreedy buy equilibrium. Asymmetric Swap Equilibrium: A strategy profile 𝑆 forms an asymmetric swap equilibrium if the agents are only allowed to arbitrarily swap own 3 In related literature, this solution concept is often called a “pure” Nash equilibrium to distinguish it from the so-called “mixed” Nash equilibria, where strategies are chosen only with certain probabilities. Since we will focus our analysis only on pure equilibria, we omit the extra term. 12 2.2 Notions of Stability, Quality, and Convergence incident edges and 𝑆 forms a Nash equilibrium. If no agent can swap one own incident edge, 𝑆 forms a greedy asymmetric swap equilibrium. Note that for this equilibrium notion, the edge price 𝛼 will be omitted, since the number of edges does not change. Swap Equilibrium (SE): A strategy profile 𝑆 forms a swap equilibrium if the agents are allowed to arbitrarily swap any incident edges and 𝑆 forms a Nash equilibrium. If no agent can swap one arbitrary incident edge, 𝑆 forms a greedy swap equilibrium. Note that for this equilibrium notion, there are no edge ownerships and thus the edge price 𝛼can be omitted. For both, the game variants with sum cost function and with maximum cost function, all these different equilibria exist. Depending on the edge price 𝛼 , either a clique (Sum-Game for 𝛼≤1 , Max-Game for 𝛼 ≤ 1/(𝑛−1) ) or a star (Sum-Game for 𝛼>1 , Max-Game for 𝛼 > 1/(𝑛−1) ) constitutes a buy equilibrium (cf. Fabrikant et al. [Fab+03] and Demaine et al. [Dem+07]). For the swap equilibrium and the asymmetric swap equilibrium, always a star network forms an equilibrium (cf. Alon et al. [Alo+13] and Mihalák and Schlegel [MS12]). Note that the named equilibrium networks are also stable for the corresponding greedy equilibrium variants. For the above equilibrium concepts, we consider agents who always want to perform a strategy change when they improve their costs. Yet, this can lead to situations where the gain of an agent is negligibly small but the effort in terms of to be changed edges is very high. Facing this, the notion of an 𝜀 -approximate equilibrium (e.g., Chien and Sinclair [CS07] and Skopalik and Vöcking [SV08]) captures agents that perform strategy changes only if they reduce their cost by a reasonable fraction. We say for 𝜀>1 that a strategy profile is an 𝜀 -approximate equilibrium if no agent can decrease her private cost by a factor of at least 𝜀 by unilaterally changing her strategy, i.e., to be at most 1/𝜀 times the former cost value. 4 Note that this notion of approximate equilibria applies to all above-mentioned equilibrium variants. 4 In the literature, there is a similar solution concept with the same name that considers the additive improvement by u� instead of the multiplicative improvement (for example, Daskalakis et al. [DMP07]). Another popular choice for the approximation parameter is u� . 13 2 Preliminaries 2.2.2 Quality of Equilibria The typical way of evaluating the quality of a network is by estimating its social cost. Our main interest here is the quality of equilibrium networks; in other words, what is the quality of solutions in a network creation game? Specifically, we ask: (a) How bad are equilibria in the worst-case? (b) How good are equilibria in the best-case? Since for most variants of network creation games the equilibria are not unique, these two questions constitute the maximal and minimal loss by the selfish acting of the agents, which can possibly be far apart. The maximum loss by selfish behavior was formalized by Koutsoupias and Papadimitriou [KP99] as the price of anarchy (PoA) and is defined as the ratio of the highest social cost of any equilibrium network and the optimal social cost. The minimal loss by selfish behavior was first studied by Schulz and Moses [SM03] and nowadays is known as the price of stability (PoS). 5 Its value is given by the ratio of the smallest social cost of any equilibrium network and a minimum social cost network (not necessarily forming an equilibrium). Definition 2.1 (Price of Anarchy and Price of Stability) . Consider a game with social cost function, cost ∶𝒮→ℝ>0, whereas 𝒮 is the set of all possible strategy profiles. Let 𝒮u�u� ⊆𝒮 be the set of all equilibrium strategy profiles and 𝑆Opt be the strategy profile with minimal social cost. Then we define: (a) price of anarchy: max u�∈𝒮u�u� cost(u�) cost(u�Opt) (b) price of stability: min u�∈𝒮u�u� cost(u�) cost(u�Opt) Note that both maximum and minimum are defined over any number of agents. Given the equilibrium networks from the previous section, it is easy to see that the price of stability is bounded to be at most two and it is even close to one for 5 The price of stability is sometimes also named the optimistic price of anarchy, see [Ans+03]. It was first mentioned under the name “price of stability” by Anshelevich et al. [Ans+04]. 14 2.2 Notions of Stability, Quality, and Convergence several equilibrium concepts and parameters. On the other hand, bounding the price of anarchy is a challenging task that was considered in a remarkable series of papers (see Section 2.3). If we have a strategy profile 𝑆 that is an 𝜀 -approximate buy equilibrium with a corresponding network 𝐺[𝑆] , we can derive an upper bound for the price of anarchy by generalizing an argument by Albers et al. [Alb+14, proof of Lemma 3.4]. Theorem 2.2. For the Sum-Game with 𝛼≥2 , let 𝑆 be a strategy profile that is an 𝜀 -approximate buy equilibrium and let 𝑆Opt be a strategy profile with minimal social cost. Then the ratio of them is at most: cost(𝑆) cost(𝑆Opt)≤𝜀(3+diam(𝐺[𝑆])) Proof. Let 𝑢 be an arbitrary fixed agent and consider 𝑇 to be a shortest path tree rooted at 𝑢 . (Note that paths to all other agents exist, since 𝑆 is an 𝜀 -approximate buy equilibrium.) For every agent 𝑣∈𝑉 , we consider the strategy change of removing all own edges that do not belong to 𝑇 and creating one new edge to 𝑢 . Thereby, let 𝑇u�⊆ 𝑇 be the set of tree edges owned by 𝑣 . Since 𝑆 is an 𝜀 -approximate buy equilibrium and no agent 𝑣 changes distu�(𝑆) by this operation, we get 𝑐u�(𝑆)≤𝜀(𝛼⋅|𝑇u�|+𝛼+(𝑛−1)+distu�(𝑆)). Hence, for the social cost we get: cost(𝑆)= ∑ u�∈u�𝑐u�(𝑆)≤ ∑ u�∈u�𝜀(𝛼⋅|𝑇u�|+𝛼+(𝑛−1)+𝛿u�) ≤𝜀(𝛼⋅|𝑇|+(𝑛−1)𝛼+(𝑛−1)2+𝑛𝛿u�) ≤𝜀(2(𝑛−1)𝛼+(𝑛−1)2+𝑛(𝑛−1)⋅diam(𝐺[𝑆])) Since the optimal solution is a star and has social cost of 𝛼(𝑛−1)+𝑛(𝑛−1) , we get as the upper bound for the social cost ratio 𝜀(2+1+diam(𝐺[𝑆])). 2.2.3 Convergence of Improving-Response Processes For both games, the Sum-Game and the Max-Game, we know that equilibria exist. In particular, this also holds for all variants of buy and swap equilibrium concepts as introduced above. Yet, if we consider some non-equilibrium 15 2 Preliminaries strategy profile as a starting point, it is a valid question whether agents can ever reach such an equilibrium state from there. Specifically we ask: Can we find for every initial strategy profile a sequence of improving strategy changes that transforms it into an equilibrium strategy profile? And, if yes, how long is such a sequence? These sequences of iterative applications of cost-improving operations of the agents are called improving-response processes. Here, an improving response (IR) denotes any cost-decreasing strategy change of an agent. An improving response is called a best response (BR) if this strategy change is optimal regarding the maximum private cost decrease for this agent. We say an improvingresponse process (or best-response process) converges to an equilibrium if the final strategy profile of the process is an equilibrium. If, for a game with a finite number of strategies, there is an infinite long improving-response process, then the process must contain a cycle. We call such a cycle an improving-response cycle (or best response cycle, respectively). A game is called a weakly acyclic game (WAG) (introduced by Young [You93]) if, starting from any initial strategy profile, there exists some finite sequence of improving responses that eventually converges to an equilibrium state. This concept resembles the natural class of games that possibly reach equilibrium states via simple and globally asynchronous strategic actions, independently of their starting states. For this, even very simple dynamics, like randomized improving- or best-response dynamics or regret-based dynamics, suffice (cf. [You93; Mar+09]). Examples for such weakly acyclic games are given by Engelberg and Schapira [ES14] and Milchtaich [Mil96]. In [Mil96], Milchtaich considered a variant of congestion games but with individual payoff functions for every player. Engelberg and Schapira [ES14] introduced a class of routing games that models aspects of Internet-routing algorithms. For both of these weakly acyclic games we have that one can find improving-response cycles and hence, not every sequence of improving strategy changes leads to an equilibrium. A class of games that was subject to substantially more research interest is the class of potential games (cf. Monderer and Shapley [MS96]). This is the subclass of all weakly acyclic games for which it holds that every sequence of improving-response operations terminates in an equilibrium: i.e., every such sequence is finite. In particular, this is known as the finite improvement 16 2.3 Known Results property (FIP). Monderer and Shapley [MS96] showed that a game has the finite improvement property if and only if there exists a generalized ordinal potential function, 𝛷∶𝑆0×⋯×𝑆u�−1 →ℝ≥0, that maps strategy profiles to real numbers such that if an agent performs an improving response, then the potential value decreases. One of the most prominent examples for games belonging to this class are congestion games (introduced by Rosenthal [Ros73]). Monderer and Shapley [MS96] showed that the class of congestion games is actually isomorphic to potential games. Note that though every sequence of improving responses is finite, these sequences still may be exponentially long (cf. Fabrikant et al. [FPT04]). The convergence properties in the context of network creation games were studied by Kawald and Lenzner [KL13]. For the Max-Game and the Sum-Game, i.e., with agents who can arbitrarily buy, delete, and swap edges, they showed that improving-response cycles may exist and hence these games cannot be potential games. They further showed that these negative results still hold if agents are only allowed to perform greedy operations as well as if the agents are only allowed to swap edges. The only positive exception, where such a game is known to fulfill the finite improvement property, are swap games where the starting network is a tree (cf. [Len11; KL13]). This means, these game variants are potential games and every sequence of improving response operations converges to an equilibrium state. For network creation games with bilateral edge operations [CP05], Kawald and Lenzner [KL13] showed that the game is not even weakly acyclic, meaning that there are strategy profiles for which no sequence of best-response operations leads to an equilibrium. The question whether the classic network creation games with unilateral edge operations by Fabrikant et al. are weakly acyclic games or not is still an open question, though. 2.3 Known Results Starting with the study by Fabrikant et al. [Fab+03], computing the price of anarchy in network creation games attracted a lot of attention. Figure 2.1 summarizes the currently best known price of anarchy results for the Sum- 17 2 Preliminaries price depending on 𝛿 . Watts [Wat01] proposed a dynamic process to analyze the outcomes of the selfish decisions of the agents. This process uniformly at random proposes possible edges to the agents, who then can decide whether they want to create the edge or not. Corbo and Parkes [CP05] considered bilateral edge creation games for agents with the Sum-Game cost function from Fabrikant et al. [Fab+03]. The authors show that theprice of anarchyisworse than forthe unilateral gameby Fabrikant et al. Along their analysis, they showed the equivalence of pairwise stability and a two-player coalition refinement of buy equilibria. Interestingly, Kawald and Lenzner [KL13] showed that best-response dynamics in this game are not even weakly-acyclic in the sum distance variant, and admit best-response cycles in the maximum distance variant. In contrast to the pairwise stability notions mentioned so far, Bala and Goyal [BG00] considered games with unilateral edge creations. Edges in their game variants are either unidirectional or bidirectional, but there is always only one agent who decides to create and pay for an edge. The utility of agents is given by exponential payoffs like in the game by Jackson and Wolinsky [JW96]. Although the cost function of the agents is different, the game is very close to the game by Fabrikant et al. [Fab+03]. Moscibroda et al. [MSW06] considered the selfish behavior of agents as peers in peer-to-peer networks, which are modeled as metric spaces. Like in the Sum- Game, the agents strive for minimizing their trade-off between the edge cost and the sum of distances to all other agents. In this setting with an underlying metric space, the authors can show a price of anarchy of O (min{𝛼,𝑛}) . They further provide negative convergence results and moreover, they show that buy equilibria do not always exist; even deciding if such an equilibrium exists is 𝒩𝒫-complete. A series of research focuses on the formation of social networks. Agents in these networks especially seek for being well connected with agents who have a high influence or centrality in the network. For example, Nikoletseas et al. [Nik+15] introduced a swap-based model where the agents’ revenue is based on the sum of degrees of their direct neighbors. With this, the authors aim to provide a model for large distributed systems that are similar to power law or preferential attachment graphs. In this game, there exists an exact potential and hence improving-response processes always converge. Hereby, 24 2.4 Alternative Models the convergence time is polynomially bounded. This still holds even when restricting the agents by a local view such that they can only probe the degrees of a fixed number of other agents; improving-response dynamics still converge in expected polynomial time. A different approach is provided by Brautbar and Kearns [BK11]. They proposed a model driven by the observation that friendships in social networks are often transitive and thus define the utility of an agent essentially by the number of triangle she is part of. Specifically, using the clustering coefficient of an agent, which is the probability of two uniformly at random selected neighbors being connected, the utility of an agent is the clustering coefficient minus the edge cost (hence, only an edge price of 𝛼 ∈ (0,1) is reasonable). Considering the agents having a high clustering coefficient, we can see which agents are important in the network in terms of being well connected via cliques. Note that for the remainder of this thesis, we will only consider variants of the classic game by Fabrikant et al. [Fab+03]. 25 CHAPTER 3 Loss and Benefit of Friendships In this chapter, we analyze the impact of non-uniform communication interests on the quality of equilibrium networks: Given a large and dynamic network, the agents are usually not interested in communicating with all other agents but only with a subset of them. Our focus lies on the different aspects of influences by such non-uniform communication regarding the negative and the positive effects on the quality of equilibria. Throughout this chapter, two agents are called friends when they want to communicate with each other. In our model, friendships are mutual and an agent is only interested in her direct friends and not necessarily her friends’ friends. This means, we do not assume any gain by having many first or second order friends, like it may be in social networks. Rather, we understand the friendships as some given allocation, which simply specifies which agents want to communicate with each other. Our analytical tool for modeling these friendships is a so-called friendship graph. Given two nodes in this graph, the respective agents are friends of each other if and only if there is a friendship graph edge between them. First, we consider the worst-case impact on equilibrium networks by friendship allocations in the Swap-Game [Alo+10]. By discarding the strong dependency of the edge price, which is present in most other models, this model is 27 3 Loss and Benefit of Friendships particularly well suited to study structural equilibrium properties. On the one hand, we seek for combinations of a friendship graph and a corresponding equilibrium network that maximizes the worst-case social cost ratio when compared to an optimal solution. On the other hand, we aim for upper bounds on the price of anarchy when facing arbitrary friendship allocations. Thereby, we will show a worst-case behavior for almost all considered variants. The only exceptions are tree equilibria for games with agents who strive for minimizing their maximum distances to their friends. In this case, we provide an interesting structural property of equilibrium networks which leads to a surprising bound for the price of anarchy of 𝛩(√𝑛). Facing these negative results, we change our focus to the analysis of beneficial effects of friendships. We exploit the properties given by friendship allocations in the Sum-Game and the Max-Game (cf. Section 3.1, [Fab+03]) that ensure best-response processes to lead to equilibria with not too high social costs. Specifically, we introduce a new concept that we name process equilibrium and show that equilibria in this natural class, for which connected components of the friendship graph correspond to connected components in the equilibrium, lead to a drastically improved price of anarchy results. For all such game variants, note that if the friendship graph is a clique, our games with friendship allocations coincide with their original versions in which every agent is interested in every other agent. Chapter Basis. The model, analysis, and results presented in the remainder of this chapter are based on the following publication: 2012 (with M. Hüllmann, P. Kling and A. Setzer). “Basic Network Creation Games with Communication Interests”. In: Algorithmic Game Theory – 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22–23, 2012. Proceedings, cf. [Cor+12]. Chapter Outline. In Section 3.1, we introduce friendship graphs to model a non-uniform communication behavior of agents in network creation games. An overview of our results and a comparison with related work is provided in Section 3.2. The main part of this chapter is given in Section 3.3, which is the analysis of the worst-case behavior of friendship allocations in Swap-Games. 28 3.1 The Friendship Model & Preliminaries Section 3.4 contrasts these negative results with a more optimistic view on friendship allocations and shows how non-uniform communication interests can have a positive effect on the overall quality of networks. Section 3.5 recaps the results and presents an outlook for future research. 3.1 The Friendship Model & Preliminaries As usual for network creation games, we consider a set of 𝑛 selfish agents 𝑉 = {𝑣1,𝑣2,…,𝑣u�} who unilaterally perform strategy changes in order to improve their private costs. The models considered in this chapter consist of two main ingredients: (a) The friendship model, which states with respect to whom agents want to reduce their communication costs, and (b) the game model, which states how agents can act. Note that we use the notions and notations from Section 2.1 and Section 2.2.3 and name only differences explicitly here. Friendship Model. Every agent 𝑢∈𝑉 has a fixed set of friends F(𝑢) ⊆ 𝑉 , whereas F∶𝑉→𝒫(𝑉) is called a friendship allocation. Throughout this chapter, if not specified differently, we only consider friendship allocations that fulfill: (a) Friendships are mutual and hence for every 𝑣∈F(𝑢)it holds 𝑢∈F(𝑣). (b) Every agent 𝑢∈𝑉hast at least one friend: i.e., |F(𝑢)|≥1. Considering such a friendship allocation, we define a friendship graph 𝐺u�= (𝑉,F) , whereas the agents 𝑉 formthe graphnodes and there is anedgebetween two nodes if and only if the respective agents are friends. Edges in this graph are bidirectional. Game Model. We combine friendship allocations with two different game concepts. On the one hand, we consider Swap-Games (cf. Section 2.2), which are convenient for analyzing structural properties of worst-case equilibrium settings by dismissing the use of an edge price parameter. On the other hand, we study friendship allocations in Buy-Games (cf. Section 2.1) with respect to the positive effects of friendships regarding the social cost. 29 3 Loss and Benefit of Friendships Swap-Game: In the Swap-Game variant, the agents 𝑉 are connected by a set of bidirectional edges 𝑆 . These edges are not owned by anyone and hence any edge can be swapped arbitrarily by any incident agent. Here, the swap operation of an agent is the simultaneous removal of an incident edge and replacement by a different incident edge, formally stated as {𝑢,𝑣} → {𝑢,𝑤} for agent 𝑢 swapping the edge {𝑢,𝑣} to edge {𝑢,𝑤} (cf. Figure 3.1). An agent’s operation can consist of an arbitrary combination of simultaneously executed swaps. The current strategy profile, which is equal to the current set of edges in the network, is called 𝑆 and in conformity with other models we denote the implied network as 𝐺[𝑆] . In these games, we only consider connected networks and restrict the agent’s actions such that agents must always preserve connectivity. Any agent strives to minimize her private cost, which is given either by the average distance or by the maximum distance cost function. Namely, in the Sum-Swap-Game,1the private cost of an agent is 𝑐u�(𝑆)≔ 1 |F(𝑢)| ∑ u�∈F(u�)𝑑u�[u�](𝑢,𝑣), and in the Max-Swap-Game, it is 𝑐u�(𝑆)≔ max u�∈F(u�)𝑑u�[u�](𝑢,𝑣). Here, 𝑑u�[u�](𝑢,𝑣) denotesthe shortest path distanceinthenetwork 𝐺[𝑆]= (𝑉,𝑆). Buy-Game: For the Buy-Game variant, we consider buy equilibria of the Sum- Game and the Max-Game (cf. Section 2.1). In this chapter, we name these games Sum-Buy-Game and Max-Buy-Game to avoid confusion with the Swap-Games. In the considered Buy-Games, agents can arbitrarily buy incident edges to other agents, each for a fixed price of 𝛼>0 . The set of edges of an agent 𝑢∈𝑉 is given by 𝑠u� and 𝑆 is the joint strategy profile of all individual strategies. For the Sum-Buy-Game, the private cost 1 Note that for the Sum-Swap-Game we normalize the distance cost by the number of friends and thus gain the average distances. This was not necessary in the original games with uniform communication interests, where every agent wanted to communicate with exactly u�−1other agents. 30 3.2 Related Work & Contribution 𝑥𝑤 𝑣𝑢 Figure 3.1: Illustration of a swap operation in the Max-Swap-Game. The blue agents denote the friends F(u�) of agent u� (red), the orange line states the initial longest shortest path from agent u� to any of her friends. The swap {u�,u�}→{u�,u�} then reduces u�’s private cost from 4to 3. function is 𝑐u�(𝑆)≔𝛼⋅|𝑠u�|+ 1 |F(𝑢)| ∑ u�∈F(u�)𝑑u�[u�](𝑢,𝑣), and in the Max-Buy-Game, it is 𝑐u�(𝑆)≔𝛼⋅|𝑠u�|+ max u�∈F(u�)𝑑u�[u�](𝑢,𝑣). The overall quality of a network 𝐺[𝑆] is measured by the sum over all private costs and is called the social cost cost(𝑆)≔∑u�∈u�𝑐u�(𝑆) . Using the same terms as in Section 2.2, we denote a strategy profile as equilibrium if no agent can improve her private cost by a unilateral strategy change. To quantify the worst-case loss of selfish behavior, we use the price of anarchy, which is the worst-case ratio of any equilibrium’s social cost and the minimal cost of any strategy profile. 3.2 Related Work & Contribution While network creation games, as introduced by Fabrikant et al. [Fab+03] and their variants, seem to capture the dynamics and evolution caused by the selfish behavior of agents in an accurate way, there is a major drawback: Most of those models assume agents to be interested in communicating with all other agents in the network. Given the immense size of communication networks, this seems rather unrealistic. In reality, agents usually communicate in small groups and each only has a small subset of the network participants she is interested in. 31 3 Loss and Benefit of Friendships The only paper apart from [Cor+12] that considers such non-uniform communication interests in the framework of network creation games is by Halevi and Mansour [HM07]. They also use the above stated concept of friendship allocations to model the non-uniform communication interests of the agents. However, their focus only lies on the Sum-Buy-Game (cf. Section 2.1), for which they proved the existence of equilibria for almost all edge prices of 𝛼 (in particular, 𝛼≤1 and 𝛼≥2 ). For general 𝛼 , they provided an upper bound of O (√𝑛) for the price of anarchy. For an average degree 𝑑 of the friendship graph, i.e., the average number of friends of the agents, in the case of 𝛼 or 𝑑 being a constant and 𝛼= O (𝑛𝑑) , they upper bounded the price of anarchy by a constant. Furthermore, the authors provided a family of problem instances for which the price of anarchy is lower bounded by 𝛺(log u� log log u�). A different approach to introduce non-uniform communication interests was used by Albers et al. [Alb+06]. They apply a so-called weighted traffic matrix to the Sum-Buy-Game such that for the communication cost of an agent every distance is multiplied by a traffic value from the interval (0,1) , which indicates how much traffic should be sent to the target. The special case of having only 0/1-weights results in the friendship graph considered in this chapter. However, their model and applied techniques explicitly require all traffic values to be greater than 0. Different to explicit a-priori given friendship allocations, there are also models where the utility of an agent is based on how many other agents are in her two-neighborhood, like Nikoletseas et al. [Nik+13], for example. In that game, the utility of an agent is the sum of degrees of her neighbors. For the results about the uniform interest case in the Buy-Game and the Swap-Game, we refer to Section 2.3. Contribution. In this chapter, we introduce a generalized class of swap equilibria in network creation games (cf. Section 2.3) by taking the different friends of individual agents into account. For the Swap-Game with friendship allocations, we provide tight price of anarchy results for all interesting model variants: The price of anarchy is worst possible for the Sum-Swap-Game, this even when restricting to the class of tree equilibria. For the Max-Swap-Game it is worst possible for arbitrary equilibria and turns out to be only 𝛩(√𝑛) for tree 32 3.3 Worst-Case Friendships in Swap-Games equilibrium networks. The latter result uses an interesting structural insight into equilibrium networks (see Binding-Sequence, Definition 3.7). We show that the price of anarchy for tree equilibrium networks in the Max-Swap-Game can be further characterized by the size 𝑀 of a maximum independent set in the friendship graph, which gives a price of anarchy of at most 2𝑀 and hence an improved bound if 𝑀≤√𝑛 . For example, for a complete friendship graph we have 𝑀=1and hence a constant price of anarchy. Moreover, we turn our interest to a more optimistic approach of how selfish behavior can deteriorate the social cost. Thereby, we identify a structural property of certain best-response processes, namely that the connected components of the friendship graph are also connected components in respective equilibrium networks. Using this, we introduce the class of process equilibria and for this class provide an improved price of anarchy bounds. For the Sum- Buy-Game we provide a so-called process price of anarchy of O (log𝑛+√𝑁) ; whereas for the Max-Buy-Game it is O (𝑛2/u�+(𝑁/𝛼)1/3) . Here, 𝑁 is the size of the largest connected component in the friendship graph. 3.3 Worst-Case Friendships in Swap-Games In this section, we consider the worst-case impact of friendship allocations in Swap-Games. Our focus lies on the existence of equilibria, the convergence of best-response processes, and specifically on bounds for the price of anarchy. For the original Swap-Games with uniform interests and thus with a complete friendship graph, we know from the discussion in Section 2.3 that equilibria always exist, that for tree equilibrium networks the price of anarchy is constant and that for the Sum-Swap-Game with 𝑛 agents it is at most 2O(√lg u�) , whereas for the Max-Swap-Game only a lower bound of 𝛺(√𝑛) is known (cf. Alon et al. [Alo+10]). We start our analysis with games utilizing the maximum-distance price function, for which we show an interestingly different behavior with regard to the price of anarchy, when differentiating between tree equilibrium networks and arbitrary equilibriums. Later, the Sum-Swap-Game will show a worst-case behavior also for the class of tree equilibrium networks. This is a remarkable difference to the games with uniform interests, where tree equilibria behave 33 3 Loss and Benefit of Friendships Then we call this sequence a Binding-Sequence (cf. illustration in Figure 3.4). For such a Binding-Sequence, we will show two key properties that hold in any tree equilibrium network: Given a Binding-Sequence and some agent 𝑣u� therein, then (a) 𝑣u� ’s successor 𝑣u�+1 cannot have a much lower private cost than 𝑣u� (cf. Lemma 3.8) and (b) the shortest path from 𝑣u� to 𝑣u�+1 can overlap by at most one edge with the shortest path to 𝑣u�’s Binding-Sequence predecessor (cf. Lemma 3.9). Later, we will show that for any agent there necessarily exists a Binding- Sequence of about the same length as her private cost value. Then, by bounding the maximum length of a Binding-Sequence, we will obtain a private cost upper bound. Lemma 3.8. For a friendship allocation F , let 𝑆 be a Max-Swap-Game tree equilibrium strategy profile and 𝑣0,…,𝑣u� a Binding-Sequence. Then, for each two consecutive sequence agents 𝑣u� and 𝑣u�+1 , with 0≤𝑖<𝑚 , it holds 𝑑u�[u�](𝑣u�,𝑣u�+1)≥𝑐u�u�(𝑆)−1 and 𝑐u�u�+1(𝑆)≥𝑐u�u�(𝑆)−1. Proof. For 𝑖 ∈ {0,…,𝑚−1} consider an agent 𝑣u� in the Binding-Sequence. Then, by Lemma 3.6 there exist 𝑥,𝑦 ∈ F(𝑣u�) with 𝑑u�[u�](𝑣u�,𝑥) = 𝑐u�u�(𝑆) and 𝑐u�u�(𝑆)≥𝑑u�[u�](𝑣u�,𝑦)≥𝑐u�u�(𝑆)−1 such that 𝑣u� is connected by at most one edge to the shortest path from 𝑥 to 𝑦 . At least one of these agents is a valid candidate for the next Binding-Sequence agent 𝑣u�+1 . Yet, even if 𝑣u�+1 is neither 𝑥 nor 𝑦 , still we gain a lower bound for the maximum distance: 𝑑u�[u�](𝑣u�,𝑣u�+1)≥min{𝑑u�[u�](𝑣u�,𝑥),𝑑u�[u�](𝑣u�,𝑦)}≥𝑐u�u�(𝑆)−1 This further gives 𝑐u�u�+1(𝑆)≥𝑐u�u�(𝑆)−1. Lemma 3.9 (Increasing Distance) . For a friendship allocation F , let 𝑆 be a Max- Swap-Game tree equilibrium strategy profile and 𝑣0,…,𝑣u� a Binding-Sequence. Then, the distances to 𝑣0 are monotonously increasing, i.e., 𝑑u�[u�](𝑣0,𝑣u�)≤𝑑u�[u�](𝑣0,𝑣u�+1) for 𝑖=1,…,𝑚−1. 40 3.3 Worst-Case Friendships in Swap-Games 𝑣0 𝑣u�−1 𝑤1 𝑤2𝑣u�=𝑤0 𝑣u�+1=𝑤u� Figure 3.5: Illustration of Lemma 3.10: edge {u�0,u�1}is used only two times. Proof. Using 𝑐u�1(𝑆)≥3 we get with Remark 3.5 that ∣F(𝑣1)∣≥2 . Hence, by Lemma 3.6 there exists an agent 𝑣2 such that the paths from 𝑣1 to 𝑣0 and from 𝑣1 to 𝑣2 overlap by at most one edge. By construction of the Binding-Sequence, the distance 𝑑u�[u�](𝑣0,𝑣2) is maximal among all distances from 𝑣0 to agents 𝑣∈F(𝑣1)and hence we get 𝑑u�[u�](𝑣0,𝑣1)≤𝑑u�[u�](𝑣0,𝑣2). Now assume that there is an agent 𝑣u� with the smallest index 𝑖≥2 in the Binding-Sequence for which the claim does not hold. This is, 𝑑u�[u�](𝑣0,𝑣u�−1)≤ 𝑑u�[u�](𝑣0,𝑣u�) and 𝑑u�[u�](𝑣0,𝑣u�)>𝑑u�[u�](𝑣0,𝑣u�+1) . Denote by 𝑥 the most distant agent from 𝑣0 who is on all shortest paths from 𝑣0 to 𝑣u�−1 , from 𝑣0 to 𝑣u� , and from 𝑣0 to 𝑣u�+1 . Such an agent 𝑥 exists, since especially 𝑣0 fulfills the restrictions. By the choice of 𝑖and since all these paths contain agent 𝑥, we get: 𝑑u�[u�](𝑥,𝑣u�−1)≤𝑑u�[u�](𝑥,𝑣u�)>𝑑u�[u�](𝑥,𝑣u�+1)(3.1) By definition of the Binding-Sequence, 𝑣u� is connected by at most one edge to the shortest path from 𝑣u�−1 to 𝑣u�+1 . Hence, 𝑥 must be an agent on the path from 𝑣u�−1 to 𝑣u�+1 . First note that 𝑥 cannot be 𝑣u� or a neighbor of 𝑣u� , since for those cases (3.1) yields 𝑑u�[u�](𝑥,𝑣u�+1)<𝑑u�[u�](𝑥,𝑣u�)≤1 . Furthermore, 𝑥 must lie on the shortest path from 𝑣u�−1 to 𝑣u� , since otherwise 𝑥 would lie on the shortest path from 𝑣u� to 𝑣u�+1 , which together with 𝑑u�[u�](𝑣u�−1,𝑣u�)≥3 would imply 𝑑u�[u�](𝑥,𝑣u�)<𝑑u�[u�](𝑥,𝑣u�−1) . But this gives 𝑑u�[u�](𝑥,𝑣u�)≤𝑑u�[u�](𝑥,𝑣u�+1) and is a contradiction. Lemma 3.10. For a friendship allocation F , let 𝑆 be a Max-Swap-Game tree equilibrium strategy profile with network 𝐺[𝑆]=(𝑉,𝑆) and 𝑣0,…,𝑣u� a Binding-Sequence. 41 3 Loss and Benefit of Friendships Then, no edge in 𝑆 is used more than two times by the shortest path visiting the agents 𝑣0,…,𝑣u�in the given order. Proof. We label the agents of 𝐺[𝑆] by their distances to 𝑣0 . This is, for every 𝑣∈𝑉 we define level(𝑣)≔𝑑u�[u�](𝑣0,𝑣) to be the distance to 𝑣0 . For an arbitrary agent 𝑣u� with 𝑘∈{1,…,𝑚−1} we consider the corresponding shortest path (𝑣u�=∶𝑤0,𝑤1,…,𝑤u�≔𝑣u�+1) to agent 𝑣u�+1 of some length 𝑡 . By definition, 𝑣u� is connected by at most one edge to the shortest path from 𝑣u�−1 to 𝑣u�+1 (for an illustration cf. Figure 3.5). By Lemma 3.9 we have level(𝑣u�−1)≤level(𝑣u�)≤ level(𝑣u�+1) . Hence, for 𝑖 = 2,…,𝑡−1 we get level(𝑤u�) < level(𝑤u�+1) . This means that at most one edge (specifically edge {𝑤0,𝑤1} ) of the shortest path from 𝑣0 to 𝑣u� is used a second time by the shortest path traversal from 𝑣u� to 𝑣u�+1 . By Lemma 3.8 we have 𝑡≥𝑐u�u�(𝑆)−1≥3 and get level(𝑣u�)<level(𝑣u�+1) . Finally, we conclude the proof of the private cost upper bound by considering a pair of most distant friends and show that their distance corresponds to a Binding-Sequence of similar length. Using that for the traversal of a Binding- Sequence every tree edge is used at most twice, we get an upper bound on its length and by this an upper bound in the maximal distance. Theorem 3.11 (Max-Swap-Game: private cost upper bound) . For a friendship allocation F let 𝐺[𝑆]=(𝑉,𝐸) be a Max-Swap-Game tree equilibrium network with 𝑛≔|𝑉|agents. Then, for all 𝑢∈𝑉we have 𝑐u�(𝑆)=O(√𝑛). Proof. Let 𝑣0∈ 𝑉 be an agent with maximal private cost. We can assume that 𝑣0 has at least one friend at a distance of at least 3 , since otherwise the claim already holds. Let 𝑣1 be a most distant friend 𝑣1∈F(𝑣0) and denote the distance between 𝑣0and 𝑣1as 𝐷≔𝑑u�[u�](𝑣0,𝑣1)=𝑐u�0(𝑆). (Existence.) Agents 𝑣0,𝑣1 obviouslyfulfillthe conditionsforaBinding-Sequence. Thus, it suffices to show that given the beginning of a Binding-Sequence 𝑣0,…,𝑣u� with 𝑐u�u�(𝑆) > 3 , for 𝑗 = 0,…,𝑖−1 , either we can find a next agent 𝑣u�+1 who suffices the conditions or otherwise 𝑐u�u�(𝑆) = 3 and the sequence terminates. If we assume 𝑐u�u�(𝑆) > 3 , then by Lemma 3.6 there exist agents 𝑥,𝑦 ∈ F(𝑣u�) with 𝑑u�[u�](𝑣u�,𝑥) = 𝑐u�u�(𝑆) and 𝑐u�u�(𝑆) ≥ 𝑑u�[u�](𝑣u�,𝑦) ≥ 𝑐u�u�(𝑆)−1 such that 𝑣u� is connected by at most one edge to the shortest path from 𝑥 to 𝑦 . Since 𝑐u�u�(𝑆)>3 , both 𝑐u�(𝑆)≥3 and 𝑐u�(𝑆)≥3 hold. Now, for at least one 42 3.3 Worst-Case Friendships in Swap-Games agent ( 𝑥 or 𝑦 ) we have that this agent is most distant to 𝑣u�−1 , she is not 𝑣u�−2 , and thus she fulfills the conditions for a Binding-Sequence. (Traversal.) Given the existence, now we can apply the previous lemmas for providing the minimal length of such a Binding-Sequence: Lemma 3.8 states that by construction of the Binding-Sequence we always have 𝑐u�u�+1(𝑆)≥𝑐u�u�(𝑆)−1 . Lemma 3.9 implies that no agent can be contained more than once in a Binding- Sequence. By the arguments above we get that we can always find a new agent for the Binding-Sequence until we reach an agent 𝑤 with 𝑐u�(𝑆)=3 . Hence, the Binding-Sequence contains at least 𝑐u�0(𝑆)−2 agents. Since the distance between two succeeding agents of the Binding-Sequence decreases by at most one per agent, a traversal of this Binding-Sequence consists of at least u�u�0(u�) ∑ u�=3 𝑖= 𝑐u�0(𝑆)2+𝑐u�0(𝑆)−6 2 edges. From these edges, by Lemma 3.10, at least (𝑐u�0(𝑆)2+𝑐u�0(𝑆)−6)/4 many edges are different. (Private cost upper bound.) Finally, we use that the traversal of the Binding- Sequence uses at least u�2+u�−6 4 -many different edges. Since the tree has exactly 𝑛−1 edges, we get (𝐷2+𝐷−6)/4≤𝑛−1 as an upper bound for the size of every Binding-Sequence and hence the private cost upper bound is 𝐷= O (√𝑛) . Next we show that this private cost bound is actually tight. This means, there are combinations of a friendship allocation and a tree equilibrium network of 𝑛 agents such that there is an agent with private cost of 𝛺(√𝑛) . For this, we consider the following ring friendship graph. Theorem 3.12. There exists a friendship allocation F and corresponding Max-Swap- Game tree equilibrium network 𝐺[𝑆] of 𝑛 agents 𝑉 in which some agent has a private cost of 𝛺(√𝑛). Proof. For the agents 𝑉 ={𝑣1,…,𝑣u�} , we consider the friendship allocation F≔{{𝑣u�,𝑣u�+1}∣𝑖=1,…,𝑛−1}∪{{𝑣u�,𝑣1}} , forming a ring friendship graph, and a corresponding network 𝐺[𝑆]=(𝑉,𝑆)as stated in Figure 3.6. We claim that the network is an equilibrium and yields a private cost of 𝑐u�u�(𝑆)=𝛺(√𝑛) for agent 𝑣u�∈𝑉 (index 𝑖 will be specified later). Specifically, for the private costs we have 43 3 Loss and Benefit of Friendships 𝑣1 𝑣u� 𝑣u�−1 𝑣u�−3 𝑣u�+u�−2 𝑣u� 𝑣u�−u�+2 𝑣u�+5 𝑣u�+2 𝑣u�+1 … … … … … 𝑣2 𝑣3 𝑣4𝑣u�−1 𝑣u�𝑣u�+1 𝑣u�+2 𝑣u�−2 𝑣u�−1 𝑣u� 𝐷−1 𝐷𝐷−1 Figure 3.6: Illustration of a Max-Swap-Game tree equilibrium strategy profile u�[u�]= (u�,u�) of u� ≔ |u�| agents with a friendship allocation ring graph such that the private cost of u�u�is u�(u�), with u�≔√u�−2+1,u�≔2u�−3, and u�=u�−∑u� u�=1u�. • for 𝑗=1,…,𝑖−1that 𝑐u�u�+1(𝑆)=𝑐u�u�(𝑆)+1and • for 𝑗=𝑖+1,…,𝑘that 𝑐u�u�(𝑆)=𝑐u�u�+1(𝑆)+1. We first compute the exact value for 𝑐u�u�(𝑆) given by this setting, then we argue why no agent in this network can perform an improving response. Denote the maximal distance from 𝑣u�to any of her friends by 𝐷. Then 𝐷must fulfill 𝑛=u�−2 ∑ u�=1 𝑖+u�−3 ∑ u�=1 𝑖+2(𝐷−2)+3=𝐷2−2𝐷+3, and hence, 𝐷=√𝑛−2+1 . This yields a private cost of √𝑛−2+1 for agent 𝑣u�when we fix the parameters as 𝑖≔𝐷−1and 𝑘≔2𝐷−3. For each agent with a degree greater than 1 in 𝐺[𝑆] we have a private cost of 1 and hence no improving response is possible. Otherwise, consider some agent 𝑣u�of degree 1in 𝐺[𝑆]. Agent 𝑣u�cannot perform any swap if and only if it holds both, ∣𝑑u�[u�](𝑣u�−1,𝑣u�)−𝑑u�[u�](𝑣u�,𝑣u�+1)∣≤1 and 𝑣u� is connected by one edge to the shortest path from 𝑣u�−1 to 𝑣u�+1 . Since this property is given by construction, 𝑣u�cannot perform any improving response. An interesting insight from the last theorem is that the used stability argument for T-configurations (cf. Lemma 3.6) characterizes ring friendship graphs in general: Every agent must be in the center of her two friends. 44 3.3 Worst-Case Friendships in Swap-Games 3.3.2 The Price of Anarchy in Max-Swap-Games Continuing the analysis of the worst-case behavior of friendships in the Max- Swap-Game, next we consider the price of anarchy. At first, we will provide a lower bound for tree equilibrium networks and then use the private cost upper bound to show that this bound is tight. In the setting of tree equilibria, we will further characterize the price of anarchy by the structure of the friendship graph, namely the size of a maximum independent set therein. We will conclude this section by showing that the price of anarchy is worst possible when considering arbitrary networks. Lemma 3.13. There exists a friendship allocation F and a corresponding Max-Swap- Game tree equilibrium network 𝐺[𝑆] of 𝑛 agents such that the social cost is 𝛺(𝑛3/2) . Proof. We create a network 𝐺[𝑆] = (𝑉,𝑆) of agents 𝑣1,…,𝑣u� . For a fixed parameter 𝐷≔ √2u�−7−3 2 , we first connect agents 𝑣u�+1,…,𝑣u�/2−u�−1 as a line and then further connect agents 𝑣u�/2,…,𝑣u� to agent 𝑣u� , whereas 𝑙 ≔ u� 2− 𝐷−(∑u� u�=1𝑖+2) . The remaining agents are connected as leaves to specific places at the line: For agents 𝑣1,…,𝑣u� , first 𝑣1 is connected to 𝑣u�+u� , then 𝑣2 is connected to 𝑣u�+2u�−1 , and further up to 𝑣u� , the agents are connected such that the distance between each next pair decreases by 1 (cf. Figure 3.8). We make the same construction for agents 𝑣u�/2−1 to 𝑣u�/2−u� , whereas 𝑣u�/2−1 is connected to 𝑣u�−u� and the remaining agents are again connected such that the distances decrease by 1 with each pair. Note that by the choices for 𝑙 and 𝐷 , we have 𝑛=2∑u� u�=1𝑖+u� 2+2𝐷+4 and hence the network can actually be constructed as stated above. The corresponding friendship graph consists of a ring, which connects agents 𝑣1,…,𝑣u�/2 , and additionally connects agents 𝑣u�/2+1,…,𝑣u� , such that each of them is a friend of both agent 𝑣u�/2−1 as well as agent 𝑣1 (cf. Figure 3.7). Considering the network 𝐺[𝑆] , this implies a private cost of (√2𝑛−7+1)/2 for all agents 𝑣u�/2,…,𝑣u� . Thus, the social cost of 𝑆 is cost(𝑆)=𝛺(𝑛3/2) . The arguments that 𝐺[𝑆] is an equilibrium for the given friendship graph apply analogously to Lemma 3.12. Theorem 3.14 (Max-Swap-Game: price of anarchy for tree networks) . In the Max-Swap-Game with friendship allocations, the price of anarchy for tree network equilibria is PoA =𝛩(√𝑛), with 𝑛being the number of agents. 45 3 Loss and Benefit of Friendships 𝑣1𝑣2𝑣3 …𝑣u�/2−1 𝑣u� ⋮𝑣u�/2 Figure 3.7: The friendship graph for the proof of Lemma 3.13. 𝑣u� 2−u�−1 𝑣u� 2−u�−3 𝑣u�−u� 𝑣u� 𝑣u�+u� 𝑣u�+2u�−1 𝑣u�+3 𝑣u�+2 𝑣u�+1 … … … … … … 𝑣u� 2−u� 𝑣u� 2−u�+1 𝑣u� 2−1 𝑣u� 2𝑣u�𝑣1𝑣2 𝑣u�−1 𝑣u� 𝐷 𝐷 𝐷−1 Figure 3.8: The network for the proof of Lemma 3.13. This tree equilibrium network corresponds to the friends as given in Figure 3.7. The parameters are u�= √2u�−7−3 2 and u�= u� 2−u�−(∑u� u�=1u�+2). 46 3.3 Worst-Case Friendships in Swap-Games Proof. For the upper bound, we apply Theorem 3.4, which states for tree equilibrium networks that the private cost of every agent is at most O (√𝑛) . By this, the social cost for every tree network is at most O (𝑛3/2) . Using Lemma 3.13, we get that this bound is actually tight and the worst-case social cost is 𝛩(𝑛3/2) . On the other hand, for any friendship allocation in an optimal solution the social cost is between 𝑛 and 2𝑛 . Hence, the worst-case ratio of both is PoA =𝛩(√𝑛). Next, we provide a different characterization of the price of anarchy for tree equilibria, namely by the size of a maximum independent set in the friendship graph. We will get this bound by using the maximum independent set size to bound the maximal length of a Binding-Sequence, similar to the proof of Theorem 3.11. Here, a maximum independent set (MIS) of a given graph 𝐺=(𝑉,𝑆) is a subset 𝑀⊂𝑉 of maximum size such that for no two 𝑢,𝑣∈𝑀 there is an edge connecting them. Lemma 3.15. For a friendship allocation F , let 𝐺[𝑆]=(𝑉,𝑆) be a Max-Swap-Game tree equilibrium network of 𝑛≔|𝑉| agents and let 𝑀⊂𝑉 be a maximum independent set in the friendship graph (𝑉,F) . Then, the length of every Binding-Sequence is at most 2𝑀. Proof. Let 𝑣0,…,𝑣u� be a Binding-Sequence with maximal length. We will prove that the agents of this sequence with even index form an independent set in the friendship graph (𝑉,F) . For this, consider an even index 𝑖 and assume for contradiction that there is an even index 𝑘<𝑖 such that 𝑣u�∈F(𝑣u�) . By Lemma 3.9 we get 𝑑u�[u�](𝑣u�,𝑣u�+1)≤𝑑u�[u�](𝑣u�,𝑣u�+2) . If 𝑣u�+2 ≠ 𝑣u� , then by Lemma 3.8 and by 𝑐u�u�(𝑆)>3, for all 𝑣u�in the Binding-Sequence, we get: 𝑑u�[u�](𝑣u�,𝑣u�)>𝑑u�[u�](𝑣u�,𝑣u�+2)+1≥𝑐u�u�(𝑆) Yet, this is a contradiction. Thus, consider the case 𝑣u�+2 =𝑣u� . Since 𝑣u�+1 is connected by at most one edge to the shortest path from 𝑣u� to 𝑣u�+2 and 𝑑u�[u�](𝑣u�+1,𝑣u�+2)≥3 we get that 𝑣u�+2 ∉F(𝑣u�) . Otherwise, we either get the same contradiction as before or 𝑣u�+1 would contradict to be the most distant agent in F(𝑣u�) who fulfills the Binding-Sequence conditions. 47 3 Loss and Benefit of Friendships Figure 3.9: Lower bound construction for the price of anarchy in the Max-Swap-Game for general networks. Each of the ring agents is a friend of her three neighbors. Each satellite agent is a friend of her ring neighbor as well of the two agents at a distance of exactly u�/6+2 . In this illustration, the three friends of a satellite agent (marked in orange) are marked in blue. Hence, the agents with an even index of the Binding-Sequence form an independent set in (𝑉,F) . Since an independent set has at most 𝑀 agents, we get an upper bound of 2𝑀. Theorem 3.16. In the Max-Swap-Game with friendship allocations, let 𝑛 be the number of agents and 𝑀 the size of a maximum independent set in the friendship graph. Then, the price of anarchy for tree equilibria networks is PoA =O(𝑀). Proof. By using Lemma 3.15, we know that the maximum Binding-Sequence length is 2𝑀 . Now we use the same arguments as in the proof of Theorem 3.11, yet with 2𝑀 as the maximum length, and get O (𝑀) as the upper bound on the private cost of every agent. With the arguments from Theorem 3.14 we deduce the price of anarchy upper from the private cost upper bound. This theorem further shows how the maximum independent set characterization of the friendship graph provides a nice parametrization of tree equilibrium networks for the original Max-Swap-Game with uniform communication interests, as considered by Alon et al. [Alo+10]. Given a game with a complete friendship graph, the maximum independent set has size 1 and hence yields a constant price of anarchy. Then, with increasing size of the independent set, the upper bound for the price of anarchy linearly increases. Corollary 3.17. In the Max-Swap-Game with friendship allocations, if the friendship graph forms a clique, then for tree equilibrium networks the price of anarchy is O(1). In the following theorem we will show that, in contrast to tree equilibrium networks, the price of anarchy will become worst possible when considering 48 3.3 Worst-Case Friendships in Swap-Games arbitrary equilibrium networks. As a reminder, for this class of arbitrary equilibrium networks we know from Alon et al. [Alo+10] that for uniform communication interests the price of anarchy is at least 𝛺(√𝑛) , although no non-trivial upper bound is known. Theorem 3.18 (Max-Swap-Game: price of anarchy for general networks) . In the Max-Swap-Game with friendship allocations, with 𝑛 being the number of agents, the price of anarchy is PoA =𝛩(𝑛). Proof. First note that the social cost of every strategy profile is upper bounded by 𝑛(𝑛−1) and lower bounded by 𝑛 . Secondly, we provide a friendship allocation for 𝑛 agents (with 𝑛 being a multiple of 6 ) and a corresponding equilibrium network 𝐺[𝑆]=(𝑉,𝑆) such that the social cost is 𝛺(𝑛2) (cf. Figure 3.9). For this, we connect (𝑛/2) -many agents as a ring and call them ring agents. For each ring agent, we connect one additional satellite agent to her. Each of the ring agents is a friend of her three adjacent agents in 𝐺[𝑆] , whereas each satellite agent is a friend of her neighbor at the ring and of both satellite agents at a distance of exactly 𝑛/6+2 . This construction is an equilibrium and all 𝑛/2 satellite agents have a private cost of 𝑛/6+2 each, which gives the claimed price of anarchy of 𝛺(𝑛). 3.3.3 The Price of Anarchy in Sum-Swap-Games In the following, we will consider the price of anarchy in Sum-Swap-Games. In comparison to the games with complete friendship graphs, as considered by Alon et al. [Alo+10], we will prove that for tree equilibrium networks as well as for arbitrary networks the price of anarchy will become worst possible. By this, the results are in stark contrast to the non-uniform variant. Specifically, we use very sparse friendship allocations to obtain these worst-case results. Note that the following result specifically applies for general networks, too. Theorem 3.19 (Sum-Swap-Game: price of anarchy for tree networks) . In the Sum-Swap-Game with friendship allocations, for tree equilibrium networks the price of anarchy is PoA =𝛩(𝑛). Proof. We consider a line network of agents 𝑣1,…,𝑣u� and select the biggest integer 𝐷 such that it holds 3𝐷+2≤𝑛 . All agents on the line are friends of 49 3 Loss and Benefit of Friendships 𝑐u�≠𝑐u� it holds 𝐵u�(𝑐u�)∩𝐵u�(𝑐u�)=∅ , we get 𝑁≥|𝐶|⋅(u�−1)2 2u� and hence 𝑙≤ 2u�u� (u�−1)2 . Using that 𝑆 is an equilibrium and thus 𝛼⋅|𝐶|≥2𝑘 , we get 2𝑘≤ 2u�u�2 (u�−1)2 , which yields: diam(𝐺[𝑆])=O((𝑁𝛼2)1/3). (Edge cost upper bound.) The minimal length of a cycle is 𝛼+1 , since otherwise an agent owning such a cycle edge could improve her costs by removing it. By this, we can apply Lemma 3.22 and get an upper bound on the edges of O(𝑛1+2/u�). (Price of anarchy.) For an optimal solution, we know that every agent is connected to at least one other agent, which gives a simple social cost lower bound of 𝛼𝑛/2 . Comparing this to the above upper bounds gives for the process price of anarchy: O⎛ ⎜ ⎜ ⎝𝑛2/u�+(𝑁 𝛼)1/3⎞ ⎟ ⎟ ⎠ 3.5 Conclusion & Future Work This chapter provided two different approaches to study the impact of friendships on equilibria in network creation games. First, driven by the commonly used worst-case approach, we saw that in Swap-Games the social cost can become worst possible. The only exception is the quality of tree equilibria in the Max-Swap-Game case, which states a remarkably different behavior. In particular, the Binding-Sequence gives a very interesting insight into the structure of worst-case equilibria. Secondly, looking from a much more optimistic view angle, we showed that using only some simple structural insights of the best-response processes suffices to drastically improve the results. Specifically, in the process price of anarchy, we tie the upper bound to the structure of the friendship graph and 𝛼. Throughout this chapter, we only considered static friendship graphs: The set of friends never changes. Yet, in practice, friends of network participants might change over time. Introducing a time model and considering (possibly restricted) changes of the friendship graph seems to be a natural way to generalize our model, yielding an interesting online problem. In particular, the 56 3.5 Conclusion & Future Work combination of dynamic friendship graphs and more problem tailored price of anarchy concepts, like the stated process price of anarchy, seems to be an interesting further direction. 57 CHAPTER 4 The Impact of Choosing Edge Qualities Network creation games try to capture the behavior of Internet-like networks, which are created by the autonomous decisions of multiple strategic agents. Specifically, the game by Fabrikant et al. [Fab+03] was introduced to study the outcome of such interactions with respect to the impact of the agents’ selfish behavior to the overall quality. For this challenging task, their classic model stays very simple and only provides one parameter, namely the edge price 𝛼 , which has major influence on the outcome. In this chapter, we extend their model by enabling agents to select edges of different qualities for different prices. When considering today’s networks, where connections are offered by several service providers with different bandwidths and latency guarantees, choosing both the target and the quality of a connection seems to be a very natural extension. We are specifically interested in latency costs, which can be modeled as the shortest path lengths in a weighted network. Our model extension introduces a set of available edge lengths, from which the agents can choose when creating or changing an edge, and a price function, which assigns an individual price to every available edge length. For this generalized model, we show that equilibrium networks exist for any combination of available edge lengths and price functions. Considering the quality loss by the selfish behavior of the 59 4 The Impact of Choosing Edge Qualities agents, we analyze the price of stability and the price of anarchy. Chapter Basis. The model, analysis, and results presented in the remainder of this chapter are based on the following publication: 2014 (with A. Mäcker and F. Meyer auf der Heide). “Quality of ServiceinNetworkCreation Games”. In: Web and Internet Economics – 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings, cf. [CMM14]. Chapter Outline. This chapter is organized as follows. In Section 4.1, we introduce our model extensions for the Sum-Game and the Max-Game variants of the classic model by Fabrikant et al. [Fab+03], in particular the notion of edge lengths and price functions, and discuss several important properties of price functions that are needed for the later analysis. A comparison to other price functions, as typically used in economics literature, is provided in Section 4.2. For the introduced game variants, in Section 4.3 we first analyze the existence and structure of equilibrium networks. Supplementing this, in Section 4.4 and Section 4.5 we provide answers on the minimal and maximal quality loss by selfish behavior of agents. 4.1 Model & Notations The considered model variants are extensions of the Sum-Game and the Max- Game models as introduced in Section 2.2. In each game, there is a set of 𝑛 selfish agents 𝑉 and a set 𝐿⊆[  𝛽,  𝛽] of available edge lengths with 0<  𝛽≤  𝛽 . For convenience, throughout this chapter we assume  𝛽 = min{𝑥 ∈ 𝐿} and  𝛽 = max{𝑥 ∈ 𝐿} , which also gives that a specific minimum and maximum edge length always exists in 𝐿 . Every agent 𝑢∈𝑉 can create edges to other agents of any available edge length 𝑥∈𝐿 . The individual price of an edge of a length 𝑥 is given by a monotonously decreasing function 𝑝∶𝐿→ℝ≥0 , which is called a price function. Every agent 𝑢∈𝑉 aims to minimize her private cost by selfishly selecting a strategy 𝑠u�⊂𝑉×𝐿 . Hereby, each (𝑣,𝑥)∈𝑠u� represents an undirected weighted edge ({𝑢,𝑣},𝑥) from 𝑢 to 𝑣 of length 𝑥 , which is created by 𝑢 and has a price 60 4.1 Model & Notations of 𝑝(𝑥) . For a strategy profile 𝑆=(𝑠u�1,…,𝑠u�u�) of agents 𝑉 ={𝑣1,…,𝑣u�} , the resulting weighted graph 𝐺[𝑆] consists of the vertices 𝑉 and the weighted edges ⋃u�∈u�{({𝑢,𝑣},𝑥)∣(𝑣,𝑥)∈𝑠u�}. Game Variants. We consider the two natural network creation game variants as discussed in Section 2.1. On the one hand, these are games in which agents want to minimize the sum of distances to all other agents, and on other hand these are games with agents who aim for minimizing their maximal distances. The private cost of an agent 𝑢 in the Sum-Pricing-Game with strategy profile 𝑆 is given by: 𝑐u�(𝑆)= ∑ (u�,u�)∈u�u�𝑝(𝑥)+ ∑ u�∈u�𝑑u�[u�](𝑢,𝑣) Here, 𝑑u�[u�](𝑢,𝑣) denotes the shortest weighted path distance from 𝑢 to 𝑣 in the weighted graph 𝐺[𝑆] . For the Max-Pricing-Game, the private cost function is: 𝑐u�(𝑆)= ∑ (u�,u�)∈u�u�𝑝(𝑥)+max u�∈u� 𝑑u�[u�](𝑢,𝑣) The social cost in both games is estimated as: cost(𝑆)= ∑ u�∈u�𝑐u�(𝑆) We refer to the first term of a cost function as edgeu�(𝑆)=∑(u�,u�)∈u�u�𝑝(𝑥) , called the edge cost, and to the second term as distu�(𝑆), called the distance cost. Price Functions. In this chapter, for a game with edge lengths 𝐿⊆[  𝛽,  𝛽] a monotonically decreasing function 𝑝∶𝐿⟶ℝ≥0 (4.1) is called a price function. Considering only monotonously decreasing functions means that we only consider price functions forwhich shorter (better) edges are more expensive than longer (inferior) ones. As noted previously, we assume  𝛽 = min{𝑥 ∈ 𝐿} and  𝛽 = max{𝑥 ∈ 𝐿} and by this know that 𝐿 contains a specific minimum and maximum value. Most of the analysis in this chapter makes use of some characteristic values 61 4 The Impact of Choosing Edge Qualities of a price function. Given a domain of available edge lengths 𝐿 and a price function 𝑝∶𝐿→ℝ≥0 , we consider the edge lengths that minimize the following functions (cf. Figure 4.1): (a) 𝑥↦𝑝(𝑥)+𝑥, (b) 𝑥↦𝑝(𝑥)+(𝑛−1)𝑥, and (c) 𝑥↦(𝑛−1)𝑝(𝑥)+𝑥. The minimizing values can be understood in the following way: If we consider the Sum-Pricing-Game, where agents aim to minimize the sum of distances to all other agents, 𝑥 ↦ 𝑝(𝑥)+𝑥 is the trade-off function between an edge length and its price for an edge that is used only for one shortest path and complementary, 𝑥↦𝑝(𝑥)+(𝑛−1)𝑥 illustrates the trade-off between an edge length and its price if the edge is used for 𝑛−1 shortest paths. Different for the Max-Pricing-Game, 𝑥↦(𝑛−1)𝑝(𝑥)+𝑥 illustrates the trade-off between an edge length and its price for an edge that is used only for one shortest path, while 𝑥↦𝑝(𝑥)+𝑥 now illustrates the trade-off between an edge length and its price, if the edge is used for 𝑛−1 shortest paths. The following lemma gives an overview of these functions and their relations, as they are needed in the later analysis. Lemma 4.1. Let 𝐿⊆[  𝛽,  𝛽] be a set of edge lengths and 𝑝∶𝐿→ℝ≥0 a price function. Then for the values •𝑥∗≔argminu�∈u�𝑝(𝑥)+𝑥, •𝑥≔argminu�∈u�𝑝(𝑥)+(𝑛−1)𝑥, •𝑥≔argminu�∈u�(𝑛−1)𝑝(𝑥)+𝑥, •𝜒∗≔argminu�∈u� u�(u�) 2+𝑥, and •𝜒≔argminu�∈u�𝑝(𝑥)+2(𝑛−1)𝑥, it holds: (a) 𝑥≤𝑥∗≤ 𝑥and 𝑝( 𝑥)≤𝑝(𝑥∗)≤𝑝( 𝑥), (b) 𝑝(𝑥∗)+𝑥∗≤(𝑛−1)𝑝( 𝑥)+ 𝑥and 𝑝(𝑥∗)+𝑥∗≤𝑝( 𝑥)+(𝑛−1) 𝑥, and 62 4.1 Model & Notations length price 𝑝(𝑥)=1/𝑥 𝑝(  𝛽) 𝑝(  𝛽)  𝛽 𝛽 𝑝(𝑥)+𝑥 𝑝(𝑥)+(𝑛−1)𝑥 (𝑛−1)𝑝(𝑥)+𝑥 Figure 4.1: For some example price function u�(u�) , the figure illustrates the differences between the functions u�(u�)+u� , u�(u�)+(u�−1)u� , and (u�−1)u�(u�)+u� . The minimal values of these functions in the domain of available edge lengths are characteristic for the later discussed prices of stability and anarchy. (c) 𝜒∗+u�(u�∗) 2≥u�∗+u�(u�∗) 2and 𝑝( 𝜒)+2(𝑛−1) 𝜒≥𝑝( 𝑥)+(𝑛−1) 𝑥. Proof. The first set of inequalities directly follows from the fact that 𝑝 is a monotonically decreasing positive function. For the second set of inequalities, we only need that 𝑥∗ minimizes the term 𝑝(𝑥)+𝑥 , which cannot have a higher value than the compared values. And finally, for the last set of inequalities, using the definition of the values gives that the respective terms at the right hand side are minimized by the used parameters. Solution Concepts. Using the terms of a buy equilibrium from Section 2.2, we call a strategy profile 𝑆 = (𝑠u�1,…,𝑠u�u�) a buy equilibrium, if for every agent 𝑣u� and every strategy 𝑠′u�u�≠ 𝑠u�u� it holds that the strategy profile 𝑆′≔ (𝑠u�1,…,𝑠u�u�−1,𝑠′u�u�,𝑠u�u�+1,…,𝑠u�u�) does not have a lower private cost for 𝑣u� . If a strategy profile is not a buy equilibrium, then there exists at least one agent who can perform a strategy change that decreases her private cost. Such a strategy change is called an improving response. If the strategy change is the best possible for the agent in terms of reducing her private cost, it is called a best response. 63 4 The Impact of Choosing Edge Qualities 4.2 Related Work & Contribution As discussed in Section 2.2, both the Sum-Game and the Max-Game were studied extensively by various authors, in particular with respect to the question of the price of anarchy (cf. Section 2.2.2 and Section 2.3). This includes the study of different solution concepts, which usually restrict the available strategies or strategy changes of the agents. Yet, there is not much work on extending the capabilities of the agents, specifically not for the question of different edge qualities. Still, when we consider network formation problems in general, edges of different qualities are quite common. For example, in congestion games (introduced by Rosenthal [Ros73]) for every edge there is a function that denotes its quality (latency) depending on the number of agents using the edge. Also in network design games (e.g., Augustine et al. [Aug+15]), edges usually have prices (weights) that are shared evenly among the agents that use them. When it comes to modeling how a price function assigns a price to a good of a certain quality, there is a great deal of microeconomics literature (e.g., Jehle and Reny [JR11, pp. 135–145] and Mas-Colell et al. [MWG95, pp. 144–147]). As a reference, we refer to convex and linear price functions (cf. Mas-Colell et al. [MWG95, p. 144]), when benchmarkingour results. In the related problem of provider competition inanInfrastructure-as-a-Service market, where providers offer access to computing resources and the resource prices change with the current load, Künsemöller et al. [Kün+14] considered a similar set of price functions by using piecewise linear functions. Contribution. For every set of available edge lengths and every price function, we show that in the Sum-Pricing-Game and the Max-Pricing-Game buy equilibrium networks exist. Specifically, our constructions yield a constant price of stability for both games. In the Sum-Pricing-Game, we can show that the price of anarchy is upper bounded by at most O (min{𝑛,(𝑝(𝑥∗)+𝑥∗)/  𝛽}) , with 𝑥∗∈𝐿 being the edge length that minimizes 𝑝(𝑥)+𝑥 . This emphasizes the importance of the trade-off between edge price and quality. In particular, we can show that the price of anarchy bound is nearly tight for a class of linear price functions, given by 𝑝∶[1,𝛼−2𝜀]→ℝ≥0 with 𝑝(𝑥)=𝛼−(1+𝜀)𝑥 , for 𝛼>0 and 𝜀∈(0,1/2) . This 64 4.3 Existence of Equilibria is in considerable contrast to the classic Sum-Game for which no non-constant lower bound is known. For the Max-Pricing-Game we provide a price of anarchy upper bound of O (3 √𝑛) . Here, we note that unlike in the Sum-Pricing-Game, introducing price functions has no major effect to the game. Note that in both games, by setting the available edge lengths to 𝐿≔{1} and the price function to 𝑝(1)≔𝛼, we obtain the original Max- and Sum-Games. 4.3 Existence of Equilibria Compared to the classic network creation games by Fabrikant et al. [Fab+03] and Demaine et al. [Dem+07], being able to select edge lengths and hence edge prices equips agents with much more freedom than before. For example, any interval 𝐿⊆ℝ≥0 of positive length gives an infinite number of available edge lengths and hence an infinite number of possible strategy choices. Since a larger strategy space can make equilibria from the classical games unstable, in this section we start by asking whether equilibria always exist. For this, given an arbitrary price function we make use of the optimal tradeoffs between edge length and edge price for edges that are used only for one shortest path and edges that are used for 𝑛−1 shortest paths. Using these edge lengths, we can construct equilibrium networks that look similar to those for the Max-Game and the Sum-Game, i.e., being either star or clique networks. In particular, the structure of the equilibrium networks depends on the characteristic price function values as introduced in Lemma 4.1. 4.3.1 Equilibria in the Sum-Pricing-Game In the following, for any combination of a given set of edge lengths and a price function, we first compute the optimal solutions regarding the social cost and secondly show that always a buy equilibrium network exists. These results will be used in later sections to estimate bounds for the prices of stability and anarchy. Lemma 4.2. For the Sum-Pricing-Game with edge lengths 𝐿⊆[ 𝛽,  𝛽] and price function 𝑝∶𝐿→ℝ≥0 , let 𝑆 be a strategy profile such that 𝐺[𝑆] is connected and no edge can be removed without increasing the social cost. Denote by 𝑥 the minimal 65 4 The Impact of Choosing Edge Qualities First, if 𝑣 creates edges of length 𝑥 to all other 𝑛−2 satellites (note that 𝑥≤2 𝑥 ), the gain is: 2 𝑥−(max{ 𝑥,𝑥}+(𝑛−2)𝑝(𝑥)) If 𝑥< 𝑥, this value is negative. But still for 𝑥≥ 𝑥, the gain is at most 2 𝑥−(𝑥+(𝑛−2)𝑝(𝑥))≤ 𝑥+(𝑛−2)𝑝( 𝑥)−(𝑥+(𝑛−2)𝑝(𝑥)≤0 since the value minimizing 𝑥+(𝑛−2)𝑝(𝑥) lies in the interval [𝑥∗, 𝑥] and thus the only possibly improving choice for 𝑣 is 𝑥= 𝑥 . Secondly, if 𝑣 creates edges of length 𝑥to all other agents, the gain is: 2 𝑥−((𝑛−1)𝑝(𝑥)+𝑥)≤(𝑛−2)𝑝( 𝑥)+ 𝑥−(𝑛−1)𝑝( 𝑥)− 𝑥≤0 Thirdly, if 𝑣creates only one edge to the center agent of length 𝑥, the gain is: 2 𝑥−(𝑝(𝑥)+𝑥+ 𝑥)≤ 𝑥−𝑝(𝑥∗)−𝑥∗ ≤ 𝑥−((𝑛−1)𝑝( 𝑥)+ 𝑥−𝑥∗) ≤(𝑛−2)𝑝( 𝑥)−(𝑛−1)𝑝( 𝑥)− 𝑥+𝑥∗<0 Hence, this star network is a buy equilibrium. (Stability of clique with one agent owning 𝑛−1 edges.) As the final case, we have to consider (𝑛−1)𝑝( 𝑥)+ 𝑥<𝑝(𝑥∗)+2𝑥∗ and 𝑥>(𝑛−2)𝑝( 𝑥) . Here, we construct a star with one agent 𝑢 owning 𝑛−1 edges of length 𝑥 and complete this star to a clique with all edges having length 𝑥 , yet arbitrary edge ownerships. We claim that this network is a buy equilibrium. At first we note that by construction, 𝑢 has optimal lengths for all of her edges. Also every other agent has optimal lengths for her edges, since by unilaterally changing her edge lengths the diameter stays at least 𝑥 . We further show that no agent will change her edge set by considering the following kinds of possible improving responses. First, for any agent replacing her current set of edges by edges to all other agents, the optimal length is 𝑥 and hence, doing so cannot improve her private cost. Secondly, by simply removing all own edges the gain is at most (𝑛−2)𝑝( 𝑥)− 𝑥<0 . Thirdly, by removing all own edges and creating 72 4.4 Quality of Equilibria in the Sum-Pricing-Game one edge to 𝑢of length 𝑥, the gain is at most: (𝑛−1)𝑝( 𝑥)+ 𝑥−( 𝑥+𝑥)−𝑝(𝑥)≤(𝑛−1)𝑝( 𝑥)−𝑥−𝑝(𝑥)≤ 𝑥+𝑝( 𝑥)−(𝑥∗+𝑝(𝑥∗))≤0 Concluding, no improving response exists for any agent and hence the network is a buy equilibrium. 4.4 Quality of Equilibria in the Sum-Pricing-Game In this section, we consider the quality of equilibria in the Sum-Pricing-Game. In particular, we provide bounds for the prices of stability and anarchy. Corollary 4.7 (Sum-Pricing-Game: price of stability) . For the Sum-Pricing-Game with edge lengths 𝐿⊆[  𝛽,  𝛽] and price function 𝑝∶𝐿→ℝ≥0 , the price of stability is at most 4. Proof. In the following, we compute the social cost ratio when comparing the equilibrium networks from Theorem 4.4 with the optimal solutions from Lemma 4.3. For this, define the characteristic values 𝑥∗≔argminu�∈u�𝑝(𝑥)+ 𝑥 , 𝑥 ≔ argminu�∈u�𝑝(𝑥)+(𝑛−1)𝑥 , 𝜒∗≔argminu�∈u�𝑝(𝑥)+2𝑥 , and 𝜒 ≔ argminu�∈u�𝑝(𝑥)+2(𝑛−1)𝑥 . If the equilibrium network and the socially optimal network have the same topology, i.e., both being star networks or both being clique networks, the price of stability is at most 2. This directly follows from the relations of Lemma 4.1, when comparing the social costs. Now consider the case when the equilibrium network is a star with all edges having length 𝑥, but the optimal solution being a clique. In this case we get: PoS ≤(𝑛−1)(2(𝑛−1) 𝑥+𝑝( 𝑥)) 𝑛(𝑛−1)(𝜒∗+u�(u�∗) 2)≤4(𝑛−1) 𝑥+𝑝( 𝑥) 𝑛(𝑥∗+𝑝(𝑥∗)) ≤4(𝑛−1)𝑥∗+𝑝(𝑥∗) 𝑛(𝑥∗+𝑝(𝑥∗)) ≤4 For the second-last estimation note that by definition 𝑥 is the argument in 𝐿 for which the function 𝑥↦(𝑛−1)𝑥+𝑝(𝑥)is minimized. Finally, consider the case when the buy equilibrium network is a clique with all edges of length 𝑥∗ and the optimal solution being a star with all edges of length 𝜒 . Considering equation (4.2) from Lemma 4.3, for the optimal solution 73 4 The Impact of Choosing Edge Qualities to be a star it must hold that 𝑝(𝜒∗)+2𝜒∗−4 𝜒≤0 and hence 𝑝(𝜒∗)+2𝜒∗≤4 𝜒 . This gives: PoS ≤𝑛(𝑛−1)(𝑥∗+u�(u�∗) 2) (𝑛−1)(2(𝑛−1) 𝜒+𝑝( 𝜒)) ≤𝑛(𝑥∗+u�(u�∗) 2) 2(𝑛−1) 𝜒+𝑝( 𝜒) ≤𝑛(𝜒∗+𝑝(𝜒∗)) 2(𝑛−1) 𝜒+𝑝( 𝜒) ≤4𝑛 𝜒 2(𝑛−1) 𝜒 ≤4 Similar to Albers et al. [Alb+14], we start our analysis of the price of anarchy by bounding the social cost of a buy equilibrium network by the diameter of the network but now incorporate arguments about maximum edge lengths and edge prices. This will yield the upper bound for the price of anarchy as stated in Theorem 4.10. Lemma 4.8. For the Sum-Pricing-Game with edge lengths 𝐿⊆[ 𝛽,  𝛽] and price function 𝑝∶𝐿→ℝ≥0 , let 𝑆 be a buy equilibrium strategy profile and define 𝑥∗≔ argminu�∈u�𝑝(𝑥)+𝑥. Then, for any agent 𝑢∈𝑉it holds: cost(𝑆)≤𝑛⋅distu�(𝑆)+𝑥∗(𝑛−1)2+2(𝑝(𝑥∗)+𝑥∗)𝑛(𝑛−1) Proof. First, we claim that in an equilibrium network all edges have a price of at most 𝑛(𝑝(𝑥∗)+𝑥∗) . For this, assume there is an edge of price 𝑝(𝑥) > (𝑝(𝑥∗)+𝑥∗)𝑛 and consider replacing it by a new edge of length 𝑥∗ . This would decrease the owner’s edge cost by 𝑝(𝑥)−𝑝(𝑥∗)>𝑛𝑥∗+(𝑛−1)𝑝(𝑥∗) , while increasing the distance cost by at most (𝑥∗−𝑥)(𝑛−1) . Since (𝑥∗−𝑥)(𝑛−1)< 𝑛𝑥∗+(𝑛−1)𝑝(𝑥∗) , this is an improving response and hence contradicts 𝑆 forming a buy equilibrium. Next, fix an arbitrary agent 𝑢∈𝑉 and consider a shortest path tree 𝑇 rooted at 𝑢 in 𝐺[𝑆] . For every 𝑣∈𝑉 , define 𝑚u�≔∣{{𝑣,𝑤}∣(𝑤,𝑥)∈𝑠u�∧{𝑣,𝑤}∈𝑇}∣ to be the number of tree edges maintained by 𝑣 . Then, for any agent 𝑣≠𝑢 we argue that it must hold 𝑐u�(𝑆)≤(𝑝(𝑥∗)+𝑥∗)𝑛(𝑚u�+1)+distu�(𝑆)+𝑥∗(𝑛−1), which we can see as follows: Since 𝑆 forms an equilibrium, deviating from her 74 4.4 Quality of Equilibria in the Sum-Pricing-Game 𝑢𝑣u�𝑣2𝑣 …𝑣1 0u� u�+u� 2u� Figure 4.2: Illustration of the diameter argument of Lemma 4.9: Agent u� creates an edge to agent u�and improves her distance cost to agents u�1,…,u�u�. current strategy cannot decrease 𝑣 ’s private cost. In particular, the resulting private cost when removing all own edges, except those belonging to 𝑇 , and additionally creating one new edge of length 𝑥∗ to 𝑢 cannot be less than 𝑐u�(𝑆) . Since this strategy change would not modify any edges of the shortest path tree 𝑇 , after the strategy change 𝑣 ’s distance cost would be at most distu�(𝑆)+ (𝑛−1)𝑥∗, while her edge cost would be (𝑝(𝑥∗)+𝑥∗)𝑛(𝑚u�+1)+𝑝(𝑥∗). Using this bound for every agent 𝑣≠𝑢 and the fact that 𝑢 only owns edges belonging to 𝑇(removing a non-tree edge would reduce 𝑢’s cost), we get: cost(𝑆)≤distu�(𝑆)+(𝑝(𝑥∗)+𝑥∗)𝑛𝑚u� +∑ u�≠u�((𝑝(𝑥∗)+𝑥∗)𝑛(𝑚u�+1)+distu�(𝑆)+𝑥∗(𝑛−1)) =𝑛⋅distu�(𝑆)+𝑥∗(𝑛−1)2+(𝑝(𝑥∗)+𝑥∗)𝑛𝑚u� +∑ u�≠u�(𝑝(𝑥∗)+𝑥∗)𝑛(𝑚u�+1) =𝑛⋅distu�(𝑆)+𝑥∗(𝑛−1)2+2(𝑝(𝑥∗)+𝑥∗)𝑛(𝑛−1) For the last equality we use that a tree with 𝑛agents has 𝑛−1edges. Lemma 4.9. In the Sum-Pricing-Game with edge lengths 𝐿 ⊆ [  𝛽,  𝛽] and price function 𝑝∶𝐿→ℝ≥0 , define 𝑥∗≔argminu�∈u�𝑝(𝑥)+𝑥 , and let 𝑆 be a buy equilibrium strategy profile. Then, the diameter of 𝐺[𝑆]is at most O(𝑝(𝑥∗)+𝑥∗). Proof. First, we show that no edge can be longer than 𝑝(𝑥∗)+𝑥∗ . Assuming there is an agent 𝑢 who owns an edge (𝑣,𝑥) ∈ 𝑠u� of length 𝑥 > 𝑝(𝑥∗)+𝑥∗ , which connects 𝑢 to an agent 𝑣 , we consider the replacement of this edge by an edge of length 𝑥∗ . Such a new strategy 𝑠′u�≔(𝑠u�⧵{(𝑣,𝑥)})∪{(𝑣,𝑥∗)} decreases 𝑢 ’s distance cost by at least 𝑥−𝑥∗>𝑝(𝑥∗) , but increases 𝑢 ’s edge cost by at 75 4 The Impact of Choosing Edge Qualities most 𝑝(𝑥∗)−𝑝(𝑥) . Since an improving response contradicts 𝑆 being a buy equilibrium, we get the upper bound on the edge length. Next, we consider the length of a longest shortest path in 𝐺[𝑆] , of which we call the incident agents 𝑢 and 𝑣 . If this path only consists of one edge, the edge would have a length of at most 𝑝(𝑥∗)+𝑥∗ and the claim holds. Otherwise, the path consists of at least two edges and we define a parameter 𝑘 ∈ ℝ≥0 such that 2𝑘=𝑑u�[u�](𝑢,𝑣) and consider the strategy change 𝑠′u�≔𝑠u�∪{(𝑣,𝑥)} of agent 𝑢 that consists of creating an edge {𝑢,𝑣} of some length 𝑥∈𝐿 . This strategy change (cf. Figure 4.2) decreases 𝑢 ’s distance cost to agents on the path that have a distance of at least 𝑘+𝑥 to 𝑢 . Let 𝑣 ≕ 𝑣1,𝑣2,…,𝑣u� denote these agents, ordered by increasing distance to 𝑣 . Since each edge has a length of at most min{𝑝(𝑥∗)+𝑥∗, 𝛽} , we get 𝑍≥⌈u�−u� min{u�(u�∗)+u�∗, u�}⌉ . With the strategy change 𝑠′u� , each distance from 𝑢 to any 𝑣u� decreases from 2𝑘−𝑑u�[u�](𝑣,𝑣u�) to be at most 𝑥+𝑑u�[u�](𝑣,𝑣u�), resulting in a distance cost decrease of at least: u� ∑ u�=1(2𝑘−𝑑u�[u�](𝑣,𝑣u�))−u� ∑ u�=1(𝑥+𝑑u�[u�](𝑣,𝑣u�))=𝑍(2𝑘−𝑥)−2 u� ∑ u�=1𝑑u�[u�](𝑣,𝑣u�) ≥𝑍(2𝑘−𝑥)−2𝑍(𝑘−𝑥) =𝑍(2𝑘−𝑥−2𝑘+2𝑥)=𝑍𝑥 Since 𝑆 is a buy equilibrium, this cannot be an improving response and hence we get 𝑍𝑥≤𝑝(𝑥). This gives 𝑝(𝑥)≥ u�−u� min{u�(u�∗)+u�∗, u�}𝑥and hence: 𝑘≤min{𝑝(𝑥∗)+𝑥∗, 𝛽}𝑝(𝑥) 𝑥+𝑥 If min{𝑝(𝑥∗)+𝑥∗, 𝛽}=  𝛽 , then the diameter of 𝐺[𝑆] is at most 2(𝑝(  𝛽)+  𝛽)≤ 2(𝑝(  𝛽)+𝑝(𝑥∗)+𝑥∗) = O (𝑝(𝑥∗)+𝑥∗) . Otherwise, if min{𝑝(𝑥∗)+𝑥∗, 𝛽} = 𝑝(𝑥∗)+𝑥∗ , then the diameter is at most (𝑝(𝑥∗)+𝑥∗)u�(u�) u�+𝑥 . For 𝑝(𝑥∗)≤𝑥∗ the lemma follows by setting 𝑥≔𝑥∗ . In case 𝑝(𝑥∗)>𝑥∗ , by setting 𝑥≔𝑝(𝑥∗) the diameter is at most O ((𝑝(𝑥∗)+𝑥∗)u�(u�(u�∗)) u�(u�∗)) . Using the monotonicity of 𝑝 , it holds 𝑝(𝑝(𝑥∗))≤𝑝(𝑥∗)and we get O(𝑝(𝑥∗)+𝑥∗). Theorem 4.10 (Sum-Pricing-Game: price of anarchy upper bound) . In the Sum-Pricing-Game with edge lengths 𝐿⊆[  𝛽,  𝛽] , price function 𝑝∶𝐿→ℝ≥0 , and 76 4.4 Quality of Equilibria in the Sum-Pricing-Game 𝑥∗≔argminu�∈u�𝑝(𝑥)+𝑥, the price of anarchy is at most: PoA =O(min{𝑛,𝑝(𝑥∗)+𝑥∗  𝛽}) Proof. Let 𝑆 be a buy equilibrium strategy profile. Then by Lemma 4.9, the diameter of 𝐺[𝑆] is at most O (𝑝(𝑥∗)+𝑥∗) . Applying this to Lemma 4.8, the social cost of 𝑆is at most: cost(𝑆)=O(𝑛(𝑛−1)(𝑝(𝑥∗)+𝑥∗)) Moreover, by Lemma 4.2 the social cost of an optimal solution is at least 2 𝛽𝑛(𝑛−1)+𝑚(𝑝(𝑥∗)+𝑥∗−4  𝛽), whereas 𝑚 denotes the number of edges. When comparing both bounds, we get for 𝑝(𝑥∗)+𝑥∗≤4  𝛽 that the lower bound is minimized with 𝑚=𝑛(𝑛−1)/2 and then becomes 𝑛(𝑛−1)(𝑝(𝑥∗)+𝑥∗)/2 , which gives a price of anarchy of O (1) . Otherwise, for 𝑝(𝑥∗)+𝑥∗>4  𝛽 the lower bound is minimized with 𝑚=𝑛−1 and we get PoA = O (u�(u�(u�∗)+u�∗)  u�(2u�−4+(u�(u�∗)+u�∗)/  u�)) . When separately considering whether 𝑛< u�(u�∗)+u�∗  u� holds or not, we get the claimed price of anarchy upper bound. Applying the price and length value ranges, we can deduce a price of anarchy upper bound, which is independent of the price function, but depends only on the range limits. Corollary 4.11. In the Sum-Pricing-Game with edge lengths 𝐿⊆[  𝛽,  𝛽] , for every price function 𝑝∶𝐿→ℝ≥0 it holds: PoA =O⎛ ⎜ ⎝min⎧ { ⎨ { ⎩1+𝑝(  𝛽)  𝛽,𝑝(  𝛽)+  𝛽  𝛽,𝑛⎫ } ⎬ } ⎭⎞ ⎟ ⎠ In the following, we will see that the price of anarchy upper bound is even tight for a broad class of price functions, including for all price functions that decrease faster than the linear function 𝑥 ↦ −𝑥 and where both 𝑝(  𝛽) ≤  𝛽 and 𝑝(  𝛽)≤  𝛽 hold. Examples of such functions are provided in the following section. 77 4 The Impact of Choosing Edge Qualities However, note that the bound cannot be tight for every price function. To see this, consider 𝑝∶[1,1]→[𝛼,𝛼] , which constitutes the original game by Fabrikant et al. [Fab+03] and for which it is known that for most ranges of 𝛼 the price of anarchy is constant (cf. Section 2.2.2). Theorem 4.12 (Sum-Pricing-Game: price of anarchy lower bound) . In the Sum- Pricing-Game with edge lengths 𝐿⊆[  𝛽,  𝛽] , let 𝑝∶𝐿→ℝ≥0 be a price function with 𝑝(  𝛽)≤  𝛽,𝑝(  𝛽)≤  𝛽, and  𝛽=𝑥∗≔argminu�∈u�𝑝(𝑥)+𝑥, then: PoA =𝛺(min{𝑛,𝑝(𝑥∗)+𝑥∗  𝛽}) Proof. Using the given constraints, we get 𝑝(𝑥∗)=𝑝(  𝛽)≤  𝛽≤𝑥 for every 𝑥∈𝐿 . In particular, this gives 𝑝(𝑥∗) ≤ 𝑥 , whereas 𝑥 ≔ argminu�∈u�𝑝(𝑥)+(𝑛−1)𝑥 , and hence by Lemma 4.4 we know that a clique network with all edges having length  𝛽is a buy equilibrium. We compare the social cost of this clique network to the social cost of a star network with all edges having length  𝛽 . This gives a price of anarchy lower bound of: PoA ≥𝑝(  𝛽)𝑛(𝑛−1)/2+  𝛽𝑛(𝑛−1) 𝑝(  𝛽)(𝑛−1)+2  𝛽(𝑛−1)(𝑛−2)+2(𝑛−1)  𝛽=𝑛(𝑝(  𝛽)/2+  𝛽) 𝑝(  𝛽)+2  𝛽(𝑛−1) Next, we separately consider the cases of 𝑛≥(𝑝(  𝛽)+  𝛽)/  𝛽 and 𝑛<(𝑝(  𝛽)+  𝛽)/  𝛽 . For 𝑛≥(𝑝(  𝛽)+  𝛽)/  𝛽, we get: 𝑛(𝑝(  𝛽)/2+  𝛽) 𝑝(  𝛽)+2  𝛽(𝑛−1) ≥𝑛(𝑝(  𝛽)/2+  𝛽)  𝛽+𝑝(  𝛽)+2  𝛽(𝑛−1) ≥𝑛(𝑝(  𝛽)/2+  𝛽) 𝑛 𝛽+2  𝛽(𝑛−1) =𝛺⎛ ⎜ ⎝𝑝(  𝛽)+  𝛽  𝛽⎞ ⎟ ⎠ Otherwise, for 𝑛<(𝑝(  𝛽)+  𝛽)/  𝛽we get: 𝑛(𝑝(  𝛽)/2+  𝛽) 𝑝(  𝛽)+2  𝛽(𝑛−1) ≥𝑛(𝑝(  𝛽)/2+  𝛽) 𝑝(  𝛽)+2  𝛽((𝑝(  𝛽)+  𝛽)/  𝛽)−1) ≥𝑛(𝑝(  𝛽)/2+  𝛽) 3 𝛽=𝛺(𝑛) Combining both bounds gives the claim. 78 4.4 Quality of Equilibria in the Sum-Pricing-Game 4.4.1 Employing Characteristic Price Functions Concluding the analysis of the Sum-Pricing-Game, we apply our price of anarchy results to some typical price functions (cf. Mas-Colell et al. [MWG95, pp. 143–147]). These are firstly the price function 𝑥 ↦ 𝛼/𝑥 , whereas 𝛼 > 0 , as an example for a convex function, and secondly a class of linear functions. Recalling Corollary 4.7, we know that the price of stability is constant for every price function. The convex function 𝑥↦𝛼/𝑥 (cf. Figure 4.1) illustrates the scenario where edge prices increase very fast for good connections but do not vary much for the tail of slow connections. Note that we only provide a price of anarchy upper bound but no lower bound, since the lower bound from Theorem 4.12 does not apply. This is due to the fact that the only interval of edge lengths that fulfills all constraints of the theorem is 𝐿={√𝛼}. Corollary 4.13. Given an interval 𝐿 ≔ [1,𝛽] of available edge lengths for some parameter 𝛽>1 , then for the price function 𝑝∶𝐿→ℝ≥0,𝑥↦𝛼/𝑥 with 𝛼∈[1,𝛽2) , the price of anarchy is at most PoA =O(√𝛼). Proof. For the upper bound, we consider Theorem 4.10 and have to compute minu�∈u�𝑝(𝑥)+𝑥, which is given by 𝑥∗≔√𝛼and yields the claim. Next, we consider a linear function and show that actually a very high price of anarchy lower bound is possible, in particular higher than anyone known for the classic Sum-Game without edge price functions. For our construction, we choose a set of linear functions that decrease just slowly enough such that a clique network is a buy equilibrium, while the optimal solution is a star. Corollary 4.14. Given an interval 𝐿≔[1,𝛼−(1+𝜀/2)] of available edge lengths, for some value 𝛼>2 and a positive value 𝜀< 1 u�−1 , we consider the Sum-Pricing-Game of 𝑛 agents. Then, for the price function 𝑝∶𝐿→ℝ≥0,𝑥↦𝛼−(1+𝜀)𝑥 the price of anarchy is PoA =𝛩(𝛼(1−𝜀)). Proof. First we see that 𝑥∗≔argminu�∈u�𝑝(𝑥)+𝑥 , which is argminu�∈u�𝛼−𝜀𝑥 in this case, has the value 𝑥∗≔𝛼−(1+𝜀/2) . Using this, by applying Theorem 4.10 weget PoA = O ((1−𝜀)𝛼) asupper bound for the price ofanarchy. Considering the ranges of 𝐿 , we see that now both constraints of Theorem 4.12 are fulfilled, i.e., 𝑝(1)=𝛼−(1+𝜀)≤𝛼−(1+𝜀/2) and 𝑝(𝛼−(1+𝜀/2))=𝛼−(1+𝜀)(𝛼− 1−𝜀/2)<1−𝜀≤1. Thus we get the corresponding lower bound. 79 4 The Impact of Choosing Edge Qualities 4.5 Quality of Equilibria in the Max-Pricing-Game In this section, we consider the quality of equilibria in the Max-Pricing-Game. In particular, these are the prices of stability and anarchy. Corollary 4.15 (Max-Pricing-Game: price of stability) . In the Max-Pricing-Game with edge lengths 𝐿⊆[  𝛽,  𝛽] and price function 𝑝∶𝐿→ℝ≥0 , the price of stability is at most 4. Proof. We compare the social cost of the three equilibrium networks from Theorem 4.6 with the social cost lower bound from Lemma 4.5. For this, define the values 𝑥∗≔arg minu�∈u�𝑝(𝑥)+𝑥and 𝑥≔argminu�∈u�(𝑛−1)𝑝(𝑥)+𝑥. For (𝑛−1)𝑝( 𝑥)+ 𝑥≥𝑝(𝑥∗)+2𝑥∗ , by Theorem 4.6 a star network with all edges having length of 𝑥∗ is a buy equilibrium. Compared to the social cost lower bound, the social cost ratio is: PoS ≤(𝑛−1)𝑝(𝑥∗)+𝑛2𝑥∗ (𝑥∗+𝑝(𝑥∗)/2)𝑛 ≤𝑝(𝑥∗) 𝑥∗+𝑝(𝑥∗)/2+2𝑥∗ 𝑥∗+𝑝(𝑥∗)/2 ≤4 For (𝑛−1)𝑝( 𝑥)+ 𝑥<𝑝(𝑥∗)+2𝑥∗∧ 𝑥≤(𝑛−2)𝑝( 𝑥) , by Theorem 4.6 a star network with all edges having length of 𝑥 is a buy equilibrium. Compared to the social cost lower bound, we get the following social cost ratio by applying the first constraint: PoS ≤(𝑛−1)𝑝( 𝑥)+𝑛2 𝑥 (𝑥∗+𝑝(𝑥∗)/2)𝑛 ≤2 𝑝(𝑥∗)+2𝑥∗ 𝑥∗+𝑝(𝑥∗)/2 ≤4 For the remaining case, by Theorem 4.6 a clique network with all edges having length 𝑥 is a buy equilibrium. Compared to the social cost lower bound, the social cost ratio is: PoS ≤𝑝( 𝑥)(𝑛−1)𝑛/2+𝑛 𝑥 (𝑥∗+𝑝(𝑥∗)/2)𝑛 ≤(𝑛−1)𝑝( 𝑥)+ 𝑥 (𝑥∗+𝑝(𝑥∗))/2 ≤2𝑝(𝑥∗)+2𝑥∗ 2𝑥∗+𝑝(𝑥∗)≤2 Lemma 4.16. In the Max-Pricing-Game with edge lengths 𝐿⊆[  𝛽,  𝛽] , price function 𝑝∶ 𝐿→ ℝ≥0 , and 𝑥∗≔argminu�∈u�𝑝(𝑥)+𝑥 , let 𝑆 be a buy equilibrium strategy profile. Then, for any agent 𝑢∈𝑉it holds: cost(𝑆)≤𝑛⋅distu�(𝑆)+2(𝑛−1)(𝑝(𝑥∗)+𝑥∗) 80 4.5 Quality of Equilibria in the Max-Pricing-Game Proof. First, we show that in a buy equilibrium network no edge costs more than 𝑝(𝑥∗)+𝑥∗ . For this, consider a strategy profile 𝑆′ such that some agent 𝑣 owns an edge of price 𝑝(𝑥)>𝑝(𝑥∗)+𝑥∗ , which has length 𝑥<𝑥∗ . If 𝑣 replaces this edge by one of length 𝑥∗ , her edge cost will decrease by 𝑝(𝑥)−𝑝(𝑥∗)>𝑥∗ , while her distance cost increases by at most 𝑥∗−𝑥 . Since this contradicts 𝑆′ being an equilibrium, we get the upper bound on the edge prices. Next, take an arbitrary agent 𝑢 and consider a shortest path tree 𝑇 rooted at 𝑢 in 𝐺[𝑆] . For every 𝑣∈𝑉 , define 𝑚u�≔∣{{𝑣,𝑤}∣(𝑤,𝑥)∈𝑠u�∧{𝑣,𝑤}∈𝑇}∣ to be the number of tree edges maintained by 𝑣 . Then, for any agent 𝑣≠𝑢 we argue that it must hold that 𝑐u�(𝑆)≤(𝑝(𝑥∗)+𝑥∗)(𝑚u�+1)+distu�(𝑆), which can be seen as follows: Since 𝑆 forms an equilibrium, deviating from her current strategy cannot decrease 𝑣 ’s cost. In particular, the resulting private cost when removing all own edges, except those belonging to 𝑇 , and additionally creating one new edge of length 𝑥∗ to 𝑢 cannot be less than 𝑐u�(𝑆) . Since this strategy change does not modify any edges of the shortest path tree 𝑇 , with the changed strategy 𝑣 ’s distance cost would be at most distu�(𝑆)+𝑥∗ , while her edge cost would be at most (𝑝(𝑥∗)+𝑥∗)(𝑚u�+1)+𝑝(𝑥∗) . Summing over all agents’ costs and using the fact that agent 𝑢 only owns edges belonging to 𝑇(otherwise removing a non-tree edge would improve 𝑢’s cost), we get: cost(𝑆)≤distu�(𝑆)+(𝑝(𝑥∗)+𝑥∗)𝑚u� +∑ u�∈u�∶u�≠u�((𝑝(𝑥∗)+𝑥∗)(𝑚u�+1)+distu�(𝑆)) =𝑛⋅distu�(𝑆)+(𝑛−1)(𝑝(𝑥∗)+𝑥∗)+ ∑ u�∈u�(𝑝(𝑥∗)+𝑥∗)𝑚u� =𝑛⋅distu�(𝑆)+2(𝑛−1)(𝑝(𝑥∗)+𝑥∗) For the last equality we use that the number of edges in a tree of 𝑛 agents is 𝑛−1. Using a similar approach like Demaine et al. [Dem+07], we derive a bound for the diameter and hence for the social cost of every buy equilibrium network in the Max-Pricing-Game. 81 5 Limits of Locality in 𝐺[𝑆] . The subgraph of 𝐺[𝑆] that is induced by the set 𝑁u�(𝑢) is called the 𝑘-neighborhood of 𝑢. In this game, agents are only allowed to perform 𝑘 -local operations, which is the simultaneous application of any combination of the actions of (1) removing an own edge, (2) swapping an own edge to an agent in the 𝑘 -neighborhood, 2 and (3) creating an edge to an agent in the 𝑘 -neighborhood. In particular, the set of actions that realize a 𝑘 -local operation must not contradict each other. Since together they form a single operation, they are also performed simultaneously and hence due to the same 𝑘 -neighborhood. If a 𝑘 -local operation consists of only exactly one of the actions (1)–(3), it is called a 𝑘-local greedy operation. Aprobing technique limits which and how many different strategies can be tested by an agent before selecting her best operation that she wants to perform. In this chapter, we consider the two probing techniques named unrestricted probing and greedy probing. Yet, for completeness and to emphasize the relation to the model by Bilò et al. [Bil+14a], we also define 0 -probing, which resembles their worst-case model. Unrestricted Probing: An agent is enabled to test all possible 𝑘 -local operations and to select a best-response strategy among them. Greedy Probing: An agent is enabled to test all possible 𝑘 -local greedy operations and to select a best-response strategy among them. 0 Probing: An agent is not able to test any 𝑘 -local operation and thus estimates the result of a strategy change by considering the worst-case of all possible networks that comply with her current 𝑘 -neighborhood (cf. Bilò et al. [Bil+14a] and the discussion in Section 5.2). Solution Concepts. Restating the notions of Section 2.2, we call a strategy profile to be a buy equilibrium if no agent can unilaterally change her strategy to decrease her cost. The strategy profile is a greedy buy equilibrium if no agent can unilaterally change her strategy by any greedy operation. When restricting agents to perform only 𝑘 -local operations with a respective probing technique, we obtain their 𝑘 -local counterparts. We say that a strategy profile is a 𝑘 -local 2 A swap-action of an agent is the simultaneous deletion of an own edge and creation of a new incident own edge. 88 5.2 Related Work & Contribution buy equilibrium and call the corresponding network to be 𝑘 -local stable if no agent can unilaterally decrease her cost by a 𝑘 -local operation. If no agent can decrease her cost by a 𝑘 -local greedy operation, the strategy profile is a 𝑘 -local greedy buy equilibrium and the network is called 𝑘-local greedy stable. Supplementing the above notions, we also consider 𝜀 -approximate equilibria (cf. Section 2.2). We call a strategy profile to be a 𝜀 -approximate buy equilibrium if no strategy change of an agent can decrease her cost by more than an 𝜀 -fraction of her current cost. Similarly, we say a strategy profile is a 𝜀 -approximate greedy buy equilibrium if no agent can decrease her cost by more than an 𝜀 -fraction of her current cost by a greedy operation. Note that in both approximate equilibria notions arbitrary operations are allowed, not only 𝑘-local ones. For a fixed price parameter 𝛼 , we define classes of equilibria due to the different solution concepts: BE is the class of all networks that are a buy equilibrium, GBE is the class of all networks a greedy buy equilibrium, k-BE is the class of all 𝑘 -local buy equilibrium networks, and k-GBE is the class of all 𝑘-local greedy buy equilibrium networks. Our notion of social efficiency of a strategy profile is the ratio of its induced social cost and the optimal social cost. Specifically, we are interested in the worst-case ratio of any equilibrium’s social cost and the optimal social cost, which we recall as the price of anarchy (cf. Definition 2.1). 5.2 Related Work & Contribution The only models in the realm of network creation games that consider games without global knowledge are by Bilò et al. [Bil+14a; Bil+14b]. In their games, the agents have limited viewing ranges and thus can access only a certain subset of information about the network. Hence, they are forced to base their decisions upon such incomplete information. Bilò et al. model this by considering conservatively acting agents, i.e., agents who perform only those actions which they know for certain to reduce their private costs. By this, the private cost of an agent can still depend on the total network, even if an agent cannot estimate it. In Bilò et al. [Bil+14a], the authors incorporate a most pessimistic locality view, which limits agents to know exactly their 𝑘 -neighborhoods. For any operation, an agent then estimates her private cost change by making a worst- 89 5 Limits of Locality case assumption about the unknown network part. Specifically, she computes an operation’s private cost change by taking the worst-case over all networks of arbitrary size that comply with her current 𝑘 -local view. Not surprisingly, the authors can provide several non-constant lower bounds for the price of anarchy in both the Sum-Game and the Max-Game. In particular, for the Sum-Game the price of anarchy is at least 𝛺(𝑛/𝑘) , when 𝑘= o (𝛼1/3) , and for the Max-Game it is at least 𝛺(𝑛/(1+𝛼)) . They further show for the Max-Game that their lower bound is still 𝛺(𝑛1−u�) for every 𝜀>0 , even if 𝑘 is poly-logarithmic and 𝛼= O (log𝑛) . For none of the considered games, the authors provide upper bounds on the price of anarchy. In the context of our probing models, these games can be understood as the 𝑘 -local Sum-Game and the 𝑘 -local Max-Game with 0-probing. In a follow-up paper, Bilò et al. [Bil+14b] considered a variant where agents have access to certain traceroute-based information, in addition to their 𝑘 -local views. Specifically, they look at how much the agents gain by having access to (1) a distance vector, (2) a minimum spanning tree, or (3) the set of all minimum spanning trees. Using these traceroute-based information, they provide the first known upper bounds on the price of anarchy for games with local view restricted agents. However, for all considered variants, the price of anarchy bounds are much worse than for the classic Sum-Game and Max-Game. For all versions of the Sum-Game, the price of anarchy is 𝛩(min{1+𝛼,𝑛}) ; while for versions of the Max-Game, it is 𝛩(𝑛) for 𝛼>1 . Notably, their price of anarchy proofs only require agents to have access to distance vector information. There is a lot of literature about network exploration and in particular about using traceroute strategies. For example, Beerliova et al. [Bee+06] consider the complexity of discovering the topology of a whole network in an online-setting and provide an O (√𝑛log𝑛) -competitive online algorithm for a network of 𝑛 agents. A good overview of applications of different traceroute protocols for network discovery is provided by Dall’Asta et al. [Dal+06]. Specifically for retrieving simple network information like distance vectors, we refer to the discussion in Bilò et al. [Bil+14b] about how to utilize traceroute protocols for this purpose. Apart from network creation games, the influence of locality has also been studied for other game-theoretic settings, e.g., in the local matching model by Hoefer [Hoe13], where agents know only their 2 -neighborhood and have to 90 5.3 Preliminaries choose their matching partners from this set. Contribution. Our main contribution is a new model for locality in network creation games. By taking the natural observation into account that agents want to test the outcomes of their strategic changes, we create not only a more optimistic but also a more realistic model. In our model, agents are still limited in their knowledge and actions, but now can probe different operations and choose the best one. Yet, our probing locality (even for viewing ranges as small as 2 ) has no impact on the hardness of best-response computations or the convergence of best-response processes. For the Sum-Game with unrestricted probing, we show upper bounds for the price of anarchy that are close to those in the classic Sum-Game. Hence, the results are in stark contrast to the worst-case model by Bilò et al. [Bil+14a], where myopic agents select their strategies without knowing the exact results of their strategy changes. Looking at the Sum-Game with greedy probing, which limits the probes to the quadratic number of greedy operations, we show the surprising insight that 𝑛2 probes suffice to gain the same results for the price of anarchy as with 2u� probes. Moreover, considering the behavior of the individual agents, we discuss how well 𝑘 -local greedy operations approximate arbitrary greedy operations. For tree networks, we specifically show that 𝑘 - local operations with greedy probing approximate arbitrary operations by 𝛩(log u� u�). 5.3 Preliminaries Starting our analysis, we first provide some observations about the structure and relations of equilibria and further show that results about the hardness of computing best responses and about non-convergence of best-response processes still apply for the 𝑘 -local Sum-Game. In particular, the hardness results hold for any 𝑘, while the non-convergence results hold for any 𝑘≥2. Observation 5.1.Agents in the 𝑘 -local Sum-Game and the 𝑘 -local greedy Sum- Game can be characterized as follows: (a) Agents with unrestricted probing are equivalent to agents who are aware of the whole network, but whose operations are restricted to be only 91 5 Limits of Locality 𝑘-local operations. (b) Agents with greedy probing are equivalent to agents who are aware of the whole network, but whose operations are restricted to be only 𝑘 -local greedy operations. Using these characterizations, we can directly derive some set relationships for the equilibrium classes. Observation 5.2.For a fixed edge price 𝛼>0 and any fixed locality parameter 𝑘∈ℕ , the following relations between the different equilibrium classes hold: (a) BE ⊆k-BE ⊆k-GBE (b) BE ⊆GBE ⊆k-GBE Sincethereexistequilibria forthe classicSum-Game (cf. Fabrikantet al. [Fab+03, Section 2]), note that there are also equilibria for both the 𝑘 -local Sum-Game and the 𝑘-local greedy Sum-Game. Theorem 5.3. For the 𝑘 -local Sum-Game with 𝑘≥1 , in general it is 𝒩𝒫 -hard to compute a 𝑘-local best-response operation. Proof. We follow the hardness proof by Fabrikant et al. [Fab+03, Proposition 1], which reduces the Minimum Dominating Set problem [GJ02] to the computation of an optimal strategy change in the Sum-Game. For a given network 𝐺= (𝑉,𝐸) , the Minimum Dominating Set problem is the task to compute a dominating set 𝐷⊆𝑉 of minimal size. Here, 𝐷 is called a dominating set if every agent of 𝐺belongs to 𝐷or has a neighbor in 𝐷. Let 𝐺=(𝑉,𝐸) be an instance of Minimum Dominating Set, then we obtain an instance of the 𝑘 -local Sum-Game as follows: Let 𝑉 be a set of agents and define a strategy profile such that for every edge {𝑢,𝑣} in 𝐸 , there is a corresponding strategy 𝑠u� with 𝑣∈𝑠u� . Thereby, edge ownerships are assigned arbitrarily. Furthermore, we add an additional agent 𝑧 to the network and set her strategy to 𝑠u�≔{𝑉} : i.e., 𝑧 owns edges to all other agents. For an edge price of 𝛼∈(1,2) and arbitrary 𝑘≥1 , we claim that a minimum cost strategy for 𝑧forms a minimum dominating set. For this, let 𝑠′u� be the optimal strategy change for 𝑧 and 𝑆′ the changed strategy profile. Since 𝛼<2 , we get that for every agent 𝑣∈𝑉 it must hold 92 5.3 Preliminaries 𝑑u�[u�′](𝑧,𝑣)<3 , since otherwise 𝑧 could improve her private cost by creating an edge to 𝑣 . Hence, the distance is either 1 or 2 . For 𝑑u�[u�′](𝑧,𝑣)=1 , agent 𝑧 owns an edge to 𝑣 and otherwise, for 𝑑u�[u�′](𝑧,𝑣)=2 , agent 𝑣 must own an edge to a direct neighbor of 𝑣 . By this, 𝑠′u� forms a dominating set and it remains to show that its size is minimal. Since the private cost of 𝑧is 𝑐u�(𝑆′)=𝛼⋅|𝑠′u�|+|𝑠′u�|+2⋅|𝑉⧵𝑠′u�|=|𝑉|+𝛼⋅|𝑠′u�|+|𝑉⧵𝑠′u�|, we get by 𝛼 > 1 that 𝑧 ’s private cost is minimized when |𝑠′u�| is minimized. Thus, an optimal strategy change for 𝑧 is a minimum dominating set in the constructed instance and directly gives a minimum dominating set in 𝐺. In the remainder of this section, we consider the convergence properties of best-response processes, as introduced in Section 2.2.3. Given a fixed game with edge price, locality parameter, and probing technique, we consider some initial strategy profile and analyze sequences of best-response strategy changes of the agents. At each time step, exactly one agent acts and we ask if such best-response processes are guaranteed to converge to an equilibrium state. Specifically, does the game possess the finite improvement property and hence, is it a potential game? Or otherwise, can we show a cyclic sequence of bestresponse strategy changes, i.e., the existence of a best-response cycle that can prevent these processes from terminating? Theorem 5.4. In both the 1 -local greedy Sum-Game and the 1 -local Sum-Game, every sequence of (𝑛−1)2 -many improving operations converges to an equilibrium. For 𝑘 ≥2 , for both the 𝑘 -local greedy Sum-Game and the 𝑘 -local Sum-Game, there are strategy profiles and best-response sequences that result in best-response cycles. Proof. For 𝑘=1 , neither in the Sum-Game nor in the greedy Sum-Game there is an agent who can create or swap an edge. Hence, the number of edges is strictly monotonically decreasing with every operation. We know for the initial strategy profile that for 𝑛=|𝑉| agents, there are at most 𝑛(𝑛−1) edges. Since no agent disconnects the network by any operation, there never can be less than 𝑛−1 edges. Hence, after at most (𝑛−1)2 -many improving strategy changes, in both models the network is an equilibrium. For 𝑘 =2 and 𝛼∈(2,3) , Figure 5.1 provides a best-response cycle in the 2 -local Sum-Game: In (1) 𝑐 swaps edge {𝑐,𝑎}→{𝑐,𝑏} , in (2) 𝑎 buys edge {𝑎,𝑒} , 93 5 Limits of Locality in (3) 𝑏 deletes edge {𝑎,𝑏} , in (4) 𝑎 buys edge {𝑎,𝑏} , in (5) 𝑏 deletes edge {𝑏,𝑒} , in (6) 𝑑 swaps edge {𝑑,𝑏}→{𝑑,𝑎} , in (7) 𝑐 swaps edge {𝑐,𝑏}→{𝑐,𝑎} , in (8) 𝑏 buys edge {𝑏,𝑒} , in (9) 𝑎 deletes edge {𝑎,𝑏} , in (10) 𝑏 buys edge {𝑎,𝑏} , in (11) 𝑎 deletes edge {𝑎,𝑒} , and in (12) 𝑑 swaps edge {𝑑,𝑎} → {𝑑,𝑏} . This gives the original network from (1) and hence a best-response cycle exists. It is easy to check that in every step of the cycle, the active agent performs a best-response operation. Since every operation is a greedy operation, the best-response cycle also holds for the 2 -local greedy Sum-Game. Note that in strategy change (6), agent 𝑑 could perform a 3 -local greedy operation (swapping edge {𝑑,𝑏}→{𝑑,𝑒} ), if the game was 3-local, and hence this construction cannot be used for 𝑘=3. For 𝑘 =3 and 𝛼∈(3,4) , Figure 5.2 provides a best-response cycle in the 3 -local Sum-Game that works as follows: In (1) 𝑏 buys edge {𝑏,ℎ} , in (2) 𝑑 swaps edge {𝑑,𝑐}→{𝑑,𝑏} , in (3) 𝑎 swaps edge {𝑎,𝑐}→{𝑎,𝑏} , in (4) 𝑏 deletes edge {𝑏,ℎ} , in (5) 𝑐 buys edge {𝑐,ℎ} , in (6) 𝑑 swaps edge {𝑑,𝑏}→{𝑑,𝑐} , in (7) 𝑎 swaps edge {𝑎,𝑏}→{𝑎,𝑐} , and in (8) 𝑐 deletes edge {𝑐,ℎ} . This again gives the original network from (1). It is easy to check that in every step of the cycle, the active agent performs a best-response operation. Since every operation is a greedy operation, the best-response cycle also holds for the 3 -local greedy Sum-Game. For any 𝑘≥4 , we refer to the construction in Kawald and Lenzner [KL13, Theorem 7], which only requires agents to perform 4 -local greedy operations and hence provides a best-response cycle for both the 𝑘-local Sum-Game and the 𝑘-local greedy Sum-Game. 5.4 Approximation Quality of Greedy Probing In this section, we investigate the agents’ perspectives in the Sum-Game in terms of how close 𝑘 -local operations approximate arbitrary strategies. Specifically, for a given 𝑘 -local game we ask by how much agents could improve their costs if they were allowed to perform arbitrary operations. First, we show that a 𝑘 -local greedy best-response operation is a 3 -approximation of a 𝑘 -local best-response operation. Then, we shift our focus to the approximation quality of 𝑘 -local greedy operations versus arbitrary greedy operations. For tree networks, we provide a tight approximation bound of 𝛩(log u� u�) and for any 94 5.4 Approximation Quality of Greedy Probing u� u�u� u� u� u� u�(1) u� u�u� u� u� u� u�(2) u� u�u� u� u� u� u�(3) u� u�u� u� u� u� u�(4) u� u�u� u� u� u� u�(5) u� u�u� u� u� u� u�(6) u� u�u� u� u� u� u�(7) u� u�u� u� u� u� u�(8) u� u�u� u� u� u� u�(9) u� u�u� u� u� u� u�(10) u� u�u� u� u� u� u�(11) u� u�u� u� u� u� u�(12) Figure 5.1: The 2 -local Sum-Game with a best-response cycle for edge price u�∈(2,3) . The orange agent performs a best-response operation: gray edges are removed, red edges are created. u�u� u�u� u� u� u� ℎ (1) u�u� u�u� u� u� u� ℎ (2) u�u� u�u� u� u� u� ℎ (3) u�u� u�u� u� u� u� ℎ (4) u�u� u�u� u� u� u� ℎ (5) u�u� u�u� u� u� u� ℎ (6) u�u� u�u� u� u� u� ℎ (7) u�u� u�u� u� u� u� ℎ (8) Figure 5.2: The 3 -local Sum-Game with a best-response cycle for edge price u�∈(3,4) . The orange agent performs a best-response operation: gray edges are removed, red edges are created. 95 5 Limits of Locality general 𝑘 -local greedy buy equilibrium network 𝐺 , we get an approximation upper bound of O(diam(𝐺)). 5.4.1 Approximation of the k-Local Sum-Game First, we consider the approximation quality of 𝑘 -local greedy operations regarding arbitrary 𝑘 -local operations. For this, we show that 𝑘 -local greedy best-response operations are 3 -approximations of arbitrary 𝑘 -local operations. Theorem 5.5. In the 𝑘 -local Sum-Game with 𝑘≥1 , every strategy profile in 𝑘 -local greedy buy equilibrium is a 3-approximate 𝑘-local buy equilibrium. Proof. We show that if an agent cannot improve her cost by a 𝑘 -local greedy operation, then this agent also cannot perform an arbitrary 𝑘 -local operation that reduces her private cost to a value less than 1/3of her current cost. For this, similar to [Len12], we reduce the best-response computation of any agent to the solution of a corresponding Uncapacitated Metric Facility Location instance (UMFL, cf. Williamson and Shmoys [WS11]). UMFL is the problem of selecting a subset 𝑋⊆ℱ of facilities with the objective to minimize the term ∑u�∈u�𝑓u�+∑u�∈𝒞minu�∈u�𝑑(𝑥,𝑣) for a given set of clients 𝒞 , individual opening costs 𝑓u�≥0 for every facility 𝑣∈ℱ , and a metric distance function 𝑑∶ℱ×𝒞→ℝ≥0 . Arya et al. [Ary+04, Theorem 4.3] provide a locality gap result that (beside other implications) states: When starting with an arbitrary facility set and performing only the operations of closing a single facility, opening a single facility, or swapping a single facility (i.e., simultaneously closing one facility and opening another one) until no further improvement is possible, this greedy local search heuristic results in a 3 -approximation of the optimal solution. Given a 𝑘 -local greedy buy equilibrium strategy profile 𝑆 for a 𝑘 -local Sum- Game with agents 𝑉 and edge price 𝛼 , let 𝑢∈𝑉 denote an arbitrary agent. For agent 𝑢 let 𝑠u� denote the set of agents to which she owns an edge and let 𝑠u� be the set of agents who own edges to agent 𝑢 . Using this, we define an instance 𝐼=(ℱ,𝒞,{𝑓u�}u�∈u�,𝑑)of the UMFL problem as follows: • The set of facilities ℱis given by ℱ≔𝑁u�(𝑢)⧵{𝑢}. • The set of clients 𝒞is given by 𝒞≔𝑉⧵{𝑢}. 96 5.4 Approximation Quality of Greedy Probing • For every facility 𝑣∈ℱ∩ 𝑠u� , we define the opening cost as 𝑓u�≔0 and for all other facilities we set 𝑓u�≔𝛼. • For a facility 𝑣∈ℱ and a client 𝑥∈𝒞 , we set the distance as 𝑑(𝑣,𝑥)≔ 𝑑u�[u�](𝑣,𝑥)+1; the distance is ∞if there is no path from 𝑣to 𝑥in 𝐺[𝑆]. Note that by using the shortest path metric to define the distances in 𝐼 , we ensure that the distances are metric. It is easy to see that 𝑐u�(𝑆)= cost(𝐼)= ∑u�∈u�u�𝑓u�+∑u�∈𝒞minu�∈u�u�𝑑(𝑥,𝑣) . Since we assume that agent 𝑢 cannot perform any improving 𝑘 -local greedy operation, the locality gap for UMFL [Ary+04] yields that the cost of agent 𝑢 in 𝑆 is at most 3 times her cost it would be by performing a 𝑘-local best-response operation. The construction by Lenzner [Len12, Theorem 3] further yields an approximation lower bound for 𝑘≥2 such that there exist 𝑘 -local greedy buy equilibria that are in (3/2) -approximate 𝑘 -local buy equilibrium. This lower bound also applies here. 5.4.2 Approximation Lower Bound in the Sum-Game In the following, we prove a lower bound on the approximation ratio for 𝑘 -local greedy operations versus arbitrary greedy operations. For this, we use the following constructed 𝑑 - 𝑙 -Tree-Star network (cf. Figure 5.3). It consists of a complete binary tree subgraph and a star subgraph, both connected by one additional agent. Complete Binary Tree 𝑇u�: For 𝑑∈ℕ , define 𝑇u� to be a complete balanced binary tree of depth 𝑑 with root agent 𝑟 such that every edge is owned by the agent who is closer to 𝑟 . Let 𝑢 denote a fixed leaf agent (i.e., an agent with maximal distance to 𝑟). Tree-Star 𝐺u�,u�: We consider a combination of a complete binary tree 𝑇u� , with root agent 𝑟 and of even depth 𝑑 , and a star network consisting of a center agent 𝑧 and 𝑙 -many leaves (cf. Figure 5.3). Both subgraphs are connected by one additional agent 𝑦 who owns one edge to the root agent 𝑟 and one edge to the center agent 𝑧 . The tree subgraph contains one (arbitrary) leaf marked as 𝑢. In the following, we will also consider the networks: 97 5 Limits of Locality 5.4.3 Approximation Upper Bounds in the Sum-Game In the following, we will show that the approximation lower bound is tight for every 𝑘 -local greedy buy equilibrium tree network. Our main insight for this result (formalized in the following lemma) is that whenever an agent can perform a swap in a tree network, then there is also a 2 -local greedy improvingresponse swap available for this agent. Since this property does not hold for general networks, we later provide another approximation upper bound that holds for arbitrary networks. Lemma 5.12. Let 𝑢 be an agent in a tree network 𝑇 . If 𝑢 can perform an arbitrary greedy edge swap in 𝑇 , then there exists an improving 2 -local greedy edge swap operation for 𝑢. Proof. Let {𝑢,𝑣} → {𝑢,𝑣u�} be a best-response edge swap of 𝑢 and assume 𝑚=𝑑u�(𝑢,𝑣u�)>2 . We define 𝑃 ≔ (𝑢,𝑣 = 𝑣1,𝑣2,…,𝑣u�−1,𝑣u�) to be the shortest path from 𝑢 to 𝑣u� (cf. Figure 5.4). For this path, we obtain 𝑣 = 𝑣1 since 𝑇 is a tree and a swap must preserve connectivity. Thus, the swap only changes distances to agents in the subtree 𝑇u�1 of agent 𝑣1 , which is rooted at 𝑢 . For all agents 𝑣u� on the path 𝑃 , let 𝑉u�u� denote the set of agents who have agent 𝑣u� on their shortest path to any neighbor of 𝑣u� on 𝑃 . Let 𝑇u� be the tree that results from 𝑢performing the edge swap {𝑢,𝑣}→{𝑢,𝑣u�}. Since the swap {𝑢,𝑣} →{𝑢,𝑣u�} is a best-response edge swap, we have 𝑐u�(𝑇u�)≥𝑐u�(𝑇u�) , for 2≤𝑖≤𝑚−1. Using this together with: 𝑐u�(𝑇u�)=u� ∑ u�=1(𝑚−𝑖+1)⋅|𝑉u�u�|+ ∑ u�∈u�(u�)⧵u�(u�u�)𝑑u�(𝑢,𝑧)+edgeu�(𝑇)and 𝑐u�(𝑇u�−1)=u�−1 ∑ u�=1(𝑚−𝑖)⋅|𝑉u�u�|+2⋅|𝑉u�u�|+ ∑ u�∈u�(u�)⧵u�(u�u�)𝑑u�(𝑢,𝑧)+edgeu�(𝑇), we get: 0≤𝑐u�(𝑇u�−1)−𝑐u�(𝑇u�) =u�−1 ∑ u�=1(𝑚−𝑖)⋅|𝑉u�u�|+2⋅|𝑉u�u�|−⎛ ⎜ ⎝ u� ∑ u�=1(𝑚−𝑖+1)⋅|𝑉u�u�|⎞ ⎟ ⎠ =−u�−1 ∑ u�=1 |𝑉u�u�|+|𝑉u�u�| 104 5.4 Approximation Quality of Greedy Probing u�−1 ⋃ u�=3u�u�u�u�(u�u�u�)= u� ⋃ u�=u�u�u�u� u�(u�u�3)= u� ⋃ u�=3u�u�u� u�−3 ⋃ u�=0 u�u�u� u�=u�0u�1u�2u�3u�u�−1 u�u�u�u�−3 u�u�−2 u�u�−1 u�u� u�u�1u�u�2u�u�3u�u�u�-1u�u�u�u�u�u�-3u�u�u�-2u�u�u�-1 u�u�0u�u�u� Figure 5.4: Illustration of the sets of agents as used in the proof of Theorem 5.13. Hence, it must hold: |𝑉u�1|≤|𝑉u�u�|−u�−1 ∑ u�=2 |𝑉u�u�|<|𝑉u�u�|+u�−1 ∑ u�=2 |𝑉u�u�|< u� ∑ u�=2|𝑉u�u�| The last estimation gives us that the 2 -local edge swap {𝑢,𝑣}→{𝑢,𝑣2} is an improvingresponsefor 𝑢 , since itdecreases 𝑢 ’s distances toexactly (∑u� u�=2|𝑉u�u�|) - many agents, yet only increases 𝑢’s distances to |𝑉u�1|-many agents by 1. We can now apply this lemma to prove that the approximation lower bound from Theorem 5.11 is tight for tree networks. Theorem 5.13 (approximation upperboundfortree networks) . Any tree network in 𝑘 -local greedy buy equilibrium is an O (log u� u�) -approximate greedy buy equilibrium. Proof. Let 𝑇 be a 𝑘 -local greedy buy equilibrium tree network. In the following, we show that 𝑇 is a O (diam(u�) u�) -approximate greedy buy equilibrium. From this, we then can deduce the claim, since Lemma 5.12 implies that every tree equilibrium is a asymmetric swap equilibrium (cf. Section 2.2), for which we know from Mihalák and Schlegel [MS12] that the equilibrium network diameter is at most O(log𝑛), where 𝑛is the number of agents. Let 𝑣0 be some agent in 𝑇 who can buy an edge to decrease her cost. We assume that 𝑣0 buys the edge {𝑣0,𝑣u�} to an agent 𝑣u� at distance 𝑚 and that this is her best-response greedy edge creation. Let the shortest path from 𝑣0 to 𝑣u� be given by 𝑃=(𝑣0,𝑣1,𝑣2,…,𝑣u�−1,𝑣u�,𝑣u�+1,…,𝑣u�−1,𝑣u�) . We then denote by 𝑇u�u� the subtree of some agent 𝑣u� that is rooted at 𝑣0 and let the sets 𝑉u�u� for all 105 5 Limits of Locality 𝑣u�∈𝑉(𝑃) be defined like in the previous proof of Lemma 5.12 (cf. Figure 5.4 for an illustration of these sets). We assume that agent 𝑣0 cannot decrease her private cost by creating an edge to any agent in her 𝑘 -neighborhood. Hence, it must hold distu�(𝑣0,𝑣u�)= 𝑚>𝑘≥2 . Since we assume that 𝑇 is a 𝑘 -local greedy buy equilibrium, 𝑣0 cannot decrease her cost by creating an edge to 𝑣u� . But since this operation would decrease 𝑣0’s distances to all agents in 𝑉(𝑇u�u�)by 𝑘−1each, we get: 𝛼≥(𝑘−1)⋅∣𝑉(𝑇u�u�)∣(5.2) Next, we consider the ratio of agent 𝑣0 ’s private cost before and after creating edge {𝑣0,𝑣u�} . For this, let 𝑇′ be the network after 𝑣0 has bought the edge and let 𝛿u�0denote the distance cost decrease of agent 𝑣0. We get: 𝑐u�0(𝑇) 𝑐u�0(𝑇′)=𝑐u�0(𝑇) 𝑐u�0(𝑇)−𝛿u�0+𝛼 =edgeu�0(𝑇)+∑u�∈u�(u�)𝑑u�(𝑣0,𝑣) edgeu�0(𝑇)+∑u�∈u�(u�)𝑑u�(𝑣0,𝑣)−𝛿u�0+𝛼 ≤∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣) ∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣)−𝛿u�0+𝛼 The last inequality holds, since all agents to that 𝑣0 decreases her distances by creating {𝑣0,𝑣u�} are in 𝑇u�3 . We can upper bound the nominator by assuming that all agents in 𝑉(𝑇u�3)are at maximum distance to 𝑣0, thus: ∑ u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣)≤diam(𝑇)⋅|𝑉(𝑇u�3)| Since 𝑣0 has at least distance 1 to all agents in 𝑉(𝑇u�3) after creating the edge {𝑣0,𝑣u�} , we have that ∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣)−𝛿u�0>0 must hold. Thus, we can lower bound the denominator by ∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣)−𝛿u�0+𝛼>𝛼. Hence, we have: 𝑐u�0(𝑇) 𝑐u�0(𝑇′)≤∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣) ∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣)−𝛿u�0+𝛼 ≤diam(𝑇)⋅|𝑉(𝑇u�3)| 𝛼(5.2) ≤diam(𝑇)⋅|𝑉(𝑇u�3)| (𝑘−1)⋅|𝑉(𝑇u�u�)| 106 5.4 Approximation Quality of Greedy Probing For 𝑘 ≤3 , this already yields u�u�0(u�) u�u�0(u�′)= O (diam(𝑇)) , since for 𝑖 ≤ 3 it holds |𝑉(𝑇u�u�)|≥|𝑉(𝑇u�3)|. It remains to show that |𝑉(𝑇u�u�)| = 𝛺(|𝑉(𝑇u�3)|) for 𝑘 > 3 . Since creating edge {𝑣0,𝑣u�−1} is a best-response operation for 𝑣0 , its gain must be bigger than when creating edge {𝑣0,𝑣u�} . Hence, swapping from {𝑣0,𝑣u�} to {𝑣0,𝑣u�−1} would increase agent 𝑣0 ’s distances to all agents in 𝑉u�u� by one, as well as decrease agent 𝑣0 ’s distances to all agents in the set ⋃u�−1 u�=⌊u� 2⌋+1𝑉u�u� by one. Since all sets 𝑉u�u�are pairwise disjoint, we get: u�−1 ∑ u�=⌊u� 2⌋+1∣𝑉u�u�∣≤∣𝑉u�u�∣(5.3) First consider the case 𝑚=5 , i.e., 𝑚−2=3 and hence 𝑘 =𝑚−1 =4 . We use that creating {𝑣0,𝑣u�} strictly decreases agent 𝑣0 ’s private cost, whereas creating edge {𝑣0,𝑣u�}={𝑣0,𝑣u�−1}does not: ∣𝑉u�u�∣>u�−1 ∑ u�=⌊u� 2⌋+1∣𝑉u�u�∣(5.4) Thus, we have ⌊u� 2⌋+1=3 and we have that |𝑉(𝑇u�3)|<2⋅|𝑉u�u�| , which implies that |𝑉(𝑇u�3)|<2⋅|𝑉(𝑇u�u�)|, yielding |𝑉(𝑇u�u�)|=𝛺(𝑉(𝑇u�3)). Next, consider the case 𝑘 > 4 . For 𝑚−2 > 3 we claim that the edge {𝑣u�−2,𝑣u�−1} must be owned by agent 𝑣u�−1 . This holds, since otherwise agent 𝑣u�−2 could perform the swap {𝑣u�−2,𝑣u�−1}→{𝑣u�−2,𝑣u�} and thereby strictly decrease her cost. This can be seen as follows: If 𝑚−1=𝑘 , then by (5.4) we have |𝑉u�u�|>|𝑉u�u�−1|=|𝑉u�u�| . On the other hand, if 𝑚−1>𝑘 , then (5.3) implies |𝑉u�u�−1|<|𝑉u�u�| , since the sum on the left has at least one additional non-zero summand. In both cases, we have that the swap {𝑣u�−2,𝑣u�−1} → {𝑣u�−2,𝑣u�} must be improving for agent 𝑣u�−2. This proves the claim. Having established that the edge {𝑣u�−2,𝑣u�−1} is owned by agent 𝑣u�−1 and using the assumption that no agent in 𝑇 can swap an edge in her 𝑘 - neighborhood to strictly decrease her private cost, the swap {𝑣u�−1,𝑣u�−2}→ {𝑣u�−1,𝑣u�−3} cannot be an improving response for agent 𝑣u�−1 , which yields |𝑉u�−2|≥∑u�−3 u�=0 |𝑉u�u�|. Since 𝑚>5 , we have that ⌊u� 2⌋+1≤𝑚−2 . By (5.3) this 107 5 Limits of Locality implies ∑u�−3 u�=0 |𝑉u�u�|≤|𝑉u�u�−2|<∑u�−1 u�=⌊u� 2⌋+1|𝑉u�u�|≤|𝑉u�u�|. Thus, if 𝑘=𝑚−1 we have that u�−1 ∑ u�=3|𝑉u�u�|≤2⋅|𝑉u�u�−2|≤2⋅|𝑉u�u�|≤2⋅|𝑉(𝑇u�u�)|, which implies that |𝑉(𝑇u�3)|≤3⋅|𝑉(𝑇u�u�)|. If 𝑘≤𝑚−2, it follows that u�−1 ∑ u�=3|𝑉u�u�|<|𝑉(𝑇u�u�)| and hence |𝑉(𝑇u�3)|<2⋅|𝑉(𝑇u�u�)|. In both cases this yields |𝑉(𝑇u�u�)|=𝛺(|𝑉(𝑇u�3)|). Finally, we prove a general upper bound on the approximation ratio, which is tight for constant 𝑘 and almost tight in general. As discussed in [CL15, Lemma 2], for general networks the property of Lemma 5.12 does not hold and thus we have to analyze edge swaps and edge creations separately. For both cases, we get the same upper bound on the approximation ratio, which is independent of 𝑘. Theorem 5.14 (general approximation upper bound) . Any 𝑘 -local greedy buy equilibrium 𝑆is an O(diam(𝐺[𝑆]))-approximate greedy buy equilibrium. Proof. Let 𝑢 be an agent and consider her best-response greedy operation in 𝑆 . We denote the resulting strategy profile as 𝑆′ and in the following consider only the cases when this greedy operation is an edge swap or an edge creation, since improving-response edge deletions would contradict 𝐺[𝑆] to be a 𝑘 -local greedy buy equilibrium. We call the agents to which 𝑢 decreases her distance 𝑋− and the agents to which 𝑢 increases her distance 𝑋+ . Then for 𝑢 ’s distance cost decrease 𝛿u�we get: 𝛿u�=∑ u�∈u�−(𝑑u�[u�](𝑢,𝑥)−𝑑u�[u�′](𝑢,𝑥))− ∑ u�∈u�+(𝑑u�[u�′](𝑢,𝑥)−𝑑u�[u�](𝑢,𝑥)) ≤∑ u�∈u�−(𝑑u�[u�](𝑢,𝑥)−𝑑u�[u�′](𝑢,𝑥)) Comparing 𝑢 ’s private cost in both networks, when the operation is an edge 108 5.5 Efficiency of Probing Locality swap we get for the approximation ratio: 𝑐u�(𝑆) 𝑐u�(𝑆′)=𝑐u�(𝑆) 𝑐u�(𝑆)−𝛿u�=edgeu�(𝑆)+distu�(𝑆) edgeu�(𝑆)+distu�(𝑆)−𝛿u�<distu�(𝑆) distu�(𝑆)−𝛿u� =∑u�∈u�𝑑u�[u�](𝑢,𝑣) ∑u�∈u�𝑑u�[u�](𝑢,𝑣)−𝛿u�≤∑u�∈u�−𝑑u�[u�](𝑢,𝑣) ∑u�∈u�−𝑑u�[u�](𝑢,𝑣)−𝛿u� ≤∑u�∈u�−𝑑u�[u�](𝑢,𝑣) ∑u�∈u�−𝑑u�[u�](𝑢,𝑣)−(∑u�∈u�−(𝑑u�[u�](𝑢,𝑣)−𝑑u�[u�′](𝑢,𝑣))) ≤diam(𝐺[𝑆])⋅|𝑋−| ∑u�∈u�−𝑑u�[u�′](𝑢,𝑣) ≤diam(𝐺[𝑆])⋅|𝑋−| |𝑋−|=diam(𝐺[𝑆]) Considering greedy edge creations, we get for the approximation ratio (note, for this case it holds 𝑋+=∅): 𝑐u�(𝑆) 𝑐u�(𝑆′)=𝑐u�(𝑆) 𝑐u�(𝑆)−𝛿u�+𝛼 ≤∑u�∈u�−𝑑u�[u�](𝑢,𝑥) ∑u�∈u�−𝑑u�[u�](𝑢,𝑥)−𝛿u�+𝛼 ≤∑u�∈u�−𝑑u�[u�](𝑢,𝑥) |𝑋−|+𝛼 <diam(𝐺[𝑆])⋅|𝑋−| |𝑋−|=diam(𝐺[𝑆]) For this estimation, the second inequality holds since agent 𝑢 must have at least distance 1to all agents in 𝑋−in 𝐺[𝑆′]. 5.5 Efficiency of Probing Locality In this section, we consider the price of anarchy in the 𝑘 -local Sum-Game, concerning the unrestricted probing and the greedy probing strategies. At first, we analyze for which choices of 𝑘 the equilibria in the 𝑘 -local model with unrestricted probing coincide with equilibria in the original Sum-Game. The results of this section are summarized in Figure 5.5. Moreover, in Section 5.5.2 we provide several specific bounds for the price of anarchy. 5.5.1 A Clash of Models We stated in Observation 5.2 that k-BE ⊆BE holds. In the following, we will discuss the limits of several proof techniques to identify the parameters for which k-BE =BE , i.e., both equilibria concepts coincide. Specifically, we ask 109 5 Limits of Locality u� u� 12√u�/2 u�1−u� u�12u�log u� 1 2 6 u�=2√u� u�=2⋅51+√log u�+24logu�+3 4.667⋅3⌈1/u�⌉ +8 PoA=u�(u� u�+u�) PoA=u�(1)PoA=u�(√u�) PoA=u�(5√log u�logu�) PoA=u�(1) Figure 5.5: Overview of our results from Theorem 5.15 and Theorem 5.28. The light blue area indicates where buy equilibria and u� -local buy equilibria coincide and the orange lines mark the ranges that are covered by different proofs. for which combinations of 𝑘 and 𝛼 any 𝑘 -local buy equilibrium diameter is smaller than 𝑘 . If this is true, then a 𝑘 -local operation can achieve the same result as an arbitrary operation. Theorem 5.15 combines the results, which we will prove below. Theorem 5.15. The equilibrium concepts 𝑘 -local buy equilibrium and buy equilibrium coincide for the following parameter combinations and yield the respective price of anarchy results (cf. Figure 5.5): We have k-BE =BE for ⎧ { { { { { { { ⎨ { { { { { { { ⎩ 𝛼∈(0,1)∧𝑘≥2 ⇒PoA =O(1), 𝛼∈[1,√𝑛/2]∧𝑘≥6 ⇒PoA =O(1), 𝛼∈[1,𝑛1−u�]∧𝜀≥ 1 log(u�) ∧𝑘≥4.667⋅3⌈1/u�⌉ +8 ⇒PoA =O(3⌈1/u�⌉), 𝛼∈[1,12𝑛lg𝑛]∧𝑘≥2⋅51+√lg u�+24lg(𝑛)+3 ⇒PoA =O(5√lg u�lg 𝑛), 𝛼≥12𝑛log𝑛∧𝑘≥2 ⇒PoA =O(1). Lemma 5.16. For parameters 0<𝛼<1 and 𝑘 ≥ 2 , it holds k-BE =BE and the price of anarchy is 1. Proof. Given any strategy profile 𝑆 and 𝛼<1 , assume there are two closest 110 5.5 Efficiency of Probing Locality agents 𝑢,𝑣∈𝐺[𝑆] that are not connected by one edge: i.e., 𝑑u�[u�](𝑢,𝑣)=2 . In this case, creating an edge {𝑢,𝑣} is an improving response for 𝑢 . Hence, the only equilibrium graph for 𝛼<1 is a clique, which is also the optimal solution (cf. [Fab+03]). Lemma 5.17 ([Dem+07], Theorem 4) . For parameters 1≤𝛼≤√𝑛/2 and 𝑘≥6 , it holds k-BE =BE and the price of anarchy is at most 6. Proof. In [Dem+07], the authors show that every shortest path tree rooted at some agent 𝑢 has a height of at most 5 . For this, they assume the contrary and show the existence of an improving response where an agent at a distance of at least 6 buys an edge towards 𝑢 . This operation is available with 𝑘 ≥6 , hence every 𝑘 -local equilibrium has a diameter of at most 5 . In this case, we get k-BE =BE and the price of anarchy bound of [Dem+07] applies. Lemma 5.18 ([Dem+07], Theorem 10) . For parameters 1≤𝛼<𝑛1−u� , 𝜀≥1/lg(𝑛) and 𝑘 ≥4.667⋅3⌈1/u�⌉ +8 , it holds k-BE =BE and the price of anarchy is at most 4.667⋅3⌈1/u�⌉ +8. Proof. In Theorem 10 of [Dem+07], the authors use an inductive argument to find some agent 𝑢 and a radius 𝑑 such that the 𝑑 -neighborhood of 𝑢 contains more than (𝑛/2) -many agents. For this, they start with their Lemma 3 (for which only 𝑘≥2 must hold) and apply their Lemma 9 iteratively. They show that the maximal radius 𝑑 , for which their Lemma 9 must be applied, is at most 4.667⋅3⌈1/u�⌉ +8 , which gives a first lower bound for 𝑘 . Using this result, they apply their Corollary 7 to show that actually all agents are contained in a ball of radius 4.667⋅3⌈1/u�⌉ +7 , for which they need the operation of creating an edge to an agent at distance 4.667⋅3⌈1/u�⌉+8 , which is the second lower bound for 𝑘. Using both results, they show that the diameter of every equilibrium is at most 4.667⋅3⌈1/u�⌉+8 . By the choice of 𝑘 , the same holds for 𝑘 -local buy equilibria. We get k-BE =BE and thus the price of anarchy is at most 4.667⋅3⌈1/u�⌉+8 . Lemma 5.19 ([Dem+07], Theorem 12) . For parameters 1 ≤ 𝛼 ≤ 12𝑛log𝑛 and 𝑘 ≥2⋅51+√lg u�+24lg(𝑛)+3 , it holds k-BE =BE and the price of anarchy is at most O(5√lg u�lg𝑛). 111 5 Limits of Locality Proof. Similar to the proof of their Theorem 10 in [Dem+07], the authors provide a price of anarchy upper bound for a larger range of 𝛼 : Again, they use an inductive argument to find an agent 𝑢 and a radius 𝑑 such that the 𝑑 -neighborhood of 𝑢 contains more than (𝑛/2) -many agents. For this, they start with looking at the number of agents in any radius (12lg𝑛) -neighborhood and then apply their Lemma 11 iteratively. They show that the maximal radius 𝑑 , for which their Lemma 11 must be applied, is at most 51+√lg u� , which gives a first lower bound for 𝑘 . Using this result, they apply their Corollary 8 to show that actually all agents are contained in a specific ball, for which they need the operation of creating an edge to an agent at distance 2⋅51+√lg u�+24lg(𝑛)+3 , which is the second lower bound for 𝑘. Using both, they show that in every equilibrium network there is an agent who contains all others in a ball of radius (8⋅51+√lg u�+24lg(𝑛)+2) . With the choice of 𝑘 , the same holds for 𝑘 -local buy equilibria and we get k-BE =BE as well as a price of anarchy upper bound of O(5√lg u�lg 𝑛). Lemma 5.20 ([Alb+14], Theorem 3.6) . For parameters 12𝑛log𝑛≤𝛼 and 2≤𝑘 , it holds k-BE =BE and the price of anarchy is O(1). Proof. In [Alb+14], the authors provide a technical proof that characterizes equilibria for 𝛼 ≥ 12𝑛log𝑛 . The main insight that is used for their bound is that there are different types of agents (see their Lemma 3.4, which uses their Lemma 3.2 and Lemma 3.3) with which they characterize equilibria and show that any buy equilibrium network with girth of at least 12⋅⌈log𝑛⌉ has a diameter of less than 6⋅⌈log(𝑛)⌉ and hence is a tree. In their Lemma 3.5, they prove that the considered big 𝛼 values ensure a girth of at least 12⌈log𝑛⌉ . The result of their Theorem 3.6 then comes from a comparison to the social optimum and gives a price of anarchy upper bound of at most 1.5. Interestingly, in all used statements, there are only two statements concerning the creation or deletion of edges. For their Lemma 3.3, the operation of creating an edge to an agent in distance 2 is considered, and for their Lemma 3.5, the operation of deleting an edge is considered. Both operations are available with 𝑘 ≥ 2 . Hence, for any 𝑘 ≥ 2 , we have k-BE =BE and the price of anarchy bound of 1.5from [Alb+14] applies. 112 5.5 Efficiency of Probing Locality 5.5.2 The Price of Anarchy Our analysis of the price of anarchy focuses on diameter bounds for equilibrium networks. The reason for this is that using the following theorem that translates any diameter bound into an upper bound for the price of anarchy. This correspondence was first shown by Albers et al. [Alb+06] and again formulated by [Nis+07, Lemma 19.4], yet with a different proof. Specifically, the latter proof requires only the availability of 1 -local edge deletion operations and hence applies without changes for both the greedy probing and the unrestricted probing 𝑘-local games. Theorem 5.21 ([Nis+07], Lemma 19.4) . For any 𝑘≥1 and any edge price 𝛼≥2 , if a 𝑘 -local greedy buy equilibrium network 𝐺 has diameter 𝐷 , then its social cost is at most O(𝐷)times the optimal social cost. In the following, we present several upper bounds on the diameter of equilibrium networks and then conclude the price of anarchy results in Theorem 5.28 by using Theorem 5.21. Note that most of the diameter bounds will be given for 𝑘 -local greedy buy equilibria and, since k-BE ⊆k-GBE , also apply directly to 𝑘 -local buy equilibria, in which arbitrary operations are allowed. We start by providing a general result for tree network equilibria and then proceed with different bounds for respective ranges of the edge price 𝛼 that concerns general networks. Finally, at the end of this section, we provide a notably non-constant lower bound for the price of anarchy in 𝑘-local buy games. Corollary 5.22 (price of anarchy for tree networks) . For 𝑘 -local greedy buy equilibrium tree networks with 2≤𝑘≤log𝑛:PoA =O(log𝑛). Proof. By Lemma 5.12, every tree network that is a 𝑘 -local greedy buy equilibrium also is an asymmetric swap equilibrium (cf. Section 2.3). Therefore, we can apply the diameter upper bounds by Ehsani et al. [Ehs+15] and Mihalák and Schlegel [MS12], and get that every tree network equilibrium has a diameter of at most O (log𝑛) . Combining this with Theorem 5.21, the price of anarchy is at most PoA =O(log𝑛). For general networks, we next provide two different network diameter upper bounds. The first bound holds for any 𝑘≥2 and the second one gives improved results when the edge price is smaller than 𝑛1−u� for any constant 𝜀≥ 1 log u�. 113 CHAPTER 6 Multilevel Network Games Layers provide the architectural basis of most computer networks. Already the OSI reference model (cf. Zimmermann [Zim80]) specified how layers should be used to gain a modular structure for the Internet and by this laid the architectural foundations of many modern computer networks. Consequently, today this architecture is present all over in the design of networks and their communication protocols. The general idea of a layered system is to provide service-specific protocol layers that stack onto each other. Each layer can access the layer below, in some architectures also several layers below, and provides services for the layers on top. At the bottom layer, we have the physical network, at which every operation of a higher layer must be reflected eventually. In this chapter, we study the interaction of two communication layers in such a layered system: One layer provides general purpose connections, the other one is a high-speed layer that allows agents to improve their communication distances. Unlike in most previous research, we take a game theoretical view on the availability of such a high-speed layer and ask about its influence to the network’s total efficiency when faced with selfishly acting agents. Specifically, we consider agents as rational actors who individually decide if they want to connect to the high-speed layer for a fixed price of 𝛼 or not, depending only on 121 6 Multilevel Network Games their private costs. The availability of such high-speed networks is motivated by various observations. Foremost, techniques as discussed in Chapter 4 for individual connections also allow offering access to a whole high-speed network and not only for single point-to-point connections. A technical different, yet from a theoretical standpoint still similar scenario, is the use of an additional logical overlay network. Similar to the way overlays are used for search overlays (cf. survey by Androutsellis-Theotokis and Spinellis [AS04]), they can provide better routing information (e.g., larger routing tables or addresses to more likely communication partners in case of non-uniform communication interests) for the shortest path communications to other agents. This means, a logical network can also drastically reduce communication costs of the individual agents by providing such routing information. For using the high-speed layer, we consider two different access models in accordance with the two named motivations. On the one hand, we see the high-speed network as an additional network to which connections have to be created in order to enter or leave it. This is the same concept as one can find in physical networks, for example, which are connected via hardware routers. On the other hand, when looking at multilevel games that originate from quality-of-service agreements like in Chapter 4, it is reasonable that only the access to the high-speed layer raises cost, but switching back to the general purpose layer is allowed everywhere. In our games, we call the first connection model bidirectional and the second one unidirectional and further denote the connection points between the layers as gateways. Chapter Basis. The model, analysis, and results presented in the remainder of this chapter are based on the following publication: 2014 (with S. Abshoff, D. Jung and A. Skopalik). “Multilevel Network Games”. In: Web and Internet Economics – 10th International Conference, WINE 2014, Beijing, China, December 14–17, 2014. Proceedings, cf. [Abs+14]. Chapter Outline. In Section 6.1, we introduce a basic model for multilevel networks. This model splits into two variants: a game variant in which layers 122 6.1 Model & Preliminaries can be switched only at gateway agents and a variant in which just entering the high-speed layer requires gateways. The more specific model descriptions for both variants are then provided in Section 6.3 and Section 6.4, alongside the respective analysis. An overview of our results and a comparison with other models is given in Section 6.2. The chapter concludes with an outlook and a summary of open questions. 6.1 Model & Preliminaries A multilevel network game (𝑉,𝐿1,𝐿2) consists of 𝑛 agents 𝑉 who are connected via two network layers 𝐿1 and 𝐿2 . In layer 𝐿1 , the agents form a bidirectional connected graph (𝑉,𝐿1) and each edge has a length of 1 . The second layer 𝐿2 is a supporting high-speed layer, which can be used to improve the agents’ communication costs. Thus, the agents are present in both network layers, however, the access to the second layer must be enabled specifically. We denote the distance between two agents 𝑢,𝑣∈𝑉 in layer 𝐿1 by 𝑑1(𝑢,𝑣) , which indicates the shortest path distance in graph (𝑉,𝐿1) . Likewise, 𝑑2(𝑢,𝑣) denotes the shortest path distance in (𝑉,𝐿2) . The maximal distance for any pair of agents in (𝑉,𝐿1) is given by diam(𝐿1)≔maxu�,u�∈u�𝑑1(𝑢,𝑣) , respectively by diam(𝐿2) for (𝑉,𝐿2) . Agents are able to use the high-speed layer only at gateway agents, which means that a path may switch from layer 𝐿1 to layer 𝐿2 . Hence, gateways function as connections between the two layers. In the following, we will study games with two fundamentally different variants of gateways: Multilevel games with bidirectional gateways: A gateway at agent 𝑢 forms a bidirectional edge of length 0 between agent 𝑢 in (𝑉,𝐿1) and agent 𝑢 in (𝑉,𝐿2) . There are no other connections between the layers other than the gateways and thus switching between the layers is only possible at gateway agents. Multilevel games with unidirectional gateways: At every agent 𝑢 , there is a unidirectional edge of length 0 from 𝑢 in (𝑉,𝐿2) to 𝑢 in (𝑉,𝐿1) and thus, switching from layer 𝐿2 to layer 𝐿1 is allowed at every agent. If an agent is a gateway, then this connection from 𝐿2 to 𝐿1 is bidirectional and thus, gateways allow switching from 𝐿1to 𝐿2. 123 6 Multilevel Network Games Considering a gateway set 𝑆 , the communication distance 𝛿u�(𝑢,𝑣) constitutes the actual distance between two agents 𝑢 and 𝑣 by making use of both layers. Although the shortest path is measured by using both layers, we use the convention that the end points of the path must be the respective agents in layer (𝑉,𝐿1) . Note that we will omit the index 𝑆 if it is clear from context. Given an agent 𝑢 and a range 𝑘>0 , then 𝐵u�(𝑢) denotes the set of all agents within a communication distance of at most 𝑘to 𝑢. In our multilevel network game, agents can decide selfishly if they want to become a gateway or not. Being a gateway means that the agent pays a fixed price 𝛼>0 and establishes the above mentioned connection between the two network layers. We call the set of gateways 𝑆 and identify it with the current strategy profile. Agents in 𝑉⧵𝑆 are called non-gateways. Analog to network creation games, the decision of becoming a gateway or not is based on the private cost function of an agent. In the Sum-Layer-Game, the private cost of an agent 𝑢is: 𝑐u�(𝑆)≔𝛼⋅|𝑆∩{𝑢}|+ ∑ u�∈u�𝛿u�(𝑢,𝑣) For the Max-Layer-Game, the private cost function is: 𝑐u�(𝑆)≔𝛼⋅|𝑆∩{𝑢}|+max u�∈u� 𝛿u�(𝑢,𝑣) For both games, the social costs are given by cost(𝑆)≔∑u�∈u�𝑐u�(𝑆). If an agent improves her private cost by changing her strategy from nongateway to gateway or vice versa, we call this an improving response. For an improving response where an agent 𝑢 changes her strategy to be a gateway, we say that 𝑢 opens. Analogously, we say 𝑢 closes if she changes her strategy from gateway to non-gateway. We call a strategy profile 𝑆 a (pure) Nash equilibrium, or simply an equilibrium, if no agent can perform an improving response. For the convergence analysis of improving-response processes 1 , we ask whether the games provide the finite improvement property or (lesser) whether they are weakly acyclic (cf. Section 2.2.3). 1 Since the strategy space of any agent contains only two possible choices, in this game every improving response is also a best response. 124 6.2 Related Work & Contribution 6.2 Related Work & Contribution The outcome of the individual strategic connect and disconnect decisions of the network’s participants is a key issue in network creation games, as it was discussed in the previous chapters: How good can such an outcome be? How bad is it at most? And is it likely that the agents will ever reach an equilibrium state despite their uncoordinated behavior? – Considering our multilevel network games, these questions still apply in order to understand and quantify the effects of individual strategic decision making. Regarding the agents’ behaviors, multilevel games are actually very similar to network creation games. Specifically, both have the property in common that strategy changes result in changes of the network’s topology. However, the substantial difference is the size of the agents’ strategy spaces: For multilevel network games, a single agent has only two possible choices, compared to 2u�−1 options previously. This means that the decision whether to use an improving network layer or not is much more drastic than before in the classic network creation games as agents cannot make any fine-grained decision like connecting for a smaller cost to only specific areas. Despite its importance, the question of strategic decision making in multilevel networks is barely studied so far. When leaving out the strategic behavior of agents but using random processes to model their actions, the effects of network interactions in complex multilevel networks received various considerations, for example the interaction between a physical layer and a congestion flow by Kurant and Thiran [KT06]. However, such an approach misses the effects of strategic behavior, which is already present when one agent decides against being a gateway in favor of free-riding via her neighbor’s high-speed connection. With a focus on network formation, Shahrivar and Sundaram [SS13] considered a multilevel network game of centralized, strategically acting designers. Together with their follow-up paper [SS15], they provide the only contributions in this field with a game theoretic view. In their games, multiple network designers simultaneously construct networks and the overall efficiency of a designer also depends on the network layers provided by the other designers. Yet, compared to our model, the individual decision making of the agents was not considered. 125 6 Multilevel Network Games Contribution. In this chapter, we introduce a new model for analyzing the effects of strategic decision making in multilevel networks. Our model is the first one that captures the effects of individual agents being strategic actors in a multilevel context, namely agents of a general purpose network who can utilize a high-speed layer. Depending on how the general purpose and the high-speed layers interact with each other, we gain two qualitatively different networks games for which we apply the classic sum and maximum private cost functions. Considering the game with bidirectional gateways, we show that computing the optimal placement of gateways is 𝒩𝒫 -hard for both variants of private cost functions. For the Sum-Layer-Game, we show that for 𝛼 ≤ 𝑛−1 and 𝛼 > 𝑛(𝑛−1) equilibria always exist and that then the price of anarchy is 𝛩(1+𝑛/√𝛼) ; for 𝛼∈(𝑛−1,𝑛(𝑛−1)) , we upper bound the price of anarchy by O (√𝛼) . For the Max-Layer-Game, we show that equilibria always exist if the networks are trees or if the girth is not too small. We further provide a price of anarchy bound of 1 , for 𝛼 < 1 , and otherwise the tight bound of 𝛩(1+𝑛/√𝛼) . Concerning the dynamics, both the Sum-Layer-Game and the Max-Layer-Game are no potential games, whereas the Sum-Layer-Game is not even weakly acyclic. Regarding the game with unidirectional gateways, in the Sum-Layer-Game the price of anarchy is at most O (1 1−u� +u� u�(1−u�)2) , whereas 𝜇∈(0,1) is the improvement factor of the high-speed layer. In the Max-Layer-Game, we provide an algorithm to compute equilibria for treenetworks, when the 𝐿2 -layer provides some exact improvement property. For the general case, we show that in this game the price of anarchy is at most O (𝛼/(1−𝜇)2) . Complementing this upper bound, we also provide a high lower bound of 𝛺(√𝑛) for certain parameters of 𝛼. 6.3 Bidirectional Gateways In this section, we analyze the multilevel network game (𝑉,𝐿1,𝐿2) with bidirectional gateways. The high-speed layer 𝐿2 is assumed to provide negligible short connections between all agents. In our sense, this means that every distance is shorter than 1 divided by the number of agents. Without loss of 126 6.3 Bidirectional Gateways generality, we can assume then that all distances in layer 𝐿2 have a length of 0 . Consequently, for the remainder of this section, we will omit specifications of the 𝐿2 -layer network and use only (𝑉,𝐿1) to state a game instance. Since the distance between any two gateways is 0 , the communication distance for 𝑢,𝑣∈𝑉resolves to: 𝛿u�(𝑢,𝑣)=min{𝑑1(𝑢,𝑣),𝑑1(𝑢,𝑆)+𝑑1(𝑆,𝑣)} Here, 𝑑1(𝑢,𝑆) denotes the shortest path distance from agent 𝑢 to any gateway. Throughout this section, we further require that one gateway must always be left in the game. Thus, a last gateway is not allowed to close even if that would be an improving response for her. It is easy to see that otherwise 𝑆=∅ would form an equilibrium for any game instance, since then no agent could improve her cost by a unilateral strategy change. 6.3.1 The Sum-Layer-Game We start our study with the Sum-Layer-Game. First, we ask the difficulty of computing a gateway set that minimizes the social cost. Note that this set is not required to be an equilibrium. Theorem 6.1. For the Sum-Layer-Game with bidirectional gateways, the computation of a gateway set that minimizes the social cost is 𝒩𝒫-hard. Proof. Let (𝑉,𝐿1) be an instance of the Sum-Layer-Game. For two parameters 𝑛,𝑚 > 4 , let there be a set of 𝑚 elements 𝑋 ≔ {𝑥1,…,𝑥u�} and further 𝑛 subsets 𝑆1,…,𝑆u�⊆𝑋 of this element set. Then, the 𝒩𝒫 -complete Set-Cover problem (cf. Karp [Kar72]) is the task to compute a minimal number of subsets that together contain all elements of 𝑋 . Given such a Set-Cover instance, we construct an instance (𝑉,𝐿1) of the Sum-Layer-Game as follows (cf. Figure 6.1): First, we create a clique 𝐶 of 𝑘 agents and mark one of its agents as 𝑐 . For every set 𝑆u� , we create a corresponding agent 𝑆u� and connect her to 𝑐 . For every element 𝑥u�∈𝑋 , we create 𝑤 -many agents 𝑥1 u�,…,𝑥u� u� and connect all 𝑥u�u� , for 𝑖 = 1,…,𝑚 and 𝑗 = 1,…,𝑤 , to all set agents 𝑆u� with 𝑥u�∈ 𝑆u� . Using the parameters 𝑤≔𝑛 , 𝑘≔𝑚−1 , and 𝛼≔4𝑛(𝑚−1) , in the following we show that an optimal placement of gateways corresponds to a solution of the Set-Cover problem. 127 6 Multilevel Network Games For now, assume that 𝑐 is a gateway agent in the optimal solution 𝑆Opt (we will prove this claim later). We claim that then no other clique agent 𝑣∈𝐶⧵{𝑐} is a gateway. For this, assume that 𝑙 further clique agents are open and compute the social cost decrease by closing all clique agents except agent 𝑐 . The decrease is at least 𝑙𝛼−2𝑙(𝑤𝑚+𝑛)−𝑙(𝑙+1)>0 and hence 𝑐 is the only agent in 𝐶∩𝑆Opt . Next, for an element 𝑥u� consider the corresponding element agents 𝑥1 u�,…,𝑥u� u� and a set 𝑆u� such that 𝑥u�∈ 𝑆u� . If there is any 𝑥u�u�∈ 𝑆 and 𝑆u�∉ 𝑆 , closing 𝑥u�u� and opening 𝑆u� does not increase the social cost. Hence, we can assume that in 𝑆Opt there is no closed set agent with an open element agent. Now, let 𝑆u� be an open set agent and assume that for 𝑥u�∈ 𝑆u� there are 𝑙 open element agents. Closing all of these element agents reduces the social cost by at least 𝑙𝛼−2𝑙(𝑘+𝑛+2(𝑙−1)+(𝑤−𝑙)+(𝑚−1)𝑤)=𝑙𝛼−2𝑙(𝑤𝑚+𝑛+𝑘+𝑙−2)>0 and hence in 𝑆Opt all are closed. Given a set of closed element agents 𝑥1 u�,…,𝑥u� u� such that for all 𝑆u� with 𝑥u�∈𝑆u� the set agents are closed, opening 𝑆u� reduces the social cost by at least 2(𝑘𝑤+(𝑚−1)𝑤+(𝑛−1))−𝛼>0 . Contrarily, opening a set agent whose element agents are already completely covered increases the social cost by at least 𝛼−2(𝑘+𝑚𝑤+𝑛−1)>0. Finally, we can see that 𝑐 actually has to be a gateway in 𝑆Opt . For this, consider an arbitrary optimal setting with all clique agents closed (if one clique agent is open, we can close it and open 𝑐 without increasing the social cost). When opening 𝑐 , we know that without increasing the social cost we can close all element agents and open corresponding set agents. Hence, when opening 𝑐 we can assume that all element agents are closed and that for each element agent a corresponding set is open. This gives a social cost decrease by opening 𝑐of at least 2𝑘𝑚𝑤−𝛼>0. Hence, the socially optimal solution 𝑆Opt is given by a gateway agent 𝑐 and a minimal number of set agents such that all element agents are covered. We now study the existence of equilibrium networks. Given a Sum-Layer- Game with a moderately small or alternatively very high connection price, we show that equilibria always exist. Proposition 6.2. Given a Sum-Layer-Game (𝑉,𝐿1) of 𝑛≔|𝑉| agents with bidirectional gateways, connection price 𝛼≤𝑛−1 or 𝛼>𝑛⋅diam(𝐿1) , then an equilibrium setting exists. 128 6.3 Bidirectional Gateways 𝑐 clique 𝐶 ⋯sets 𝑆1,…,𝑆u� elements 𝑥(⋅) 1,…,𝑥(⋅) u� ⋯ Figure 6.1: Illustration of the 𝒩𝒫 -hardness reduction from Set-Cover to optimal gateway placement. Proof. For 𝛼≤𝑛−1 , consider the strategy profile 𝑆≔𝑉 in which every agent has a private cost of 𝛼 . If any gateway closes in this setting, her distance cost would become at least 𝑛−1 . This cannot be an improving response and hence 𝑆=𝑉is an equilibrium. For 𝛼>𝑛⋅diam(𝐿1) , consider an arbitrary setting with |𝑆|=1 . Assuming a second agent would open, then her distance cost decreased by not more than 𝑛⋅diam(𝐿1)<𝛼and hence this cannot be an improving response. Proposition 6.3. Given a Sum-Layer-Game (𝑉,𝐿1) of 𝑛≔|𝑉| agents with bidirectional gateways and a connection price 𝛼≤𝑛−1 . Then, 𝑆=𝑉 minimizes the social cost and the price of stability is 1. Proof. Let 𝑆 be a socially optimal solution and assume that there are 𝑚 closed agents. When opening all of them, then for any gateway 𝑣∈𝑆 the distances to all these 𝑚 agents reduce by at least 1 each, while for 𝑢∈𝑉⧵𝑆 the distances reduce by at least 𝑛−1 each. Hence, setting the strategy profile to 𝑆 = 𝑉 changes the social cost by 𝑚𝛼−((𝑛−𝑚)+𝑚(𝑛−1))<0 . This holds for any setting with fewer than 𝑛 gateways and thus, it is the socially optimal solution. Since 𝑆=𝑉is also in equilibrium, the price of stability is 1. Note that Proposition 6.3 does not contradict the 𝒩𝒫 -hardness proof of Theorem 6.1, since in that proof the connection price 𝛼 was chosen to be bigger than the number of agents. 129 6 Multilevel Network Games 𝑢⋯ ⋯𝑣 ⋯ ⋮𝑘paths ⌊√𝛼⌋−1agents Figure 6.4: Equilibrium construction for the Sum-Layer-Game that gives a lower bound on the price of anarchy with u�≥4,u�≔⌊u�−1 ⌊√u�⌋−1⌋, and u�being the only gateway. For the remainder of the proof, consider 𝛼≥4 . In this case, we construct a star-like 𝐿1 -layer (cf. Figure 6.4) consisting of one center agent 𝑢 , 𝑘 ≔ ⌊u�−1 ⌊√u�⌋−1⌋ -many disjoint paths 𝑃1,…,𝑃u� , each consisting of ( ⌊√𝛼⌋−1 )- many agents, and possibly an additional path 𝑃u�+1 consisting of the remaining agents. The first agent on each path is connected to 𝑢 . We select one leaf agent 𝑣 at a distance of exactly ⌊√𝛼⌋−1 to 𝑢 to be a gateway. Then, no agentcan perform an improving response, since the maximal distance cost decrease by opening is ∑⌊√u�⌋−1 u�=1 2𝑖<𝛼 . We estimate a social cost lower bound by considering the private cost of 𝑢, which is minimal for all agents: 𝑐u�(𝑆)≥𝑘⌊√u�⌋−1 ∑ u�=1 𝑖= 𝑘 2(⌊√𝛼⌋−1)⌊√𝛼⌋ This gives for the social cost: cost(𝑆)≥ 𝑛 2⌊𝑛−1 ⌊√𝛼⌋−1⌋(⌊√𝛼⌋−1)⌊√𝛼⌋ Comparing this to the social cost 𝛼𝑛 of the optimal solution, we get as the result PoA =𝛺(𝑛/√𝛼). Lemma 6.13. In a Sum-Layer-Game (𝑉,𝐿1) of 𝑛≔|𝑉| agents with bidirectional gateways, for 2≤𝛼≤𝑛−1the price of anarchy is O(𝑛/√𝛼). Proof. Let 𝑆⊆𝑉 be an arbitrary equilibrium strategy profile. Using Proposition 6.3, we know that 𝑆=𝑉is the socially optimal solution. If 𝑆≠𝑉 , then it must hold |𝑆|≤⌈𝛼⌉ , since otherwise a non-gateway could reduce her distance cost by more than 𝛼 by opening. Further, for every non- 136 6.3 Bidirectional Gateways gateway 𝑣∈𝑉⧵𝑆 , we get that 𝑑1(𝑣,𝑆)≤ 2⌈√𝛼⌉ , since otherwise opening 𝑣 would reduce her private cost by at least: ⌈√u�⌉ ∑ u�=1 2𝑖=⌈√𝛼⌉(⌈√𝛼⌉+1)>𝛼 Thus, for all gateways 𝑣 ∈ 𝑆 it holds 𝑐u�(𝑆) ≤ 𝛼+|𝑉 ⧵𝑆|⋅2⌈√𝛼⌉ . Since a non-gateway cannot have a higher private cost than a gateway, we get: cost(𝑆)≤𝑛𝛼+𝑛⋅|𝑉⧵𝑆|⋅2⌈√𝛼⌉≤𝑛𝛼+2𝑛2⌈√𝛼⌉ Comparing this to the social optimum yields: PoA ≤𝑛𝛼+2𝑛2⌈√𝛼⌉ 𝛼𝑛 ≤1+ 2𝑛 ⌈√𝛼⌉=O(𝑛 √𝛼) Lemma 6.14. In a Sum-Layer-Game (𝑉,𝐿1) of 𝑛≔|𝑉| agents with bidirectional gateways and a connection price 𝛼>𝑛−1, the price of anarchy is: PoA =⎧ { { ⎨ { { ⎩ O(√𝛼)for 𝛼∈(𝑛−1,𝑛(𝑛−1)), 1for 𝛼≥𝑛(𝑛−1). Proof. First, we show that for an arbitrary strategy profile 𝑆′⊆ 𝑉 it holds cost(𝑆′) > 𝛼⋅|𝑆′|+𝑛⋅|𝑉⧵𝑆′| . We define 𝑘 ≔ |𝑉⧵𝑆′| to be the number of non-gateways and can use 𝑘(𝑘+1)<𝑛𝑘, since |𝑆′|≥1. This gives: cost(𝑆′)≥𝑘(𝑛−1)+|𝑆′|⋅(𝛼+𝑘) =𝑘𝑛−𝑘+𝑛𝛼+𝑛𝑘−𝛼𝑘−𝑘2 =2𝑘𝑛−𝑘(𝑘+1)+𝛼(𝑛−𝑘) >𝛼(𝑛−𝑘)+𝑘𝑛 Now we consider an equilibrium strategy profile 𝑆 . If 𝑆=𝑉 , then the social cost is 𝛼𝑛 . For the case 𝛼>𝑛(𝑛−1) , no agent wants to open and hence exactly one gateway exists, which gives 𝛼+𝑛(𝑛−1) for the social cost. Since the social cost lower bound is minimized when having exactly one gateway, we 137 6 Multilevel Network Games get PoA ≤u�+u�(u�−1) u�+(u�−1)u� =1. For 𝑛(𝑛−1)≥𝛼≥𝑛 , let 𝑚 be the number of gateways in an equilibrium 𝑆 . Since 𝑆 is an equilibrium, the maximal distance from a non-gateway to a gateway is 2√𝛼 . This gives for any gateway 𝑢∈𝑆 that 𝑐u�(𝑆)≤𝛼+(𝑛−𝑚)2√𝛼 and for any non-gateway 𝑣∈𝑉⧵𝑆 that 𝑐u�(𝑆)≤(𝑛−1)4√𝛼 . The social cost can be upper bounded by: cost(𝑆)≤𝑚𝛼−𝑚(𝑛−𝑚)2√𝛼+(𝑛−𝑚)4√𝛼(𝑛−1) ≤𝑚𝛼−𝑚22𝛼+4√𝛼𝑛(𝑛−1) The global maximum of this upper bound is at √𝛼/4 , which has the value of u�√u� 8+4√𝛼𝑛(𝑛−1) . Comparing this to the social cost lower bound of 𝛼+𝑛(𝑛−1) , we get PoA =O(√𝛼). 6.3.2 The Max-Layer-Game Similar to the Sum-Layer-Game, we start our analysis of the Max-Layer-Game by studying the hardness of computing a socially optimal solution, followed by a discussion of the convergence properties of improving-response processes and the price of anarchy. Theorem 6.15. For the Max-Layer-Game with bidirectional gateways, the computation of a gateway set that minimizes the social cost is 𝒩𝒫-hard. Proof. For two parameters 𝑛 and 𝑚 with 𝑚=2𝑛 , let there be a set of 𝑚 elements 𝑋≔{𝑥1,…,𝑥u�} and further 𝑛 subsets 𝑆1,…,𝑆u�⊆𝑋 of this element set. Then the 𝒩𝒫 -complete Set-Cover problem (cf. Karp [Kar72]) is the task to compute a minimal number of subsets that together contain all elements of 𝑋 . Given such a Set-Cover instance (𝑉,𝐿1) , we construct an instance of the Max-Layer- Game as follows (cf. Figure 6.1). First, we create a clique 𝐶 of 𝑘 agents and mark one of them as 𝑐 . For every set 𝑆u� , we create a corresponding agent 𝑆u� and connect her to 𝑐 . For every element 𝑥u�∈ 𝑋 , we create an agent 𝑥u� and connect her to all set agents 𝑆u� with 𝑥u�∈𝑆u� . Using the parameters 𝛼≔3 and 𝑘≔𝛼𝑛=3𝑛 , in the following we show that an optimal placement of gateways corresponds to a solution of the Set-Cover problem. For now, assume that 𝑐 is a gateway agent in the optimal solution 𝑆Opt (we will prove this claim later). We claim that then no other clique agent 𝑣∈𝐶 with 138 6.3 Bidirectional Gateways 𝑣≠𝑐 is a gateway. For this, assume that 𝑙 further clique agents are open in 𝑆Opt and compute the social cost decrease gained by closing all of these clique agents except 𝑐 . If 𝑙<𝑘−1 , then at most the distances of these 𝑙 agents are increased by one each, which gives a social cost decrease of 𝑙𝛼−𝑙>0 . Otherwise, the social cost decrease is at least (𝑘−1)𝛼−(𝑘−1)−𝑚−𝑛=2(3𝑛−1)−3𝑛>0 . Hence, there can be at most one gateway agent 𝑐contained in the clique. Next, assume that there are 𝑙 open element agents in 𝑆Opt . If 𝑙<𝑚 and if at the same time there are open set agents who form a set cover, then by closing all element agents, only the maximal distances of these element agents increase and the social cost decreases by at least 𝛼𝑙−𝑙>0 . If there are not yet set agents open that form a set cover, we have to open at most 𝑛 set agents to form a set cover. By opening them and simultaneously closing all element agents, the maximum distances for all clique agents decrease by one each, which gives a social cost decrease of at least 𝛼𝑙+𝑘−𝛼𝑛−𝑙=3𝑙+3𝑛−3𝑛−𝑙>0 . Finally, if 𝑙=𝑚 , by closing all element agents and opening a set cover, the social cost decreases by at least 𝛼𝑚−𝛼𝑛−𝑚−𝑘=6𝑛−3𝑛−2𝑛>0. Finally, we can see that 𝑐 actually has to be a gateway in 𝑆Opt . For this, consider an arbitrary optimal setting with all clique agents closed (if one clique agent is open, we can close it and open 𝑐 without increasing the social cost). When opening 𝑐 , we know that without increasing the social cost we can close all element agents and open corresponding set agents. Hence, when opening 𝑐 we can assume that all element agents are closed and that for each element agent a corresponding set is open. Hence, the socially optimal solution 𝑆Opt is given by a gateway agent 𝑐 and a minimal number of set agents such that all element agents are covered. Equilibria and Convergence Properties Given a Max-Layer-Game (𝑉,𝐿1) with bidirectional gateways, next we study the existence of equilibria and the convergence of improving-response processes. For the simple cases when the connection price is very small or very big, we can provide positive convergence results and by this implicitly show the existence of equilibria. Likewise, for the class of tree networks and networks with big girth, whereas the girth is the length of a shortest cycle in the network, we can compute equilibrium settings in polynomial time. Yet for the general 139 6 Multilevel Network Games case, it will turn out that the Max-Layer-Game is not necessarily a potential game. If the connection price is at most 𝛼<1 , then for any non-gateway it is an improving response to open and also no gateway will ever close. Hence, no improving-response process can be longer than 𝑛−1 steps and such a process always converges to the equilibrium state 𝑆=𝑉 . Moreover, for 𝛼>diam(𝐿1) no non-gateway will ever open and every gateway wants to close. Hence, also here we have the same convergence properties. Next, we consider the non-trivial case of arbitrary networks with big girth. Proposition 6.16. Given a Max-Layer-Game (𝑉,𝐿1) of 𝑛≔|𝑉| agents with bidirectional gateways such that the girth 2 is at least girth((𝑉,𝐿1)) ≥ 4𝛼 , then for 𝛼∈[1,diam(𝐿1))a Max-Layer-Game equilibrium exists. Proof. Let 𝑥1,𝑥2 be two maximal distant agents in (𝑉,𝐿1) . If 𝑑1(𝑥1,𝑥2)<2𝛼 , we get by girth((𝑉,𝐿1))≥4𝛼 that (𝑉,𝐿1) is a tree and there exists an agent 𝑣 who has a maximal distance of less than 𝛼 to every other agent. In this case, opening 𝑣yields an equilibrium. Otherwise, define 𝑅≔⌊min{𝛼−1,(𝑑1(𝑥1,𝑥2)−𝛼)/2}⌋ . Since agents 𝑥1 and 𝑥2 are at maximal distance, none of them can be connected to a leaf agent. For both of these agents, we do the following (cf. Figure 6.5): We consider the breadth-first-search trees up to level 𝑅 , rooted at 𝑥1 and 𝑥2 , respectively. From the agents at level 𝑅 , we open a maximal set of gateways such that no two gateways are at a distance less than 𝑅. Now we claim that for every agent 𝑥 in such a tree, there exists a gateway within a distance of at most 𝑅 . For this, consider a shortest path to an agent 𝑢 at level 𝑅 . If 𝑢 is not a gateway, then there must also be another agent 𝑢′ at level 𝑅 who is a gateway. Since the girth is at least 4𝛼 and 𝑅<𝛼<diam(𝐿1) , the shortest path from 𝑢to 𝑢′can only consist of agents of the tree and hence 𝑑1(𝑥,𝑢′)<𝑅. Next, iteratively open a maximal set of further agents such that each new agent has a minimal distance of exactly ⌈𝛼⌉ to a gateway. By construction, since every non-gateway has a maximal distance of ⌊𝛼⌋ to a gateway, a non-gateway can improve her maximal distance by at most ⌊𝛼⌋ and hence cannot perform any improving response. For every gateway 𝑣 , it holds that her private cost 2Note that for an acyclic graph the girth is infinity. 140 6.3 Bidirectional Gateways ≥⌈𝛼⌉ 𝑥1𝑥2 𝑅 𝑅 Figure 6.5: Illustration of the equilibrium construction in the proof of Proposition 6.16 for the Max-Layer-Game with bidirectional gateways and girth of at least 4u� . Orange agents denote gateways. is 𝑐u�(𝑆) = 𝛼+𝑅 (with both 𝑥1 and 𝑥2 at maximal distance, since otherwise we get a contradiction to the maximal distance of 𝑥1 and 𝑥2 .) Considering the private cost change of closing 𝑣 , her maximal distance increases by exactly ⌈𝛼⌉ and hence this is not an improving response. Theorem 6.17. The Max-Layer-Game with bidirectional gateways and a connection price 𝛼>1is not a potential game. Proof. Consider an 𝐿1 -layer consisting of 𝑛≔3⌊𝛼⌋+4 agents that are connected as a line. We denote the first agent of the line as 𝑢 , the agent at distance ⌊𝛼⌋+1 to 𝑢 as 𝑣 , and the agent at distance 2⌊𝛼⌋+2 to 𝑢 as 𝑤 . Initially, only 𝑢 is a gateway. Then, 𝑣and 𝑤form an improving-response cycle: I: 𝑤opens since 2⌊𝛼⌋+2>𝛼+⌊𝛼⌋+1. II: 𝑣opens since 2⌊𝛼⌋+2>𝛼+⌊𝛼⌋+1. III: 𝑤closes since 𝛼+⌊𝛼⌋+1>⌊𝛼⌋+1. IV: 𝑣closes since 𝛼+2⌊𝛼⌋+2>2⌊𝛼⌋+2. Hence, the game does not provide the finite improvement property. Price of Anarchy Previously, we already argued that for 𝛼<1 the only equilibrium is 𝑆=𝑉 . Since this is also the socially optimal solution, both the price of anarchy and 141 6 Multilevel Network Games the price of stability are 1 then. For the remaining connection prices of 𝛼≥1 , next we provide a tight price of anarchy result. Theorem 6.18. Given a Max-Layer-Game (𝑉,𝐿1) of 𝑛≔|𝑉| agents with bidirectional gateways, then for 𝛼≥1the price of anarchy is 𝛩(1+𝑛/√𝛼). Proof. (Upper bound.) We start with an upper bound on the price of anarchy. For this, let (𝑉,𝐿1) be a game instance and 𝑆⊆𝑉 an arbitrary equilibrium strategy profile. With 𝐷≔diam(𝐿1), it trivially holds that cost(𝑆)≤𝑛𝐷. Now we want to consider the minimal social cost when placing exactly 𝑘 gateways on a longest shortest path 𝑃 . Having only these 𝑘 gateways, the total cost of the agents on 𝑃is: 𝛼𝑘+2𝑘⌊u�/(2u�)⌋ ∑ u�=1 (𝑖+⌊𝐷 2𝑘⌋)≥𝛼𝑘+ 3 4𝑘𝐷2 The total cost of all agents not on 𝑃 is at least (𝑛−𝐷)u� 2u� , which gives a social cost lower bound of: 𝛼𝑘+ 3 4𝑘𝐷2+(𝑛−𝐷)𝐷 2𝑘 =𝛼𝑘+𝐷2+2𝑛𝐷 4𝑘 This term is minimized by 𝑘=√u�2+2u�u� 4u� , which corresponds to a social cost of at least √𝛼(𝐷2+2𝑛𝐷) . Comparing this value to the previously computed social cost upper bound for any equilibrium setting gives 𝑛𝐷 √𝛼(𝐷2+2𝑛𝐷) ≤𝑛 √𝛼, which is the claimed upper bound for the price of anarchy. (Lower bound.) For 𝑛∈ℕ , 𝑘≔⌊(𝑛−1)/3⌋ , we consider the following 𝐿1 -layer: We select one agent 𝑐 as a center agent, connect two disjoint paths of each 𝑘 - many agents to 𝑐 , and finally connect one path consisting of (𝑛−2𝑘−1) -many agents to 𝑐 . When opening the leaf agent of the last connected path, we obtain an equilibrium strategy profile since no agent can improve her maximum 142 6.4 Unidirectional Gateways distance by opening. The social cost of this equilibrium is at least: 3u� ∑ u�=1(𝑖+𝑘)=3𝑘2+3 2(𝑘+1)𝑘=𝛺(𝑛2) Next, consider the socially optimal solution. For √𝛼≥𝑛 , the optimal solution coincides with the equilibrium. Otherwise, we get the optimal solution by opening 𝑐 as well as a maximal set of agents on each path such that between each two neighboring gateways the distance is ⌊𝛼⌋ . The resulting social cost of this solution is at most 𝛼u� ⌊√u�⌋ +𝑛 u� ⌊√u�⌋ , which gives the price of anarchy lower bound of 𝛺(𝑛/√𝛼). 6.4 Unidirectional Gateways In this section, we consider multilevel games with the property that switching from layer 𝐿2 to layer 𝐿1 is permitted at any agent, but access to the 𝐿2 layer is restricted to gateway agents. As introduced in Section 6.1, these games are called multilevel games with unidirectional gateways. Different to the games with bidirectional gateways, we now consider arbitrary second layer networks, yet still keep our high-speed assumption. Applied to the new model, this means that we restrict our analysis to games (𝑉,𝐿1,𝐿2) that ensure for every distance in the 𝐿1 -layer that the corresponding distance in 𝐿2 is at most a 𝜇 - fraction of the original one. Formally, we call this property 𝜇 -improving and it states that for every 𝑢,𝑣∈𝑉it must hold: 𝜇⋅𝑑1(𝑢,𝑣)≥𝑑2(𝑢,𝑣) The following lemma states a first consequence of this property: Any shortest path between two agents switches at most once from 𝐿1 to 𝐿2 and then exclusively uses edges from 𝐿2, until it reaches the target agent. Lemma 6.19. Let (𝑉,𝐿1,𝐿2) be a 𝜇 -improving multilevel game with unidirectional gateways, 𝑆⊆𝑉 a set of gateways, and 𝑢,𝑣∈𝑉 two arbitrary agents. Then, for the edges (𝑒1,…,𝑒u�) of any shortest path from 𝑢 to 𝑣 it holds: there is a 𝑘∈{0,…,𝑚} such that 𝑒u�∈𝐿1, for all 𝑖≤𝑘, and 𝑒u�∈𝐿2, for all 𝑖>𝑘. Proof. Assume there is an edge 𝑒u�∈𝐿2 such that the succeeding edge of the 143 6 Multilevel Network Games shortest path belongs to 𝑒u�+1 ∈𝐿1 . Let {𝑥,𝑦}=𝑒u�+1 denote the end points of this edge. Since the 𝐿2 -layer is 𝜇 -improving, we know that there also exists a path of length at most 𝜇 from 𝑥 to 𝑦 purely consisting of 𝐿2 edges. Yet, this would contradict 𝑒u�+1 belonging to a shortest path. 6.4.1 Existence of Equilibria Compared to the multilevel games with bidirectional gateways, the computation of equilibria in the unidirectional model seems to be even harder than before, given that now the 𝐿2 -layer can have an arbitrary structure. In the following, we show the existence of equilibria in the Max-Layer-Game for the case when the 𝐿1 -layer is a tree and furthermore the 𝐿2 -layer provides the so-called exact𝜇 -improving property. For a game (𝑉,𝐿1,𝐿2) we say that it is exact𝜇 - improving if it fulfills 𝜇⋅𝑑1(𝑢,𝑣)=𝑑2(𝑢,𝑣) for every pair of agents 𝑢 and 𝑣 . Specifically, the following theorem provides a polynomial time algorithm for computing an equilibrium setting. Theorem 6.20. Let (𝑉,𝐿1,𝐿2) be an exact𝜇 -improving Max-Layer-Game instance with unidirectional gateways such that (𝑉,𝐿1) is a tree. Then, there exists a set of gateways 𝑆⊆𝑉 forming an equilibrium, which can be computed in polynomial time. Proof. We start with an empty gateway set 𝑆 and compute a solution as follows: (a) If diam(𝐿1)≤ u� 1−u�, then output 𝑆=∅as the solution. (b) If 2u� 1−u� >diam(𝐿1)> u� 1−u� , then select an arbitrary agent 𝑧 such that it holds 𝑑1(𝑧,𝑣)≤ u� 1−u� for all 𝑣∈𝑉 and furthermore, there is some agent 𝑥∈𝑉with 𝑑1(𝑧,𝑥)≥ u� 1−u�. Then output 𝑆={𝑧}as solution. (c) If diam(𝐿1)≥ 2u� 1−u� then: (i) Considering only the first layer 𝐿1 , select an agent with the smallest maximal distance to all other agents, name her 𝑟and open 𝑟. (ii) Next, iteratively consider the other tree agents in a sequence such that the first layer distance to 𝑟 is increasing. If for such an agent 𝑣 it holds that 𝑣 would reduce the distance to 𝑟 by at least 𝛼 by opening, then we open this agent. Otherwise 𝑣stays closed. 144 6.4 Unidirectional Gateways We claim that the so-computed solution 𝑆 forms an equilibrium setting. First, if diam(𝐿1)≤ u� 1−u� , then no agent can improve her maximum distance by more than 𝛼and hence 𝑆=∅is an equilibrium. In case 2u� 1−u� >diam(𝐿1)> u� 1−u� , then there exists an agent 𝑧 with the specified properties. Specifically, every agent has a distance of at most u� 1−u� to 𝑧 and hence no agent can improve her maximum distance cost of more than 𝛼 by opening. Since 𝑧 would increase her maximum distance by closing, it follows that 𝑆={𝑧}is an equilibrium. Now we consider the interesting case of diam(𝐿1)≥ 2u� 1−u� . For this, we first show that no gateway wants to deviate from her strategy and, furthermore, that also no non-gateway wants to open. We use ℎ(𝐿1) to denote the maximal distance in the 𝐿1-layer from 𝑟to any agent. Gateways: By construction, for gateway 𝑟 it holds that the closest other gateway is at a distance of at least u� 1−u� . Hence, 𝑟 would increase her longest shortest path distances by at least 𝛼 when closing, which cannot be an improving response. We denote the gateways as 𝑟,𝑣1,…,𝑣u� , ordered in the sequence they were opened. For the 𝑖 -th opened gateway 𝑣u� , the shortest path distance from 𝑣u� to 𝑟 was improved by at least 𝛼 . We further know for 𝑣u� that for both strategies, 𝑣u� being a gateway or being a non-gateway, there is a longest shortest path containing 𝑟 . For 𝑣u� being a gateway, this directly holds by choice of 𝑟 . But also if 𝑣u�∉𝑆 , since 𝑟 is a gateway, 𝛿(𝑣u�,𝑟)+𝜇ℎ(𝐿1) is an upper bound on every distance and by choice of 𝑟 there must be a shortest path over 𝑟 to some agent 𝑥 to which this is the distance. Hence, the maximum distance to any other agent, and by this the private cost of 𝑣u�, is given by the distance to 𝑟. Thus, agent 𝑣u� would close only if this distance increased by less than 𝛼 . By construction, only the opening of a gateway 𝑣u� with 𝑗 > 𝑖 can cause a strategy change of 𝑣u� . We denote the closest common predecessor of 𝑣u� and 𝑣u� in the rooted tree by 𝑧 and get 𝑑1(𝑟,𝑧)≤𝑑1(𝑟,𝑣u�)≤ 𝑑1(𝑟,𝑣u�) . Hence, if 𝑣u� closed, this would incur additional distance cost for 𝑣u� of at least min{𝛼,𝑑1(𝑣u�,𝑧)+𝑑1(𝑧,𝑣u�)+𝜇𝑑1(𝑣u�,𝑟)−𝜇𝑑1(𝑣u�,𝑟)} . Yet, the same also holds for 𝑣u� and since 𝑣u� was opened after 𝑣u� , it must 145