Thursday, December 18, 2008

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.

Tuesday, December 16, 2008

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.)

Wednesday, December 10, 2008

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.

Thursday, December 04, 2008

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.

Friday, November 28, 2008

Pattarawit Polpinit PhD defense

Congratulations to my PhD student Pattarawit Polpinit, who today successfully completed his PhD defense, and passes subject to the usual minor modifications. The title of the thesis is "The Computation of Equilibria in Congestion Networks". Piotr Krysta was internal examiner, Tom Friedetzky was external.

Thursday, November 06, 2008

A fun partisan statistic

This article at the BBC news web site points out that stock markets do better under Democratic administrations than Republican ones. While it seems like the evidence for this is genuine, the following observation (taken from the article) probably pushes it too far:

"Indeed, a recent study published in the New York Times showed that $10,000 (£6,263) invested in the S&P 500 in 1929 would have grown to $11,733 if invested under Republican presidents, but to $300,671 under Democratic presidents."

It sounds like a fun fact to point out to a US voter with a defined-contribution pension scheme. But, I note that it was Republican president Herbert Hoover who presided over the 1929-33 Depression, so perhaps the Democrats had a bit of a headstart in this race. (Meanwhile, share prices right now are still doing badly. But I guess Obama hasn't been sworn in just yet.)

Wednesday, November 05, 2008

US election result

It is known (see this article) that foreigners (to the USA) strongly preferred Obama to McCain. Also, plenty of anecdotal evidence suggests that academics generally strongly prefer Obama. Being a non-USA academic, it should come as no surprise that I too was backing the winner.

A purist might note that the above conclusion makes some sort of statistical assumption along the lines of "naive Bayes" that two distinct indicators for an outcome should independently add to our belief in that outcome. And as it happens, that's a good observation in this case -- for foreign academics there is a potential downside to the Obama victory.

The problem is easy to state. The academic marketplace, both for students and faculty, has become increasingly globalised. And in the world's leading English-speaking nation, the conditions look much improved for it to become a magnet for students and staff alike. When it comes to recruiting overseas students, and retaining staff, the UK and Australia have maybe had a relatively easy ride over the last few years.

Still, I supported Obama anyway, and here is the "professional" reason. Few academics can afford to turn their backs on the USA. And the USA, with its dominance of the algorithms and computational complexity scene, is extra important to those of us in that field. The European algorithms community is better-off for having their American counterparts in a nation that is willing to work with and cooperate with the rest of the world.

Monday, November 03, 2008

Peer review survey

Here is a link to an online survey being conducted by EPSRC, soliciting feedback on their peer review process, used for research grant proposals. Dissatisfied as I am with this process, I felt the urge to contribute. (The survey's closing date is November 7th.)

The general problem with their procedure for peer review, is that it is very primitive, in comparison with the process by which conference submissions are reviewed. You send in a grant application, you get 3 or 4 reviews, you get to submit a response, and these get considered by the panel. A specific problem with this is the shortage of interaction amongst the parties. Suppose that two reviewers think the proposal is excellent, and another thinks it's rubbish. The correct thing to do, surely, is to get the reviewers to settle their differences via a discussion, and preferably solicit another review. This is exactly what program committees do when papers are selected for conferences. In some conferences that I have been involved with, the authors of a submitted paper make a response to the reviews, the reviewers then continue their discussion in the light of the author's response. The whole thing is much more interactive, and helps to ensure transparency and accountability.

Given that it is more significant to get a research grant than to publish a paper (both for the grant applicant/author, and for the taxpayer) it is bizarre in the extreme that EPSRC still uses such a primitive system. There is a case for still more effort being directed towards ensuring that good choices are made. For example, perhaps research grant applicants should be interviewed by the panel (however, suggestions like that go beyond the scope of the above mentioned survey).

Wednesday, October 22, 2008

CACM 51(10)

In the latest CACM, this article caught my eye, since I have in the past played Go competitively, and tried my hand at Go programming. The article reports that the Go-playing program Titan defeated a human expert, Titan having been given a 9-stone advantage. (An earlier press release is here. This report gives more details, and has a link to the game itself in SGF format. Mick's computer go page keeps track of events like this, and gave me the previous link.)

On the one hand, I like to hope that Go engages the human brain in mysterious ways, so that programs will never catch up with human experts. On the other hand, I suspect that Go will go the same way as chess, and computer programs will eventually win. It is reasonable to hope that will need more emphasis on smart algorithms than on raw computing power. But, regarding the prediction in the article, my guess is that programs won't beat human experts by 2020.

Elsewhere in this CACM, is an article my my former colleague at Warwick, Martin Campbell-Kelly, on the history and future of open source software.

Unrelated: this article in the latest Times Higher is about UK academic blogs, but this blog doesn't get a mention :-(

Tuesday, October 14, 2008

why LaTeX is like Latin

I got my graduate student to stop sending me documents in MS Word, and start using LaTeX, but my objection to Word didn't get to the heart of the problem. Of course, mathematical expressions look bad in a Word document, and the typesetting in generally worse in other respects, but it would be wrong to focus solely on appearance.

The rationale for LaTeX is analogous to a common cliché about the use of Latin, which is that Latin supposedly lets one express things very precisely. One thinks of old-fashioned lawyers making that observation to justify their use of Latin tags, although I don't know enough Latin to say whether that is valid. But, in the context of mathematics and science, MS Word provides a kind of license for sloppiness that is denied by LaTeX. Symbols, especially when the have superscripts, primes, and similar embellishments, do not get a consistent appearance in Word. Extra space amy appear before a superscript, or sometimes the font size changes, because the author doesn't have enough control. In LaTeX, any symbol has a corresponding sequence of ASCII characters in the source file, and there is no ambiguity about whether two symbols are the same, or different. Furthermore, features like the "theorem" and "proof" environments force us to state our theorems and proofs in a self-contained way, rather than having discursive paragraphs that segue vaguely into something that could possibly be interpreted as a theorem statement.

LaTeX, like Latin, does not prevent one from writing down a statement that is incorrect. (A widely cited example is "Dulce et decorum est pro patria mori.") But it does help to prevent vagueness.

Monday, October 06, 2008

Time for smugness?

In the movie Mary Poppins, there is a scene where the admiral asks Mr. Banks how things are in the banking industry, and his smug reply goes something like "credit has never been stronger, and the British pound is the envy of the world!"

After a quick perusal of other blogs that I occasionally read, I find little evidence that the academic community thinks anything to the contrary. This reference to the banking crisis is a rather tangential one, this link from Mitzenmacher's blog. (Conclusion: if you have tenure, sit back and enjoy as the rest of the world crumbles.) This post at Luca Aceto's blog briefly refers to financial turmoil, towards the end. (A blog based in Iceland seemed like a good place to search for comments on this topic.) (Added 15.10.08: this post at the Fortnow/Gasarch blog now addresses the topic.)

Articles here and here tell a pessimistic story, focussing on the increase in pay costs faced by UK universities, due to the increase in inflation. But the banking crisis itself is more likely to impact on the Universities Superannuation Scheme.

Like other private-sector pension schemes -- indeed, like its US counterpart TIAA-CREF -- the USS is underpinned by its stock market investments, and recent declines in share prices have opened up a hole in its finances. Plainly, the right thing to do is for USS to raise the contribution level from staff. Tenure or not, this amounts to an effective pay cut, but the only alternatives are a sudden major recovery of the stock market (unlikely), or a decline in academic life expectancy (hopefully also unlikely). (Note: the situation is different for TIAA-CREF, which is a defined-contribution scheme. For that, the value of your pension goes up and down with the stock market, and it's up to the individual to decide how much more they need to contribute to it.)

I recommend Robert Peston's blog for insightful commentary on the economy.

Wednesday, October 01, 2008

WINE 2008 papers

As a member of the WINE 2008 program committee, I hereby exercise my right to advertise on my blog, the list of accepted papers. If I appear to be "late with the news", my excuse is that I was waiting for the list of short papers to appear, not just the list of long papers. For your inconvenience, both lists seem to appear as Excel spreadsheets, doubly annoying if, like me, you previously made the mistake of installing the odious Office 2007 in place of the slightly more benign Office 2003.

Moving from presentation to content, I see an continued emphasis on non-cooperative games, and in particular, congestion games on networks is still going strong. There's a bit of social choice theory, like "Anonymity-Proof Voting Rules" by Vincent Conitzer, and "Frequent manipulability of Elections: The Case of Two Voters" by Shahar Dobzinski and Ariel Procaccia. I do not count "Biased Voting and the Democratic Primary Problem" (by Kearns and Tan) in this set, since there the emphasis is more on information diffusion in networks, than on properties of voting rules. There are one of two papers on cooperative games, but not many. (e.g. "Overlapping Coalition Formation" by Chalkiadakis, Elkind, Markakis and Jennings.)

On a completely different topic, it nice to read about Richard Stallman having a go at "cloud computing". His complaint, that it's a mechanism to suck users into locked, proprietary systems, looks entirely valid. Also from the article: His comments echo those made last week by Larry Ellison, the founder of Oracle, who criticised the rash of cloud computing announcements as "fashion-driven" and "complete gibberish". Indeed. I would personally criticise the phrase "cloud computing" itself; and note that any intended metaphor is misleading.

Monday, September 29, 2008

start of term

Time to commemorate my first lecture with a blog entry. (year 2 module: "decision, computational and language"). My Monday at 9am slot makes it the "welcome back" lecture, likely to be better-attended than most of its successors...

From meeting my tutees last week, and a few others at a reception for new students, I got the idea that our students are coming for farther afield than last year. This year we have the first cohort of XJTLU students, but I'm actually making that observation about UK/EU students. I may be wrong; my sample is admittedly too small to be statistically significant.

If it's true however, that is an important asset for Liverpool generally. In order to prosper, a city the size of Liverpool has to provide goods and services that go beyond its immediate region, and preferably beyond the UK. My impression is that Liverpool still does not have enough employers that achieve that objective.

(Unrelated: Here is a sensible take on the forthcoming vice-presidential debate.)

Friday, September 19, 2008

Mathematics: understanding the score

A new report by Ofsted, Mathematics: understanding the score criticises school maths lessons for being dull, uninspiritional, and "teaching to the test". The report, which received some good coverage on the radio this morning, is also reported here.

The report addresses a common complaint within the British academic computer science community (and presumably in the maths community as well). We see lots of students with supposedly good A levels in maths, who appear to have gained the qualifications based on memorised formulae. And then they go on to use these formulae without a baisc understanding of how or why they work.

The problem is long-standing. Most of my school maths lessons were uninteresting; I think my motivation for pursuing the subject further came from various outside things, e.g. popular science book, puzzles, an exhibit in the Science Museum, etc. And to be fair, some of my lessons were genuinely interesting. Specifically, the ones that did not teach to the test.

It is very good to see this problem get the official recognition that is needed. (Will there be anything similar on computing in schools?)

Tuesday, September 16, 2008

credit crunch

I seem to have promised to do more tasks than I have time to complete them. If my creditors catch me making a lengthy post to this blog, I would have some explaining to do.

Tuesday, September 09, 2008

conclusion of COMSOC-2008

The COMSOC web site now has the proceedings and most of the slides that were presented. (Next thing to do, is try to call in the remaining slides.) Also there is a link to some great photos by Ji Ruan, including a group photo taken outside the Ashton Building, which gives the misleading impression that the weather was good. I was very happy with the way COMSOC went overall. Despite the well-known pitfalls of judgement aggregation, I think the conclusions of the business meeting can be distilled into the opinion that any subsequent COMSOC should be much like this one.

Friday, August 22, 2008

CACM 51(8)

The latest issue of Communications of the ACM is "newly renovated" according to the president's letter, by outgoing ACM president Stuart I. Feldman. So far as I am concerned, the contents of this issue hit the spot nicely, with an article by Yoav Shoham on "computer science and game theory", and one by Hal Varian on "designing the perfect auction". Shoham's article gives a very nice high-level overview of the field, with a historical perspective that reminds one that the relationship between CS and GT is not just a recent thing, but goes way back to Von Neumann in the 1950s. The article also does a good job of summarising the research issues, and general future directions.

Monday, August 18, 2008

Cities Unlimited

A man who is tired of London commonly invokes "quality of life", for there is to quality of life much that London cannot afford. Oliver Mark Hartwich does exactly that in a newspaper article written a couple of days ago. Entitled "Parting Shot", he celebrates his imminent departure to Australia by complaining about the high prices and shortage of housing, that he is leaving behind. The article is conceptually not very original, but it is well-written, and he probably enjoyed writing it. As a northener, I quite enjoyed reading it. Its most interesting aspect, however, relates to its author.

Hartwich is chief economist at Policy Exchange, the think tank whose report Cities Unlimited elicited howls of protest for its conclusion that the UK economy would be well-served by large-scale internal migration from cities like Liverpool, to London, Oxford and Cambridge. The spectacle of one of the report's authors emigrating from London, will do no favours to its credibility.

Section 9 of the report is the part that explains why Oxbridge (alongside London) get fingered as attractive sites to re-settle hordes of disgruntled Scousers. The authors are probably giving too much weight to the ability of famous universities to serve as indicators of economic potential. If Oxbridge could attract millions of new residents based on their universities, shouldn't they have done so by now? After all, they have had plenty of time. Their failure to do so is blamed on planning restrictions. Their alleged ability to do so is attributed to their high land prices, however those land prices may only be sustained by the planning restrictions. It is unreasonable to expect local people to willingly open their doors to floods of new immigrants -- there are too many vested interests in the form of high local house prices.

Finally, for the purpose of assessing successfulness of universities, they are measured by taking the proportion of government funding they receive for research, as a fraction of total government funding. This measure conveniently puts Oxbridge and London well ahead of the pack. But it also causes any university to get worse and worse with every additional student that it attracts, which to most people is counter-intuitive.

Thursday, July 31, 2008

COMSOC-2008 progress

Ulle and I recently finished making the program for the 2nd International Workshop on Computational Social Choice (COMSOC-2008), a task that is a bit like solving a sudoku. Then I took a look at some CS conferences that I have been involved with recently, to see how much social choice theory has appeared there. (Not much in CS theory conferences, see below for a summary; but there's more in AI and multiple-agents conferences. Indeed, a few of the COMSOC papers appeared at conferences like AAAI.)

I looked at conferences that attract a lot of computational game theory. So, what is the difference between game theory and social choice theory? Game theory studies the outcomes of interactions amongst multiple agents. Social choice theory is about aggregating multiple opinions/world views/preferences into an overall one. Elections are the most obvious examples of such a process. (For elections to be interesting to study, you have to solicit more than just a single preferred candidate from each voter. If voters provide rank-ordered lists, life gets interesting. It gets more interesting still if the decision is more than just a single winning candidate, e.g. if the decision is a set of winners, or a rank-ordered list.) For computer scientists, game theory is our opportunity to play at being economists. With social choice theory, we get to diversify into politics and philosophy also. (As an aside, at the 2000 BCTCS conference (held here at Liverpool), Les Valiant gave an invited talk in which he proposed an answer to the question: "What academic discipline would have attracted today's computer scientists if computer science had not yet been invented?" I thought he was going to say mathematics, but his answer was philosophy. Which makes a lot of sense, when you think about it.)

EC 2007: 42 papers, nothing obviously about social choice. Mostly game theory and mechanism design.

EC 2008: 38 papers, one of which is "A Sufficient Condition for Voting Rules to be Frequently manipulable" by Xia and Conitzer.

WINE 2007: 31 regular papers and 30 short papers, one of which is "PageRank as a Weak Tournament Solution" by Felix Brandt and Felix Fischer.

Then I took a look at STOC 2008, and was reminded that it is home to a wonderful paper: "The Chow Parameters Problem", by Ryan O'Donnell and Rocco Servedio. This is the paper I was trying to write when I wrote this precursor. Quoting their paper: "In the realm of social choice and voting theory the Chow Parameters represent the Banzhaf power indices of the n voters -- a measure of each one's influence over the outcome." Besides the big technical contribution of this paper, I think it's the first one to explain the importance of Chow parameters both to learning theory as well as voting theory.

Thursday, July 24, 2008

John Savage's "Models of Computation"

I read in DMAnet that John Savage's book "Models of Computation" is now available here (as PDF) under a Creative Commons license. I have my own traditional paper copy, but it's very nice to see such a comprehensive heavyweight textbook become freely available, and get rescued from the twilight zone of many books (when they remain in copyright but it gets harder and harder to get a copy). Now I can think of a bunch of other books for which this would be nice...

Thursday, July 17, 2008

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
rk
ppppp
pp
P
P
P
BPPPP
RK
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.)

Wednesday, July 16, 2008

Poster sessions

Yesterday I attended a poster session at GAMES 2008, and today went downtown to AAAI 2008 to meet up with colleagues and attend the poster session over there.

So, about poster sessions. I am reminded that correctly treated, they can be one of the fastest ways of learning about someone's research, since they provide the opportunity to quiz the presenter about any aspect that is unclear to you. At talks, it is usual to fail to take in some crucial aspect of the mathematical model being analysed. At a poster session, the problem can be eliminated, if you don't mind interrupting the presenter frequently. At GAMES 2008 I took in a nice poster presentation by Liad Wagman (Vincent Conitzer was co-author) on "Optimal False-Name-Proof Voting Rules with Costly Voting", which happened to also be a paper at AAAI that picked up an Outstanding Paper award (I missed the talk because the room was packed out). I think the other 2 posters at GAMES that I took in in detail were "The Theory of Collusion under Financial Constraints" (Yosuke Yasuda) and "On loss aversion in a bargaining game with alternating offers" (Bram Driesen). At AAAI, where the subject matter was, shall we say, highly diversified, I found myself gravitating towards the posters on graphics and image processing; there was one on rendering scenes based on natural-language descriptions, another on scribble analysis - given a scribble over an element of a sketch, is it a filling-in or a deletion?, another on domino tiling (given a fixed collection of dominos, arrange them to form a best-possible picture of a target image. More relevant to my own research, I take in a poster by Piotr Faliszewski, about how, despite the NP-hardness of manipulating elections, there is an approximation algorithm.

At GAMES, I attended an entertaining performance by stand-up economist Yoram Bauman.

Tuesday, July 15, 2008

The future of Game Theory

I have attended Peyton Young's presidential address, "STRATEGIC LEARNING: Recent Advances and Open Problems", also Sergiu Hart's plenary talk addressing the question of when does there exist natural dynamics leading to Nash Equilibrium (Hart is president-elect). Also, yesterday I attended the "Nobel Panel", which is as you might guess, a panel discussion by Nobel laureates (Aumann, Maskin and Myerson). Notwithstanding Aumann's delightful rendition of "que sera, sera", there are some take-home messages.

Computer Science, and the notions that we in the CS community work with, are of great interest to mainstream game theory; a paper by Papadimitriou used the phrase "as the ice between game theory and computer science continues to melt..." -- well I can report that it is well and truly melting. This is a great time for computer scientists to continue to work at making contributions to game theory. Sergiu Hart himself is very conversant with the relevant terminology and concepts from CS, perhaps in part due to his work with Yishay Mansour (to appear in GEB).

It was claimed that the time is ripe for more emphasis on cooperative solution concepts, as opposed to non-cooperative ones. (I would note that work in the AI community is addressing this topic.)

Generally, the word "decentralized" is a big buzz-word around here. I did not foresee when I wrote my most recent research proposal "efficient decentralised algorithms for computational game theory" quite how mainstream are the general topics on which I was proposing to work. Indeed, if anything the situation is "too good", in that my research program is being pursued by some of the top people in the game theory field, and I have to take care in a future version of the proposal, to identify a distinctive agenda. (added 21.7.08.): By the way, this web page describes a long-running conference series on "decentralization", based in the economics community, that I just found out about.

Sunday, July 13, 2008

Game Theory and Computer Science Prize

OK, it's the main reason I attended the conference, since it was awarded to Constantinos Daskalakis, myself and Christos Papadimitriou for our paper “The Complexity of Computing a Nash Equilibrium”, which first appeared at STOC in 2006. The plan is to award this prize once every world congress of the Game Theory Society (so, every 4 years) for a recent CS/game theory paper. It's an encouraging sign of the interest that the game theory community has for work going on in CS.

Constantinos Daskalakis gave the talk; in the audience was John Nash himself (Nash equilibrium was named after him since he was the one to prove (back in 1950!) that any game has one (at least one, to be more precise.)) Nash is now 80 years old, so he was 22 when he obtained that famous result.

Other bits and pieces: I attended a very nice talk at a session on "Roommate and Marriage Models", given by Thayer Morrill, on "The Roommates Problem Revisited". From memory, here's the idea. The problem with looking for a solution to the Stable Roommates Problem (in contrast with the Stable Marriage Problem) is that for some instances of the problem, any proposed solution may have at least one blocking pair. (That is, a pair of participants who prefer each other to the partners to which they have been assigned.) So, what we need is, a new solution concept. Morrill notes that shared rooms are scarce - the members of a blocking pair typically cannot go off together and move in with each other unilaterally. Instead, a solution should be deemed stable, essentially if there is no group of participants who can re-distribute the keys to their rooms in such a way that they are all happier than before. A solution should be Pareto optimal in this sense. Given this notion of what it means to be a solution, there is a simple algorithm that finds solutions efficiently, called something like "iterated random dictator", in which at each step, a participant is chosen, who gets to select his/her roommate; those two are paired off and we continue with the remaining participants.

Another session I attended was on "Algorithms and Games", where I got to attend talks by COMSOC invited speakers Tuomas Sandholm and Rohit Parikh. (It clashed with a session on "War", which I was sorry to miss.)

Outgoing president of the Game Theory Society, Peyton Young, gave a great plenary talk about viewing the search for a Nash equilibrium as an iterative learning process in which a player should interact with the other players solely by trying to improve his own payoff and not by attempting to model the behaviour of the other players. The wonderful thing about this talk, as far as I'm concerned, is how much it overlaps (coincides?) with my own research agenda. It is great to hear that the mainstream game theory community is very interested in these issues. I hope to talk to him later in more detail, but already I have some very interesting literature to look into, and will certainly write my next research proposal with that much more conviction.

This evening I got to attend a dinner hosted by Ehud Kalai; I came away feeling slightly star-struck by all the eminent game theorists who were in attendance...

Saturday, July 12, 2008

GAMES 2008

I arrive in Chicago after a fairly trouble-free flight. When I am asked at immigration what game theory is, I say it's a branch of economics. I feel like I am "going native" (the process by which computer scientists migrate from "computational X" to "X".

I meet Trevor and Katie in immigration queue; they are going to AAAI, which is "co-located" with GAMES 2008, but in fact is 15 miles away. They are the ones who had the sense to be in the city centre; my conference is out in the boonies of Evanston.

Thursday, July 10, 2008

ACM-EC 2008

The ACM EC'08 conference has now started; I am not there myself, but one of my papers is. And I am happy to say that it was selected as one of two "outstanding papers" at the conference; the papers that received the award are

  • Self-Financed Wagering Mechanisms for Forecasting, by Nicolas Lambert, John Langford, Jennifer Wortman, Yiling Chen, Daniel Reeves, Yoav Shoham and David Pennock

  • Uncoordinated Two-Sided Matching Markets, by Heiner Ackermann, myself, Vahab Mirrokni, Heiko Roeglin and Berthold Voecking



Our paper, Uncoordinated Two-Sided Matching Markets, considers the stable marriage problem, which as we know, is efficiently solved by the Gale-Shapley algorithm. We consider two simple randomised algorithms that have the advantage over GS that they are arguably less "centralised" (participants don't have to be told what to do a central controller), and which are guaranteed to terminate. We show that unfortunately, for carefully-chosen preference lists, these algorithms take (in expectation) exponential time. I can imagine that further work might involve identifying conditions (hopefully not too onerous) on the preference lists, that would imply fast convergence of these algorithms.

Monday, July 07, 2008

COMSOC notification

Program co-chair Ulle Endriss and I finally finish choosing papers for presentation at COMSOC-2008. Thanks to the program committee members for their work, and also to everyone who submitted papers. We accepted 36 out of 55 submissions (not including a handful of off-topic or duplicate submissions that were deleted at the outset). Authors have now been notified of the decisions on their papers. Here are some thoughts about picking papers for this particular meeting.

The process of choosing papers was done in computer-science style, i.e. with the aid of a program committee of established researchers in the field, who reviewed the papers in detail. We obtained three reviews per paper, which were mostly passed back to the authors. This approach is of course geared towards a system whereby you are looking mainly for technical merit of papers.

Computer science conferences are treated as publication forums, but in economics (and I believe in most other disciplines) conferences are much more informal. There is a proceedings but papers may be in a preliminary state. Fundamentally, COMSOC is a meeting, not a publication forum, and we took papers that appeared elsewhere. But, we compromised a bit with the Computer Science way of doing it.

In CS conferences, at least the ones where I have reviewed papers, the aim is to select (from the papers deemed relevant to the meeting) the ones of highest technical quality. The discussion of which papers to select is aimed at a rank-ordering of the submissions, in terms of quality, and the "best" ones are taken. For COMSOC, we had that bias, but we also aimed for representation of different sub-topics, and had a bias towards younger authors and paper that had not so far been presented anywhere else (actually, for CS conferences, that last aspect is not so much a bias as a requirement; since they are publication forums a paper is disqualified if it was given at a previous conference).

Grounds for rejection included "not being about computation", which applied to a sizeable minority of papers, including some quite interesting ones. (You have to be caseful to make a broad interpretation of what it means to be about computation, however.) "not being about social choice" was only applied to one paper that I know of, where it seemed to be more about a standard optimization problem that was being discussed in the context of a particular social choice setting.

I liked the approach of attempting to build a program that we believe should develop new interactions and attract interesting participants, rather than just select for technical quality. There's something quite liberating about being able to admit that it's OK to take one paper and reject a "better" one.

Due to the compromise that we adopted, there is a risk that some contributors from CS, as well as come from (say) economics, especially ones whose papers were rejected, will be taken aback by the approach to selecting papers. An obvious topic for the business meeting is whether we want a subsequent COMSOC to veer towards one or the other type of conference.

Adam Smith

A few months ago he made it onto the twenty-pound note. Now, Adam Smith gets a statue in Edinburgh. It is ironic that this event coincides with recent government pronouncements that hold his big ideas in disrespect. Thus, Gordon Brown urges us to stop wasting food, because waste is contributing to price rises. As I see it, that's the whole point of these price rises: to stop us wasting food! We need the price rises in order to change our behaviour. A similar point holds regarding the Government's plans to ban the use of incandescent light bulbs in order to save energy (and thus, lower its cost.) It's topsy-turvy thinking. Price should be allowed to do its job.

Here's a more complex example that affects me professionally. This article attempts to explain why the Government is right to introduce the "full economic cost" regime for research grants. Essentially, the effect of this regime (by comparison with the previous one) is that when you get a grant, they pay you more money for doing the same amount of work. The rationale is that universities were trying too hard to attract under-funded research projects, which leads to infrastructure decline, and is supposed to be unsustainable. But, hang on a moment: if universities were already fighting like rats in a sack to get these insufficient research grants, why stop them? I'm not just a researcher, I'm also a taxpayer, and I like the idea of my money going further, even when it's being spent on research. And from a selfish academic perspective, if each research project only attracted half the money it ought to, it would presumably double my chances of getting one.

Monday, June 30, 2008

PhD interviews

Last week we interviewed most of the applicants for our department's PhD studentships that are due to start in September. (I was on the interview panel; note that I am PhD admissions tutor.) Subsequently I have sent out some informal offers by email. We had two kinds of studentship on offer: doctoral training account (DTA) studentships (given out by the research councils and only available to Uk students) and department funded ones (available to EU students).

The DTA studentships were allocated very late this year, at the end of April, which is the fault of the research councils, which are clearly out of touch with the process. They don't seem to appreciate that a highly-qualified, well-organised student will want to have a place stitched up round about Jan/Feb. Add to that the constraint to UK students, and you begin to see why it was more fun to fill the department-funded places. The late allocation of the DTA quota is the second-most annoying thing that has happened to me this year; the most annoying thing is conveniently co-located in my previous post to this blog.

Having said which, I concede that we should probably try to raise our game vis-a-vis the process of advertising to prospective students.

Monday, June 09, 2008

Dog Bites Man

As hinted in this earlier post, I learned that a recent grant application of mine just failed. (It was joint with colleagues here and at Warwick, on the general topic of algorithmic game theory.)

Now, I have good reason to be very dissatisfied with the way the grant application was treated, but I won't do the details just now. For the moment, here are a couple of more "philosophical" observations.

  • It costs you nothing to submit a proposal (except in considerable time spent preparing it), and it gets vetted by unpaid volunteers. You get what you pay for!

  • In Fleet Street, "man bites dog" is news, but "researcher's grant application fails" is most definitely not news.

Campaign for the University of Oxford

Today I receive some literature on behalf of the Campaign for the University of Oxford, in my humble capacity of an alumnus. Since I work for another university I don't feel that inclined to contribute. Actually, I guess that employees of Oxford Univerity itself are probably the poorest prospects in that respect.

The first "campaign for Oxford" was begun while I was a student there; the student union at the time was opposed to it, for reasons which didn't make sense to me at the time. I understand that that earlier campaign was quite successful.

The case being made in the literature that I received, is trapped in a kind of contradiction, which is that it is based on the current success of the university, to the point that one might ask why they need more money, if they are already doing so very well. On the other hand, the Matthew effect is so widespread in academic life, that it stands a good chance for that reason.

Saturday, June 07, 2008

No longer young

Last week's Times Higher had a feature (pp. 30-35, and front cover) on "Rising Stars: The young academics who are tipped to go places". Their definition of "young" was the most liberal I have seen, namely 40 or younger. Only a few weeks ago I would have qualified! Damn.

Incidentally, one of those who made that hall of fame (in the capacity of "the philosopher") is social choice theorist Christian List at LSE, who is on the COMSOC program committee and is going to give a tutoral at the workshop. Kudos to my co-chair Ulle Endriss for recruiting him to these tasks.

A recrudescence of the national debate about the importance of mathematics saw Ben Goldacre calling into question the case for more maths teaching. This article by Simon Jenkins in the Guardian, attempts to do the same. He dismisses the value of intellectual disciplines that purport to train the mind, and alleges that promotion of such study "panders to the political correctness of the conservative classes". Maybe I should just admit myself to be a member of those evil "conservative classes" that he deplores. Winston Churchill supposedly said that you don't have a heart if you are not a socialist before age 30, and you don't have a brain if you are not a Tory after that. I guess that makes me about 10 years too late.

Tuesday, June 03, 2008

definition of computational complexity

This post on the Fortnow/Gasarch blog caught my eye, partly because some of my own work is cited, towards the end. In the post, Lance Fortnow argues that proofs of NP-completeness do not constitute work in computational complexity, but rather in algorithms. This is because a typical NP-completeness proof consists of an efficient algorithm that translates an instance of some pre-existing NP-complete problem, into a corresponding instance of the problem of interest.

Lance's dividing-line between "algorithms" and "computational complexity" disagrees with a passage of text I wrote for one of the pages of my research group, in which I said: This kind of analysis belongs to two closely-related research fields: algorithmics, the design of algorithms with provable performance guarantees, and computational complexity, the classification of problems according to the kinds of algorithms that can solve them. According to what I wrote, an NP-completeness result is a work of computational complexity, albeit not usually a very interesting one.

I would not be that interested in getting into a debate about where exactly to draw this dividing-line. But I tend to prefer my own definition, mainly because it defines computational complexity in terms of what it is, rather than what it isn't. The other problem with Lance's definition is that one can imagine some Grand Inquisitor of Computational Complexity, managing to exile all sorts of results from the hallowed halls of computational complexity to the chilly uplands of algorithms, on the grounds that they are often tainted with algorithmic content. Take for example Savitch's Theorem, and its corollary that nondetermistic polynomial space is equivalent to deterministic polynomial space. The proof uses the reachability method, which is clearly an algorithm.

Friday, May 23, 2008

Liverpool Algorithms Day


The department has just hosted the Liverpool Algorithms Day (LAD'08). The main highlight was Leslie's inaugural lecture; there were also another 7 talks, each of half an hour.

I estimate that the event attracted about 50 participants from outside the university. An important feature of the meeting is that it is short enough that attending is not too big an imposition; it seems quite a successful formula. Previous LADs were held in 2003 and 1999; also we had a Warwick Algorithms Day 2 or 3 years ago. Informal discussions indicated that it would be good to have such an event every year.

It seems that most people failed to appreciate the logo (shown above), which is of my own design. OK, most people recognised the Liverpool football outfit. Someone (Alan Gibbons(?)) asked when it was put on display at the start of the meeting: "Who's the little chap at the top right-hand side?". I waited for half-a-dozen people to pipe up: "It's a lad of course! as in the lad came to the door at night. Refers to the meeting's acronym!"... but answer came there none. I guess I was right not to pursue a career in advertising.

Thursday, May 22, 2008

Case against discrimination based on socio-economic background

An article that appeared today on the BBC news web site, is provocatively entitled Working classes 'have lower IQs'. It's about a paper by evolutionary psychiatrist Bruce Charlton claiming that one reason why the children of the affluent are more likely to go to university is because they deserve to (to put it crudely); they are smarter. It look like the paper was first highlighted in today's Times Higher, less provocatively titled Elite institutions' class bias simply reflects 'meritocracy'. It has also already also been featured in various other mainstream newspaper websites (e.g. The Guardian and The Telegraph). Note that the Times Higher has a link to Charlton's article in full (in Word format).

Let's leave aside for the moment the question of whether it's true that richer kids are smarter. For my part, I am delighted that the government has been put on the defensive over this issue. This is the first challenge I have seen to the government's article of faith that universities are behaving badly by not packing in large numbers of working-class students. Lest we forget, this is the same government that introduced top-up tuition fees, and which still refuses to ackowledge their impact on the attractiveness of higher education, to people on low incomes. Of course, Charlton is going to get a barrage of flak for his article, some of which can be found in the comments section attached to the report in the Scotsman, for example.

Just to be ultra-topical, Labour's protestations of meritocracy do not chime well with their campaign in today's Crewe and Nantwich by-election --- as critiqued here, they are fighting a class war against the wealthy Tory candidate Edward Timpson. Their own candidate is the daughter of the deceased former MP Gwyneth Dunwoody (whose death is lamented by many, including myself). Fielding her daughter as candidate does not look very meritocratic to me.

Tuesday, May 13, 2008

meetings

It has gone quiet today; some CTAG colleagues are at this meeting at Dagstuhl, while most of the agents group is at AAMAS 2008. I am co-author of one of the AAMAS papers (my first paper to appear at AAMAS). Countering the "gone quiet" aspect, Leszek is doing a great job, with visitors Robert Elsässer, Petra Berenbrink and Jurek Czyzowicz.

Friday, May 09, 2008

Rejection (not mine, luckily)

Today's Times Higher calls attention to the youtube movie Rejection, whose author David Scott reflects on having his grant application turned down. Having received nearly 500 views so far (and a mention on the front page of the Times Higher), maybe that's some sort of consolation prize.

Since my recent grant application could easily get the same treatment in a few weeks, I was rather hoping for a good rant; instead, his remarks were rather measured and circumspect. He discusses his own experience in detail, including the means by which he was notified, but does not offer any solutions. The resulting tedium is relieved by Scott's engaging manner, and the (anonymous) cameraman's overenthusiastic use of the zoom lens.

Thursday, May 08, 2008

A surfeit of reading

Reading material in my notional in-tray includes undergraduate project write-ups, drafts of thesis chapters or preliminary results from PhD students, a conference submission that I agreed to sub-referee, and some older papers that I should cite as background work in new papers. Also a journal paper and a conference paper that I working on, with co-authors. It does not currently include journal papers that need referee reports (hooray) or grant applications in need of referee reports (double hooray).

Now, I ought to happily lap up at least some of the above material, but I reckon that I am not a reader by nature, despite my job title. Or at any rate, not the perfect academic. When I actively work on a problem, it gives me the incentive to read up on the ideas and techniques that have been applied to it in the past. Contrary to the "natural" order of things, for me, study does not come before research.

Some thought on different types of reading material: journal paper submissions to review are rarely interesting because they are yesterday's news; conference submissions have the advantage of being new material being released for the first time. Textbooks - I have tried to read these, and never get very far. Reading textbooks feels like too much a passive activity, plus, they've got the "yesterday's news" problem. Research proposals may be interesting, if only for all the wrong reasons. You get to find out the authors' salaries, which is one of the many things that is wrong with the process of evaluating grant applications. Trashy novels - by far the best bet.

Friday, May 02, 2008

GAMES 2008

I am going to attend the Third World Congress of the Game Theory Society, which takes place on the 13th-17th July, 2008 in Chicago. I will add more details at that time.

Sunday, April 27, 2008

Sacrilege of Modern architecture's high priest

I saw in today's Sunday Times that Norman Foster is going off to live in an 18th century chateau in Switzerland. Hey, I admire his taste. But, why do the rest of us have to carry on trying to like (or pretend to like) all the ugly glass-and-steel modern stuff that he and others designed, when he turns his own back on it? (Aside: when I looked at Foster's Wikipedia entry, linked-to above, the news article that I also link to, was already linked-to from the Wikipedia entry! I admire Wikipedia's efficiency.)

Friday, April 25, 2008

Doctoral Training Centre proposal

I am helping to prepare a bid for a "Doctoral Training Centre" (DTC) in response to this call for proposals. We need to make a 3-page outline to submit by the 6th of May, then some of these outlines lead to invitations to submit more detailed proposals.

It seems that Liverpool is preparing about 5 of these bids. According to one of the people who is helping to coordinate the bids, it is likely/plausible that this is going to be the new model for how PhD studentships are allocated by the research councils, as opposed to the "doctoral training account" ones I mentioned in my previous post here. While my participation in this proposal suggests a certain level of endorsement of the general concept, I can still consider the advantages and disadvantages in a fairly impartial-looking way...

DTCs can be advertised effectively; a DTC may typically take in about 50 PhD students over 5 years, so it's a big centre. You can spend money on proper advertising, and better yet, you know in advance that you will have the funds for the students, so you can make a proper advertising campaign. (Note the complaint I made in my previous post.)

But, because they're big centres, taking in a large part of limited funds, DTCs lead to concentration of activity in a small number of institutions. Good news if you're one of the "winners", I guess, but the losers face the prospect of having to get out of the business of PhD supervision altogether, at least if the prognosis mentioned above is accurate.

Can DTCs as envisaged, be faulted for reducing the choice available for prospective research students? (Thus, currently, prospective students can submit their own research proposal, hopefully after working on it with an academic who could supervise.) I don't think that's a problem --- I reckon that prospective research students cannot identify a research project in much detail; it only makes sense to expect them to know their general research area of interest, e.g. "algorithms and computational complexity". (Experto crede — I am PhD admissions tutor!) On the other hand, I think they can be criticised for reducing academic freedom, or at any rate, flexibility in choosing a research topic for one's PhD student.

Finally, whatever our success at this effort, it is somewhat interesting to get to meet up with people at the University from outside my own department, and get a view of the bigger picture.

Thursday, April 24, 2008

PhD studentships

Finally, we get our allocation of Doctoral Training Account studentships from EPSRC. I have posted the following advert to various lists and encouraged colleagues to do similarly. I am unhappy about the delays to the allocation of these studentships; I have no idea what caused it, e.g. maybe some university entered into a dispute with EPSRC about their total allocation? That is sheer speculation, but it's the sort of thing that may have happened. Basically, the studentships get allocated by EPSRC to universities, based on research grant income, and then universities allocate them to departments.


Applications are invited for PhD positions at the Department of Computer Science of the University of Liverpool, UK. The Department has funds to support three PhD studentships to begin on or around September 2008, and to run for 3 to 4 years. Further details are at:



http://www.csc.liv.ac.uk/~pwg/2008-studentships.htm



The Department has particular strengths in Algorithms and Complexity, Logic in computation, and multi-agent systems, so we particularly encourage applicants with an interest in any of these areas.

Note that two of these posts are EPSRC Doctoral Training Account studentships, and are only available to students who are resident in the UK; the above web page has details on eligibility. The other studentship (funded by the Department) is available to any candidate who is a citizen of an EU country.

Tuesday, April 22, 2008

COMSOC-2008

I am helping to organise COMSOC-2008, the second International Workshop on Computational Social Choice. Specifically, I am co-chair of the program committee. Fundamentally, it's an informal meeting; there is a proceedings but it does not purport to publish papers; it just provides a forum for presenting work in the area. One of my better ideas regarding this meeting was to solicit ideas from the invited speakers about additional events, such as an open problem session, which should, at this point, go ahead, provided there is sufficient interests from participants. Next thing on my list is to send out an updated Call For Papers to various mailing lists and other places... Paper submission deadline is June 3rd.

Tuesday, April 15, 2008

EC'08 accepted papers

In the time-honoured manner, I hereby commemorate my work on the program committee of ACM-EC 2008 by linking to the list of accepted papers. (Although, since it was a big program committee, my contribution was correspondingly small.)

Wednesday, April 09, 2008

Who rates the league tables themselves?

This article at the BBC News website (Tables "affect university policy") reports that universities' policies are strongly influenced by their effect on the various league tables that are used to compare universities. That fact will not be surprising to most academics. The article is about a New report compiled by HEFCE, Counting what is measured or measuring what counts? that raises the concern that league tables may have a bad effect on universities themselves, and may fail to measure the quaities that they purport to measure.

Since they compiled by the popular press, often in haste, and without the attention to detail and rigour that we take for granted in the acedemic world, we should not be surprised by this finding. The one thing we can sure of is, however, that they will undoubtedly continue to exist in their present form, and will continue to be used extensively by, for example, prospecitive students, simply because that's all the comparative analysis they've got.

Tuesday, March 18, 2008

Daft league table

Today's topic of lunchtime conversation was this league table, the Halifax-Times Higher Education quality-of-life index, which appeared in the Times Higher about two weeks ago. It purports to compare the "quality of life" amongst the different higher education institutions in the UK.

Which is not a bad idea, in and of itself. Indeed, lifestyle factors played a part in our decision to move from Warwick to Liverpool in 2006. You get the coastal location, grammar schools, proximity to Snowdonia, that sort of stuff. Here's the catch: according to the league table, we seem to have made an appalling howler! We seem to have plunged from 16th place to 109th place (which is pretty close to the bottom, almost as bad as Manchester).

In contrast to the geographical area around Warwick, it would seem that Liverpool suffers from a relatively low level of owner-occupancy (although I myself was never required to live in rented accommodation), a lower pass rate amongst school pupils of GCSEs (although, we academics, crafty devils that we are, might be expected to avoid the weaker schools, or failing that, our kids might actually have the smarts to do well despite the performance of their peers), and a higher amount of road traffic (well, it's a city, isn't it). Advantages mentioned in the above paragraph did not enter into the equation.

As I say, studying the general attractiveness of different universities in the context of the "bigger picture" seems to be a worthwhile endeavour. But, unless such a study is carried out with rigour, discipline and a willingness to question one's own approach, it ends up being completely pointless. Although, if it causes people to lose faith in league tables generally, that may be a useful side effect.

Wednesday, March 12, 2008

Talk at Warwick

Yesterday I went to the Dept of Computer Science at Warwick to give this talk (not sure how long that link will last but there it is) on recent work on computing approximating Nash equilibria. This is my first trip to Warwick since leaving a year and a half ago. Looking at the list of talks in previous weeks, they have a nice line-up of speakers. I meet a number of former colleagues, who are in the middle of student project presentations this week.

I see the Warwick digital lab under construction; this looks like it might be some sort of opportunity for the CS dept to get involved, but I did not discover any plans for that, from people I talked to. I reckon they ought to get involved, but I did detect a moderate perception of it as threat rather than opportunity.

I finish the day by dropping in on Alun Wyburn-Powell, and having a chat with him and Diana.

The 2 other guests at the B&B are a music examininer, and a former student from Warwick CS, who had sat through some of my lectures but who didn't seem to hold it against me, and is now working for a company started by Mike Rudgeyard (like me, a former Warwick CS lecturer).

Return train trip is disrupted by high winds (never noticed them myself) which mean that I have to change trains 3 times, but in the event the total delay wasn't too bad.

Monday, March 10, 2008

A random rant about global warming

I'm sure someone else has made the following point, probably more articulately than this, but I just haven't seen it yet...

So, there are people like myself, who believe that glocal warming is a genuine problem that we should do something about, and there are two kinds of opposing view: some people disbelieve in glocal warming entirely, and there are others who say that glocal warming is not man-made; it's natural, caused by sun-spots or something like that, so there is no point us trying to deal with it. And it's that latter viewpoint that strikes me as completely unworthy of respect, for the following reason:

By way of analogy, suppose I find a lump on my skin, and say "Yaah! I think I've got cancer!". The glocal-worming deniers are like someone who says: "ignore it, it's probably something benign". But the ones who dismiss global warming as being a natural phenomenon, are like someone who says "Well, cancer is natural, people often die of it, so stop complaining. Don't bother with a doctor and don't bother to change your lifestyle.". That is, their attitude is completely defeatist. Maybe we have the ability to save our lives, but those people simply don't want to use that ability.

Tuesday, March 04, 2008

School allocation

Here is an article about the dreaded moment when you find out about your kids' secondary school allocation. Isaac passed the eleven plus so gets offered a place at Calday Grange Grammar School. The article I linked to is mainly about the majority of schools outside the grammar-school system, but it's still a nervous moment to check that you obtained the intended result.

How best to allocate schools to children, in the presence of their (or usually, their parents') preferences? I don't have an strong opinion, although lots of people have theirs. The way German kids get into gymnasiums (equiv of grammar schools), which is done by agreement between parents and primary school teachers, seems good, if you can restrain the excessive demand (which I gather is something of a problem).

(added later:) Many criticisms of the current system seem shrill, for example this one, an editorial in the Daily Mail. Certain pupils are said to be "condemned to third rate comprehensives... a life-sentence to underacheievement", also note that lottery-type systems have "scattered middle-class pupils far and wide, breaking down the critical mass of talent on which our best schools depend to serve pupils from every background." (this what lotteries do, and it's the entire point of them. I don't know whether talent has a "critical mass" effect, although disruptive behaviour in schools probably does have such an effect.) The article seems to be in favour of the grammar school system, but doesn't quite say so.

Monday, March 03, 2008

Product endorsement

We all know, of course, that game boy cartridges are washable. They can go through the washer and tumble-drier, and are still usable. When it comes to mobile phones, by contrast, the Sony Ericsson W800i cannot even be safely taken out in a rainstorm without suffering catastrophic water damage. A few months ago, when I sent in Arthur's Sony W800i for warranty repair/service, they refused to help me, citing "water ingress contamination" or some such phrase.

It would seem like an experiment not worth attempting, to take an alternative brand of mobile phone, of unspecified water resistance, and subject it to the same test that game boy cartridges have successfully undergone. But, to the true scientist, there is no experiment not worth attempting, and Isaac's LG phone, LG KG220 has just survived it! The screen was a bit fogged after rescue from the drier, but a couple of days later, and we just made a call from it!

Friday, February 29, 2008

Road works

The end is finally in sight for the raod works outside my office. It's just about been turned into a paved pedestrianised area. I'm a bit sceptical about the concept, but let's hope for the best.

This blog is the sort of thing I could easily waste hours reading if I had the time. (For some reason, it got reported on the BBC and in major newspapers, which is how I heard about it.)

Friday, February 22, 2008

PhD

Congratulations to my former PhD student Nick Palmer, who just rang me up to let me know that he successfully defended his PhD thesis after a one-and-a-half hour viva at Warwick. Thanks must go to Artur Czumaj (internal examiner) and Martin Anthony (external examiner).

Submitting referee's report

This is sort of a follow-up to a recent post about refereeing journal papers. I just submitted a referee report for a paper submitted to Elsevier's Games and Economic Behavior journal. Now, I initially just emailed it to the editor, and he asked me to upload it via their website. Doing that, I found that they keep track of a previous report I submitted for GEB a year or so earlier. The significance of this is that referees can actually build up some sort of track record of their contributions, which is kept on a centralised database. This has the potential for researchers to gain some sort of credit for their refereeing work, which as mentioned in my previous post, is currently missing. As a result, the slightly tedious process of uploading a review via a website, suddenly makes a whole lot more sense to me. I would even go so far as to say that it helps to justify having large numbers of journals under the control of a single publisher (such as Elsevier), if they can ultimately allow reports for submissions to other Elsevier journals to share the same database as GEB, for example. (The context for that observation is the common complaint that profit-making publishers are increasingly an obstacle to the effective dissemination of research results, rather than as assistance.)

Wednesday, February 20, 2008

New memory stick

I manage to impress my colleagues by acquiring a 32 gigabyte memory stick, a substantial upgrade from it's 512 megabyte precessor, bought about 3 years ago. They both look more or less identical, see picture.




The old and the new


The new one contains one million times as much memory as the first computer I ever used, a BBC micro. If there's one thing that gives you faith in Progress with a capital P, it's the exponentially-increasing amounts of computer memory one can buy, in conjunction with increasingly convenient and robust formats. I am guessing that in a year or two, no new laptops will have hard drives, it will all be solid-state and much more compact.

Tuesday, February 19, 2008

An Odious Organisation

For a few weeks I have been receiving spam email from an organisation based in London called "The LifeLeague", an extremist anti-abortion organisation that also opposes various other things such as stem-cell research, and is not too fond of homosexuals either. (As an aside, they also call themselves an anti-spam organisation, but I cannot agree with this claim, since I have tried unsuccessfully to get off their mailing list. Although, unusually for spammers, their emails have an address and phone numbers.)

Mostly I delete their emails without looking beyond the subject line, but I did take a look at today's effort, which included the following:


IVF Linked to Infertility


Britain is facing an infertility timebomb because the increasing use of IVF means that couples with inherited fertility problems are able to have children and pass the condition on to the next generation.

The LifeLeague says: These latest findings only serve to back up what we as pro-lifers have been saying for so long. IVF - as well as being immoral - is medically dangerous too. Thanks to IVF, vulnerable, desperate, childless couples are being exploited.

The Telegraph 15.02.08 Click here for more information.


Let's ignore for now the fact that this hysterical alarmism about fertility decline flies in the face of every available shred of evidence. What's most noteworthy about this comment is the conclusions that it entails, once we follow this logic to its conclusion. Because, if people with poor fertility pose a theat to the gene pool, the same presumably holds for all sorts of other undesirables, such as diabetics, the chronically obese, and maybe even the short-sighted. I suppose, if the LifeLeague were to have it's way with all these substandard human beings, it might eventually nullify the need for stem-cell research, thus helping to achieve one of their objectives.

The Nazis were the most notorious for outlawing abortion, homosexuality and the genetically inferior. Lest we forget, their intellectual heirs are not lurking in the closet; they are still openly campaigning in our streets and cities.

Sunday, February 17, 2008

Refereeing journal papers, and saving the planet

The following similarity occurred to me yesterday, while I was trying to save the planet. "Saving the planet" seems to refer to an assortment of unsatisfying activities, which in my case consisted of attaching an address label to a spent printer cartridge (courtesy of HP Planet Partners) and sending it back to HP. The post office turned out to be closed by the time I reached it. 'Twould have been easier by far to discard the cartridge in the dustbin, like an unwanted and embarrassing corpse. As it is, I still have it.

Now, all these kind of minor environment-saving measures have one thing in common, which is that they do the individual no good at all; quite the contrary, they involve you in some amount of expense and inconvenience. It's remarkable that anyone bothers, but they're motivated by some sort of moral pressure that's hard to ignore. This brings me neatly to the topic of refereeing research papers, especially journal submissions. The motivation for this activity (yes, I'm in the middle of doing one at the moment) is entirely moral, again. You incur these tasks by submitting papers, so you ought to perform such tasks. Trouble is, there's no pay-off. Allegedly you get some respect from the editor, but this doesn't seem to translate into any kind of concrete advancement.

The reason why journal papers are worse than conference papers to referee, is firstly, that they are more work --- you really are supposed to check them in detail. Also, they are yesterday's news; the conference version usually came out about a year previously. Luckily, the one I'm in the middle of is well-written and on a topic that is highly relevant to my research, so I can't complain about it too much.

(added later:) I guess the reason why I find this interesting, is that it contradicts a standard premise of game theory, namely, rational behaviour (i.e. selfish behaviour). No doubt people have tried to model this kind of "irrational" behaviour, but I don't know how well that has worked.

Saturday, February 09, 2008

Oh go on, just one more...

I agree to join the program committee of WINE 2008. Right now I am bidding for papers as member of the PC of ACM-EC 2008. Also I am PC co-chair of the COMSOC workshop.

In computer science in particular, we use this sort of activity as evidence that one is a respected member of the research community in question. (Another standard example is being a journal editor.) Most computer scientists seem to list their current (and often previous) PC work on their web pages. Publications get less prominence.

With regard to the title of this post, I suspect there is a tendancy to overdo it, that is, accept too many of these invitations.

Tuesday, February 05, 2008

The History Man

I'm a bit of a sucker for campus noevls, even though I don't really believe that "campus novel" is a meaningful literary genre. I belated finished reading The History Man yesterday, after having previously read this review in the guardian.

The book's wikipedia entry attests to its significance, although it's not a very good overview; David Lodge's view is more to the point. I guess one way to interpret the book, probably not the right way, is as a lesson in why, over the past 30 years, universities have had to comply with externally-set standards, why teaching quality has been put on a more and more formal basis, and why we all started to frown on sexual harrassment. (Of course, it's nearly always a mistake to write a novel with the objective of teaching the reader a lesson, which is why I say this is the wrong way to interpret the book. But it may help some readers come to terms with the way it deals with a thoroughly unpleasant man, who fails to get his come-uppance.)

Tuesday, January 29, 2008

XJTLU

I attend a presentation by pro-vice-chancellor Kelvin Everest about progress on Xi'an Jiaotong-Liverpool University, Liverpool's partnet instsute in China, and the university's big project. From the statistics, and the pictures of the development in which this university forms a small part, you just have to be wowed by the sheer scale and pace of the economic development in China.

I would like to go there, if only for a short time, just to witness and play a small part in this major piece of history, i.e. the economic rise and rise of China. As academics (especially research-active ones), we purposefully cut ourselves off from the general business of "making things happen", but I for one can't pretend to be indifferent!

XJTLU will be a new university, built from scratch and then peopled with staff and students, all within about 10 years, and will be just one of 10 new universities on a 240 square km "business park", really an entire city. People who have been there are awed by the pace of change that you see from visit to visit.

Thursday, January 24, 2008

Examinations; invigilation

Today I handed in my exam marks for the module I teach (formal language theory, not that that's relevant to this discussion). Always good to get that task completed. The exam itself was about a week ago. There is scope for debate on whether examinations are more onerous and disagreeable for the examiner, or the examined, and this is the sort of question one considers during the exam itself, while one is invigilating it.

Of course, you usually get to invigilate your own exam, as I did a week ago. The session just involved my own students; there were no other exams being taken at the time, which simplified it a lot. A far cry from the glory days of my invigilation career back at Warwick, when some sessions had about 300 students, taking half-a-dozen different papers between them, all ending at different times. If you had to make an announcement, you needed to repeat it in about 3 different places, although later they installed a PA system.

Examinations, like degree ceremonies, are something of a ritual, and like degree ceremonies, they provide some of us (namely the invigilators) with an excellent opportunity to enter into a pointless and unproductive reverie about the academic process. The instruction is given to begin. The room goes quiet, that is to say, even quiter than it was. As for a degree ceremony, you get the feeling that it is intended to be caught in a time-warp. There should be a battered wooden box on your desk, inked-stained and chalk-dusty, containing miscellaneous things like treasury tags, elastic bands, and anything else that might come in handy. There should be numerous piles of different kinds of answer sheets, dog-eared log table books, and spare scraps of paper. If it's a big session, the senior invigilator will dutifully make handwritten notes on who leaves the room early, and when, and he will direct his underlings to sort out the scripts and escort assorted students when they take toilet breaks. No-one ever wants to be senior invigilator, of course.

Wednesday, January 23, 2008

new gadget, with an old technology

I take delivery of a new phone/PDA, an HP iPAQ hw6915. I took care to choose a PDA that has a QWERTY keyboard; not all of them do. Ah, the wonderful QWERTY keyboard, like Dr. Watson, a fixed point in a changing world. People have been predicting its demise for decades, like they have been predicting the demise of newspapers. But it lives on, basically because it's a fundamentally good idea. My old PDA (a Handspring Treo) also had a keyboard (perhaps it still has; but it got stolen last week). Its predecessor, I think, did not. In the late 90's when everyone used Palm Pilot, one of the exciting new gimmicks was the "graffiti" method of text entry. But that idea doesn't seem to have lasted.

For keyboards to disappear, some good alternative would have to arise, and I can't guess what it would be. Speech to text translation is no good, since we don't always want to make a noise while entering our data, or let other people hear about the data. And there's ongoing work on recongising gestures/sign language, which may be useful for some people, but would probably not become mainstream.

(Added 24.1.08.) A useful thing I discovered recently is that when you are filling in an online form, you can use the tab key to jump from box to box. No longer do I have alternate between mouse and keyboard in order to fill in multiple boxes! Makes a good use of the tab key, whose original purpose is by now obsolete.

Friday, January 18, 2008

You know you're writing too many papers when...

...you get some conference submission rejected, and you get a sense of relief that you will not have to write up a proceedings version anytime soon.

They would have needed a camera-ready version by the 9th Feb. Come to think of it, isn't this "camera-ready" concept getting a bit passé? No-one uses cameras any more to print conference proceedings, right?

Thursday, January 10, 2008

Holiday reading

Some books I read over the holiday --

Ghost, by Robert Harris. A taut, efficient thriller, just right for a 10-hour flight from London to Denver. The main character is not as vivid and 3d as the blurb makes him out to be. A good book for people who don't like Tony Blair. Dark Rivers of the Heart by Dean Koontz. Started reading it at the condo in Breckenridge. It's too damn long! The political rants I can deal with, there's only about five, and I'm quite a sucker for political rants, even when I profoundly disagree with them. It's just the excessive detail on certain unimportant characters, and the houses they live in, stuff like that. And worst of all, the occasional flare-up of literary affectation. A disappointment after Watchers. The Road by Cormac McCarthy. For me, a bit too arty for a post-apocalypse novel. I can't see why it got pressed-ganged into the service of the environmentalist movement.

Yesterday, I finally got a research proposal submitted, that has taken ages to write. Never mind whether it succeeds, just for the relief of getting it out of the way...