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.
Assumption:
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.
Art Sedighi