The deadlock only arises in a very specific circumstance. Let's work with the stage list in the document, Battlefield/FD/Yoshi's/Prism Tower/Tomodachi/Ferox/Brinstar.
Player 1 | Player 2
Battlefield | FD
FD | Battlefield
Yoshi's | Ferox
Ferox | Yoshi's
Prism Tower | Tomodachi
It's impossible to objectively decide between Battlefield and FD even though they're both the top 2 choices for both players Likewise for Yoshi's and Ferox. This is the deadlock. And the last entry is no help because they're unique to their respective lists.
The solution is to have the players add the rest of the stages to their list, using the same method. I haven't done a rigorous proof, but I suspect that there is always a non-deadlock solution if you include all stages in the list given that there is an odd number of stages total.
TL;DR It only deadlocks when both lists mirror each other such that for each pair of stages in one list, the same pair appears in reverse for the other list in the exact same spots, and the remaining slot in each list does not match at all.