GAMES over

The conference ended today, with the last plenary session being the Shapley Lecture, given by Tim Roughgarden. Followed by one last technical session. Among the technical talks I heard, James Schummer gave a nice presentation on "voting with money" (joint work with Vohra). I guess I like theorems that begin with the statement "Suppose taxation is 100% wasteful."

Afterwards, I had a chat with Lloyd Shapley, originally with a view to finding out some details about the game so long sucker, although in the event quite a lot of other topics were covered, including a fiendishly complicated chess puzzle. (This is Shapley of the classical Gale-Shapley algorithm (1962), for the stable marriage problem, which has been worked on extensively in the CS community, and which we hopefully all teach in our undergraduate classes.)

Here is the chess puzzle; I think it's one that he just took an interest in rather than constructed himself. The question is "can white castle?" More formally, the question is whether there is a sequence of legal moves that lead up to the position shown, such that at this point, white can still castle.

The follow-up question is: if the pawn at F5 was at F6, could white still castle? Which leads me to suspect that the answer is different. For myself, it's tough enough to reconstruct any kind of sequence of moves that lead to these positions, without worrying much about whether it can/cannot be done while allowing white to still be able to castle. (This puzzle seems to be an example of retrograde analysis.)

black
r				k
p		p		p		p	p
	p		p
					P
				P
	P
B		P		P		P	P
R				K
WHITE

White pieces are denoted with capital letters, black with lower-case. K (or k) denotes a king, not a knight (all the knights have been captured). A1 is bottom-left, H1 is bottom-right, and so on.

And finally, this post at Lance Fortnow's blog (as well as some adjacent ones) also is about GAMES 2008; he's the only other one I know of who's been cluttering up the internet with impressions of this conference, so if you're interested, take a look there (if you haven't already been there.)