Concurrent with recent theoretical interest in the problem of metric embedding, a growing body of research in the networking community has studied the distance matrix defined by node-to-node latencies in the Internet, resulting in a number of recent approaches that approximately embed this distance matrix into low-dimensional Euclidean space. There is a fundamental distinction, however, between the theoretical approaches to the embedding problem and this recent Internet-related work: in addition to computational limitations, Internet measurement algorithms operate under the constraint that it is only feasible to measure distances for a linear (or near-linear) number of node pairs, and typically in a highly structured way. Indeed, the most common framework for Internet measurements of this type is a beacon-based approach one chooses uniformly at random a constant number of nodes (“beacons”) in the network, each node measures its distance to all beacons, and one then has access to only these measurements for the remainder of the algorithm. Moreover, beacon-based algorithms are often designed not for embedding but for the more basic problem of triangulation , in which one uses the triangle inequality to infer the distances that have not been measured. Here we give algorithms with provable performance guarantees for beacon-based triangulation and embedding. We show that in addition to multiplicative error in the distances, performance guarantees for beacon-based algorithms typically must include a notion of slack —a certain fraction of all distances may be arbitrarily distorted. For metric spaces of bounded doubling dimension (which have been proposed as a reasonable abstraction of Internet latencies), we show that triangulation-based distance reconstruction with a constant number of beacons can achieve multiplicative error 1 + δ on a 1 − ϵ fraction of distances, for arbitrarily small constants δ and ϵ. For this same class of metric spaces, we give a beacon-based embedding algorithm that achieves constant distortion on a 1 − ϵ fraction of distances; this provides some theoretical justification for the success of the recent Global Network Positioning algorithm of Ng and Zhang [2002], and it forms an interesting contrast with lower bounds showing that it is not possible to embed all distances in a doubling metric space with constant distortion. We also give results for other classes of metric spaces, as well as distributed algorithms that require only a sparse set of distances but do not place too much measurement load on any one node.

A fundamental principle in social network research is that individuals can benefit from serving as intermediaries between others who are not directly connected. Through such intermediation, they potentially can broker the flow of information and synthesize ideas arising in different parts of the network. These principles form the underpinning for the theory of structural holes, which studies the ways in which individuals, particularly in organizational settings, fill the holes between people or groups that are not otherwise interacting.We apply a game-theoretic approach to this notion, studying the structures that evolve when individuals in a social network have incentives to form links that bridge otherwise disconnected parties. We model payoffs as a trade-off between the benefits of connecting non-neighboring nodes, and the cost, in effort, to maintain links - including settings where the costs are non-uniform to reflect the increased difficulty in spanning different parts of a hierarchical organization.We find, both through theoretical results and computational experiments, that the equilibrium networks in this model have rich combinatorial structure, and capture qualitative observations arising in the study of structural holes. In particular, even in completely symmetric settings, individuals will differentiate themselves in equilibrium, occupying different social strata and receiving correspondingly different payoffs.

Network design is a fundamental problem for which it is important to understand the effects of strategic behavior. Given a collection of self-interested agents who want to form a network connecting certain endpoints, the set of stable solutions—the Nash equilibria—may look quite different from the centrally enforced optimum. We study the quality of the best Nash equilibrium, and refer to the ratio of its cost to the optimum network cost as the price of stability. The best Nash equilibrium solution has a natural meaning of stability in this context—it is the optimal solution that can be proposed from which no user will defect. We consider the price of stability for network design with respect to one of the most widely studied protocols for network cost allocation, in which the cost of each edge is divided equally between users whose connections make use of it; this fair-division scheme can be derived from the Shapley value and has a number of basic economic motivations. We show that the price of stability for network design with respect to this fair cost allocation is $O(\log k)$, where k is the number of users, and that a good Nash equilibrium can be achieved via best-response dynamics in which users iteratively defect from a starting solution. This establishes that the fair cost allocation protocol is in fact a useful mechanism for inducing strategic behavior to form near-optimal equilibria. We discuss connections to the class of potential games defined by Monderer and Shapley, and extend our results to cases in which users are seeking to balance network design costs with latencies in the constructed network, with stronger results when the network has only delays and no construction costs. We also present bounds on the convergence time of best-response dynamics, and discuss extensions to a weighted game.

In many settings, competing technologies -- for example, operating systems, instant messenger systems, or document formats -- can be seen adopting a limited amount of compatibility with one another; in other words, the difficulty in using multiple technologies is balanced somewhere between the two extremes of impossibility and effortless interoperability. There are a range of reasons why this phenomenon occurs, many of which -- based on legal, social, or business considerations -- seem to defy concise mathematical models. Despite this, we show that the advantages of limited compatibility can arise in a very simple model of diffusion in social networks, thus offering a basic explanation for this phenomenon in purely strategic terms. Our approach builds on work on the diffusion of innovations in the economics literature, which seeks to model how a new technology A might spread through a social network of individuals who are currently users of technology B. We consider several ways of capturing the compatibility of A and B, focusing primarily on a model in which users can choose to adopt A, adopt B, or -- at an extra cost -- adopt both A and B. We characterize how the ability of A to spread depends on both its quality relative to B, and also this additional cost of adopting both, and find some surprising non-monotonicity properties in the dependence on these parameters: in some cases, for one technology to survive the introduction of another, the cost of adopting both technologies must be balanced within a narrow, intermediate range. We also extend the framework to the case of multiple technologies, where we find that a simple model captures the phenomenon of two firms adopting a limited "strategic alliance" to defend against a new, third technology.

