The Effect of Malice on the Social Optimum in Linear Load Balancing Games

Details The Effect of Malice on the Social Optimum in Linear Load Balancing Games The Effect of Malice on the Social Optimum in Linear Load Balancing Games

2009-10-14

arxiv.org/abs/0910.2655v2

Computer Science

Computer Science and Game Theory

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

The Effect of Malice on the Social Optimum in Linear Load Balancing Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Effect of Malice on the Social Optimum in Linear Load Balancing Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Effect of Malice on the Social Optimum in Linear Load Balancing Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-19466