New academic year

My first lecture was at 9am today. Welcome to new lecturers Rahul Savani and Martin Gairing who join our Economics and Computation research group, from the University of Warwick and UC Berkeley, respectively. In the coming year we will be looking to appoint three new permanent faculty members to this research group; watch this space if you think you might be interested.

No time to raise tuition fees

As Gordon Brown's spending spree judders to a halt, the diners at the UK's economic table look at each other uneasily, as the time approaches for someone to pick up the bill. Enter the Confederation of British Industry, with a modest proposal to raise tuition fees from university students.

You've got to admire their chutzpah. Over the past decade, business leaders have been regularly enjoying double-digit pay increases. Meanwhile, the one single aspect where the present government has actually saved money, and not spent more of it, is on student finance. Specifically, they stopped paying for students' tuition, and now expect them to borrow the cash instead. Admittedly, the government lends it to them, at low interest rates.

That's not good enough for the CBI however. They've awarded themselves the above-mentioned pay increases on a regular basis, and only received a pusillanimous, relatively recent, 10% tax increase on incomes over 150k. So what we now have is a bunch of fat cat business leaders telling a bunch of penniless students to pick up the bill for Gordon Brown's uncontrollable spending habit. It's blindingly obvious that taxes will have to go up -- my own as well as the CBI's. You don't have to be an economist (or perhaps you do have to be non-economist) to figure that out.

Homotopy methods for Nash equilibrium computation

In computational game theory, we prefer fast algorithms to slow ones, but we also prefer algorithms that seem "natural", capable of being carried out in the real world. This is perhaps a special feature of computational game theory (in comparison with most other areas of algorithmics) - we do not just want a solution, but the solution should represent something that happens "out there". (This recent blog post by Vohra makes the stronger claim that if a game-theory problem is polynomially solvable, there is usually a natural algorithm for it.)

Homotopy methods are based on a simple and appealing idea - given some game of interest, you start by constructing a version of that game where the numbers involved (that is, the payoffs associated with the various strategy combinations) have been changed so that there is a single "obvious" solution. (And let us assume that it is Nash equilibrium that we are interested in.) Then you gradually move all the numbers towards the ones that represent the game of interest, keeping track of this Nash equilibrium, which should change continuously.

The "starting" game (i.e. the one with the obvious, easy-to-find Nash equilibrium) can perhaps be assumed to represent some kind of prior belief by the players about what each other are doing, or what is the best action in the absence of knowledge about the other players. In that case, the above process seems to represent some kind of natural learning process that you can believe might actually happen. What we get in addition is a criterion for equilibrium selection --- we would like to believe that there really is a single correct answer to the question of "what is the outcome of this game?" and where there are multiple Nash equilibria, this kind of procedure usually identifies just one of them.

Browder's Fixpoint Theorem

Browder's fixpoint theorem -- not to be confused with Brouwer's fixpoint theorem -- can be used to show that such a path of Nash equilibria actually exists. The theorem says the following. Suppose you have a compact domain X, so that Brouwer's (not Browder's) fixpoint theorem promises that any continuous function from X to X has a fixpoint. Suppose that for each t in [0,1], f_t is a continuous function from X to X. Furthermore, the functions f_t are actually a continuum of continuous functions; if u converges to w then f_u converges to f_w. Then there is a path connecting some fixpoint of f₀ with a fixpoint of f₁. But, it should be noted that the path need not be monotonic as a function of t. In the context of games, it is easy to construct 2-player 2-action games where you have to backtrack in moving from one to the other.

Some literature

I recently read the following 2 papers in some detail, so far have probably just scratched the surface. The first paper (in Economic Theory, 2009) listed below gives a survey of different methods and how they work. It includes a nice explanation of how the Lemke-Howson algorithm can be seen to be a homotopy method.

The second paper (in GEB, 2002) addresses computation of approximate Nash equilibria for multiplayer games. It uses the notion of ε-Nash equilibria that some of us in the CS community worked with more recently. Recall that for multiplayer games, one needs to give up on exact NE in general, since they may require irrational numbers to specify them. (For 3+ players, a NE may need to be the solutions of a high-order polynomial.) Given a homotopy between multiplayer games, they first partition the space into simplices, then approximate the payoffs within each simplex by linearly interpolating between its vertices (i.e you evaluate the true payoffs at the vertices, but inside a simplex the approximate payoffs are allowed to differ from the correct ones). Having discretised the space in this way, the algorithm implicitly constructs a graph on simplices and sub-simplices, of degree at most 2, whose degree-1 vertices are approximate equilibria of the games at the extremes of the homotopy. So, to get from the NE of the "starting game" to the game of interest, you follow this path. I haven't understood the details yet; not even sure if the graph is directed like in PPAD problems.

The paper does not apply Browder's theorem, but Browder's theorem essentially follows from the construction of the graph, at least in the context of approximations to multiplayer games.

Homotopy methods to compute equilibria in game theory by Herings and Peeters

Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games by Herings and van den Elzen

Competitive journals

I just got an email circular to "Editors and Reviewers of Games and Economic Behavior" (I am just a humble reviewer, not an editor). It noted that last year it received over 500 submissions and anticipates publishing under 80 papers per year. Two points raised were: Please raise the bar (only accept papers of broad interest) and Faster publication - each new issue to contain about one-third of the papers in the current publication queue.

In the context of recent discussions about whether CS journals can, or ought, to be more competitive than conferences, these points look like good ones to bear in mind for journals that want to be competitive. (Of course, it's fun to stereotype people and research areas, and say that it's appropriate that a game theory journal should have figured that out. But, most other research areas also have the feature that the top journals are what are important.)