Winning strategy for a given game on graphs

Question

The game goes as follows. Two players are playing a game, player 1 and player 2, in which the first player starts by naming a hero $h_1$, then player 2 responds with a villain $v_1$ who has played in a movie with $h_1$. Then player 1 responds with another hero $h_2$ who has played in a movie together with $v_1$, and so forth. Each hero and villain can be used at most once. The first player that can not name any character (available heroes/villains do not have a common film with the last choice of the other player), loses the game. Player 1 always starts the game.

The input is a set of heroes $H$, a set of villains $V$ ($|H| = |V| \geq 1$) and a family of movies $M$, where each movie is a set of heroes and villains who appeared in that movie.

The question is: Can you, based on $H$, $V$ and $M$, decide which player wins the game assuming both players are playing optimally?

---

Example:

Given the following data: the heroes are Iron Man, Captain America, Thor and Spider-Man. The villains are Whiplash, Ultron, Thanos and Vulture. The movies are Avengers: Infinity War (stars Iron Man, Captain America, Thor, Thanos and Spider-Man) and Spider-Man: Homecoming (stars Iron Man, Vulture and Spider-Man). Can you decide which player has the winning strategy?

---

My approach is to use maximum bipartite matching to find out which player has the winning strategy, because we can split the data in two sets, namely $H$ and $V$ and have relations between those two sets. The Hopcroft-Karp algorithm can take two of such sets and find out the maximum cardinality. Please correct me if I'm wrong: in the cases in which there is a perfect matching, player 2 wins and otherwise player 1 wins. Whenever there is a perfect matching, it means that player 2 has always had an answers to the hero that player 1 named.

How would you solve this? Is there a better, more efficient solution than some maximum bipartite matching.

Answer 1

The short answer is, Player two wins if and only if the corresponding graph admits a matching that "covers" the set $H$.

---

Here is a bit of explanation.

Your idea is almost right. However, the proof is not intuitive and you might miss some details which you need if it is a theoretical question or if you need to design the exact winning strategy and not only output the winning player.

So let us start with the part missing from your answer. Assume a given instance corresponds to a graph that admits a perfect matching. According to your strategy, Player 2 wins in this case which is right. Now assume the same instance is given with one more villain, or ten more villains or one thousand of them. Clearly, player two still wins since adding villains, regardless to how we assign them, only helps the second player. So your claim does not always hold. However, your answer is very close to my claim and have the same intuition. It is only missing a bit of formality.

Claim. Assuming both players are playing optimally, Player 1 wins if and only if, given an instance $I$, the corresponding graph does not admit a matching saturating the set $H$.

So what does that mean? A matching saturates a set of vertices $S$, if each vertex in $S$ is incident to a vertex in the matching. Now we prove the claim. We show two winning strategies one for Player two when the graph admits a matching the saturates the set $H$ and one for Player two when the graph does not admit such a matching.

Proof. Now assume the graph admits such a matching. Let this matching be $M$. The strategy goes as follows. As long as Player one did not lose, for each choice $h \in H$ for Player one, choose $v \in V$ the vertex matched to $h$ in $M$.

The correctness follows directly from the fact that each vertex of Player two is unique and adjacent to the choice of Player one (due the properties of a matching). Intuitively, Player one will run out of moves at some point (possibly after choosing all heroes in the set $H$).

Now assuming the graph does not admit a matching saturating $H$, according to Hall's theorem, there is a subset $A \subseteq H$, such that $|N(A)| < A$. Choose such a set that is minimal inclusion-wise. We claim that there is a matching $M'$ that saturates $N(A)$. Assuming otherwise, again due to Hall, there is a subset $S \subseteq N(A)$ such that $|N(S)| < S$, but then removing $N(S) \cap A$ from $A$ and $S$ from $N(A)$ yields a subset of $A$ that also contradicts Hall's condition which forms a contradiction to the choice of $A$ to be minimal. Hence, there is a matching $M'$ that saturates $N(A)$.

Now the strategy goes as follow. Choose a vertex in $A$ that is not incident to any edge in $M$. Such a vertex exists since $|N(A)| < |A|$. Choose this vertex at first and for each choice $v \in V$ of player two, choose the vertex $h \in H$ matched to $v$ in $M'$.

Again, it is easy to see that Player two will run out of moves at some point (possibly after choosing all vertices in $N(A)$) and hence, Player one wins.