Defining an optimal protection strategy against viruses, spam propagation, or any other kind of contamination process is an important feature for designing new networks and architectures. In this paper, we consider decentralized optimal protection strategies when a virus is propagating over a network through an SIS epidemic process. We assume that each node in the network can fully protect itself from infection at a constant cost, or the node can use recovery software, once it is infected. We model our system using a game-theoretic framework and find pure, mixed equilibria, and the Price of Anarchy in several network topologies. Further, we propose a decentralized algorithm and an iterative procedure to compute a pure equilibrium in the general case of a multiple communities network. Finally, we evaluate the algorithms and give numerical illustrations of all our results.
Game theoretical studies for network problems have been conducted, in routing @cite_34 @cite_50 , network flow @cite_6 , workload on the cloud @cite_2 or optimal network design @cite_16 @cite_4 , employing standard game-theoretic concepts @cite_33 @cite_10 such as pure Nash or mixed equilibrium. The Price of Anarchy (PoA) @cite_5 @cite_10 is often used as an equilibrium performance evaluation metric.
@cite_4 @cite_33 @cite_34 @cite_6 @cite_50 @cite_2 @cite_5 @cite_16 @cite_10
1987511126 2113692632 2156816884 2155361616 2094330223 2009106897 2112269231
The effect of virus spreading in a telecommunication network, where a certain curing strategy is deployed, can be captured by epidemic models. In the N-intertwined model proposed and studied in [1], [2], the probability of each node to be infected depends on the curing and infection rate of its neighbors. In this paper, we consider the case where all infection rates are equal and different values of curing rates can be deployed within a given budget, in order to minimize the overall infection of the network. We investigate this difficult optimization together with a related problem where the curing budget must be minimized within a given level of network infection. Some properties of these problems are derived and several solution algorithms are proposed. These algorithms are compared on two real world network instances, while Erdos-Renyi graphs and some special graphs such as the cycle, the star, the wheel and the complete bipartite graph are also addressed. The authors consider a communication network shared by several selfish users. Each user seeks to optimize its own performance by controlling the routing of its given flow demand, giving rise to a noncooperative game. They investigate the Nash equilibrium of such systems. For a two-node multiple links system, uniqueness of the Nash equilibrium is proven under reasonable convexity conditions. It is shown that this Nash equilibrium point possesses interesting monotonicity properties. For general networks, these convexity conditions are not sufficient for guaranteeing uniqueness, and a counterexample is presented. Nonetheless, uniqueness of the Nash equilibrium for general topologies is established under various assumptions. > The existence of Nash equilibria in noncooperative flow control in a general product-form network shared by K users is investigated. The performance objective of each user is to maximize its average throughput subject to an upper bound on its average time-delay. Previous attempts to study existence of equilibria for this flow control model were not successful, partly because the time-delay constraints couple the strategy spaces of the individual users in a way that does not allow the application of standard equilibrium existence theorems from the game theory literature. To overcome this difficulty, a more general approach to study the existence of Nash equilibria for decentralized control schemes is introduced. This approach is based on directly proving the existence of a fixed point of the best reply correspondence of the underlying game. For the investigated flow control model, the best reply correspondence is shown to be a function, implicitly defined by means of K interdependent linear programs. Employing an appropriate definition for continuity of the set of optimal solutions of parameterized linear programs, it is shown that, under appropriate conditions, the best reply function is continuous. Brouwer's theorem implies, then, that the best reply function has a fixed point. We study a class of noncooperative general topology networks shared by N users. Each user has a given flow which it has to ship from a source to a destination. We consider a class of polynomial link cost functions, adopted originally in the context of road traffic modeling, and show that these costs have appealing properties that lead to predictable and efficient network flows. In particular, we show that the Nash equilibrium is unique, and is moreover efficient, i.e., it coincides with the solution of a corresponding global optimization problem with a single user. These properties make the cost structure attractive for traffic regulation and link pricing in telecommunication networks. We finally discuss the computation of the equilibrium in the special case of the affine cost structure for a topology of parallel links. Cloud computing is an emerging paradigm in which tasks are assigned to a combination (“cloud”) of servers and devices, accessed over a network. Typically, the cloud constitutes an additional means of computation and a user can perform workload factoring, i.e., split its load between the cloud and its other resources. Based on empirical data, we demonstrate that there is an intrinsic relation between the “benefit” that a user perceives from the cloud and the usage pattern followed by other users. This gives rise to a non-cooperative game, which we model and investigate. We show that the considered game admits a Nash equilibrium. Moreover, we show that this equilibrium is unique. We investigate the “price of anarchy” of the game and show that, while in some cases of interest the Nash equilibrium coincides with a social optimum, in other cases the gap can be arbitrarily large. We show that, somewhat counter-intuitively, exercising admission control to the cloud may deteriorate its performance. Furthermore, we demonstrate that certain (heavy) users may “scare off” other, potentially large, communities of users. Accordingly, we propose a resource allocation scheme that addresses this problem and opens the cloud to a wide range of user types. We study the performance of noncooperative networks in light of three major topology design considerations, namely the price of establishing a link, path delay, and path proneness to congestion, the latter being modeled through the "relaying extent" of the nodes. We analyze these considerations and the tradeoffs between them from a game-theoretic perspective, where each network element attempts to optimize its individual performance. We show that for all considered cases but one, the existence of a Nash equilibrium point is guaranteed. For the latter case, we indicate, by simulations, that practical scenarios tend to admit a Nash equilibrium. In addition, we demonstrate that the price of anarchy, i.e., the performance penalty incurred by noncooperative behavior, may be prohibitively large; yet, we also show that such games usually admit at least one Nash equilibrium that is system-wide optimal, i.e., their price of stability is 1. This finding suggests that a major improvement can be achieved by providing a central ("social") agent with the ability to impose the initial configuration on the system. We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given its congestion; the objective is to route traffic such that the sum of all travel times---the total latency---is minimized.In many settings, it may be expensive or impossible to regulate network traffic so as to implement an optimal assignment of routes. In the absence of regulation by some central authority, we assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general such a "selfishly motivated" assignment of traffic to paths will not minimize the total latency; hence, this lack of regulation carries the cost of decreased network performance.In this article, we quantify the degradation in network performance due to unregulated traffic. We prove that if the latency of each edge is a linear function of its congestion, then the total latency of the routes chosen by selfish network users is at most 4 3 times the minimum possible total latency (subject to the condition that all traffic must be routed). We also consider the more general setting in which edge latency functions are assumed only to be continuous and nondecreasing in the edge congestion. Here, the total latency of the routes chosen by unregulated selfish network users may be arbitrarily larger than the minimum possible total latency; however, we prove that it is no more than the total latency incurred by optimally routing twice as much traffic.