Monday, June 28, 2010

Accepted papers for SAGT

The web site for SAGT 2010 (3rd Symposium on Algorithm Game Theory) now has the list of 28 accepted papers (and a nice facility to show the abstracts). Lots of interesting topics, especially if you're into equilibrium computation. (30.6.10. Hmm, their link to the papers seems to have disappeared. Here it is.)

Friday, June 11, 2010

Competition for rank

It looks like today's the day that my co-author Carmine Ventre gives a talk at ACM-EC on the paper Ranking Games that Have Competitiveness-based Strategies, our take on competition for rank in league tables. At the same time, news that Liverpool University has gone up 8 places to the 39th place in the Guardian's league table of UK universities feels a bit like the news that BP's share price has gone up by 5% this morning. Historically, the university has performed poorly in the Guardian's league table. Regardless of that, positive progress is always welcome.

As I've sometimes mentioned in talks on the topic, the thing about competition for rank is, that when you start thinking about it, you start to see it absolutely everywhere. The games that we consider in the paper seem to capture a lot of the features of this type of competition, and (so far!) we have positive results, by which I mean polynomial-time algorithms. So what we've got is, a class of games that describe a lot of real-world competitions, but for which Nash equilibria (or at any rate, approximate ones) can be found in polynomial time. Of course, my hope is for more work to appear on this topic.