GAMES 2010

The games-for-verification crowd seems to be a different community from those of us who do algorithmic game theory (coming from economics). The topic is not covered in the textbook (fair enough I suppose, the book is big enough already). I dropped in on them to give a tutorial Nash equilibria and computational complexity, at the meeting GAMES 2010, the annual Workshop of the ESF Networking Programme on Games for Design and Verification. I got the impression that France and Poland are well-represented in that community, although that may just be an artifact of the composition of the network.

They have the main open problem of: what is the complexity of solving parity games? (Google: did you mean party games?) Parity games are known to be in both NP and co-NP, also known to be mildly subexponential (Zwick and Paterson), so believed to be in P. Currently there are no proposed algorithms that are conjectured to do the job; apparently there used to be one, but it was recently shown to be exponential in the worst case, for an artificial class of examples. The parity games problem is derived from the problem of checking whether a formula in modal mu-calculus is satisfied by a given Buchi automaton, and I gather that is a poly-time reduction. There is also an exponential-time reduction if instead the formula is in monadic second-order logic. However, the work on parity games seems to take on a life of its own, without the need to refer to model-checking. So for example, I am not sure that the question of finding a mixed equilibrium for a parity game relates to solving a model-checking problem, but it's an interesting topic.

cap on non-EU migrants

I got an email a few days ago that was circulated to all staff, notifying us that all of a sudden, the university will only be able to employ a very small number of people from outside the EU. It applies to all universities, see this article. It's a big problem for universities that deserves wider attention, but as yet I haven't seen it discussed in the Times Higher. The article linked-to above quotes the chief executive of Universities UK who spells out the problem clearly:

The proposed cap will be difficult for universities as a significant proportion of the academic workforce is, and always has been, international. In the UK, over 10 per cent of all our academic staff are non-EU nationals and many are working in key subject areas such as science, technology and engineering.

...

The success of the UK’s higher education sector depends on our ability to attract the most highly talented people to work and study here. Anything that diminishes our ability to do this will undermine the quality of what we do and our ability to compete internationally.

This lamentably crude approach to reducing immigration to the UK does not make one optimistic that they will come up with a more sensible way to regulate overseas students. If they end up choking off the flow of overseas students, that would be complete catastrophe (a short-term one; the impact on staff hiring is a long-term one).