"Consider the following game with n players $\{1, . . . , n\}$. Each player is invited to two parties. All players like to party, but the parties are on the same day, so each player has to decide which of the two parties to attend. Some of the players are enemies. The set of enemies of player i is denoted by $E_i ⊆ \{1, . . . , n\}$. If player $j$ is an enemy of player $i$, player $i$ is also an enemy of player $j$, that is, $j \in E_i \iff i \in E_j$.
Each player wants to minimize the number of enemies that attend the same party as they do. In other words, if $L$ of player $i$’s enemies attend the same party as player $i$, player $i$’s payoff is $−L$."
I'm trying to argue that the game has a pure Nash equilibrium. However, I'm having trouble understanding how the addition of new players, who may have enemies already present at one or both of the parties, can be done without disrupting the choices of those players who've already gone to one of the parties.
Here is a proof that the game has a Nash equilibrium in pure strategies. Suppose we pick an allocation of players to parties that minimizes the total number of enemies at the same party. Such an allocation must exist because the number of possible allocations is finite. Such an allocation will be a Nash equilibrium. If a player could switch from one party to another because he/she has fewer enemies at the other party, then such a switch would also reduce the total number of enemies at the same party. Therefore, if there was such a deviation, that would contradict the assumption that we have picked an allocation of players to parties that minimizes the number of enemies at the same party.