Unrelated parallel machine scheduling game

The following game can be described as a sort of network congestion game (but it is not a congestion game in the usual sense) or as a scheduling game. We are given n players, each represents a job. There are m unrelated parallel machines. Unrelated means that there is an n*m matrix indicating the processing time of job j if executed on machine i. Each player has to choose the machine on which it wants to execute, this is the set of strategies available to each player. The load of a machine is then the total processing time over all jobs assigned to that machine. The payoff for every player is then the negative of the load of the machine to which it is assigned. Of course a player wants to be scheduled on the least loaded machine. So we say that a player is happy if he cannot improve its payoff by choosing a different machine. We want to find an assignment where all players are happy. This is called a pure Nash equilibria in game theory.

The following observation has been published in (Convergence Time to Nash Equilibria, Eyal Even-Dar, Alex Kesselman, Yishay Mansour, ICALP 2003). A simple potential function argument shows that there is always a pure Nash equilibria for this game: The multiset of m machine loads decreases lexicographically strictly whenever a player improves its payoff. Formaly we say that S is lexicographically smaller than S' (for |S|=|S'|) if either max S< max S' or max S=max S' and S\{max S} is lexicographically smaller than S'\{max S'}. The open problem now is whether such a pure Nash equilibria can be found in polynomial time or not.

For the special case of m=2 machines, the problem is easy.


The colored cell in each row indicates which machine the player uses. It is red if the player is unhappy and otherwise it is green. Click on the matrix entry to assign a player to a different machine and try to make all entries green.

Initialize with the following values :