Alice and Bob play the following game Alice starts by naming

Alice and Bob play the following game: Alice starts by naming an actress A₁. Bob must then name an actor B₁ who has co-appeared in a movie with A₁. Then Alice must name an actress A₂ who co-apparead with B₁, and so on. (Alice must always pick from the set of actresses, and Bob must pick from the set of actors.) The catch is that the players are not allowed to name anyone they have named already. The game ends and a player loses if he/she cannot name an actor/actress who hasn’t been named already.

Suppose we are given as input a set of all “eligible” movies and their cast, and suppose that the total number of actresses is equal to the total number of actors. We can view it as a bipartite graph between actresses and actors, in which there is an edge iff the two have co-appeared in a movie.

(a) Prove that if this graph has a perfect matching, then there exists a winning strategy for Bob. (I.e., no matter how Alice plays, Bob can win.)

(b) Prove the other direction, i.e., if there is no perfect matching, then Alice has a winning strategy.

Solution

A)

If there is a perfect matching, then there exists a winning strategy for Bob. To do so, Bob fixes a perfect matching P. Whenever it is his turn (the current vertex B_x is fixed) Bob selects the unique edge B_xA_x from P such that there is no edge between A_x and any unvisited vertex. Then Bob wins the game.

B)

Alice fixes some maximum matching M. She starts with an unmatched vertex under M. Alice must start by picking a vertex A_y which is unmatched under M. Since there is no perfect matching, such a vertex must exist.

Alice can win if she plays as follows. Let M be a maximum matching. Alice starts with a vertex A_y not covered by the matching. In the sequel, before the game ends, Alice can ensure that A_yB_y is an edge from E\\M (where B_y is covered by M), while B_yA_y+1 is from M. This follows from the fact that if M is maximum, there are no augmenting paths.