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).
As we note in the introduction, the focus of the works above were on the effect of malice on the equilibrium of the system: how the equilibrium degrades and how the game between the selfish agents and the malicious agent takes place. On the other hand we are more interested in how the presence of malice affects the social optimum itself. Thus our work complements the works of Karakostas and Viglas @cite_7 and Babaioff @cite_1 .
@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.