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?
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.