In this paper we initiate the study of how collusion alters the quality of solutions obtained in competitive games. The price of anarchy aims to measure the cost of the lack of coordination by comparing the quality of a Nash equilibrium to that of a centrally designed optimal solution. This notion assumes that players act not only selfishly, but also independently. We propose a framework for modeling groups of colluding players, in which members of a coalition cooperate so as to selfishly maximize their collective welfare. Clearly, such coalitions can improve the social welfare of the participants, but they can also harm the welfare of those outside the coalition. One might hope that the improvement for the coalition participants outweighs the negative effects on the others. This would imply that increased cooperation can only improved the overall solution quality of stable outcomes. However, increases in coordination can actually lead to significant decreases in total social welfare. In light of this, we propose the price of collusion as a measure of the possible negative effect of collusion, specifying the factor by which solution quality can deteriorate in the presence of coalitions. We give examples to show that the price of collusion can be arbitrarily high even in convex games. Our main results show that in the context of load-balancing games, the price of collusion depends upon the disparity in market power among the game participants. We show that in some symmetric nonatomic games (where all users have access to the same set of strategies) increased cooperation always improves the solution quality, and in the discrete analogs of such games, the price of collusion is bounded by two.

The success of the Internet is remarkable in light of the decentralized manner in which it is designed and operated. Unlike small scale networks, the Internet is built and controlled by a large number of disperate service providers who are not interested in any global optimization. Instead, providers simply seek to maximize their own profit by charging users for access to their service. Users themselves also behave selfishly, optimizing over price and quality of service. Game theory provides a natural framework for the study of such a situation. However, recent work in this area tends to focus on either the service providers or the network users, but not both. This paper introduces a new model for exploring the interaction of these two elements, in which network managers compete for users via prices and the quality of service provided. We study the extent to which competition between service providers hurts the overall social utility of the system.

Network design is a fundamental problem for which it is important to understand the effects of strategic behavior. Given a collection of self-interested agents who want to form a network connecting certain endpoints, the set of stable solutions - the Nash equilibria - may look quite different from the centrally enforced optimum. We study the quality of the best Nash equilibrium, and refer to the ratio of its cost to the optimum network cost as the price of stability. The best Nash equilibrium solution has a natural meaning of stability in this context - it is the optimal solution that can be proposed from which no user will "defect". We consider the price of stability for network design with respect to one of the most widely-studied protocols for network cost allocation, in which the cost of each edge is divided equally between users whose connections make use of it; this fair-division scheme can be derived from the Shapley value, and has a number of basic economic motivations. We show that the price of stability for network design with respect to this fair cost allocation is O(log k), where k is the number of users, and that a good Nash equilibrium can be achieved via best-response dynamics in which users iteratively defect from a starting solution. This establishes that the fair cost allocation protocol is in fact a useful mechanism for inducing strategic behavior to form near-optimal equilibria. We discuss connections to the class of potential games defined by Monderer and Shapley, and extend our results to cases in which users are seeking to balance network design costs with latencies in the constructed network, with stronger results when the network has only delays and no construction costs. We also present bounds on the convergence time of best-response dynamics, and discuss extensions to a weighted game.

Concurrent with recent theoretical interest in the problem of metric embedding, a growing body of research in the networking community has studied the distance matrix defined by node-to-node latencies in the Internet, resulting in a number of recent approaches that approximately embed this distance matrix into low-dimensional Euclidean space. Here we give algorithms with provable performance guarantees for beacon-based triangulation and embedding. We show that in addition to multiplicative error in the distances, performance guarantees for beacon-based algorithms typically must include a notion of slack - a certain fraction of all distances may be arbitrarily distorted. For metrics of bounded doubling dimension (which have been proposed as a reasonable abstraction of Internet latencies), we show that triangulation-based reconstruction with a constant number of beacons can achieve multiplicative error 1 + /spl delta/ on a 1 - /spl epsiv/ fraction of distances, for arbitrarily small constants /spl delta/ and /spl epsiv/. For this same class of metrics, we give a beacon-based embedding algorithm that achieves constant distortion on a 1 - /spl epsiv/ fraction of distances; this provides some theoretical justification for the success of the recent global network positioning algorithm of Ng and Zhang, and it forms an interesting contrast with lower bounds showing that it is not possible to embed all distances in a doubling metric with constant distortion. We also give results for other classes of metrics, as well as distributed algorithms that require only a sparse set of distances but do not place too much measurement load on any one node.

We introduce a simple network design game that models how independent selfish agents can build or maintain a large network. In our game every agent has a specific connectivity requirement, i.e. each agent has a set of terminals and wants to build a network in which his terminals are connected. Possible edges in the network have costs and each agent's goal is to pay as little as possible. Determining whether or not a Nash equilibrium exists in this game is NP-complete. However, when the goal of each player is to connect a terminal to a common source, we prove that there is a Nash equilibrium as cheap as the optimal network, and give a polynomial time algorithm to find a (1+ε)-approximate Nash equilibrium that does not cost much more. For the general connection game we prove that there is a 3-approximate Nash equilibrium that is as cheap as the optimal network, and give an algorithm to find a (4.65+ε)-approximate Nash equilibrium that does not cost much more.

The authors give the first constant factor approximation algorithm for the facility location problem with nonuniform, hard capacities. Facility location problems have received a great deal of attention in recent years. Approximation algorithms have been developed for many variants. Most of these algorithms are based on linear programming, but the LP techniques developed thus far have been unsuccessful in dealing with hard capacities. A local-search based approximation algorithm (M. Korupolu et al., 1998; F.A. Chudak and D.P. Williamson, 1999) is known for the special case of hard but uniform capacities. We present a local-search heuristic that yields an approximation guarantee of 9 + /spl epsi/ for the case of nonuniform hard capacities. To obtain this result, we introduce new operations that are natural in this context. Our proof is based on network flow techniques.