Two players are playing a game on a bipartite graph where all of the edges are nim-heaps of various sizes. A token starts on one of the vertices, and on your turn you must move the token over an edge and pick up some of the matchsticks in the nim heap corresponding to that edge. If all of the edges meeting the vertex containing the vertex are empty when you start your turn, you lose.
Is there a polynomial time algorithm to decide this game?
I am interested in a multiplayer combinatorial game played as follows: between every pair of people sits a combinatorial game. One player starts with a "hot potato" token. Whoever has the token must make a move on one of the games incident to him to pass the token to the other player playing that game. If he can't make a move in any of the games adjacent to him, he loses and everybody else wins.
Since multiplayer games are hard to analyze, we can simplify the problem by splitting the players into two teams, where each team wants the potato to end up in the hands of the other team. To simplify the game further, we might also assume that no two players on the same team have a game between them. Even then, if all of the games are numbers then this problem is directed bipartite geography which I'm pretty sure is PSPACE-complete, so I'm assuming all of the games are impartial as well.
If all of the nim-heaps have size one or zero, though, then this problem becomes undirected bipartite geography, which can be solved in polynomial time, so I strongly suspect that bipartite nim-geography should have a polynomial time solution as well.