In this note we consider the following problem to study the effect of malicious players on the social optimum in load balancing games: Consider two players SOC and MAL controlling (1-f) and f fraction of the flow in a load balancing game. SOC tries to minimize the total cost faced by her players while MAL tries to maximize the same. If the latencies are linear, we show that this 2-player zero-sum game has a pure strategy Nash equilibrium. Moreover, we show that one of the optimal strategies for MAL is to play selfishly: let the f fraction of the flow be sent as when the flow was controlled by infinitesimal players playing selfishly and reaching a Nash equilibrium. This shows that a malicious player cannot cause more harm in this game than a set of selfish agents. We also introduce the notion of Cost of Malice - the ratio of the cost faced by SOC at equilibrium to (1-f)OPT, where OPT is the social optimum minimizing the cost of all the players. In linear load balancing games we bound the cost of malice by (1+f 2).
In the computer science community, there have been a number of studies investigating the effect of malicious agents in congestion games. The first work closest to our setting was by Karakostas and Viglas @cite_7 who study how the presence of malicious agents in a congestion game effects the price of anarchy. That is, how the ratio between the cost of agents in a Nash equilibrium and the social optimum, which the authors call the coordination ratio, change with the amount of malice in the system. More recently, Babaioff @cite_1 consider the malicious agent in the game along with the infinitesimal players and show that for general latency functions, the game need not have a pure Nash equilibrium, and they show the existence of a mixed Nash equilibrium. Moreover, they define the Price of Malice as the rate of deterioration in the total performance of the remaining selfish players per unit flow of malice and show that there exist networks where the price of malice may indeed be negative, while on the other hand there are networks where the price could be quite large.
@cite_1 @cite_7
2124034793 2075488114
We study the equilibria of non-atomic congestion games in which there are two types of players: rational players, who seek to minimize their own delay, and malicious players, who seek to maximize the average delay experienced by the rational players. We study the existence of pure and mixed Nash equilibria for these games, and we seek to quantify the impact of the malicious players on the equilibrium. One counter intuitive phenomenon which we demonstrate is the "windfall of malice": paradoxically, when a myopically malicious player gains control of a fraction of the flow, a fraction of the players change from rational to malicious, the new equilibrium may be more favorable for the remaining rational players than the previous equilibrium. We consider the problem of characterizing user equilibria and optimal solutions for selfish routing in a given network. We extend the known models by considering malicious behavior. While selfish users follow a strategy that minimizes their individual cost, a malicious user will use his flow through the network in an effort to cause the maximum possible damage to the overall cost. We define a generalized model, present characterizations of flows at equilibrium and prove bounds for the ratio of the social cost of a flow at equilibrium over the cost when centralized coordination among users is allowed.