Some combinatorial games

For some fun over the holiday season, why not try to figure out the complexity of winner detemination for the following games. I do not know if they have been considered before; I searched around a bit on the internet without finding them.

The first one is a generalization of a simplified version of the Yu-Gi-Oh! Trading Card Game. There are two players, each of whom has a set of cards, and each card has an "attack value" and a "defense value". All cards can be seen by both players. Players take turns, and when it's your turn, you select one of your own cards, and one of the opponent's cards such that the opponent's card's defense value is less than your card's attack value. That opponent's card is removed. If you cannot do this, you must "pass". Of course, you win if you can end up removing all your opponent's cards.

Here's a more general, abstract version. The game begins with a directed graph, and each vertex is labeled 1 or 2 (depending on which player the vertex belongs to). The meaning of an edge from vertex v to vertex w is: "vertex v can destroy vertex w". When it's your turn, you select an edge from one of your own vertices to one of the opponent's, and use it to destroy that opponent vertex. As before, you win if all opponent vertices get removed.

This graph based game is strictly more general that the previous game, in that not all graphs can be expressed using the "numbered cards" game. I suspect that it is PSPACE-complete, like generalized geography.

Here's another version that raises the level of mathematical abstraction just a little more. Combinatorial game theorists seem to like impartial games, and the following is an obvious impartial version of the previous version. Begin with a directed graph, this time with no labels on the vertices. Players take turns to select edges, and when an edge is selected, the "downstream" vertex is removed (along with all its other edges, of course). The player who removes the last remaining edge, wins. In contrast with the previous games, notice that in this version, one or other player must eventally win; there is no possibility of a draw.