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.

Day of Reckoning

Stress, like the common cold, is infectious, and there's a lot of both going about in the UK academic community over the past couple of weeks. In one case it's due to the weather, in the other it's due to the Research Assessment Exercise for which the results become known today. If you work in a British university, it's no good claiming you're not interested - that would be like the chap who tried to stand in the corner for 5 minutes without thinking about polar bears. The Wikipedia entry for the RAE provides a brief description. The results get released to universities today, according to a surprisingly detailed timetable, and then they get properly published tomorrow. I won't do any further discussion here - one thing we can all count on is a lengthy episode where the statistics will be endlessly sliced and diced, and viewed from this angle or that one, and subjected to assorted criticisms (the Times Higher will be the best place to read that stuff, if you care.)

Too much pressure to complete PhDs quickly?

Last week's Times Higher featured an article "Doctor, doctor, quick, quick" highlighted on the front page, in addition to an editorial "British doctorates in the dock". These articles question the UK's approach of trying to get PhDs by age 24 or 25 (3 years undergraduate study, then 3 years of PhD).

I guess every country's higher education system generates pet peeves amongst its users -- I've come across various complaints about the Italian one recently -- but I reckon that at least within most of Computer Science, the above is a genuine problem, mainly because the result is that our PhDs struggle to compete in a tough international job market. No need for me to rant about it though - I can just direct the reader to "British doctorates in the dock".

From the articles linked-to above, I learned about Vitae, which aims to promote an emphasis on rather generic skills training, at the expense of technical subject-based skills. The web site has lots of on-line advice to PhD students and postdocs about career development, but does not emphasise nearly enough the importance of publication. Their News page is, I think, quite a useful resource.

Finally, unrelated, another rant-by-proxy, I recommend Sleepwalking into a Police State, at Willem Buiter's blog. This blog is mainly heavy-duty economic commentary, but this post has Buiter wearing his academic cap, and commenting on pressure on universities to monitor the attendance of overseas students at seminars, and report them to the Borders Agency if they are not attending.

problem about coalition formation

Our local networks went down this morning and I started thinking about cake-cutting. Didn't get very far, but on the way, came up with the following question.

Given n players, and a binary game tree, each of whose leaves is labelled with one of the players, who is deemed to be the winner if that leaf is the outcome of the game. Each node of the tree is also labelled with a player, with the understanding that if that node is reached during the game, the that player gets to choose one of the two subtrees.

Question: how hard is it to find the smallest coalition that has the property that they can ensure that one of their members ends up winning? (There are two versions of this question: you can require them to nominate a winner in advance, or you could just require that the winner is one of them, but precisely who, depends on the behaviour of the non-members of the coalition.)

Comment: Let's focus on the second of the above versions. In that case, there are many winning coalitions of size n/2. Why? You can partition the players into 2 subsets (opposing teams that play against each other), then treat each subset as a single player, resulting in a 2-player version. You can find out which of those two "players" can win, in a bottom-up fashion. So, if the subsets are the same size, you end up finding a subset consisting of half the players, that can win.

Another question: leaving aside computational issues, should it always be possible to find winning coalitions of size less than n/2? Probably not.

Disclaimer: I don't know if this is a new problem, it could may have been worked on already.