March 28, 2012 1 Comment
We can assume, as mentioned before, that the users of a Grid are playing a zero-sum game against each other. In that one’s gain is another one’s loss. Or more explicitly, if one user gets more CPU’s, the other[s] get less as a result.
This is fairly easy to prove as we have a set of CPU’s that does not change. In a zero-sum game, there always exists a Nash’s Equilibrium. Finding Nash’s Equilibrium is not easy; in-fact it falls under a calls of problems call PPAD, but we know that one does exist.
Two comments can therefore be made:
1. If we assume that Nash’s Equilibrium is in-fact the standard fairness point, then if the scheduler deviates from NE, it is not a fairshare scheduler. Proving that fairshare is in-fact, not fair.
2. If a user by changing its strategy is able to increase its utility (i.e. get a higher portion of the available resources), then the system is not in Nash’s Equilibrium and the scheduler is not dividing up resources in a fair manner.
and 2.1. The user is inclined to change its strategy so it can get a larger portion of the system. This is where we see “Price of Anarchy” developing.
One assumption we have made throughout is that Nash’s Equilibrium point presents the only fair point at which point all participants are treated fairly.