Paul Goldberg

publishers versus openness

2012-01-17T01:15:00.000-08:00

Academic publishers have become the enemies of science — the article explains how the US Research Works Act would “allow publishers to line their pockets by locking publicly funded research behind paywalls”.

A related issue is the Stop Online Piracy Act (Sopa) which has led to Wikipedia’s forthcoming protest (see the warning message on Wikipedia itself) in the form of a blackout that will take place on Wednesday. this article seems to provide hope that sanity will prevail; it’s reassuring to hear Rupert Murdoch accusing the Obama administration of bowing to “Silicon Valley paymasters”.

(added slightly later:) This new post at Tim Gowers' blog also comes out in favour of the one-day blackout.

heterogeneous prices for parking spaces

2012-01-09T01:01:00.000-08:00

The following question occurred to me during a recent search for a car parking place. Maybe it’s been done to death somewhere in the economics literature; let me know if you’ve seen it.

So I’m having trouble finding a parking space, and being a good liberal my reaction is to throw money at the problem. Since the car park’s full, the people who run it should jack up the price, right? With any luck, it would rise to a point where some of these cheapskates would get priced out, and I would still be in the game. Actually, there’s a smarter trick possible: you should have some cheap parking spaces and some expensive ones. The first people to arrive at the car park are able to take the cheap spaces, and later arrivals who are desperate for a space have to buy the expensive ones.

To see that this can increase the revenue, suppose that you own 100 spaces and there are 200 potential users, 190 of whom would pay £1 for a space, but the other 10 would be prepared to pay £5. Clearly we should charge either £1 or £5 for spaces, and if we charge £1 for all of them we raise £100, while if we charge £5 for all of them we raise £50 (selling 10 spaces and leaving the other 90 idle). Suppose instead that 99 spaces cost £1 and the other one costs £5. Suppose further that car park users arrive in a random order. In that case you are very likely to sell all spaces and raise £104; there is probability of only 2^-10 that the 10 high-value users will be amongst the first 100 users to arrive, which would lead to the £5 space ending up idle and a revenue of only £99.

This suggests the following computational problem. You have n parking spaces and there are N>n users, where each user has a known value that he assigns to receiving a parking space. Assuming they arrive in a random order, how should you price the parking spaces so as to maximize the expected revenue? (Whenever a user arrives, they buy the cheapest available space, unless their value is less that the cheapest space, in which case they leave.) Indeed, for a given set of n prices for the spaces, I don’t see how to efficiently compute that expected value, although it would be easy enough to approximate by simulation (repeatedly generate random orderings of the users and see what happens).

It seems like the effectiveness of heterogeneous prices is greater when N is quite a lot larger than n. In the case that n>N, I don’t know of any examples where revenue-maximization requires prices to be non-uniform.

a couple of articles

2011-12-22T14:21:00.000-08:00

Reach for the cyanide pills! From the hallow’d pages of the Times Higher comes the shock horror news that one in four new undergraduate courses attracts no students. This is portrayed as some sort of colossal waste of money; universities should have figured out in advance whether there will be a market for their new courses, before they set them up. Unsurprisingly, the study was funded by the Higher Education Funding Council for England (HEFCE). Can one imagine an attitude like that in Silicon Valley? If it had, the likes of Google or Facebook would never have seen the light of day. It is fun to imagine HEFCE as venture capitalists saying: “I’m sorry Mr Page, but the business failure rate for this kind of web site is in excess of 25%”.

From madness to sanity. I recommend Universities Under Attack by Keith Thomas, who was president of Corpus Christi College, Oxford way back when I was a student there. Read it! Read it and weep, but read it nonetheless. By way of contrast with the other article I mention, he recalls

a time when the ‘new’ universities of the 1960s were devising novel syllabuses, constructed with an eye to the intellectual excitement they generated.

Also, the article is not just hand-wringing: he proposes action that the academic community could take in response to the current malaise.

pensions strike

2011-12-05T03:42:00.000-08:00

Considering whether the UCU should have joined the general strike last week over public-sector pensions, there’s a weak argument in favour and two stronger arguments against.

In favour: while it’s true that universities have undergone creeping privatisation over the past few decades (and in a technical sense, never were public-sector in the first place), this process has not been welcomed by most people who have anything to do with universities, most of whom have a public-service ethic. Unfortunately we’ve all been dragged kicking and screaming into a social contract we never signed up for. Under these circumstances, the strike looked like an opportunity to show that we believe in the public-service ethic.

The case against: We’re not in the public sector and more importantly, neither is our pension scheme. The above clip from a Guardian web page shows UCU placards in defence of better public-sector pensions. Indeed, I saw a few such placards in the flesh last Thursday. The point of using a clip from the Guardian rather than just taking a photo, is that it indicates that the UCU is managing to put about the incorrect message that the universities’ pension scheme (the USS) is a public sector scheme.

The other reason — more important to me — is the inter-generational contract. Fundamentally, a pension is a legal claim to the fruits of someone else’s labour, namely the next generations’. Consider this article in the Guardian, which reports the surprising finding that

When asked to select which generation's needs should take priority in terms of sharing the Earth's resources, the majority of people (64%) say that "all future generations" should take priority rather than "my children's generation" (13%), "my generation" (13%) or "my grandchildren's generation" (7%).

At least, that’s what we said in response to an opinion poll, along with general agreement that Government policy is too biased towards short-term gratification. But, when push comes to shove, it seems that we go on strike to stitch up a better-paid retirement at the expense of the next generation, who have just been lumbered with unprecedented tuition fees, and a poor job market, and a worsening housing shortage. The “ intergenerational theft” narrative is easy to criticise, but it makes as much sense as the “bankers crashed the economy and made off with ill-gotten gains” narrative. This article at the Intergenerational Foundation describes the problem very effectively. Maybe I’m sensitive to it because, in this story, I’m one of the villains.

new PhD

2011-11-30T14:47:00.000-08:00

Congratulations to my soon-to-be-ex PhD student Neelam Gohar, who passed her PhD viva today. Neelam came here from Pakistan with a government scholarship, and has a teaching position at a university there. Her thesis studies the properties of sequences of tactical or manipulative changes of vote, in the context of voting systems where each agent maintains a declared preference amongst the alternatives, and may change their declared preferences in response to those of the other voters.

Work to rule your HEI

2011-11-14T03:59:00.000-08:00

A flurry of stickers on the university’s car-park entry barriers carry the slogan “Hands off our pensions”, a current campaign by the UCU. This has resulted in an action called a work-to-rule. When I first heard the phrase, I thought “rule” was a verb, and you were supposed to parse it like “play to win”, but it actually refers to the practice of doing the minimum work stipulated in one’s contract of employment, which is a tricky notion in the context of academic life. I’m not sure it’ll do the pension scheme any good, but it has the interesting side-effect of shedding light on the general ‘academic experience’, the way diverse academics perceive the job. This page has links to some press coverage, including one to this article in the Guardian, which (along with the readers’ comments) provides insights into the way academics manage their time, and the pressures they’re under, attitudes to research (do you do it because it’s part of the job description, or because you can’t stop yourself doing it?), and whether we perceive ourselves to be working for a specific university, or for a research community. That raises the question of whether it makes any sense to take any form of industrial action.

The article also highlighted the grey area between work, and stuff that’s vaguely related to work but isn’t, talking of which... On Friday I read this panel discussion on the future of universities, also in the Guardian, of particular interest since Lance Fortnow was one of the panelists. Does reading that stuff constitute work? You can make the case that if you know what the future holds, you’ll serve your own institution better. Then again, you might just conclude you should get a job at Google. Anyway, the introduction to the panel discussion read:

The way universities deliver learning, see their role in society and fund their activities is changing fast. But what will HEIs look like in 2020? Join our live chat Friday 11 November

Anyway, to be honest, the discussion was a bit of a disappointment. I guess the warning lay in that usage of “HEI” (that’s ‘higher education institution’.) I’ve never seen an interesting passage of text that contains the abbreviation HEI. Just as slang and colloquial words serve the purpose of flagging up informality, “HEI” connotes a dreary managerialism. More seriously, I think the problem with the discussion is that it focused on the impact of political trends on universities, rather than the more interesting economic ones (e.g. the globalized academic job market, and whether China and India will produce more prospective students, or recruit more academic staff), and it also missed out on the even more interesting technological trends, such as whether the internet will take over from traditional teaching methods like lectures.

notes from FOCS

2011-10-24T19:36:00.000-07:00

There’s a table with free copies of the proceedings of FOCS 2010 and FOCS 2001, but there are not so many takers, seemingly. FOCS 2010 is a muddy green colour, and are the last paper proceedings — the proceedings of FOCS this year come on USB sticks, not paper, saving me the weight on the return trip, and also cutting down the cost of producing the proceedings to about $1,000, as mentioned during the business meeting. I believe that it’s the privilege of the local organizers to choose the colour of the proceedings, but I don’t know if the lime-green colour of the USB follows that tradition.

The conference had 236 registrations of which 82 were students. The number is similar to recent years. 85 papers were accepted out of 283 submissions. The Machtey award was awarded jointly, likewise the best paper award. (Really, we should maintain some central web page with a list of who won them; for the former there’s the wikipedia page, but at the time of writing it has not been updated for 2011. For the latter, when I googled for “FOCS best paper 2011” I got pointed to this blog post of Claire Mathieu of 1st April 2011, which featured prominently in Rafi Ostrovsky’s overview talk at the business meeting, but does not identify the relevant papers.) The business meeting featured an extensive discussion of how the conference should adapt to better serve the community: the format hasn’t changed much over the years, meanwhile things like arxiv have taken over some of the functions of conferences. The desired state of affairs is that lots of people would attend even if they don’t have papers there. Maybe next time we should have poster sessions, open problem sessions, that sort of thing. (Maybe the proceedings will be supplied in a shared Dropbox folder, USB sticks are getting a bit passé...)

I attended the tutorial talks on Saturday: I liked Kirk Pruhs on “Green Computing Algorithmics”: you want to save energy expended during computation; unfortunately there’s unlikely to be a very distinctive theory in which energy joins time and space as a resource you try to minimize; since computation can be made reversible there is no thermodynamic reason to lower-bound energy requirements; a “big-O” theory of energy would treat it like computation time. On the other hand, there’s still a “mother lode” of algorithmic problems relating to architecture-dependent scenarios.

Project Waterloo

2011-10-05T09:45:00.000-07:00

I tried playing Microsoft Research’s Project Waterloo on Facebook; details are here, see also here. It’s a Colonel Blotto game: each player (there are 2) has 100 soldiers that he uses to attack 5 hills¹, and you capture any hill if you attack it with more troops than your opponent. In each round you divide your soldiers between the hills, doing your best to guess how the opponent is dividing his, and you win the round if you capture 3 or more hills. Quoting the MSRC site:

The game is complex from a game-theoretic perspective, involves randomized strategies, and can be approached by reasoning about the opponent's reasoning. We have also found it to be fun, engaging, and slightly addictive. It is thus a great test case for studying actual strategic behaviour of people on Facebook.

I’m wondering whether it’s meant to be straightforward to devise an optimal strategy... it’s a zero-sum game, the catch is, there’s a large number of pure strategies — but do you have to mix over a large number of pure strategies (to guarantee to break even over time)? Maybe there’s a set of 5 good numbers (e.g. 34,26,21,15,4) that work if you allocate them at random to the hills; those suggested numbers look like a good bet against opponents who split their troops about equally amongst 3,4 or 5 hills.

Next I start thinking up ideas for improvement, usually after losing a round... how about a multi-round variant, in which the surviving troops get to defend the hills they captured? In a subsequent round, a defender would cancel out (say) three attackers, and you are allowed to send additional troops to a hill you already captured, in which case, you have to cancel them out with opponent’s attackers, and if any survive, they add to the defenders of that hill. It looks like eventually, all hills will end up with so many defenders that further attacks should be futile, but there is no guarantee of how long it will take to reach that state.

¹“Hill” comes from the Gross and Wagner paper linked-to in the Wikipedia page. More abstractly they are sometimes called battlefields or sites.

more on tuition fees

2011-09-26T05:25:00.000-07:00

What should we make of Labour’s newly-announced policy on tuition fees (BBC news article, Guardian article)? If we’re meant to be grateful that they’re less than the current fees, then all I can say is, if this is game theory, I find it extremely depressing. I recommend (most of) the comments that Guardian readers appended to the Guardian article linked-to above.

The fee cut is said to “fully-costed”: it is paid for with some sort of graduate tax on high-earning graduates, and a raise in tax on banks. In which case, they should explain why the following measures quoted from this article, are completely uncosted:

His [Ed Balls] five-point growth plan includes:

Repeating the bank bonus tax - and using "the money to build 25,000 affordable homes and guarantee a job for 100,000 young people"

Bringing forward long-term investment projects, such as schools, roads and transport, to create jobs

Reversing January's "damaging" VAT rise now for a temporary period

Immediate one-year cut in VAT to 5% on home improvements, repairs and maintenance

One-year national insurance tax break "for every small firm which takes on extra workers, using the money left over from the government's failed national insurance rebate for new businesses"

How come all the above goodies don’t have to be paid for by some other revenue-raising measures? They simply can’t have it both ways.

On a happier note, this article argues that by cutting tuition fees, you reduce CPI inflation, which in turn reduces the amount the state needs to pay to pensioners and welfare claimants. To the extent that maybe a cut in tuition fees automatically pays for itself!

(Added 28.9.11:) Meanwhile, we have an alternative white paper produced by a campaign led by senior academics... but where has the UCU gone — why are they not joining in? Now that Labour want fees nearly as high as the Tories, can we expect the UCU’s opposition to fade away?

Planning travel is a time-sink

2011-09-08T08:07:00.000-07:00

To get started on a happy note, here is a picture of me at the Xerox Research Centre Europe (XRCE), Grenoble, last week. Many thanks to Onno Zoeter, Guillaume Bouchard, Chris Dance and Shengbo Guo for excellent hospitality and stimulating discussions.

When taking any trip, booking the flights etc takes a significant amount of time. It was a particularly big problem while planning my trip to FOCS. FOCS is in Palm Springs, a place which I had heard of already since it gets a mention in I had trouble in getting to Solla Sollew. Too many decisions, is the problem. The narrator of IHTIGTSS wouldn’t sympathize, but he never had to ponder the relative merits of a more direct flight versus a longer trip by shuttle bus, or what are the best arrival/departure times. He never had to make any bookings, either. Endlessly refining searches on kayak, you know that a great itinerary is out there, if only you could find it.

I was reminded of this talk by Kevin Leyton-Brown, who also (via Google+) drew my attention to decision fatigue. The talk was about a model of economic decision making in which the agents incur a cost for assessing the value they attach for some outcome. It makes sense that one should indeed incur a cost for evaluating one’s own valuations. Decision fatigue means what you think it means.

On a related topic, I learned that I’m not allowed to charge any kind of seat upgrade to the research grant that pays for this trip; even some kind of “premium economy” is off-limits, never mind business class. In light of the above, maybe I should be glad to have my choices limited, but it’s a worrying restriction; if economy class travel continues to deteriorate in quality, that will become quite a big deterrent to attending conferences overseas.

Easychair never forgets!

2011-08-30T22:35:00.000-07:00

When I log on to Easychair and select “My conferences” it returns a list of thirteen conferences (going back to 2007) with which I’ve been involved with in various capacities. If you were chair, you get to see everything that was submitted, and what the reviews were. A PC member can see all submitted papers, and discussions on the papers he/she was assigned. For some conferences, it seems like a PC member can in fact see the reviews of all papers; I guess it depends on what settings were originally chosen by the chair. Thus, if you submit a flakey paper to a conference that used easychair, and you got a well-deserved rejection, it remains possible for various people to log on subsequently and roar with laughter as they review your ineptitude.

Actually I quite like easychair; I even like the fact that it’s possible to dig up some vaguely-recalled paper that you reviewed in the past. But it may be a matter of concern to some people. It seems like the chair(s) of a conference/workshop can delete any submissions to that meeting, but I don’t see an obvious facility for cleanly closing the book on discussions that have served their purpose. My question: does anyone think it’s a problem that all those rejected papers and discussions continue to be available, year after year?

Disappearing money

2011-08-20T16:52:00.000-07:00

This post relates to a minor gripe about academic life, and since it has not arisen for me very recently, now is a good time to air it. While money always tends to disappear, there’s a certain kind of money that disappears automatically, much like the leprechaun gold in Harry Potter. By way of example, some time ago I had some cash, or rather my employer owned the cash on my behalf, and it was available to be spent on business travel or equipment. Then one day my employer said: you must spend it all by such and such a date, after which you lose the money¹. So, I bought a laptop that I didn’t really need, and underused it subsequently. The result of slapping a use-by date on the money was that it was used less effectively.

A colleague of a colleague (OK, this is like “friend of a friend” but never mind) had to urgently find a PhD student to fill a place he or she had; due to time pressure the CoaC would accept even a weak candidate. More time would presumably let the CoaC find a stronger candidate. Funding agencies impose onerous time constraints on grants — researchers rush to spend against grants that are about to expire, or make suboptimal hiring choices due to time limits.

This is not to argue that funds should be held by researchers on a completely open-ended basis. Presumably such funds were awarded at a time when there was evidence that the researcher would use them effectively, and the longer you wait, the less certainty there is that the usage will be effective. But there is scope for discussion about the length of deadlines, which would probably result in longer deadlines. Better yet would be an acknowledgement that these kind of deadlines result in an unnecessary all-or-nothing situation, where there is scope instead for a smooth transition between one extreme and the other. An institution could tax unspent money at some fixed rate, if inflation is not depreciating it fast enough. How about using Chiemgauer notes... see this recent article in the FT, or from this web page:

The "Chiemgauer" currency (named for the Bavarian region of Chiemgau) is the most successful to date. The project was started by Christian Gelleri, a Waldorf school teacher, and six of his students in Bavaria in 2002. The regional currency's annual turnover climbed to an impressive €1.5 million ($2 million) last year. About 90,000 Chiemgauers are currently in circulation. Unlike the Urstromtalers, they can be converted back into euro for a fee. "Our currency circulates three times more rapidly than the euro," says Gelleri. But in order to achieve this, the system puts pressures on currency holders to spend: The Chiemgauer loses two percent of its value every three months and has to be "topped up" by purchasing a coupon.

The idea for a so-called "depreciative currency" was pioneered by Silvio Gesell, a German merchant and social reformer. Gesell witnessed a serious economic crisis in Argentina at the end of the 19th century. He explained it in terms of excessive hoarding and insufficient monetary circulation. His solution was to make money perishable like other commodities -- bank notes, he believed, should "rust."

There’s an analogy with the way we impose deadlines on students to hand on coursework. There are two ways to penalise students who are late, both of which I have experienced. One of them is to give them zero credit if they miss the deadline. The other way to penalise at the rate of (say) 5% per day of lateness. Of course, the first of these leads to tedious disputes about whether a coursework submission should be deemed to be handed in on time. Under the second regime, if a student is slightly late and has a weak excuse, he takes the 5% penalty and hopefully notes that the way to be sure to make a deadline is to get the work done some time in advance, without getting pushed into making excuses in order to avoid wasting the work he wanted to turn in.

¹Of course, it doesn’t really vanish; it reverts to the employer/funder, which hopefully puts it to some good use. But there’s a widespread —and rather regrettable— attitude that it vanishes entirely.

Staying connected

2011-08-18T10:29:00.001-07:00

I did not write any email during a vacation over the last 10 days. I occasionally checked my inbox for messages of the reply-to-this-or-you’re-fired variety, and so watched the inbox backlog build up, with the same kind of gruesome fascination with which I watched the stock market. Is this failure to reply to emails in violation of a social convention? Plenty of academic colleagues seem to send email while on holiday, but I reckon it’s a behaviour that’s fairly specific to academics.

In support of answering emails while on vacation, is the notion that you let the world know that you’re a virtuous workaholic, and (by being online at all hours) a truly modern academic. In opposition, there’s the point that we end up cultivating the expectation that we answer emails promptly, without in fact gaining any credit for workaholism. Email gets in the way of deep thought. I know one distinguished academic — now retired — who insists that he got all his best ideas while holed up in his vacation retreat, since it had no telephone. Also, while the post-vacation hangover is no doubt painful, email is most efficiently dealt with in batch mode rather that on-line. Indeed, some of the problems that were emailed to me had fixed themselves before I had time to assist (some feedback forms were lost, then found, for example), and some of the documents colleagues sent me got superseded by later versions that were re-sent a few days later. Finally, by ignoring your inbox you take a valiant last stand against the fate of being a truly modern academic.

(added later:) Recent article on “worliday” — not sure the word will catch on though.

ICEC, ACE

2011-08-05T03:01:00.000-07:00

I went along to some talks at ICEC 2011 here at Liverpool, including an interesting invited talk by Robert May on Stability and Complexity in Banking Ecosystems, along with some others in the general area of agent-based computational economics (ACE). A lot of this research is experimental: you set up a virtual marketplace along with traders who compete in it, then “The modeler then steps back to observe the development of the system over time without further intervention” (to quote the wikipedia page).

Of course, current economic problems serve to motivate this topic a great deal and perhaps will cause it to attract a bigger share of research funds, over the next few years. Robert May's talk reported on some experiments involving models of interbank lending aimed at predicting the spread of bank failures, along with some basic (by the standards of most theory people, I would guess) calculations of how the probability of systemic failure is affected by the extent to which banks diversify their assets. Another talk that I went to, compared two markets in which traders bought and sold a single good: one version was a centralised market in which a single price was maintained, while the other version worked by bringing together pairs of traders at random, and a trade would go ahead if the trader with higher value, could afford to buy from the other one. The latter version does not perform “price discovery” so effectively, since trades can take place at the same time at different prices, but there’s apparently a sense in which it’s more stable. Also, incompetant traders get “weeded out” in the decentralised version since they get ripped off, while in the centralised version they can free-ride on the wisdom of the crowd, due to the single current price. You may or may not consider that to be a good thing. The trading strategies were produced by some kind of evolutionary algorithm in which the poorly-performing ones get eliminated while the good ones prevail (and maybe get mutated, I can’t remember).

I would conjecture that there is scope for the theory community to contribute to this research area, somewhat by analogy to Ingo Wegener’s work on genetic programming: genetic and evolutionary algorithms was purely experimental, and he and co-workers contributed the first proofs of performance guarantees for some of these. Such a contribution could help to guide experimental design in computational economics, or address concerns about the realism of the models used in simulations.

Here is a video of an earlier similar talk by Robert May.

A laundry list of observations about blogs

2011-07-27T01:29:00.000-07:00

The following have been building up over some time.

If you read blogs but wouldn’t want to write one, you may still want to consider making a “passive” blog that contains the ones you read, since it’s great to automatically get a list of them ranked by how recently they were last posted to.

If you want to kill yourself and make it look like you are still alive, simply write up a few blog posts and use the “post options” to cause them to be published at whatever times you like in the future, that way you continue to blog from beyond the grave.

The great thing about blogs, in contrast with Facebook, Google+ etc is the simplicity of the contract between writer and reader: anyone can read your stuff without having to sign up in any sense. There are no nasty surprises in privacy settings. It’s true that Google+ allows you to declare some of your ramblings to be public, but that’s not the same somehow.

Putting together a blog post is quite a satisfying work of craftmanship¹; I couldn’t get the same feel from using Twitter, although I see there may be an interesting challenge to packing some observation into 140 characters.

Studying one’s pageview statistics can get rather addictive if you’re not careful. Blogger lets you pull up very detailed charts showing pageview history, which web sites, countries etc produced the pageviews, etc.

When I set up my Google+ account, it integrated in my picasaweb photos, which turns out to mean the pictures that I have in the past used to illustrate blog posts. Along with other stuff I had forgotten about (like some stuff on Google docs), all of which I found a bit spooky.

¹this post being something of an exception

Conferences becoming like journals?

2011-07-24T15:11:00.000-07:00

A recent post (on spotting bugs in papers) at Claire Mathieu's blog reminded me of something a colleague told me recently: he noted that conferences are requiring more mathematical rigour from submitted papers, than they used to (say, about 10 years ago). Where previously we could get away with “proof (sketch)” there is now a stronger expectation that the whole thing will be written down, either in an appendix or on Arxiv. If we make a mistake we now face rejection; no longer do we just try to convey the general idea, but it’s required that the details be done correctly. My own limited experience agrees with the theory that this is a trend, but I am mainly just passing on hearsay. (Let me know if you think this is indeed a trend.)

This all seems fine, and yet... I have concerns. The main one is the risk that conferences threaten to usurp the traditional role of journals, in purporting to showcase papers that are guaranteed to be correct. The traditional life cycle of a paper envisages a conference version that publicizes the idea, which results in the author(s) receiving feedback on the paper, that may inform or contribute to a subsequent journal version, whose main purpose is to be correct, in some cases setting the record straight if there are bugs in the conference version. If we’re going to insist on correct conference papers, it raises the question of whether the guarantee is as strong as it is for journal versions. If so, there is no point in the journal paper.

Should we mind if a few conference papers are buggy? I’m not sure that’s such a big problem. If the paper attracts interest it will receive sufficient scrutiny to detect errors, and furthermore will be submitted for journal publication (as warranted by the interest it attracts). Thus, a buggy paper will either get exposed, or else no-one will read it. Moreover, is it even desirable that our literature should be entirely pure — is there not room for the human factor to obtrude? There is mild entertainment to be obtained from the occasional reminder that a paper may have been driven by over-enthusiasm on the part of its authors, and it can be reassuring to see that even our more esteemed colleagues sometimes get things wrong.

Higher education white paper

2011-07-14T05:21:00.000-07:00

Wikipedia tells us that a white paper is “an authoritative report or guide that helps solve a problem”. Some of us might say that Students at the Heart of the System poses a challenge to that definition. I don’t have time to read it, but I did take a look since the various article in the press are not very informative. There’s an executive summary of sorts here, but it’s a bit one-sided.

At the beginning of the white paper, we read:

Higher Education is a devolved matter in Scotland, Wales and Northern Ireland so this is a White Paper for England. [...] All facts, figures, policies and actions refer to England only, except where stated otherwise. “National” should be taken to mean England-wide except where the context indicates otherwise.

(I feel a twinge at this. Maybe we should not care about national identity, but when it comes to Higher Education, England always gets the thin end of the wedge.)

My interest was in the way student numbers are to be managed. The discussion of this topic was done with reference to the current system under which universities get quotas of students. The quota system is portrayed by its critics as providing universities with a captive customer base, relieving them of the need to compete, and disallowing any kind of market to guide student recruitment. That is not quite fair; back when I was at Warwick, for a while Computer Science was getting far more prospective students than we could take, and we (the university) applied to HEFCE and got the quota increased. But, admittedly it was slow, and I think it was a collective university quota that was raised; it was left to the university to expand the department and I have no idea how much attention HEFCE paid to that process. Naively, if you’re in a system where “the funds follow the students” it looks like popular institutions would be able to expand to meet demand, and unpopular ones would contract, all of their own accord.

If I’ve got the right general idea, that principle is to be applied to students who get AAB or better at A level (see paragraph 4.19 of the paper. There are about 65,000 such students (out of a total national annual cohort of about 480,000). Student quotas get scaled down to cover the remaining 415,000 places, and presumably if your fraction of AAB students is below average, you lose out, and if it’s above average you could expand. But there are plenty of unanswered questions, and paragraph 4.12 notes that “the sector” is being consulted on the details. (So, some of the vagueness in reports on this document stem from lack of conclusions it has, in some respects.)

Some forecasts: much wrangling about who should count as a high-achieving student: AAB at A level does not address the “widening access” agenda: students with non-traditional qualifications lose out. Since some A levels are considered better than others, there will be discussion about whether A level grades should be deemed to be the same, or not. A potential boost for General Studies if they’re all deemed the same. With regard to a further 20,000 places to be assigned to institutions that charge less than £7,500 on average, after various discounts: an unexpectedly high number of institutions could claim eligibility for those. That is because the rush to charge £9,000 was partly based on the understanding that the effective fee will always be less, together with the fact that £7,500 is needed to break even. So, places that announce £9,000 may often just be expecting to get £7,500.

This article in the Times Higher provides a robust criticism of the white paper. Here’s a quote:

The intention to place teaching on a par with research is laudable, but this cosmetic fix short-changes everyone. A document that has been touted as putting students in the "driving seat" sounds good in theory, but there is a reason why young drivers pay high insurance premiums: they have a high risk of coming unstuck because they lack experience of the road ahead.

A contrasting article at the Adam Smith institute blog points out that Adam Smith went to study at Oxford and was dismayed that the professors were not being incentivized to teach. He approved of the system at Glasgow, under which he taught, and was paid, in some sense, directly by the students. But this seems to be an argument against “putting students in the driving seat” — if Adam Smith got it wrong, why should today’s students do any better?

Prepayments on student tuition fees

2011-07-11T05:41:00.000-07:00

There is pleasure (but not much) to be had from the spectacle of a Government department caught up in a web of its own contradictions. The Dept of Business, Innovation and Skills (BIS) is currently consulting on whether there should be a scheme for early repayment of tuition fees, and what should the rules be.

Recall that the current plan is that interest on student loans is to be charged at Retail Price Index plus 3%. BIS say:

We are committed to the progressive nature of the repayment mechanism. It is therefore important that those on the highest incomes after graduation are not able unfairly to buy themselves out of this progressive mechanism by paying off their loans early. That is why we are consulting on potential early repayment mechanisms – similar to those paid by people who pre-pay their mortgages.

This quote is an admission that the Government is rubbing its hands at the prospect of lots of lovely interest being paid on their loans, and don’t want to let people pay them off early. The word “progressive” has been hijacked to refer to a scheme for keeping us all in debt for as long as possible. (Should people who can buy houses without mortgages be prohibited from “unfairly” buying them without incurred interest payments?)

Digging deeper into the consultation document, we get:

These mechanisms would need to ensure that graduates on modest incomes who strive to pay off their loans early through regular payments are not penalised. For example, a five per cent levy might be charged on additional repayments each year over a specified amount such as £1,000 or £3,000. Alternatively, those on higher incomes (e.g. over £60,000) who made an additional repayment could be required to pay a five per cent levy on this sum.

Further down, they admit that there’s a case in favour of allowing early repayments, in that “It allows graduates on modest incomes to pay off their loans early.” Here they flat-out contradict themselves by admitting that people should actually be encouraged to pay their debts. Provided, that is, you’re on a “modest income” — if someone who could actually afford to repay tries to do so, well, that would just not be cricket.

I could go on, but there’s no need to; for anyone who wants to read further criticism there are some good responses on the web site; I recommend the comment by Tim Leunig.

hat tricks

2011-07-06T10:30:00.000-07:00

Among many things the internet has been blamed for, is the phenomenon of people only ever reading stuff that they agree with, and thereby reinforcing their opinions without having them challenged. By analogy, do we spend too much time hanging out with our familiar research communities? At the 23rd British Combinatorial Conference, to which I was invited to give a talk, I now have to struggle to come to terms with research on topics that have obvious computational questions, but where it’s other questions that get considered.

One talk was on a topic that is, at a stretch, vaguely game-theoretic: “Hat problem on a graph” by Marcin Krzywkowski relates to a kind of puzzle described here¹, in particular the 3 hat problem. Three players are fitted with hats, each hat may be either red or blue, the colour chosen uniformly at random. Of course, you can see the other players’ hats but not your own. Each player may (simultaneously) make a guess as to his own hat colour, or else abstain from guessing. They win if at least one player makes a correct guess and no player makes an incorrect guess. For this 3-player case there is a simple guessing scheme whereby their win probability is 3/4. As hinted in this version of the puzzle, if the players can flip coins, there is a randomized scheme that lets them win with probability 3/4 even if the hats are allocated by an adversary — but the adversary should not be able to eavesdrop on their coin-flipping before they get fitted with the hats. (A question: suppose the adversary can eavesdrop on them beforehand but then they can flip coins after the hats have been fitted. The players can win with probability 1/2 by delegating one of them to guess at random. I don’t think they can do better and would guess there should be a nice proof that even works for any number of players, but haven’t figured one out.)

Back to the paper — suppose there are n players and suppose that there are some restrictions on which players can see each others’ hats. It is natural to represent this with a graph on the players, in which a player can see only his neighbours, so that the basic hat problem would assume the complete graph. Then, one can ask how well the players can do for various kinds of graph. If I recall correctly, the players can win with probability 1/2 if the graph is a path; other kinds of graph are also considered.

¹I thank Sophie Huczynska for drawing my attention to this web site.

Computer games as a lens on higher education policy

2011-06-20T10:50:00.000-07:00

Trying out the Facebook app "global warfare", it seems that a player can equip his town with various facilities, one of which is a university. Of course, my own biases being how they are, I promptly acquire one and proceed to spend all my resources on upgrading it (which is not something that usually happens in real life, but computer games are there to allow players to indulge their fantasies). Anyway, given a university, a player can then click on "research" and select from a list of topics to devote one's (virtual) academic efforts. Unfortunately, "computational complexity" was not on the list. Instead, I settled for "drilling", which when completed, causes your oil production to increase by 10%. This helps to make sense of the various calls for proposals that emanate from EPSRC; I have a vivid vision of our political leaders clicking on topics like "construction" or "military science" in an effort to obtain a quick reward. Maybe next time I will select "espionage" which could perhaps lead to cryptography, and thence to computational complexity.

nchum

2011-06-06T04:58:00.000-07:00

Taking a break from marking exam scripts, I am intrigued by this new story about the New College for the Humanities, www.nchum.org, reported at the BBC: Academics launch £18,000 college in London, the Guardian: Richard Dawkins heads line-up at private £18,000-a-year university (with howls of dismay in the comments), discussed at Mary Beard's blog here (with some skepticism that I share), and see this new post at the Exquisite Life blog for some more sensible skepticism: “rushed and half-baked”.

I first spotted the story yesterday in a headline in the Sunday Times while at the supermarket, a clue that while this story has sprouted legs, it is not going to go the distance. Surely we should have had some preliminary reports in the Times Higher ages ago (they now highlight it: Top names, top whack: new humanities-focused institution to charge £18K fees".) A new venture of this nature is something that will be interesting to watch; I am not dismayed like the UCU (Launch of new private arts and humanities college is proof government is entrenching 'inequality'), but....

Various things don’t quite compute. For one thing, the numbers. 18k per student isn’t enough to bring in all these top academics, at least not with the sort of commitment from them that might be imagined by an uninformed reader. The USA has better options. Plus, the people who invested in this venture will want some return on investment. The name of the web site seems... poorly considered. “nchum” will get pronounced “en-chum”... also, why use the .org suffix as opposed to .edu, or .ac.uk? Over at the Daily Telegraph, Boris Johnson is still enthusiastic:

The trouble with Britain today, he [A C Grayling, the new master of nchum] said, was that we simply didn’t have enough elite university provision – and especially not in the humanities subjects, where teaching budgets are under such pressure.

But, that’s got more to do with the definition of “elite” — the whole point of elite provision is that there shouldn’t be enough of it. If you create more elite provision, you end up killing the thing you love.

All right, back to the marking.

(Added 7.6.11: this article raises the above financial concern in more detail. This critique of the "money-grubbing dons" has attracted over 500 comments but doesn't address the concern about viability.)

Watching one’s own talks on video

2011-06-01T14:48:00.000-07:00

For readers who don't get beyond the first sentence, the take-home message is that it’s a great idea to watch videos of your own talks, for the purpose of improving your style and presentation.

The papers we write are very restricted in format. Indeed, a paper is pretty much determined by the result you’ve obtained. You get to name the variables, but that’s about it. Thereafter, you follow the well-worn path of introduction, model, results, and conclusions.

Contrast that with the activity of giving a talk on the work. Do you make jokes? Do you dress up? How much technical detail do you include? Do you compromise on accuracy for the purpose of conveying the intuition? Do you include cute animations in your slides? Do you stand primly to one side of the screen, or do you prefer to pace around? Do you sound informal and chatty, or grand and authoritative? Do you memorize any key passages? Decisions, decisions!

And, there are no right answers to the above questions; the answer depends on who you (and the audience) are, and what you’re talking about. Different approaches work for different people. And here’s where watching oneself on video can help.

I watched the video of my talk at the iAGT workshop mentioned in the previous post (and also here :-). And —this is the key point— various mistakes in the delivery of which I was blissfully unaware were suddenly exposed to the harsh light of day as a result. I then tracked down a video of a talk I gave at Microsoft Research (Cambridge) a few months ago, just for the purpose of gathering more data. The only previous time I watched myself give a talk was at a training session on lecturing quite a while ago, where a group of us had to give short fragments of undergraduate lectures, that were recorded and played back. At the time, the equipment was cumbersome and analogue, so you did not get to study your performance at leisure, at a later date. Also, it’s worth taking in a video lasting half an hour or so, to see if your style changes over time.

As it gets more common to record talks, you hopefully get more chances to do this. If not, maybe you should get a colleague to record one of your undergraduate lectures, or any other similar technical presentation.

iAGT workshop, May 22nd-26th

2011-05-29T05:34:00.000-07:00

I just returned from the workshop on Innovations on Algorithmic Game Theory at Hebrew University, Jerusalem. This blog post is to warmly thank the organisers, Noam Nisan and Michal Feldman and the student “volunteers” (that phrase with its inverted commas appeared on their offical T-shirts, along with a picture of a chess pawn). (Noam himself has not so far mentioned it at his blog; I guess that being too busy would be a valid excuse.) Anyway, it was a great meeting, indeed at a time when there is much to complain about academic life, a reminder of why I went into this business (ie, you get to meet up with interesting people and exchange interesting ideas). Later I’ll hopefully get around to discussing in more detail some topics that came up. There are videos of the talks and panel discussion here (and here is the link to presentations 21-37).

SAGT and WINE

2011-04-30T13:47:00.000-07:00

In the unlikely event that someone reading this hasn't already read it at Noam’s blog, I was also asked to publicize them, so here goes. Publicizing them here may, at least, help to boost their rank in Google searches, which is especially worthwhile for WINE.

Giuseppe Persiano asked me to post a reminder that the submission deadline is coming up (May 9th) for SAGT 2011, the 4th international Symposium on Algorithmic Game Theory (meeting in Amalfi, Italy, Oct. 17-19). Edith Elkind asked me to advertise WINE 2011, the 7th Workshop on Internet and Network Economics (submission date July 31st; meeting in Singapore, Dec. 11-14).

AV referendum: it's the results, stupid!

2011-04-28T03:30:00.000-07:00

Winston Churchill said "However beautiful the strategy, you should occasionally look at the results." But, that observation has had little impact on the debate about which voting system to support in the forthcoming referendum. That is to say, there is much discussion about which voting system better represents the will of the people, or would give us strong versus weak governments, or would make our MPs work harder. But those us who support AV should address the possibility that the present voting system may, despite the objections, actually produce good outcomes. Where "good outcomes" does not mean strong governments or representative governments, rather it means social welfare.

At the risk of coming on like David Cameron, my general impression is that the current system has let us down. Right now, being a citizen of the UK makes me feel like a shareholder of a company that is underperforming, and I'm watching its price steadily go down. My sense is that we're getting things wrong where other countries are getting them right. This is not the place to review examples in detail— in contrast to David Cameron I'll simply test out this claim by taking a look at the obvious evidence: our performance in quality-of life rankings. The results do not reflect well on the status quo!

2007: down 2 places to 17th; 2010: down 5 places to 25th; 2009: quality of life poor relative to other EU countries 2009: child poverty: European league table: The UK came 24th, well below countries of similar affluence (despite 10 years of a Govt that supposedly tried to improve it!) 2008: Zut! France leapfrogs UK in economic table

What we are seeing here is not just poor performance, but poor and worsening performance. So you can't just blame the weather! The obvious culprit is bad public policy. AV offers a genuine change to the system by which the electorate gets to influence public policy. The time has come to vote for Churchill, not Cameron.

(Added 6.5.11: OK I admit it, the reason why Britain is declining is that we just have a lower average IQ than most other places.)

(Added 6.6.11: UK slipping down the global rankings, Centre for Policy Studies warns.)

Alternative Vote referendum

2011-04-18T05:51:00.000-07:00

To see why you should vote in favour of the move to Alternative Voting on the 5th of May, look no further than the contorted arguments of its opponents. Here is David Cameron on the topic:

Too often debates about AV are less like political arguments, and more like scientific discussions, where people get lost in a language of proportionality and preferences, probabilities and possibilities.

Of course, some of these things are important. But for me, politics shouldn't be some mind-bending exercise. It's about what you feel in your gut – about the values you hold dear and the beliefs you instinctively have. And I just feel it, in my gut, that AV is wrong.

To think that we (the academic community) once had him eating out of our hands, studying for a degree on Philosophy, Politics and Economics. And what a colossal failure of education that the above is DC's take on social choice theory. Not that Oxford PPE is very strong on social choice theory; I took a look the course information page; it's a nicely-designed web site, but I think you'd be lucky to graduate with a knowledge of Condorcet's theorem. And I would like to know if anything could possibly more central to PPE.

(Added 23.4.11: This article in the Guardian contains what is for me the first sighting of the Gibbard-Satterthwaite theorem in a national newspaper. This blog post by Tim Gowers proves that by voting yes, I am in good company!)

Incentivizing reviewers to make sincere predictions

2011-03-18T07:40:00.000-07:00

I'm not sure that there's a research problem to be derived from the following discussion, but it was fun to write. Our main finding is that two reviewers are better than one, on the grounds that they can be incentivized to provide accurate forecasts of the acceptability of a paper by a program committee that is arbitrarily unlikely to read it.

We regard the reviewer’s review as a forecast of whether the paper will be accepted, rather than an input to the decision. This has the advantage that the reviewer is not required to make a value judgment on the paper; a forecast is just a guess as to whether the paper will be accepted. The obvious problem is that if the forecast gets used to help with the decision, it is at risk of becoming a self-fulfilling prophesy.

We model the paper selection process as follows. Any paper has an associated quantity p∈ [0,1] that represents the probability with which it ought to be accepted, and furthermore, this value is revealed to a careful reader. In an ideal world, the PC passes the paper to a reviewer, who reads it and reports this number p to the PC, and the PC proceeds to accept the paper with probability p. (We assume that the PC has access to an unlimited source of randomness, which appears to be a realistic assumption.)

Suppose now that a reviewer knows in advance that his review will be ignored by the program committee, who will instead read the paper and accept it with the correct probability. In that case, if the reviewer reports probability p, he/she should be given a reward of log(p) if the paper is accepted, and log(1-p) if it is rejected. (These quantities are negative, but we do not claim that reviewing papers is rewarding.) These rewards incentivize the reviewer to report the correct probability.

Now, suppose when the PC has received the review (the number p), they then read the paper with some probability r. If they read the paper, they accept with the correct probability, and if they don’t read it, they accept with probability p. The problem is that if r is very small, and the reviewer finds that the paper should be accepted with probability about 1/2, the above rewards tempt him to go to extremes and report (say) 0⋅01 or 0⋅99. Important note: the reward should depend only on the review (the reported p) and the (binary) acceptance decision, since you don’t want to reveal any secret discussions to the reviewer. So the PC doesn't have the option to read the paper with some small probability and punish him if they then find he lied.

Given 2 reviewers, we can exploit their professional rivalry to make them tell the truth, by carefully aggregating their forecasts into a single probability, as follows. A basic requirement for a reward scheme is that if a reviewer has obtained value p from a paper, and the other reviewer is truthfully reporting that value p, then the remaining reviewer should also have the incentive to do likewise. Suppose we use the logarithmic rewards above, and the PC uses the average of the 2 reported probabilities, to decide on the paper. The following problem arises: suppose it's a great paper and p=0⋅999. A reviewer might be tempted to report (say) p=0⋅5, since that way, the PC will use a probability of about 0⋅75 to accept the paper, exposing the other reviewer to a big risk of a large penalty. The assumption here is that a reviewer aims to get a higher reward than the other one (his professional rival); the reward being some sort of credit or esteem rather than money.

Let q be the other reviewer's probability, and we seek a function f(p,q) that should be used by the PC as probability to accept the paper; we have noted that (p+q)/2 is not a good choice of f, in conjunction with the logarithmic rewards.

The reviewer’s utility u(p) is his expected reward minus his opponent’s expected reward:

u(p) = f(p,q)(logp-logq)+(1-f(p,q))(log(1-p)-log(1-q))

We now notice that the above must be identically zero, since it should not incentivize the reviewer to change his mind if q is incorrect, but it should not incentivize him not to change his mind if q is correct. Setting the above to zero tells us the function f should be

f(p,q)=(log(1-p)-log(1-q))/(logq-logp+log(1-p)-log(1-q))

It just remains for the PC to read the paper with any probability ε>0, and in the event that they read it, accept with the correct probability. If they read the paper, the reviewers are incentivized to tell the truth, and if they don’t, (and use the above f) the reviewers have no incentive to lie, so overall their incentive will indeed be to tell the truth.

(Added 6.6.11: at the iAGT workshop, I heard about 2 papers that relate (so now, an answer to the first comment below). Only valuable experts can be valued by Moshe Babaioff, Liad Blumrosen, Nicolas S. Lambert and Omer Reingold, about contracts that will be accepted by self-proclaimed experts, provided that they really do have expert knowledge (and will be declined by a rational charlatan). And, Tight Bounds for Strategyproof Classiﬁcation by Reshef Meir,
Shaull Almagor, Assaf Michaely and Jeff Rosenschein, about learning classifiers where the class labels of data have been provided by agents who may try to lie about the labels. The latter paper is closer to the “self-fulfilling prophesy” situation described above.)

(Added 22.8.11: This article on “decision fatigue” suggests another reason why it may be better to ask people to try to predict the outcome than to influence it (assuming you believe it puts less strain on someone to make a prediction than to make a decision. It does sometime stress me out a bit to make an accept/reject recommendation for a paper.))

game theory/tuition fees

2011-03-03T00:09:00.000-08:00

(found some of the following links from a facebook post) this link to an attempt to write down a game that expresses the setting of tuition fees. In the comments, this link to a speech by David Willetts "The ideas that are changing politics" (dated 20.2.08, so now a couple of years ago) in which he is enthusiastic about game theory (follow the link to PDF of the speech at the bottom of the page). This new article “What are David Willetts' options for limiting spending on student loans?” is worth reading by anyone who would like to keep track of this issue. The previous article gives the text of a speech on universities made by Willetts; the speech mentions game theory, and so too does one of the annotations that have been inserted. Here’s a quote from the speech:

Of course, academics approach these issues with great sophistication, and I have been warned that we face a dilemma from game theory in which the incentives for individual institutions are different from the interests of the sector as a whole. But it's not the dilemma in its classic form, because this is not a one-off. You need to think of subsequent years – not just in terms of funding levels but also the challenges you will face from new competitors if you come in at such a high fee level. And you also need to think of the collective interests of students.

IIT student seeks internship at your esteemed institute

2011-02-22T13:53:00.000-08:00

A question: has anyone taken on one of these prospective interns? (And if so, how was it?) Most of them would clearly be hopeless, but there are some that look like they might be OK. The trouble is, there's some kind of economic principle at work here, that says that in a market that's flooded with bad eggs, the good eggs cannot be sold. In this case, what happens in that we end up deleting all these emails without reading them.

One such email that I bothered to read yesterday was typical: it claims to have read the recipient's work in detail, then goes on to profess an interest in a range of topics none of which related to anything I know about. I suppose that email was sent off indiscriminately to a large number of academics, and you might be fooled if, by chance, you have the same research interests as the ones mentioned.

I'm vaguely disturbed by the way these emails produce a kind of stereotype of these students; eventually you cease to regard them as individuals. I'm curious as to why it is Indian Institutes of Technology that produce them, and no other countries seem to do so. (I could not find much from a brief perusal of the web. Here is a related earlier discussion.)

Academia and the deterioration of jobs

2011-02-12T01:18:00.000-08:00

A recent article in the New York Review of Books, The Grim Threat to British Universities makes interesting reading since it discusses a UK problem from a US perspective. It highlights the key difference between the British and American systems, namely the vulnerability of the British one to central control and manipulation, and seeks to draw lessons that could be learned within the American one. It blames certain US business schools for generating the managerialist ideas that have subsequently beset British universities. It goes on, via a critique of research assessment, to study the growth (in the USA) in use of short-term, untenured faculty to provide teaching.

Some thoughts on the article:

It makes a mistake that is common to most polemics against the decline in academic working conditions, namely that the author has not tried to place himself in the position of his adversary, and consider how it looks to the opposition. Consider the following quote:

The growth of the contingent academic workforce brings the labor economics of the call center and the Wal-Mart store to higher education. With these contingent academics, few of whom have firm contracts, managers now have at their disposal a flexible, low-cost workforce that can be hired and fired at will, that can be made to work longer or shorter hours as the market dictates, and that is in a poor position to demand higher pay.

The problem with this observation is that the situation it describes looks pretty good to anyone whose job is not university teaching. Taken out of context, it could pass for high praise for the trend that it criticizes. I can't see call-centre workers, or most other people, losing much sleep abut the problem being highlighted. Furthermore, many jobs and professions have suffered from debasement over the past few decades. I have heard from a flight attendant about how the growth of low-cost airlines has led to poorer working conditions, poorer safety training, and more disagreeable passengers. And, a general background story of the past few decades, both in the USA and Europe, is the decline of the steady, well-paid, blue-collar job.

In the presence of a working public who have their on-the-job performance being measured and assessed in various onerous ways, it is pretty hard to rail against research assessment. And that does not mean we should not criticize excessive performance monitoring and managerialism, but let's not do it in the name of “scholarship”, and expect to be taken seriously. The following cri-de-coeur quoted from the article is not helpful:

The bureaucratization of scholarship in the humanities is simply spirit-crushing. I may prepare an article on extremism, my research area, for publication in a learned journal, and my RAE line manager focuses immediately on the influence of the journal, the number of citations of my text, the amount of pages written, or the journal’s publisher. Interference by these academic managers is pervasive and creeping. Whether my article is any good, or advances scholarship in the field, are quickly becoming secondary issues. All this may add to academic “productivity,” but is it worth selling our collective soul for?

If a flight attendant used the word “flightmanship” the way we use “scholarship”, they would be laughed out of the room. And by the way, I don't know what “good” is being used to mean in the phrase “whether my article is any good”. None of which is to say that we should give up trying to defend our working conditions, only that we should do so using the levels of intellectual rigour that we urge on our own students.

Added 1.3.11: This article is very relevant: it gives a bigger picture to the problem, explaining the general threat to “middle class” jobs in Western countries.

Added 15.3.11: just spotted this review of The Global Auction: The Broken Promises of Education, Jobs, and Incomes a book that studies this problem. Rahul Savani pointed me to this new-ish article by Paul Krugman that also considers it. Both of these seem to be about people going to university, expecting it to be their ticket to a middle-class lifestyle, and getting disappointed by the outcome. This new post at the Fortnow/Gasarch blog has relevant links, including the Krugman article, but focuses on the impact of CS/AI on future jobs.

Obscurantist jargon

2011-01-30T11:50:00.000-08:00

Nick Cohen takes academics to task for writing sentences like the following

The move from a structuralist account in which capital is understood to structure social relations in relatively homologous ways to a view of hegemony in which power relations are subject to repetition, convergence, and rearticulation brought the question of temporality into the thinking of structure, and marked a shift from a form of Althusserian theory that takes structural totalities as theoretical objects to one in which the insights into the contingent possibility of structure inaugurate a renewed conception of hegemony is bound up with the contingent sites and strategies of the rearticulation of power.

The above sentence won the bad writing contest a few years ago. Cohen takes it as evidence of academia’s failure to engage with the public, and deduces that we academics are the architects of our own misfortune through this failure.

My first thought on reading Cohen’s article was: Has he ever seen the stuff that I come up with? Loads of complicated mathematical formulae couched in the definition-theorem-proof style, surely even worse than the above. My only excuse for writing that stuff is that I was not actually trying to impress the wider public, and I never thought the above quoted sentence was pitched at the man in the street, either. Like legalese, some other people are paid to read it and determine whether it's any good, and according the division-of-labour principle advertised on the twenty-pound note, I should get on with my own work and trust them to know what they are doing.

Scrolling through the comments, I found that I’ve already been outed by fellow computer-scientist Ross Anderson who wrote

The same sorts of criticism can be made of much academic writing even in "respectable" disciplines such as mathematics and computer science... Believe me; the median paper has a tiny idea (if any) dressed up in fifteen pages of stuff that looks like mathematics.

Damn. Mind you, I would hope that most mathematics papers would indeed look like mathematics, even if it’s unreadable to most people. And let’s admit that it’s hard to come up with a major idea in every paper.

However, I can’t possibly leave the topic of obscurantist jargon without complaining about cricket commentary. They’re endlessly dropping phrases like “403 for 3 not out” without explaining what those numbers refer to, and whether it represents good news or bad news for the team being discussed. After I left school and people stopped making me play cricket, I assumed that this sort of thing was now someone else’s problem, or alternatively that sooner or later, someone on the radio would have a spare minute or two to explain their jargon to the uninitiated. But it hasn't happened yet.

Professor Fluffy

2011-01-20T03:00:00.000-08:00

Professor Fluffy is the officlal name of the mascot shown below.

We are told that universities may only charge the upper limit of £9000 per year in fees, if they commit to “widening access”, but like many aspects of the new fees regime, the details are unclear. It seems natural to consider whether scholarships could be used for this purpose, or alternatively just as way to attract good applicants, and if so, how to design the scholarships.

Yesterday Liverpool University held a kind of open-house session to discuss organisational strategy with staff, with reference to the funding regime. I went over to find out what the thinking is on scholarships; my own observation on the topic is that the university has, for PhD study, just one scholarship that is not restricted to any particular kind of applicant, and despite the fact that this particular scholarship can hardly help much to increase student numbers, it has the effect of attracting applications from ambitious students, who may then be available to pick up alternative PhD studentships.

My thought was that we should consider having one or two undergraduate scholarships based entirely on academic results that made no reference to a student’s background. What I learned, talking to our widening-access expert Tricia Jenkins, is that the idea may not apply so well at the undergraduate level. The difference is that at postgraduate level, the student is deemed to be responsible for his academic track-record, but someone with high-school qualifications is not. This refers to the well-known fact that a student from a poorly-performing school will outperform (at university) a student from a very good school, if they have the same A level grades. Indeed, apparently 3 B's at A level from a weak school is better than 3 A's from a strong school, in this sense. Consequently, if a scholarship is based on academic excellence, it should be biased this way.

The downside is, that such a scholarship could not possibly be used to attract students from good schools, no matter how smart or committed those students were. And, these scholarships would require decision-making about how exactly to design the bias in favour of certain types of applicant (it is not just about schools — should you also give a student credit for having been in foster care for some number of years?)

Anyway, I couldn't get away without learning about Professor Fluffy, who as the picture suggests is sort of a mascot, designed to attract the interest of primary-school children in going to university, based on the observation that by the time they are their teens, you've left it too late. Fluffy was born in Liverpool in 2004. Apparently he (or she) makes more money for the university than any other professor, due to licensing fees — it would appear that Fluffy is quite widespread. By now, Fluffy has a Chinese sister, Professor Long Long. And the plan is that Fluffy (along with other colleagues, tba) will shortly feature in mobile phone apps designed for young children. I don't know the details, presumably not “tap fluffy to hear her complain about the rejection of her last research grant application.”

Wikipedia hard to edit

2011-01-15T11:15:00.000-08:00

Jimmy Wales says Wikipedia too complicated for many ...from the article:

He said a lot of people were "afraid" to contribute to the site by the sometimes complicated code - known as Wiki mark-up - needed to format entries.

"If you click edit and you see some Wiki syntax and some bizarre table structure - a lot of people are literally afraid.

and a good thing too! The last thing Wikipedia needs is to get hacked about by people who are too clueless to figure out a bit of syntax.

(And congrats to Wikipedia on reaching age 10.)

EU research proposals

2011-01-12T07:54:00.000-08:00

“Don’t ever agree to serve as coordinator of an EU-funded multi-site research project” is something I have heard many times. The trouble is, if every day on your way to work, you pass a big lever with the words DO NOT PULL written on it, then sooner or later any self-respecting scientist... Right now we're still in the proposal-writing stage. Communication overhead is the fundamental problem. One's email habits start to resemble nicotine addiction (“He's a 40-a-day man, he'll be off to an early grave”).

One thing I'll note for people who criticise the European Commission for wasting money, is that projects funded by the Research Executive Agency do not, seemingly, provide much opportunity for lining the pockets of the organizations involved. Then there are various audits and monitoring which I plan to worry about nearer the time, ie if we get the grant. And, we need to have industrial partners, and schemes that add value to the Phd studentships that would be supported. I'm starting to believe that it would be a pretty good opportunity for the students.

The upside, implicit in some of the above discussion, is that it's a pretty good exercise in networking. And maybe this sort of thing is easier the second time you do it, than the first. And if it gets funded, the university gets some credit for increased research income. And it might actually result in some good research...

The submission deadline is the 26th. Whatever's wrong with the proposal at that point, fortunately I won't be able to do anything about it afterwards, and will have to move on to other things.

Another critique of tuition fees

2010-12-13T03:35:00.001-08:00

The problem with the Internet is that for nearly all topics, something is available out there that does a better job than one own's efforts could achieve. This new post at the excellent Exquisite Life blog does a great job of the criticizing the dire state of higher education policy in the UK, and should be mandatory reading for anyone who wants to engage with the associated debate. The main focus of the article is on the failure of the tuition fees to fix the fiscal problems that supposedly motivated them, and it also explains the flaws in the arguments that the fees regime is more “progressive” than the current one.

The Campaign for the Public University (which I also found out about via the Exquisite Life blog) has a collection of articles and resources on the topic.

Game-theoretic board games

2010-12-12T06:43:00.000-08:00

'Tis the season (almost) to sit around the fire playing board games and pretending to enjoy it. I recommend two board games, namely Poleconomy and Apocalypse, that I played a few times when I was a student; these came up in a conversation recently due to having some interesting game-theoretic content. I gave a talk at Microsoft Research (Cambridge) on Thursday, and Yoram Bachrach told me about the ripoff game, which has been played by human volunteers for cash prizes. Each individual game takes about one minute and works as follows. Each player is allocated a number, a fraction in the range [0,1] which is his “weight”. A subset of the players can form a winning team if their weights add up to at least 1. However, the winning team has not won the round until they have agreed on how to share the prize (worth 1 pound). For this purpose, each player gets to control another number in the range [0,1], which is the fraction of the prize that he requests from the winning team. And, the team does not win (and share the prize) until those fractions add up to at most 1. Apparently, the players sit in the same room but interact via computers, so the negotiation is somewhat stylized. Anyway, it turns out that Shapley value is quite a good predictor of the winnings associated with weights (although, there is variation from round to round, and some players are better at the game than others). A computational agent was implemented, which computed its Shapley value and then added 10%, and it performed well in competition.

This reminded me of an aspect of Poleconomy, a board game that simulates the interactions of politicians who happen to occupy corporate directorships “on the side”. (The game was developed in the early '80s.) From time to time, an “election” takes place, in which the players cast dice to determine the number of “votes” they obtain, and a Government may be formed by any subset of players who happen to have received a majority of the votes between them. There is some advantage to being in Government, so the immediate outcome of an election is a flurry of mental arithmetic and bargaining amongst the players to identify and agree upon a winning subset.

In Apocalypse, a player's move consists of a sequence of attacks. In each attack, the player chooses a number of units with which to attack another player, a whole number in the range 1...6, which is identified by placing a standard die with the chosen number uppermost underneath a cup; the player being attacked tries to guess the number. If the attacked player guesses correctly, that is the number of units that are lost by the attacking player; otherwise, the attacked player loses a single unit (and the attacking player gains a nuclear weapon, or part thereof, so there is an incentive to make lots of attacks.) Thus, each attack is a kind of generalized matching pennies, where the probability of choosing a smaller number is clearly larger than the probability of choosing a larger number, but all probabilities are positive.

Are there any other board games out there with interesting game-theoretic aspects?

CS as STEM

2010-12-01T19:27:00.000-08:00

In the Guardian, Stephan Collini imagines an alternative world where the British government is proposing to withdraw all financial support for the teaching of sciences, as opposed to humanities. Meanwhile, a recent flurry of email on the CPHC mailing list¹ addresses the status of Computer Science as a STEM field. (That's “Science, Technology, Engineering and Mathematics”.) The background being that these STEM subjects are the ones that in fact benefit from favoritism² from Government due to their economic importance.

In more detail, STEM subjects will continue to receive a fee premium from Government. CS is STEM, right? Well, maybe not, if STEM is a shorthand for “HEFCE band A or B”; CS narrowly misses out on band B, as a result of reductions in the cost of computing facilities. The Browne review hints that “priority programmes” are primarily bands A and B, with a bit of representation from band C.

The email was about lobbying for recognition as a STEM subject, or alternatively, as “strategically important and vulnerable (SIV)”. Quoting UUK report Changes in student choices and graduate employment

The strategically important and vulnerable (SIV) subjects are chemistry, engineering, mathematics, physics and some area studies, quantitative social science and modern foreign languages (HEFCE, 2010a). They are considered so in relation to the anticipated demands of the economy rather than the exercise of student choice.

While CS is not sufficiently “vulnerable” to classify as SIV, one email argued that computer programming in particular should maybe qualify, and gave some anecdotal evidence of a decline of computer programming in schools in the UK, blamed it on the teaching of ICT in schools, and contrasted it with a relatively high interest in programming in India. ICT, as currently taught here, tends to evade the interesting technical challenges and is an example of the bad driving out the good.

One lesson we should learn: if we really care about our STEM status, it's not just a matter of lobbying to retain that recognition. It's a matter of ensuring that the intellectual content justifies the claims. We need to keep both programming and rigorous mathematics right at the heart of CS.

¹Council of Professors and Heads of Computing. I sometime consider getting myself demoted so that I don't have to be on the mailing list.

²Relative, not absolute!

Student protests

2010-11-25T05:43:00.000-08:00

It's pretty hard to come up with anything very original to say about the student protests yesterday and earlier. The fact that there is no major political party here that would reverse this increase in university fees, leaves me with the sense that the protesters are praying to a god that does not exist. As an atheist, I fully acknowledge the benefits some people derive from praying to gods that do not exist, but I don't think the protests will do any good politically.

This comment article in the Guardian made most points that are worth making. This article in the Daily Mash is, I must admit, a trenchant and effective critique of the protest movement. Any case in favour of "higher education as public good" should take it into account. This blog post calls attention to the unresolved issues with the current proposals. We learn that Nick Clegg is "haunted" by his election promise. (That's good of him. I wish Tony Blair and David Blunkett were haunted by their 2001 manifesto commitment not to introduce tuition fees. Or should we all accept that making and breaking promises is the price of winning an election?)

I actually struggle to make a principled case for HE as public good. It's relatively easy to make a practical case: e.g. that there's a slippery slope -- next we'll expect people to pay for post-16 school education, and (following Dearing's logic), since the main beneficiaries of the NHS are the patients, then patients should pay back the costs of their treatment. But, the slippery-slope argument evades the question of what's wrong with high tuition fees themselves. The other practical (not principled) case is that the fees make us out-of-step with most of the industrialized world (as I hinted previously). To elaborate on that, one could accept that high tuition fees are correct in principle, but also accept that nations compete amongst each other for academic talant and skills. Hence we risk a new brain drain not just of staff but of students. Although, that may help with the government's efforts to reduce net immigration.

Universities, conservatism and Hotelling's Law

2010-11-07T08:40:00.000-08:00

I'm not sure what to make of Simon Jenkins' recent article in the Guardian, in whch he accuses universities of being lazy, wasteful, addicted to public money, and resistant to any form of change or innovation. He is probably being more harsh than he really feels, in order to provoke a reaction in the comments contributed by readers, and any reader who takes his article at face value will find that the comments that follow are a useful antidote.

Let's take the article seriously for a moment, and consider whether there is any truth in the central charge that conservatism is the driving force behind academic life. Unreasonable resistance to change is so widespread that it would be amazing if universities were free of it. You only have to look at some of the reaction to Obama's health care reforms to verify this: the hysteria, fear and anger of the rhetoric against these highly incremental reforms is evidence of a psychological disability to cope with any form of change and innovation, one that affects tens of millions of Americans.

But there's another reason why universities might not make the changes that Jenkins urges, and that's Hotelling's Law. That is the observation that in a lot of competitive marketplaces, the rival providers (of goods or services) tend to position themselves very close to each other, rather than go for product differentiation. If one provider does decide to aim at a particular section of the market (say, lower-cost goods) then in order to do so, he just offers goods at a very slighter lower cost than his rivals: he does not consider his cost in isolation, but relative to the competition. (As an aside, I'm not sure that hotels obey Hotelling's law, but other things do, e.g. political parties.)

In an increasingly global marketplace for staff and students, universities are understandably reluctant to go to extremes in order to capture some segment of that market. Despite Jenkins' call for 2-year degrees and year-round teaching, even if there is indeed a big market for those things, universities should be reluctant to go there. British ones are already taking a fairly extreme position on short degree timescales (most countries have 4 or more years for first degrees). And they are, reluctantly, taking an extreme position on low levels of state support for their activities. They are already well into the danger zone and should go no further.

complexity and elections

2010-10-31T13:20:00.000-07:00

I just read an interesting review article (Using Complexity to Protect Elections, by Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra) in the CACM on the complexity of election schemes, and various "attacks" on them, such as searching for voter manipulation opportunities. The article is aimed at a general computer-science audience, and written in quite a colourful style. It touches on a problem with this line of research, one that has bothered me since I started following its progress:

... perhaps the greatest single worry related to using NP-hardness to protect elections—a worry that applies to NP-hardness results not just about manipulation, but also about control and bribery. That worry is that NP-hardness is a worst-case theory, and it is in concept possible that NP-hard sets may be easily solved on many of their input instances even if P and NP differ.

They go on to mention the theory of average-case complexity, but it seems not to have been applied in this context. Is it ever going to be worth using a highly-artificial voting system, just to ensure that a potential manipulator gets a problem that is hard in worst case, but may generally be easy in practice? Perhaps one should look at other sources of difficulty for the manipulator, such as uncertainty about the other voters' preferences.

Added 1.11.10: Another nice survey that Ariel Procaccia pointed me to, ("AI’s War on Manipulation: Are We Winning?" by Piotr Faliszewski and Ariel D. Procaccia) — considers in more detail the problem of NP-hardness as just a worst-case problem for the manipulator, it reviews some work giving negative results, i.e. fundamental obstacles to the project of designing voting systems that are typically computationally resistant to manipulation.

SAGT 2010

2010-10-21T14:05:00.000-07:00

Here are some notes from the 2010 Symposium on Algorithm Game Theory (SAGT), mostly typed up at Athens airport. SAGT had about 60 participants and next year will take place in Amalfi, near Naples. If you want to host it in 2012 then I believe the steering committee would like to hear from you. In the following I mention some of the papers that caught my eye; it is by no means a complete overview, being biased to my own interests, plus I suspect that "conceptual" papers tend to be more eye-catching than "technical" ones.

A special tutorial session on "Games played in physics", along with one of the regular papers "Mixing time and stationary expected social welfare of logit dymanics" highlights a line of research that looks like it could go a long way. Given a game, there's an associated Markov chain whose states are pure-strategy profiles, and transitions consist of the selection of a random player, who then updates his strategy in a way that makes better responses more likely than worse ones (although, it is possible for him to switch to a worse response). Specifically, the probability assigned to a response with payoff x is proportional to exp(βx) where parameter β is the "noise rate": β=0 is entirely noisy and players move at random; as β increases the noise goes down and players prefer better responses. The solution concept for the game is the stationary distribution of the chain. The topic of interest is the mixing rate (a function of β). A connection with physics is that the Glauber dynamics on the Ising model (a topic of enduring interest in the math/CS community) corresponds to a party affiliation game where the players lie on a grid, and in the ferromagnetic version you want to join your neighbours, and in the antiferromagnetic version you want to disagree with them.

2 papers from the "Learning and dynamics" session: one is "On the rate of convergence of Fictitious Play", which I have mentioned earlier. An important point: the lower bounds on convergence rate (for 2-player zero-sum games) apply to convergence to the "correct" strategies, as opposed to convergence to the value of the game. The paper "On learning algorithms for Nash equilibria" forms part of a proposed search for general lower-bound results stating that a broad class of algorithms should fail to find Nash equilibria, even in the 2-player case. They get some negative results for iterative weight-update approaches. They mention that the question of the convergence rate of FP for zero-sum 2-player games to the value of the game is something of a long-standing open question, and seemingly the only convergence rate known is the very slow one that results from the 1951 proof of Julia Robinson.

A cute result: "Responsive lotteries" by Feige and Tennenholtz consider the problem of incentivising someone to reveal their true preference-ranking of a set of items, by awarding one of them to the person, selected from a distribution that is derived from their declared ranking. You have to design the distribution carefully.

Peter Bro Milterson's talk was about NP-hardness and square-root-sum hardness of testing equilibria for being trembling-hand stable; I like the topic since it relates to the complexity of finding equilibria that are restricted to comply with some equilibrium selection/refinement concept. The focus on the "doomsday game" example was nice, and he gave a nice overview of the 3-player hide-and-seek game of Borgs et al (The myth of the folk theorem).

2 papers on network congestion I will mention: Yonatan Aumann's talk on "Pareto efficiency and approximate Pareto efficiency in routing and load balancing games" started by noting that the concept of Pareto efficiency can be used to distinguish the inefficency of the Braess paradox network from that of the Pigou network - in the Pigou network, when you move from equilibrium to optimum flow, some but not all agents benefit, in Braess, all benefit. They continue by studying a notion of approximate Pareto efficency, focussing on parallel links. Then a very nice talk by Martin Macko studies a model of dynamic flows on networks, and shows Braess-paradox-like results... In the model, backlogs may develop at nodes in a flow network, like the build-up of a traffic jam at a junction whose capacity is lower than the rate of incoming traffic. Assuming everyone has up-to-date traffic information, there comes a point in time where some other route is preferred (and possibly, itself becomes overloaded as a result, again not only due to the usage it attracts, but possibly due to a build-up of backlog at some point along it...). And, they get some results characterising the topology of networks that produce Braess-like paradoxes, that are different from the characterision for the standard Braess paradox.

OK, so I'm a bit of a sucker for cake-cutting... Omer Tamuz ("Truthful fair division") gave a nice talk on a protocol where you get the players to declare their valuations of items to be shared, and then you share them out in an envy-free manner. Of course, you want the sharing rule to incentivise the players to be truthful (at a high level, the set-up is similar to the "responsive lotteries" topic noted above). So, this can be done, but if you want a "super-fair" truthful mechanism, it cannot be deterministic.

Dearing Report

2010-10-14T15:12:00.000-07:00

I took a look, by way of reminder, at a copy of the Dearing Report, which has a lot in common with the Brown Review discussed previously. I reckon that you need to know about Dearing in order to write a sensible analysis of Browne, and understand the mess we're in and how we got there. They are both reports with recommendations on higher education funding that got commissioned by unpopular Governments shortly before an election that they duly lost. The Dearing Report got a lot of coverage and discussion in the Times Higher at the time, especially in the run-up to its publication in 1997. Reading it now, it seems terribly overtaken by events -- despite being written only about 15 years ago, it seems to address a situation a lifetime ago, when the basic assumptions about HE finance were totally different. It can be blamed for playing a part in the process of change and decay that it purported to manage. The underlying narrative of UK higher education funding over the past few decades, has been a path of least resistance. It has not been guided by principles; what has happened instead is that certain principles have been retro-fitted to the lazy decisions that have been made.

Dearing's report purported to set the HE funding scene for the next 20 years, but was in practice mainly in the business of short-term fixes rather than an attempt to settle the matter decisively. Its context was a decline in the unit of resource for teaching of about 40% over the previous 20-odd years, this decline having been billed an "efficiency gain". Universities (some of them) were making noises about charging top-up fees. The report concluded that the sector could manage a further 2% cut over the next 2 years, but the planned 6.5% cut would lead to a loss of quality. The report had some good stuff: a recognition that international competitiveness was important, and a recommendation that public spending on HE should increase in real terms by 1% a year. It broached the subject of income-contingent repayment of tuition costs, decided that a graduate tax is unworkable, and proposed a scheme for repaying 25% of a student's tuition costs. Obviously it's a shame we did not stick to that figure of 25%; it looks benign by present standards.

Some other stuff that caught my eye: It recommended a target of 45% participation in HE, which for some reason was rounded up to 50% by the subsequent Govt, but wasn't achieved. With regard to the short-term funding gap resulting from student loans coming from Govt, it recommended that national accounting rules should be changed so that the loans could be treated as a Govt asset.

Here's a point made by Dearing whose dread significance was probably not so very apparent at the time. The Dearing commission considered the question of the benefits to society arising from higher education, and concluded that the main beneficiaries are the graduates themselves, due to improved job opportunities. Not a very remarkable or surprising conclusion to reach, but it has allowed that aspect to crowd out all other considerations of the wider social benefit. Participation in HE has been reduced to an act of economic rationality, an act of selfishness.

Browne Review

2010-10-12T07:43:00.000-07:00

The Browne Review (wikipedia page) came out today and is being widely discussed. Here is a link to one of many news articles. (Added later: this blog post reports on a devastating critique of the Browne report. Added still later: another great critique in the London Review of Books. Added 20.8.11: another critique (by the same writer, Stefan Collini) with more overview of the historic context.)

On the plus side, it does an efficient job of demolishing the ludicrous "graduate tax" idea. Also, it acknowledges that

Other countries are increasing investment in their HEIs and educating more people to higher standards

And the graphic design is striking in a rather retro way. It would have been improved by being embellished with the dirty fingerprints of assorted Labour party politicians, since the previous Government commissioned the report, but although the fingerprints are missing, the following quote serves that purpose:

Students do not pay charges, only graduates do; and then only if they are successful. The system of payments is highly progressive. No one earning under £21,000 will pay anything.

We estimate that only the top 40% of earners on average will pay back all the charges paid on their behalf by the Government upfront; and the 20% of lowest earners will pay less than today. For all students, studying for a degree will be a risk free activity. The return to graduates for studying will be on average around 400%.

Of course, the above is too good to be true. It reeks of Gordon Brownism, in that it's making promises too good to be true: no-one pays anything, you get much more back that you pay in later, and Government can print all the money needed to fill the short-term funding gap. There's also some stuff about student charters that looks suitably new-Labourish.

However, the present government seem happy to accept this gift. The headline figure of 7000 pounds per year to study at a UK university is dismaying many people, although not nearly as much as the lack of any limit on the fees that may be charged.

Here's a David Blunkett quote that I found here

This is a complete betrayal by the Liberal Democrats of everything that they have ever said on higher education and of the platform they stood on at the general election. The Tories have already performed a volte-face on their previous policy. This leaves only the Labour party with any credibility on student funding and the future of our great universities ...

The fact that the Labour party introduced university fees in the first place, and commissioned this report, seems to have escaped his attention! And here is the single take-home message of this blog post: Labour is to blame (or, if you like fees, they get the credit). Don't ever forget that. And don't ever forgive people like Blunkett for trying to trying to pass on the blame to his opponents.

What happens next? i.e., more specifically, how much will universities will charge? Probably there will be a high ``sticker price'' embellished with a system of discounts and bursaries for students with good exam results. It is tempting to assume that Oxford and Cambridge will gleefully impose very high fees, but they will be reluctant to be seen to be shutting out poorer candidates. Below them, prestigious universities will want to be seen to have a relatively high fee since university degrees are a Veblen good, but then they will have concerns about being able to attract enough students at the basic sticker price. If high fees do not deter too many UK students, then overseas students may be a casualty, at least if they no longer pay substantially higher fees than home students.

trip to Glasgow

2010-10-01T05:39:00.001-07:00

Congratulations to Eric McDermid, who successfully defended his PhD at his viva yesterday at the ~~department~~ School of Computing Science, University of Glasgow (myself as external examiner, Patrick Prosser as internal examiner). Title of thesis: A Structural Approach to Matching Problems with Preferences, I thought it was very nice work. I was also fortunate to be able to attend Rob Irving's retirement presentation, which coincidentally took place on the same day.

GAMES 2010

2010-09-23T14:45:00.000-07:00

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

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

cap on non-EU migrants

2010-09-16T03:11:00.000-07:00

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

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

...

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

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

Peer to peer lending

2010-08-30T08:17:00.000-07:00

I've been reading about Funding Circle in
this article in the Guardian (Funding Circle's home page also contains links to other news articles that have featured it). It's a new internet-based market that allows individuals to lend money to small businesses. So, it is similar to Zopa, which supports lending of money amongst individuals.

I've not tried it myself but am tempted... you just need a few hundred pounds to make available for loans, and your money gets divided amongst 20 different businesses, so as to spread the risk, and then the claim is that you make on average about 6% on your savings, as opposed to about 2-3% as you currently make in a savings account. Interesting features include: lenders can bid their interest rate, resulting in a trade-off in that if you set a higher rate, it may take longer for your funds to be accepted. You can also set up or join a "circle" (see the help centre) to specialise which businesses you lend to. If you want your money back, you have to sell your outstanding loans to another lender (I assume that effectively results in a penalty for early withdrawal). The system supports "autobid" which manages the division of your funds amongst distinct businesses, and recycles repayments into new loans so that your funds continue to earn interest. Finally, on the downside, my impression from reading the help page is that the tax treatment of income is not very lenient.

Two shocks to the (British university) system

2010-08-16T13:04:00.000-07:00

Two recent news articles caught my attention: this one in yesterday's Observer, and this one in today's Guardian. In different ways, they raise profound questions about how British universities will evolve over the next ten years.

The first of the above articles draws attention to a “recruitment drive” by EU universites, aimed at would-be university students in this country. It may come as news to many such students (or their parents) that they have the option to study for degrees in various other EU countries, where the fees are lower than in the UK, and get tuition in English. The article focuses on Maastricht University, by way of example. It's an attractive option: nice town, English language tuition in some subjects, strong research. The recruitment drive is claimed to be driven by our own supply-and-demand problem: too many UK students chasing too few places. The interesting question is whether foreign universities can attract students who actually could get places over here. That potentially reverses higher education's role as a net exporter for the UK. Can this be used as an argument for better state support for universities?

The second article (similar one here), entitled London is most cost-effective UK city for students, publishes a league table, the “2010 NatWest Student Living Index” which evaluates the cost of living for students for 25 cities in the UK, and favours London, surprisingly — the catch is, that cost-effectiveness is a function of a student's earning potential in the city, rather than just cost of living. Seemingly, students are now “meant” to be working part-time while studying (at least, in order for the ranking to be meaningful). Of course, many students get support from their parents and so some of them have the option to study full-time, but (as mentioned in both articles) 46% do not. Universities themselves, meanwhile, remain pretty much oblivious to these inequities — if a student fails an exam, you can cut him some slack on the grounds that his grandmother died recently, but you can't make allowances for him having been pulling pints in the local bar every evening. I think the best fix that is likely to be achievable, would be for universities to be more flexible about the duration of study. The current rigid three-year schedule is dictated by the (declining) Government funding scheme for students, as devised when full-time study was the standard. We could move towards a more German approach of getting your degree in however long it takes you (and we should accept a higher drop-out rate).

added 17.8.10: A new Guardian article:

A landmark review into university finance is expected to recommend that student loans, now only available to those on full-time courses, are extended to part-time students to cover the fees they must currently pay upfront, the Guardian has learned. Such a move would pave the way for a major change in the way university education is viewed, with a three-year stint in a new city no longer a given.

Part-time study is a way forward, but I wonder whether you need a binary divide between full-time and part-time study, or whether we should be able to allow for study schedules that fall between the two.

Fictitious play

2010-08-10T11:16:00.000-07:00

Fictitious play is a very simple iterative procedure for finding a Nash equilibrium of a game. Before stating an open problem of interest, let me give a quick summary of how it works (or, you can read the Wikipedia page for a more careful description). It's an iterative process that if it converges, must converge to a Nash equilibrium, but unfortunately it doesn't always converge. However it always works for 2-player zero-sum games, more on that below.

Assume you have a 2-player game. To begin with, each player chooses a single pure strategy. Then, both players construct sequences of strategies according to the following rule: At each step, a player considers the sequence chosen by the other player, he supposes that the other player will randomize uniformly over that sequence, and he chooses a best response to that mixed strategy. (So, a player's sequence is treated as a multiset of strategies, one of which is selected uniformly at random.) Technically, we should explain how to choose a best response in the event of a tie (2 equally good responses) - there are various options, but I won't discuss them. Anyway, the chosen best-response is added to a player's sequence, and that's how the sequences get extended.

I have recently been pestering various people with the following question: What is the complexity of the following problem:

input: a bimatrix game. For each player, an initial pure strategy.

question: does FP converge when those initial strategies are chosen at the start?

Additional question: If it converges, give the NE that it converges to.

(and just to be clear, this is not the same thing as asking about the complexity of FP itself.)

I recently read one of the early papers on the topic, namely: Robinson, J. (1951) "An Iterative Method of Solving a Game", Annals of Mathematics 54, 296-301. It is a beautiful paper, just 6 pages; I would recommend anyone to read it. It proves the result mentioned above, that for any zero-sum game, the payoffs obtained by the players do indeed converge to the value of the game. (The convergence rate that is implicitly obtained is very slow - maybe it can be improved?) Note, that is not the same thing as showing that the players play the correct strategies after any given number of iterations - a new paper in SAGT (Felix Brandt, Felix Fischer and Paul Harrenstein "On the Rate of Convergence of Fictitious Play") indicates it may take arbitrarily long to find the right strategies, depending on the payoff values.

Another nice question follows up on a paper by Vince Conitzer "Approximation guarantees for fictitious play" (Allerton 09). This paper studies the quality of approximate equilibria obtained by FP, in a scenario where the number of iterations is less than the number of pure strategies per player. But, if it's applied to a n×n game, and allowed to run for more than n iterations, for all we know it may actually do better than the best currently-known polynomial-time approximation algorithms (that obtain round about 1/3-approximation, if all payoffs are in [0,1].) Although, I will pessimistically guess that some troublesome games that haven't yet been identified, have it obtaining just a 1/2-approximation.

Mathematical conversation-starters

2010-07-28T15:25:00.000-07:00

It comes up, from time to time, in discussions we have with each other. You're chatting with that long-suffering creature, the Intelligent Layperson, and you feel the urge to explain your professional interests to him/her. And, it has been established that n×n chessboards just don't cut it, or even 100×100 chessboards.

It's time to identify some topics that really work - here's one I tried recently. Consider the following quote from the beginning of the paper Minimal Subsidies in Expense Sharing Games by Meir, Bachrach and Rosenschein, to appear in SAGT.

Three private hospitals in a large city plan to purchase an X-ray machine. The standard type of such machines cost $5 million, and can fulﬁll the needs of up to two hospitals. There is also a more advanced machine which is capable of serving all three hospitals, but it costs $9 million. The hospital managers understand that the right thing to do is to buy the more expensive machine, which will serve all three hospitals and cost less than two standard machines, but cannot agree on how to allocate the cost of the more expensive machine among the hospitals. There will alway be a pair of hospitals that (together) need to pay at least $6 million, and would then rather split off and buy the cheaper machine for themselves.

The question you ask your audience is, what will be the outcome of the negotiation between the hospitals? Hopefully, someone will begin by saying that 2 hospitals will share a $5M machine, and with any luck, someone else will suggest that the 3rd hospital will offer to share a $5M machine with one of the first two, and pay more than 50%. At this stage, you are in good shape.

Now, you might object that this has nothing to do with computational complexity, which is sort of true, however you can introduce some later on in the discussion if you feel the urge (non-constant number of hospitals or machines). What makes this a nice mathematical topic is that - assuming your audience start to consider a sequence of offers and counter-offers - it raises the issue of making a proper mathematical model of the negotiation (so, if 2 hospitals make an agreement, is it meant to be binding? Presumably not if the 3rd one can "attack" it with a more attractive offer. But if it's not binding, how can the process come to an end?) Finally, despite the fact the problem is ill-posed, there is still a cute answer that is analogous to the answer to this ill-posed problem: when asked what the outcome should be, you say "by symmetry, the hospitals will share a $9M machine". (Actually, don't use the phrase "by symmetry".)

Research funding, pensions

2010-07-10T13:49:00.000-07:00

Quite a flurry of genuinely important material for the Times Higher. The story that the REF will be delayed a year to resolve the dispute over "impact" is good news; regardless of whether this aspect of the REF is a good thing, any delay is a win, simply because of the enormous expense (mainly on academics' time) of national research assessment. Lots of comments follow the article, with Philip Moriarty in good form. (added 12.7.10: 2 more interesting links: This article (5.12.09) discusses the "James Ladyman index" and attracted a lot of comments; this one (1.7.10) has a comment by Ladyman)

The outcome of the USS meeting I mentioned previously is that probably the USS will switch to career-average earnings to compute pensions. In an attempt to make that fact sound interesting, let me put it this way: In the future, your pension contributions statement will not state the number of years of service you have accrued, but it will state your pension entitlement as a sum of money. Oh well, if that bores you, maybe you are wiser than I am.

This article reports on a speech by David Willetts on the case for science funding. So, he believes in it, that's a good thing. From the article:

Mr Willetts said he could not talk about spending commitments until the Comprehensive Spending Review is published this autumn, but warned that the UK could not afford to emulate the examples of the US, Canada and France, which had reacted to the recession by spending more on science.

Full marks, at any rate, for admitting that these other countries are raising spending on science.

Finally, sort of a weak forecast: maybe full economic costing of research grants is not going to collapse under the weight of its own stupidity, as I thought it would. Here's the argument. The Government wants to cut spending on universities but at the same time, wants to protect the strong against the weak. Now, one way to do that is to identify specific universities for preferential treatment, and I guess that's sort of what they're doing in Germany, but it's delicate, to say the least. Alternatively, you can identify characteristics of "strong" and show favoritism to universities having those characteristics. And research grants are quite handy, for that purpose. So, artificially inflate the value of all research grants, and the Matthew effect is duly enforced.

USS changes

2010-07-01T01:02:00.000-07:00

The Times Higher is a good magazine to read if you're feeling a bit euphoric, there's an unaccountable spring in your step, and you need to simmer down a bit. Last week's issue raised the alarm about the sustainability of the Universities Superannuation Scheme (USS). The article notes a forthcoming meeting (7th July) between representatives of the University and College Union (UCU) and USS to negotiate changes. The UCU's question-and-answer page on changes to the USS, argues that no change is needed. Trouble is, we all know that very few final-salary pension scheme still exist; in the private sector most of then closed down to new member during the past 10 years. In a recent blog post, Robert Peston gives an overview of cuts to the benefits from the BBC's pension scheme (which like the USS and the private sector, is also a funded pension scheme.) From Peston's post:

Even those on relatively high salaries, who don't expect their earnings to rise, will have to think twice about whether it makes sense to continue with contributions.

This presents scheme managers with a dilemma - they have to keep the deal sweet enough to retain members and attract new ones, a problem that becomes much more urgent when a scheme is in deficit. When that happens, the whole thing is at risk of being sustained by promises that managers cannot ensure they will be able to keep.

To be honest, I think the UCU is obstructing the necessary dose of bad news that will be necessary to ensure the USS's sustainability. One problem that's come up: the USS's 3rd-largest equity holding is BP, with a market value of 693.7M (the list I got that information from is updated only every 3 months, so BP is likely to be lower-down by now.) USS has a total of about 22Bn in invested capital. (Not that I blame them for owning some BP. It looked like a good bet a few months ago.)

Here's a quote from that UCU question-and-answer page.

Q: Aren't all public sector pension funds going to have to make changes to save money. Whys should academics have special treatment?

A: USS is not a public service pension scheme, so it has to meet the same targets as other funded occupational pension schemes in the private sector. Its big advantages over such schemes are that the HE sector as a whole is less likely to go bust than any individual group of companies, so that it can afford to take a longer view. That does not mean that the politics of envy will not give traction to attacks on USS; but that is no good reason for the preemptive cringe that is part of what characterises the stance of the employers' negotiators.

Full marks for emphasizing that the USS is not public-sector, but the usage of "politics of envy" made me cringe. Finally, here's a fragment of the USS investments page to show that in some respects they have impeccable taste.

(It's the Go game that caught my eye.)

Accepted papers for SAGT

2010-06-28T13:06:00.000-07:00

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

Competition for rank

2010-06-11T01:18:00.000-07:00

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

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

Research in an age of austerity

2010-05-16T11:05:00.000-07:00

Concidence: the new British government is a coalition that is united mainly by the belief that the budget deficit should be tackled sooner rather than later. At the same time, the crisis in the Eurozone has led to severe austerity measures in Greece, Portugal and Spain. All of a sudden, it seems like cost-cutting is "in the air"; our own government will no doubt be encouraged in cutting spending by being able to answer its critics "go to Spain and see how much worse things are over there", or perhaps "if we don't cut now, we'll end up like Greece."

I expect research to be in the line of fire; an open question is whether cuts to the research councils' budgets will be "game-changing" ie will they have an impact on the way funding is handed out, and researchers' approach to competing for it. A bit of reform could be something of a silver lining on the cloud.

Let's try to foresee some changes.

Increased importance of EU funding. This is easy, just look at the figures. European Research Council funds have been spiralling up in recent years, just as EPSRC is facing a cut.

Full economic costing of research grants has got to go. In a nutshell, the background is this. About 10 years ago, universities complained to the Government that their research activities were bankrupting them, because research grants did not cover the expenses incurred. It is important to note that this problem did not actually stop them from fighting like rats in a sack over these supposedly inadequate research grants. And the Govt duly boosted Britain' s science budget, but... the way the funds were handed out, was essentially by doubling the cost of individual grants. The result: heightened competition for grants, and a boom/bust pattern to peoples' (and universities') research incomes. Reviewers of research proposals are told to ignore all value-for-money considerations, and comment only on the quality of the research, leading to anomalies like successful applicants getting more than 100% of their salary paid by their grants... enough of this!

A simplified research funding regime. I'm entering the wishful-thinking zone here. The rationale is, that if you've only got ten quid to dish out to the research community, there's no point making them spend hours poring over impact statements, and peer-reviewing each others' long and highly-technical grant proposals. You should just give it to a subset of universities, or share it equally amongst anyone who can exhibit a decent track-record, or something. The new government is likely to cause a welcome delay to the Research Excellence Framework.

Theoretical research may be well-placed to survive a worst-case scenario. This is appropriate, since a lot of theoretical CS addresses worst-case performance of algorithms. Actually, CS generally may be in better shape than other sciences, since computers are cheap.

And finally, a tongue-in-cheek suggestion: Since London-based academics receive London weightings to their salaries, they end up doing the same work at a higher cost. It makes sense to support academic research (and indeed teaching) in less expensive locations.

UK election game

2010-05-12T14:13:00.000-07:00

Here's a fun game-theory problem; Martin Gairing helped me find a solution during lunch, which I will add later.

There are 2 political parties and N constituencies; each party wants to win as many of them as possible. Both parties have an amount M of money (to spend on election campaigning) which they split amongst the N constituencies; for each constituency, it is won by the party that allocated it the larger amount of money. A party's payoff is the number of constituencies it wins, so it's a zero-sum game. The problem is to find a Nash equilibrium. You can assume that M is infinitely divisible, or if not, you're allowed to find an approximate solution with error proportional to 1/M.

Note that there is no pure equilibrium; if a party fails to randomize, the other one will be able to narrowly defeat it in nearly all constituencies while allocating no money to one(s) that it loses.

Obviously lots of generalizations are possible...

Experiments with envy-prone cake cutting

2010-04-30T02:26:00.000-07:00

Suppose that 3 people share a cake as follows. Player 1 cuts it into 3 pieces, then player 2 takes a piece, then player 3 takes one, then player 1 takes the remaining one. Player 1 can avoid envy by cutting into pieces that he values equally, player 2 can avoid envy since he gets first choice, but the worst case for player 3 is terrible - he may see player 2 walk off with a piece that he (player 3) deems to contain all the value in the entire cake. Consider the following "fix": after player 3 has taken a piece, he has the right to combine it with player 2's and challenge him to cut-and-choose. In this case, player 1 can end up envious: he can ensure his own piece is worth 1/3 of the total, but he may watch as one of the other players ends up with a share that he values as 2/3. Indeed, player 2 can also end up envious of player 1, under this scheme.

An obvious way to quantify the envy of a cake-cutting scheme is to say that each player values the cake at 1 unit, and look for the worst case envy of any player, i.e. the maximum amount that he may be forced to value another player's share more than his own. The first scheme above has an envy of 1 in the worst case, and the second version is 1/3.

We can analyze schemes in an ad-hoc manner to figure out their worst-case envy, but can we do it automatically? For an undergraduate programming project I got the student (Amir Niknafs-Kermani) to try doing this as follows. Model the cake as a unit line segment. Represent a player's value function by a set of N (typically about 1000) points on the line, each worth 1/N. Generate for each player, an initially random value function, and run the scheme on them, and measure the level of envy (which is typically zero or very low for a sensible scheme, since these value functions all more or less agree with each other). Then, try to tweak the value functions by adding and removing points that define those functions. The hope is that points get added in "sensitive" regions of the line, and when you re-run the scheme, the envy goes up. Repeat until you don't manage to raise it further, and you've got a lower bound for the worst-case envy.

And the results, briefly, are that it works pretty well, at least for simple schemes. The envy level that is found by the algorithm varies quite a lot (depending on the initial random choice of value functions) but is often close to the theoretical limit. But the performance gets worse with larger number of players.

Since it is unknown whether there is a 4-player envy-scheme with a finite number of cuts, perhaps it is interesting to study the above "level of envy" measure, and how fast it can go down towards zero, as a function of the number of cuts in specific types of schemes.

On May 6th, I'm voting for France

2010-04-25T10:04:00.000-07:00

The United Kingdom is no longer capable of governing itself. Labour is simply awful, and the Tories are incompetant. The Liberal Democrats meanwhile, are trying as hard as they can to position themselves in the exact centre of gravity of the other two.

Luckily, help is at hand. A cursory glance of history will convince anyone that every nation-state harbours the ambition to conquer and swallow up its rivals. What the UK needs to do is to select another country, and invite them to take us over. For administrative purposes, it may be necessary to declare war on them and promptly surrender, but that is a technical detail -- the main challenge is to choose the best country.

I have compiled a list of what I consider to be the strongest candidates, arranged in descending order of my own assessment of their merits. I discuss the case to be made for each one, and some of the possible objections.

France. France has a natural geographic advantage, which is likely to be the cause of the extensive history of takeover bids that have occurred in both directions, over the last thousand years. In 2009 for the fourth year running, France has headed the International Living Quality of Life league table. A short excerpt from that web site gives some of the explanation:

The French believe that every day is a pleasure to be slowly savored—and lingering at the dinner table for three hours in conversation isn’t considered abnormal. Family, friends, and good food are all vitally important to the French—and so is having enough time to appreciate them all.

Sounds good to me! On the downside, we would have to speak their language. However, since any red-blooded Englishman knows that he is naturally gifted at driving, golf, and speaking French, this should not be a major problem.

While academic salaries are somewhat lower in France than in the UK, this is undoubtedly offset by a lower cost of living. Finally, while French academics are apt to complain extensively about their Government's higher education policy, I suspect that is just Gallic bloody-mindedness.

The United States of America. For the better part of a century, the USA has served as a beacon to would-be migrants all over the world, especially academics. Furthermore, if the UK became a part of the USA, we would gain a strong sense of destiny having been fulfilled. The USA's federal structure may ease the administrative process of assimilation, since the UK could become a new state of the union. Readers of the Daily Telegraph and the Daily Mail would be delighted to revert to feet and inches, gallons and degrees Fahrenheit. Finally, anything that reduces the inconvenience of transatlantic air travel is surely to be welcomed.

The downside (based on conversations with many Americans) is that the USA may decide to cherry-pick Scotland and Ireland (and possibly Wales) but leave England hanging out to dry.

Germany. While Germany is a strong candidate, most of the arguments in favour apply in at least equal measure to France. The language is said to be easier, being adequately supplied with consonants. The main downside is that it would make nonsense of our highly cherished World War 2 movies.

China. There are some significant cultural synergies from a takeover by China. On the one hand you have a communist country with a capitalist work ethic, on the other hand you have a capitalist country with a communist work ethic. The Chinese "one-child" policy would not be popular here, but it would do wonders for primary school class sizes.

India The great thing about soliciting a takeover by India, is that they may just possibly agree to do it. They might make the mistake of viewing it as a status symbol to be in charge of the UK.

3 papers for my reading list

2010-04-24T14:18:00.000-07:00

Last week I was at the EPSRC Symposium Workshop on Game theory for finance, social and biological sciences at Warwick University, an event that lived up its multidisciplinary title; here are 3 papers that people told me about, that I hereby undertake to try to read.

"On the rate of convergence of fictitious play" by Brandt, Fischer and Harrenstein, available from Felix Brandt's web site, actually qualifies to be mentioned here at Noam Nisan's blog, where he put out a call for recommendations for as-yet-unpublished algorithmic game theory papers. The paper explains clearly what is meant by Fictitious Play (which was a prominent topic at the above workshop) and for types of game for which is known to converge (to Nash equilibrium), shows it takes exponential time. Surely a very timely set of results, in view of recent related results in CS about the convergence rate of various dynamic processes in game-theoretic settings.

"Fairness and Desert in Tournaments" by Gill and Stone, available here at David Gill's web site, I find interesting since it relates to my (and 3 co-authors) paper on competition for placement in a ranking, to appear in EC. The word "tournament" is not being used in quite the same sense as in social choice (a mechanism to pick a winner using a program of pairwise contests); it's (related) meaning is a competition where one player gets a prize, but there is quantified value to the prize, as well as cost for alternative levels of effort that go in to winning it. The emphasis is on the impact of players' sense that they deserve to win or lose, something that is modeled mathematically.

"Chaos in learning a simple two-person game" by Sato, Akiyama and Farmer, available here, in fact focuses on rock-paper-scissors, and shows that a particular learning process may exhibit chaotic behaviour, perhaps because if the behaviour was predictable, then a player could predict it and take advantage of what is about to happen.

impact of the election (or vice versa)

2010-04-23T03:52:00.000-07:00

I received another email update on the campaign against assessing research by impact yesterday; here is a link to the last post I made on the previous update on that. Rather than quote the whole thing, here is a quick summary: it is optimistic on progress; most concretely, it pointed out that HEFCE are ready to delay the REF another year or two to work through the debate on the topic (story in Times Higher) - that is itself a good achievement even if they don't back down. Both the Conservatives and Lib Dems are skeptical about usage of impact statements for research funding.

By the way, this article by Simon Jenkins contributes the following great quote to the debate:

This dirigisme reached its logical conclusion when Lord Mandelson took universities into his "business, innovation and skills" department, and rendered their planning a matter of political infallibility. Last year, many universities lost the will to live when he demanded a measure of every scholar's "contribution to demonstrable economic and social impacts", with reference to "public policy, cultural impact and improving the quality of life". It was a Leninist parody.

email addresses with/without academic domain names

2010-04-12T03:52:00.000-07:00

Most academic colleagues use email addresses that end with .edu or .ac.uk, or related endings for other countries. But some (more often, younger people) use gmail, for example. I suspect that it is a mistake to do that, and that academic domain names are a genuinely good thing, simply because they help to certify the identity of the sender. I have a gmail address but I only use it for personal, not professional correspondence.

If someone emails me who is interested in a job or studentship with my research group, I give the message more credibility if it's an academic address (is it wrong to do so? I try not to be biased in how I respond to the message... but certainly there's a bigger risk that it looks, at first sight, like spam.) Or, if someone writes me a reference on behalf of someone else, the fact that it originates from a sender with a university email address is as good as a signature on paper - better in fact, since I don't recognize most people's signatures.

Is the above opinion sensible, or old-fashioned (or possibly, both)?

2 new faculty posts at Liverpool, UK

2010-03-31T08:37:00.000-07:00

Having just send the ad to various mailing lists, it should also appear at the blog...

THE UNIVERSITY OF LIVERPOOL -- DEPARTMENT OF COMPUTER SCIENCE
LECTURESHIPS IN ECONOMICS AND COMPUTATION (2 POSTS)

The Department was ranked in the top 10 UK Computer Science departments in RAE2008, and building on this success, we seek to significantly expand current research around existing strengths at the intersection of economics/game theory and computer science. You will join Professor Paul Goldberg, Dr Piotr Krysta, Dr Martin Gairing and Dr Rahul Savani in our research group on Economics and Computation. The group carries out research in the computational foundations of economics and game theory and enjoys close collaborative links with other strong research groups in the Department. You will be expected to contribute to our MSc in Computation and Game Theory.

You should have a PhD in Computer Science or related discipline and an excellent track record of research at the intersection of computer science and economics/e-commerce/game theory.

Relevant topics of interest include (but are not restricted to):

algorithmic game theory;
e-commerce;
mechanism design and auction theory;
complexity and computation of solution concepts;
optimisation problems in economics;
computational social choice.

salary in range GBP 36,715 - GBP 41,323 pa; Job Ref: A-570581; Closing Date: 30 April 2010

Further details

online applications/job description

For informal discussions please contact Prof Paul Goldberg, Head of Group (mailto:goldberg@liverpool.ac.uk).

For full details, or to request an application pack, visit here
e-mail jobs@liv.ac.uk
tel +44 151 794 2210 (24 hr answerphone).

Dagstuhl 10101

2010-03-11T10:08:00.000-08:00

I am at Dagstuhl seminar 10101 (schedule) on computational social choice; it ends tomorrow. Much of the chatter in the evenings has been about the AAAI conference, due to author feedback to reviews being made available a couple of days ago; to a lesser extent ACM-EC accepted papers, also announced a couple of days ago. I will not try to do a complete overview; let me try a more vignette-like approach.

A nice talk by Jérome Lang was in the context of conducting a collection of yes/no votes where there is preferential dependencies between attributes, meaning that a voter's support for one issue may depend on the outcome of the vote on one or more of the other issues. The example used was voting to build a swimming pool and voting to build a tennis court, where some voters would like one or the other, but not both (too expensive). Each voter is represented by a preference relation on the 4 possible outcomes (for n yes/no issues, he uses a more concise representation, "CB-nets"). The question is, how hard is it for the "chair" (who chooses which order the issues are voted on) to control the outcome. Commonly NP-hard, which is taken to be good news, although it is noted that it raises the question of easier manipulation in typical or average cases. That issue is analogous to the hardness of a voter choosing a strategic vote (a ranking of the candidates that is not his true ranking) so as to get a better outcome. While that is NP-hard for some voting schemes, it may often be easy in practical settings. Indeed, Edith Hemaspaandra's talk was about polynomial-time manipulability when there is single-peaked preferences over the candidates.

The rump session (not covered in the above schedule) was 11 talks each of 5 minutes, really aimed at stating problems where no results have been obtained. I gave an introduction to the "chairman's paradox" (to ask about related computational issues) -- it was identified by Farquharson in 1969 and goes as follows. Say you have a committee of 3 voters {1,2,3} who have to choose one of 3 outcomes {A,B,C}. Let voter 1 be the "chair" and voters 2 and 3 be the ordinary members. The special role of the chair is that if all 3 outcomes get one vote each, then the one supported by the chair is the winner. The paradox is that if the voters' preference lists are generated at random, and your solution concept is pure Nash equilibrium, then the chair gets what he wants less often than the other members. For example, consider the (Condorcet cycle) preferences where 1 has preferences ABC (in descending order), 2 has preferences BCA and 3 has preferences CAB. Then, voter 2 will vote for C since that results in C rather than A winning (2 and 3 supporting C). Voters 1 and 3 continue to support A and C respectively, having no incentive to switch. That is the only pure Nash equilibrium that results from iterative removal of weakly dominated strategies, and notice that 1 (the chair) gets his worst outcome C. I will note that the last time I had to chair a committee of this nature, I felt disadvantaged, although not quite for this reason. The session contained an interesting talk by Kóczy on a method for ranking economics journals (someone has to do it I suppose; see this article on the ranking obsession factor). Finally I should surely mention Felix Brandt's entertaining talk on the "kicker theorem".

Edith Elkind's talk on plurality voting with abstentions was related to the above in using pure Nash equilibrium as the solution concept with a bunch of voters and alternatives (not just 3). An interesting open problem she raised is: Suppose you have sets of voters and alternatives, and for each voter/alternative pair there's a numerical utility of that outcome to that voter. Assume that in the event of a tie, the voter's utility is the average (furthermore, let's assume that all numbers and averages are distinct). Suppose voters cast their votes in some prescribed order, and consider the solution concept of subgame perfect equilibrium. What is the complexity of computing their votes? (On a less formal note, Aviv Zohar told me about a "taxicab game" he had played rather poorly, in which a sequence of (say) 10 people board a minibus with 11 seats, and you aim to end up next to the vacant seat, or failing that, maybe some seats/neighbours are better than others. OK, it needs to be specified more precisely.)

Here is another recent blog post on computational social choice, just to prove I have been paying attention.

inaugural lecture

2010-03-05T04:26:00.000-08:00

The illustration is from one of my slides - it is intended to give an idea of how to make a hard instance of 2D-SPERNER. I must thank my colleagues in the EcCo research group for the talks they gave in the morning, also Troels Bjerre Sorensen, David Manlove, Kousha Etessami and Bernhard von Stengel for visiting and giving very nice talks in the afternoon, as well as other visitors and everyone who attended the talks.

Writing references

2010-02-24T03:20:00.000-08:00

At Cambridge, Mary Beard blogged recently about the reference-writing burden. Here's a quote:

evaluating students, ex-students and colleagues is an important part of my job; I'm not complaining about being asked to do it (so no need to feel remotely guilty about asking me) -- I'm complaining about the cumbersome, inefficient and sometimes downright obstructive infrastructure.

Regarding academic references (for students applying for postgraduate study), Beard notes that some departments

To save themselves money and to maximise your irritation, many departments now have feeble, barely secure systems where you hand the reference back to the student in an envelope, signed across the seal and then covered with sellotape.

From recent experience, having produced a bunch of references for students applying for MSc study, I can reveal that Cambridge is by far the worst offender in this respect. At York and Edinburgh, they email you a URL, you go there, and upload the reference in PDF. At Oxford, it's bit worse, they email you a URL, username and password, you login and have to provide details of your contact info, affiliation and next of kin (I exaggerate slightly) which gets checked by "inspector" software, then you finally get to upload a PDF. At Cambridge, the student has to come by your office with a reference form in triplicate (you don't often get to use that word these days) and you have to print and sign three copies of the reference (one for each reference form) then you go through all the amateur cloak-and-dagger stuff with the signature and sellotape.

The point is, I guess, that Cambridge (and to some extent Oxford) are the only universities that can afford to be so obstructive to potential customers. The trouble is, they are mainly wasting the time of the referees, not just the students, and referees are ethically obliged to cooperate with whatever stupid system is being used. But I will complain to them about their system, and report here on any response I receive.

Forthcoming inaugural lecture

2010-02-08T07:30:00.001-08:00

My inaugural lecture (on Computational Game Theory) is on the 2nd of March; I'm currently working on the slides. Here is a schedule of a one-day mini-workshop we are having on topics in computational game theory, to take place alongside the lecture. Here is an electronic invitation that anyone reading this is most welcome to. Here is a link to the university's web site on the current series of inaugural lectures, includes a registration facility for anyone who wants to attend.

mainly about cuts

2010-02-04T23:06:00.000-08:00

I went to a university staff meeting today where our Vice-chancellor began with a presentation on funding cuts, and after he was done, I asked him which way we should all vote in the next election. It's the kind of question you ask when you've just finished marking 40 exam scripts. His response touched on the fact that the USA, Japan, Germany and France all are spending more rather than less on higher education, as part of their fiscal stimulus packages. I knew about the USA, but it's great to hear that all these other places also regard universities as part of the solution and not the problem. (added a day later): This beautifully-written article in the Guardian is a must-read for anyone who is interested in this topic!

The VC also noted that the funding formula is now allocating more weight to research that received the highest RAE rating (4*) than it previously did. It is starting to look like it is wrong to refer to "3* and 4* research" in the same breath; in reality we should all be chasing after 4* research, and disregard anything less.

Back to exam marking - no-one likes doing it, but it's nice when someone gets everything more or less correct, and you think, hey, I really got through to this guy.

On Facebook, Ulle Endriss called attention to this web site about the closure of the Group of Logic, Language and Computation at Kings College London. I would guess that the people being laid off would not get so much sympathy in the wider community, at a time when unemployment is still rising in the USA, and is still very high over here. It's a reminder that universities are not in the public sector, and are all in thrall to fiscal constraints.

Finally, a definition: meritocracy: government by people with a powerful sense of entitlement.

New MSc course

2010-01-28T05:39:00.000-08:00

We have started advertising our new MSc degree course in Computation and Game Theory. (I am hoping it will not confused with computer games; the summary below should help.) Here are details on the department's web site. Here is the link on the university's web site for applying to join the course.

The following is a 100-word summary that should appear in findamasters:

Success stories of the Internet giants like Google have generated great interest in new techniques for e-commerce. New career opportunities are emerging that exploit the rapidly expanding research area in the intersection of economics and computer science. These arise both in research and commercial development. The MSc in Computation and Game Theory program aims at providing students with a broad understanding of current issues and gaining specialist qualification in this field. The program covers a number of foundational theoretical areas, including cutting edge modules such as algorithmic mechanism design, and covering modern applications such as Google's sponsored search auctions.

This is of course the general topic of the Economics and Computation Research Group.

Piotr Krysta is the main contact for details.

Tories to review HEFCE's plans on impact

2010-01-19T08:18:00.000-08:00

Following on from my earlier post, the latest email in the series is entitled REF campaign update - some good news. Apart from the title of this post, also - see below - scientists are being invited to submit feedback on this to the Science and Technology Select Committee.

REF campaign update:

I wanted to write to you to update you with some good news, showing that our lobbying and the publicity we have generated over the ‘impact’ campaign is having an effect. Please see below:

Tories call for REF to be shelved:

David Willetts announced last week that if elected, the Tories would shelve HEFCE’s plans on impact until the completion of a two year review. The shadow minister for higher education, David Willetts, said he would delay proposals that would force 25% of future research to be assessed on 'economic impacts' by two years in order to listen to the concerns of the academic community. The news comes just a week after a UCU poll of top professors revealed that over a third (35%) would consider pursuing their academic career abroad if the plans were introduced. Read more here: http://www.timeshighereducation.co.uk/story.asp?sectioncode=26&storycode=409991&c=2 This is a measure of the pressure we are building up on political parties and HEFCE and a testament to your support, so thank you again.

Calling all scientists! – Science and Technology Committee calls inquiry on funding and ‘impact’

Following UCU lobbying, the Science and Technology Select Committee has announced an inquiry into Science funding and one aspect the committee will be particularly interested in is the proposals for ‘impact’. The Committee is interested in “what evidence there is on the feasibility or effectiveness of estimating the economic impact of research, both from a historical perspective (for QR funding) and looking to the future (for Research Council grants)”. If you are a researcher in the sciences, this is your chance to speak directly to the politicians by making an individual or group submission.

How to send a submission:
Focus on the feasibility of an impact measure in your field – can you measure impact over the short term? What would it do to pure science and basic research?
Keep your submission to a maximum of 3000 words and put it in Word format (no later than 2003) and number your paragraphs
The deadline for submissions is 27 January so time is short.
Don’t leave it to others! With the disappearance of a committee that specifically represents universities it’s harder than ever for the academic voice to be heard. Volume of responses will be important. If you have something to say, now’s the time to say it!

Please send your submissions by e-mail to scitechcom@parliament.uk and marked "Research funding cuts" and please send a copy to us too at jwhite@ucu.org.uk. An additional paper copy should be sent to: The Clerk, Science and Technology Committee House of Commons, 7 Millbank, London SW1P 3JA.

You can read full details of the Inquiry’s remit here: http://www.parliament.uk/parliamentary_committees/science_technology.cfm

Best wishes

Jonathan

Jonathan White

Deputy Head of Campaigns

UCU

Surds and the pursuit of happiness

2010-01-16T06:07:00.000-08:00

My son Arthur mentioned that he had learned about surds in maths, so we asked him what one was. The definition I vaguely recalled from my school days was that a surd is an irrational number, but of course that's not the whole story, since it would seem that not every irrational number is a surd. Arthur did not know an exact definition, and it would seem that no-one else has tried very hard to pin it down precisely. Higher GCSE Mathematics for Edexcel by Alan Smith, p492, states:

Some quantities in mathematics can only be written exactly using a square root symbol.

For example, if x²=5, then the exact value of x is √5 (or -√5).

Quantities like these, written using roots, are called surds.

Based on discussions and exercises on the following pages, it appears that a number like 1+√2 is a "surd expression" rather than just a surd, but neither was it ruled out as being a legitimate surd. The book gave no hint about whether, for example, the cube (as opposed to square) root of 2 is a surd.

Other sources are similarly imprecise. Wikipedia indicates that a surd in an N-th root (presumably, an N-th root of a positive integer, where N is also a positive integer). It says here that

An unresolved root, especially one using the radical symbol, is often referred to as a surd.

Based on the usage of the word in that web page (which also explains its origin) it looks like it's supposed to be a (real-valued) positive integer root of a positive integer.

This web page states the most restrictive definition: "A surd is a square root which cannot be reduced to a whole number." Presumably they mean: a square root of a positive integer, and not a number like √(9/4) = 3/2. Wiktionary says: "An irrational number, especially one expressed using the √ symbol." (which would appear to allow 1+√2).

With a view to inducting my sons into the family trade, I thought that it would be a worthwhile mathematical exercise to discuss what should be the right definition. (The definition itself will not be interesting mathematically, but the pursuit of one is of great value; by analogy, the chap who coined the phrase "Life, liberty and the pursuit of happiness" clearly figured out that pursuit of happiness, rather than happiness itself, was the point.) It's a topic that touches on all sorts of issues, such as which if any, of the alternative definitions are equivalent, and why. More fundamentally, it addresses the issue of what constitutes a genuine mathematical definition, as opposed to some general guidelines on usage. Finally, the alternative definitions will have various different merits, such as being a set of numbers that is closed under addition. In the event the discussions did not get very far, but looks like a good one to have in high school math lessons.

(added later: Mark Jerrum pointed out this link on mathematical terminology; in the case of surds, it contains more historical detail than wikipedia's page.)

UCU takes the gloves off?

2010-01-07T14:52:00.000-08:00

This post follows on from two previous posts quoting email updates on the UCUs campaign against the proposed ways that UK academic research will be measured in the REF. Again I quote the entire thing below - it has some useful links and it is noteworthy in highlighting the risk of a renewed brain drain if the proposals go ahead.

One thing you learn from the study of bargaining and negotiation from a computational perspective, is that to make the case for a particular price, you need to appeal to the marketplace. In selling a house, it is no good to say to a buyer "you should pay me more because my house is worth more than your offer". You must say "you should pay me more because some other potential buyer would pay me more". Likewise, I believe that if a researcher is threatened with financial and reputational penalties if he refuses to bend to the Government's agenda, he is possibly mistaken to focus on explaining that pure research is valuable. Rather he should say "There are other buyers out there for the services I prefer to sell".

Dear colleagues,

UCU poll shows one third of professors considering leaving the country if impact pushed through:

I am just emailing to update you on recent progress in UCU’s campaign against HEFCE’s ‘impact’ proposals. The REF campaign hit the press in a big way today as three of the broadsheets feature a UCU poll showing that more than one third of professors would consider pursuing their academic careers abroad if HEFCE’s impact proposals are pushed through. One in five professors polled also said they knew someone already considering leaving. You can read more about the poll in a double page spread in the Independent:

http://www.independent.co.uk/news/science/nobel-laureates-dont-put-money-before-science-1860138.html

You can also read it in the Times and the Telegraph:

http://www.timesonline.co.uk/tol/life_and_style/education/article6978437.ece

http://www.telegraph.co.uk/education/6943360/Warning-over-academic-brain-drain.html

The revelation that the impact agenda could trigger a brain drain in UK academia should give pause to the funding council and the government, providing yet more evidence of the danger posed by these proposals.

But are they listening? Peter Mandelson’s recent HEFCE grant letter, besides announcing swingeing cuts to the unit of resource, appeared to pre-empt the results of the REF consultation, committing the government firmly to the impact agenda. Lord Mandelson wrote to HEFCE: "On research, securing greater economic and social impact will be important over the next year. I want you to continue to develop proposals for the Research Excellence Framework, following the consultation that ended on 16 December. These should provide significant incentives to enhance the economic and social impact of research."

The press attention to our poll shows that the enormous opposition to the impact proposals is finding public expression. Our task now is to turn this into pressure at a political level.

The foundation of this campaign has been the support shown by you and your colleagues in signing the 18,000 strong petition. If we are to raise the pressure on the government we will need your support again and will shortly be writing to tell you how you can help us put pressure on your MP. Watch this space.

Thank you again for your support,

Best wishes

Jonathan White

Deputy Head of Campaigns, UCU

contributing to Wikipedia

2010-01-01T22:18:00.000-08:00

What Wikipedia really needs, it occurred to me recently, is an article about the complexity class PPP. Not everyone will agree with that assessment; some people reckon that what Wikipedia really needs is to get rid of its liberal bias. For myself, I gave up waiting for the article on PPP to appear, made a account at Wikipedia, negotiated the rather unconventional syntax you use to edit articles, and wrote the above-linked-to page (that is, the first one, not the second one). Then I added links from the articles on PPAD and PPP (disambiguation). Then I wrote an article about the complexity class PPA, which as the whole world needs to know, is another denizen of the terra incognita that lies between PPAD and FNP. And if you think there's anything wrong with any of those articles, don't come hassling me about it, go and edit the pages yourself! It's not like they belong to me.

Then I contributed fifty quid to Wikipedia, after repeatedly seeing all those fundraising appeals from its founder Jimmy Wales.

Then I added most of the content on the current version of the page on the Research Excellence Framework (REF). Like the fundraising appeals, the REF is a bit hard to ignore, at least for UK academics. If you don't know what it is, consider yourself fortunate. If you want to know, follow the above link, it's as good a starting-point as any, in my unbiased opinion.

Happy new year, by the way.

"Stand up for Research" again

2009-12-10T12:22:00.000-08:00

OK, a slightly incremental update to my previous post... the UCU petition is continuing to pick up more and more support, see this copy of an email I got today.

Stand up for Research - Last push for 20,000

Dear colleagues,

Thank you for signing UCU’s ‘Stand up for Research’ statement. The response to this campaign has been overwhelming, with more than 16,500 academics signing up.

As a result of the petition’s growth, the campaign is winning more press attention. Clive James used his ‘A Point of View’ column on Radio 4 to attack the proposals. You can read this here: http://news.bbc.co.uk/1/hi/magazine/views/a_point_of_view/

Also, read Sally Hunt’s comment in the Times Higher Magazine here:

http://www.timeshighereducation.co.uk/story.asp?sectioncode=26&storycode=409381&c=1

BUT we still need more.

We have less than one week now to push as close to 20,000 as possible. Please take a moment to help us to get there. Forward this email to all your colleagues with a last request to sign up. We will be submitting this petition to HEFCE as part of our response to their consultation and every signature will count.

Colleagues can sign the statement here: http://www.ucu.org.uk/standupforresearch

Thanks again for all your help,

Jonathan

Jonathan White
Deputy Head of Campaigns
UCU
Carlow Street
London
NW1 7LH

Meanwhile, Universities UK are proving to be a bunch of spineless yes-men; in this article their president is quoted saying about the pre-budget statement: "However, the sector is already absorbing considerable efficiency savings and the announcement that by 2012-2013, £600 million will be cut from higher education and science and research budgets will be extremely challenging for universities." (translates as: we won't lift a finger to fight back.)

Let me conclude this post with some more links etc: This image was sent to me by Greg Kochanski. This article on science budget cuts is enough to turn me into a Tory. An enthusiastic endorsement of Educators for Reform - read the blurb on the web site - great stuff.

"Stand up for Research" petition update

2009-11-25T01:16:00.000-08:00

Here's an email I received this morning - sign the petition if you have not yet done so! (I posted earlier about this topic here and here; and this page is a collection of links in support of the campaign, in addition to links that make the general case for curiosity-driven research.)

Dear colleague,

I wanted to update you on the progress of the “Stand up for Research” campaign.

More than 12,500 academics have now signed, making this the biggest ever such petition UCU has run. The signatories represent all disciplines, applied as well as pure research and come from every kind of university, defying the way in which the proposals trade research communities off against one another.

You can also read more about the campaign in the forthcoming edition of UC magazine, in which Professor Philip Moriarty from Nottingham University argues that “The imposition of impact criteria in peer review and in the REF is nothing less than an assault on core academic principles and the ethos of university research. It will also, perhaps counter-intuitively, be immensely damaging to the long-term socio-economic impact of academia.”

We now have only THREE WEEKS left to make this statement impossible to ignore.

Please help us do this by forwarding the link to the page to someone you know and asking them to sign it: http://www.ucu.org.uk/standupforresearch

Yours sincerely

Jonathan White

Journal special issues for conferences - why bother?

2009-11-13T06:11:00.000-08:00

Question: why do we bother with special issues of journals for conferences?

In an effort to appear scholarly, I googled a bit and found this article ("If Special Issues of Journals Are Not So Special, Why Has Their Use Proliferated?" by Richard T. Mowday in the Journal of Management Inquiry). That article considers special issues devoted to specific research subfields, rather than conferences, so is not very relevant to my question. (Various arguments for and against are dismissed as invalid, but they don't include the ones I mention below.) The topic arises in this blog post (Lance Fortnow, "Are conferences worth fixing?") but the topic is merely touched on in some of the comments.

My general understanding is that your conference paper is supposed to acquire a seal of approval from being invited to the special issue. The other motivation is that the journal paper should appear more rapidly than usual, but this does not always happen in my experience, and the delay of having to coordinate one's paper with half a dozen others is partly to blame. So we return to the "prestige" motivation. The trouble is, that the journal hosting the special issue, is not necessarily the one you would have submitted the paper to, in the absence of a special issue. Some people decline the invitation to the special issue (and submit to a different journal), and that seems to severely undermine this purpose of a special issue.

Am I right that special issues are supposed to be prestigious? I realise that any answer is to some extent, a self-fulfilling prophesy.

Full professorship in Economics/Game Theory and Computation

2009-11-06T01:24:00.000-08:00

Note, this is the first of three positions we will be advertising (see below), in an aim to build an internationally leading research group in this area. An official advert with details on how to apply, will appear on Nov 12th at the URL given below.

THE UNIVERSITY OF LIVERPOOL -- DEPARTMENT OF COMPUTER SCIENCE

CHAIR IN COMPUTER SCIENCE -- ECONOMICS AND COMPUTATION

Salary negotiable

The Department of Computer Science was ranked in the top 10 UK Computer Science departments in RAE2008, and building on this success, seeks to significantly expand current research around existing strengths at the intersection of economics/game theory and computer science. To this end, we invite applications for a full Professorship to be attached to the newly established Economics & Computation Research Group.

Led by Professor Paul Goldberg, the Group carries out research in the computational foundations of economics/game theory and economic theory in computer science. In addition to Prof Goldberg, the group currently has three other faculty members: Dr Martin Gairing, Dr Piotr Krysta, and Dr Rahul Savani.

Current areas of research activity in the group include:

* algorithmic game theory;

* mechanism design and auction theory;

* complexity of solution concepts, algorithms for solution concepts;

* optimisation problems in economics;

* computational social choice.

We welcome applications from candidates in these areas, as well as more application-oriented areas, such as recommender systems, and related areas, such as computational finance and computational economics.

Two further faculty positions have been approved for this group, and will be advertised after the professorial appointment. It is expected that the successful candidate will be actively involved with these appointments.

The successful candidate will have an excellent track record of research leadership at the intersection of computer science and economics/game theory, and will join a dynamic, world-class Department.

Informal enquiries may be directed to the head of group:

Professor Paul W. Goldberg

mailto:P.W.Goldberg@liverpool.ac.uk

phone: +44 151 795 4259

** Job Ref: A-570583

** CLOSING DATE FOR APPLICATIONS: 8 January 2010 **

Further details and an application pack will be available from the following URL after 12 November:

http://www.liv.ac.uk/working/job_vacancies/

** AN EQUAL OPPORTUNITY EMPLOYER

EPSRC's Schlimmbesserung

2009-11-05T08:21:00.000-08:00

I was recently circulated a letter from EPSRC (UK's main scientific research funding body) announcing that, in order to "alleviate pressure involved in our peer review process" they would

no longer accept uninvited resubmissions of proposals

constrain "repeatedly unsuccessful applicants" to submit only one application over a 12-month period

In the letter there is a definition of "repeatedly unsuccessful applicant" which does not bear repeating here.

I have figured out what is wrong with this policy: far from relieving pressure on peer review, it has the opposite effect. Note first that the research proposals that now end up getting prohibited were always easy to criticize, while the proposals that survive this cull are the ones where you have to think hard about how they rate in competition with each other. That does not in itself explain why it becomes harder to review a proposal --- the reason why it gets harder, is that a reviewer now has a much heavier responsibility to "get it right": if a proposal fails, someone's research agenda has just been closed down permanently (they can't resubmit) and in the worst case, they get personally blacklisted, just for good measure.

Based on some brief web searches, it seems that Schlimmbesserung is a variant of a more standard German word Verschlimmbesserung, meaning an improvement that makes things worse. (The claim is that English-speaking fans of long German words usually prefer "Schlimmbesserung". This page is informative.)

Stereotyping universities

2009-11-03T05:16:00.000-08:00

God, I hate being stereotyped. I don't think I'm absent-minded, nor do I wear a mortar-board. When Peter Mandelson says that universities should not be "islands or ivory towers" (see here) he is of course insinuating that universities are just that, out of touch with the real world, and so on. Well, it's a salutary reminder of what it must be like to belong to a social or racial group that gets itself stereotyped on a more frequent basis. Mandelson's remark forms part of a dismal-looking package of proposed reforms to the higher education system that purport to enhance the "customer experience"... not much in the way of concrete proposals, which is probably just as well, it's mainly a vague attempt to get universities perceived as just another industry. Mind you, if that's where he's coming from, can someone point out to him that we are, at least, a net exporter? Bloody politicians - they're all the same, got nothing better to do than spend half their time spouting off whatever cheap populist slogans it takes to get elected (not that we can accuse Mandelson of getting elected), and the other half making fabulous sums of money on after-dinner speeches and consulting contracts. All right, back to marking my COMP209 class test...

question about random sequences

2009-10-27T07:48:00.000-07:00

OK, a respite from my last two posts about the Research Excellence Framework. The following question occurred to me, I make no promise that it is interesting.

Suppose you repeatedly roll a fair die and write down the sequence of numbers you get. I'm going to delete numbers from the sequence according to the following rule. Let X be the first number in the sequence. I delete the first block of consecutive X's (which will usually just be the single X of course), then I delete the second block of consecutive X's, but retain everything in between. Then I do the same thing to the rest of the sequence of dice rolls - it will start with some Y not equal to X, so I get rid of the first two blocks of consecutive Y's and continue.

For example, I would delete the bold-face elements of the following:

2,3,6,1,1,2,2,4,2,3,3,5,4,5,5,4,6,2,3,2,4,1,5,2,3,2,...

And the question is, is the sequence of undeleted numbers indistinguishable from a completely random sequence? Seems to work for 2-sided dice (coins).

Research Excellence Framework (part 2)

2009-10-19T16:05:00.000-07:00

Continuing from my previous post; once again, foreigners who are not into schadenfreude should again read no further. Some new web links follow. First a couple of petitions:

Stand up for Research - the UCU petition; sign this!

another petition which is mainly on behalf of arts and humanities.

A new collection of web pages highlighting this topic: The Danger of Assessing Research By Economic Impact

The topic has led to a flurry of emails on the CPHC mailing list; opinions there are divided, there are some who don't mind the proposal, some who are defeatist and some who also object to it. Some discussion has addressed whether one should push for a broader definition of "impact" beyond economic impact, and also the general burden of assessment -- it is costly to have to stop what you're doing every 5 years and enter into an episode of acute navel-gazing, and the present Government does not propose to compensate us for that! Outside of CS, there is a stronger consensus against the proposed definition of "impact". Do not be defeatist - the REF is a version of (and probably largely plagiarized from) Australia's Research Quality Framework (RQF), a similar Gradgrind-like model which was cancelled in December 2007 due to a change in government. Notice that in the UK, prospects for a change in government are very strong -- let's see if history repeats itself!

And finally, let me quote from an article in the Guardian yesterday by Madeleine Bunting addresses the point that Market theory closed down public discourse about injustice. But we urgently need to describe what we should value. From the article:

But don't look to economists to get us out of this hollow mould of neoliberal economics and its bastard child, managerialism – the cost-benefit analysis and value-added gibberish that has made most people's working lives a mockery of everything they know to value.

Research Excellence Framework

2009-10-16T01:35:00.000-07:00

Readers from outside the UK may wish to stop reading at this point, unless they are into schadenfreude. I recommend readers from the UK to sign this petition, which is sponsored by the Universities and College Union (UCU). It relates to the Research Excellence Framework (REF). The following text accompanies the petition; below I add some of my own comments.

The latest proposal by the higher education funding councils is for 25% of the new Research Excellence Framework (REF) to be assessed according to 'economic and social impact'. As academics, researchers and higher education professionals we believe that it is counterproductive to make funding for the best research conditional on its perceived economic and social benefits.

The REF proposals are founded on a lack of understanding of how knowledge advances. It is often difficult to predict which research will create the greatest practical impact. History shows us that in many instances it is curiosity-driven research that has led to major scientific and cultural advances. If implemented, these proposals risk undermining support for basic research across all disciplines and may well lead to an academic brain drain to countries such as the United States that continue to value fundamental research.

Universities must continue to be spaces in which the spirit of adventure thrives and where researchers enjoy academic freedom to push back the boundaries of knowledge in their disciplines.

We, therefore, call on the UK funding councils to withdraw the current REF proposals and to work with academics and researchers on creating a funding regime which supports and fosters basic research in our universities and colleges rather than discourages it.

It is not only the UCU which expressing grave concerns about the REF; universities and societies that represent academic disciplines are also similarly concerned, and I will give examples of these in later posts. For the moment, the REF seems to be doing the impossible, namely to make us feel nostalgic for the Research Assessment Exercise (RAE). At least the RAE was exactly that, a research assessment exercise. It did not set out to distort the meanings of the words it uses such as "impact" and "excellence".

The REF -- in its proposed form -- discriminates against theoretical work and imposes an artificial incentive to do work that has short-term economic impact. And you know what? I've got nothing against economic impact. But if a certain kind of research is able to make money, that should be its own reward; government-funded money-making is ridiculous. And just don't call it "research excellence", it's not the same thing.

Some articles

Article in the Independent Against The Grain: 'I didn't become a scientist to help companies profit' by Philip Moriarty

See the comments that follow this article in the Guardian (the comments that get highly-recommended are correct)

State the open problems!

2009-10-05T13:33:00.000-07:00

A few incoming paper-review requests remind me of the following long-standing gripe.

A nice feature of theoretical computer science is that the results we obtain tend to raise lots of very well-defined research questions. I'm very much in favour of the practice of stating these open problems in detail, in our research papers. Indeed, a thorough discussion of future work is arguably as important as including references to all appropriate previous papers -- the latter puts you in touch with the past and the former makes the connection with the future. Some papers take a lot of care to spell out what the open problems are, but some (most?) don't bother. Maybe the authors think it should be obvious what the open problems are. Occasionally they perhaps don't want the reader to pick up on an open problem they've got lined up for a follow-up paper.

Let's consider the case where the open problem being raised is "obvious". For instance, suppose you give an algorithm that approximates some objective within a factor of 2.5. Clearly, any approximation ratio of better than 2.5 is (implicitly) raised by the paper's result, so why bother to point it out? I would say it usually is worth pointing out, partly just to confirm that you really would find further progress to be interesting, and partly because you might have some useful additional discussion to add, such as a consideration of the prospects for improving beyond a ratio of 2, say.

If someone writes a paper that is able to claim to have solved an open problem stated explicitly in a previous work, that's usually a good piece of relatively objective evidence that the result is interesting. Most papers do not manage to achieve this - they usually solve some variant of an open problem posed previously, and indeed "posed" may just mean implicitly rather than explicitly. This is, there is a scarcity of "official" open problems (those that have been raised and deemed to be interesting in a published paper).

(There are some web sites that help, e.g. Comp geometry problems has links to other open problem pages. Open problem garden: wiki for general math problems.)

New academic year

2009-09-28T07:35:00.000-07:00

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

2009-09-21T01:29:00.000-07:00

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

2009-09-07T06:46:00.000-07:00

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

2009-09-02T02:18:00.000-07:00

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

The need for copyright reform

2009-08-27T04:01:00.000-07:00

The UK pirate party has picked up press coverage recently, e.g. here and here in the Guardian. I am quite tempted to give them a protest vote at the next election; I have been dismayed by the way copyright law has been changed recently, as well as with new proposals. The articles relate to draconian proposals that could cut off your internet access if your kid downloads a copyrighted file without paying.

The Public Domain: Enclosing the Commons of the Mind is a new, freely-downloadable book by James Boyle (at Duke University law school) that discusses these issues. This paper by Hal Varian analyses the economics of copyright. (credit to this blog entry for pointing me to Varian's paper.)

Page 127 of Varian's article gives a brief history of how the term of copyright has been repeatedly extended in the USA. Now, copyright holders like to talk about "theft" and "stealing" in the context of copyright infringement. Well, if theft is by definition illegal, I guess what rights holders themselves have done does not qualify. On the other hand, if theft is simply the appropriation of something of value from someone else, without their consent, then extensions to copyright most definitely qualify. It's time to get angry with those people! They call us immoral, but they have stolen, and stolen repeatedly, from the public domain, all sorts of great works that ought to belong to us all. An enormous amount of work by long-dead authors is just about inaccessible, the collateral damage of copyright extensions that were motivated by the desire to "protect" only a small number of works. The collateral damage also includes all sorts of trivial stuff - books you once picked up in a used-book store, comics and magazines you once read as a kid, stuff that someone, somewhere would have put online, if only it were legal, but it's not, so instead it all get banished to a diminishing collection of dusty paper copies that no-one can ever find. All this for the sake of being able to profit from the creativity of someone who died over 70 years ago.

I'm not urging some kind of collectivist utopia where no intellectual property belongs to anyone. But, copyright should be like patents, that expire after (I think) 17 years. That's plenty of time to make money out of the intellectual property.

Time to move on from three-year degrees

2009-08-12T11:51:00.000-07:00

UK-centric post follows... This post is to discuss a situation that is becoming increasingly anomalous and unsustainable, namely the system in English universities in which the standard period of study time for an undergraduate degree is just three years. (Earlier I criticised a similar problem in the context of PhD degrees.) Here is the historical explanation for it:

English schools encouraged early specialisation, traditionally three "A levels" during the last two years of study (so you would focus for example, on Maths, Physics and Chemistry)

Students at university are financed by the local education authority, which would pay for three years of study only

Both of the above reasons are getting tenuous. There is a general understanding that A levels have gotten watered-down, and school-leavers are not so specialised (the latter is probably a good thing!). And students increasingly have to pay for their own education, either though government loans, or the lucky ones get their parents to foot the bill.

Reasons why the three-year system is coming under pressure, and not merely losing its historical justification, include:

Students have to work part-time to avoid large debts. So they can't be expected to put in three years of intensive full-time study, as was the traditional expectation. With respect to this, most people over age 40 seem to maintain an outmoded image of the student lifestyle.

A consequence of the three-year timescale is that it can be very unforgiving for students who fail exams. This aspect gains added urgency from the recent debate (here's a nice article) about what universities should be doing to help disadvantaged students (who are more likely to have part-time jobs, and hence fail exams).

International standards in general, and EU in particular, envisages at least four years of undergraduate study. I see loads of CVs from prospective PhD students from overseas and they nearly all have 4 years of undergraduate study, and often have additional masters-level study.

Putting the above points together, the reason why in most countries you expect to take 4+ years is precisely because you want the flexibility to re-take exams where necessary while holding down a part time job.

What's the way forward? I think the change can be achieved incrementrally; for starters universities should allow students to graduate "a year late"; if a student needs to pass one or two modules in order to get a degree, let him re-take the exams the following year, attend the courses, pay reduced fees for that year.

bacterial computation

2009-07-27T02:53:00.000-07:00

This article in the Guardian is attracting attention; rather over-inflated claims on behalf of the ability of bacteria to solve hard computational problems... (I did not post any of the comments attached to that article, but they are fun to read.) Could swine flu turn out to be even smarter than E. Coli?

I am now posting from Athens, visiting Koutsoupias and Papadimitriou; the instructions that blogger provides for logging in are rather hard to read...

Balanced set systems

2009-07-22T08:23:00.000-07:00

I've been trying to understand Scarf's core theorem, which says that if a coalitional non-tranferable utility game is balanced, then it has a non-empty core. In the context of transferable utility games, there is another definition of "balanced game" which should not be confused with the one for NTU games. Osborne and Rubinstein's book studies balanced TU games in some detail, but only briefly mentions balanced NTU games.

The definition (NTU case) uses the notion of a balanced set system, defined as follows...

Given a set N, suppose that C is a collection of subsets of N, i.e. C is a subset of 2^N. Let C={C₁,...,C_z}. We say that C is balanced if there are non-negative real numbers α_i, one for each C_i, such that, for every element of N, the sum over all C_i of their α values is 1.

The above definition is used in Scarf's 1967 paper.

The def can also be characterized as follows: Associate each member of N with a coordinate in Euclidean space, in fact let's associate it with a point in space representing the unit vector pointing in the direction of that coordinate. More generally, associate any subset of N with the average, or center of gravity, of the points corresponding to the members of that subset. An equivalent definition of "balanced collection of subsets of N" says that the point corresponding to the entire set N should be a convex combination of the points corresponding to these subsets of N. (the equivalence is straightforward; it is pointed out in this paper and probably quite a lot of others.)

There's an alternative definition that requires that the α_i should be positive, rather than just non-negative (e.g. this paper). This is not equivalent in terms of which set systems are balanced (but the definitions are indeed the same modulo their use in the definition of a balanced NTU game). Let's use the phrase "positively balanced" to refer to set systems where the α_i can all be positive. To see how they differ, suppose N={1,2,3} and consider the subsets {1},{2,3},{3}. These subsets are balanced, using the α values 1,1,0 respectively. It is easy to see that {3} must be given the value 0, so that these sets are balanced but not positively balanced.

From a geometrical perspective, "positively balanced" seems rather unsatisfying since a set system that is balanced but not positively balanced, is from the perspective of the α_i, nevertheless arbitrarily close to being positively balanced. I am wondering if there is some nice alternative combinatorial characterization of positively balanced set systems. On the other hand, for set systems that are not balanced (under the original definition) the set of all non-negative weighted sums of their corresponding points in space, is presumably bounded away from the average of all the points. Maybe it's interesting to ask how close you can get? (My guess: for N={1,2,...,n}, take the n-1 subsets N-{1}, ..., N-{n-1}; these are not balanced; but give each one α_i=1/(n-2), so for each i< n you get a total of 1, and for n you get a total of (n-1)/(n-2); pretty close to the all-ones vector.)

playing with javascript

2009-07-15T07:03:00.000-07:00

One thing missing from Facebook's "shite gifts for academics" is "web page of colleague who has just discovered javascript". Here is a modest example - my reason for learning javascript is partly because I teach a class on formal language theory, and thought it would be useful motivational material to show the students how javascript lets you use regular expressions to verify user input to a web page. And, I wanted to improve the functionality of COMSOC's program page, although by now I guess that collection of papers is yesterday's news.

BTW, another missing gift is "invitation to review paper by unspecified authors that requires you to log on to the publisher's web site using a hard-to-remember user name" - I recently got one of those, but not via Facebook.

Game theory and ad-hoc networks

2009-07-08T07:23:00.000-07:00

I am wondering if this could be a growth area... so there's been some work at this intersection, e.g. this paper posted to arxiv (CS and Game Theory) on Tuesday 7th July. Ad-hoc networks are composed of nodes, which in a game-theoretic context would constitute the agents or players.

I recently read another paper "New strategies for Revocation in Ad-Hoc Networks" (link) which doesn't have a game theory spin; I took a look at it because it was reported on in the New Scientist, and it relates to general issues I'm interested in, networks of decentralised agents trying to reach an agreement (so maybe there's an element of social choice theory?) where there are good and bad agents, and the good ones have to avoid being misled by the bad ones... "revocation" means removing the bad agents from the system, or at any rate, "blackballing" them.

For a theorist the paper is a bit unsatisfying to read since it doesn't spell out a mathematical model of what's going on (in terms of how agents can communicate, and what they are trying to achieve). And perhaps there is no nice model that wouldn't rule out the sort of approach one would want to use in practice, or else rule out the sort of attacks that the bad agents are supposed to be capable of. From time to time, agents may observe other agents misbehave, and when that happens, the observing agent, assuming it is one of the "good" agents, would want to report on the "bad" (misbehaving) agent to the other good ones. However, it is apparently possible for a bad agent, or agents, to bear false witness, so care must be taken in how to process one of these accusations. The only advantage the good agents have, is that they are in the majority (much less than one-third of agents are assumed bad). The paper mentions Byzantine generals, but doesn't really discuss the relationship. It would be interesting to come up with a model and relate it to the ones in The Byzantine Generals Problem and maybe also the FLP paper (Impossibility of distributed consensus with one faulty process).

Advertising PhD studentships

2009-06-30T02:16:00.000-07:00

(The following is motivated by my work on PhD admissions at Liverpool CS.)

Terence Tao opines that you should move from place to place when you progress from undergraduate to postgraduate to postdoctoral research. I tend to agree, but my sense is that within the UK most students are reluctant to do so.

One obstacle is that departments like to keep their best undergraduate students on their own PhD programmes, another is lack of information about outside opportunities, and which research strengths are located in which departments. New and new-ish web sites that advertise PhD study opportunities may alleviate this problem. Here's a list I made after hunting around; I thought that findaphd.com is probably the best for finding phd studentships, and the discussions on the postgraduateforum will be of interest to most current PhD students. These web sites are mainly geared towards specific projects; to locate general research strengths still requires a prospective student to ask around, or visit individual department web sites.

jobs.ac.uk
(mainly UK, not specifically for PhD studentships; (Uni of Warwick/Eduserve, Coventry));
find a PhD.com;
(UK/Europe, (The Science Registry Ltd, Sheffield), also operates find a masters and find a postdoc);
postgraduate forum
(UK, many online discussions of PhD study issues (The Science registry Ltd, Sheffield));
postgraduate studentships;
(UK, (online resource pages, North London))
hobsons postgrad and postgrad.com
(UK, (Hobsons, USA); links to a discussion forum, but postgraduateforum has more traffic);
find a PhD.co.uk
(UK, links to other sites);
PhDs.org
(USA, rank institutions based on your own priorities);
whatuni
(UK, mainly reviews of universities, allows search for PhD courses but not many there (hotcourses.com));
hotcourses.com
("the UK's largest course finder", but would you want to use a website with a name like "hotcourses"?)
prospects.ac.uk;
(UK; click on "postgrad study"; the site crashed when I tries to search for CS research programmes)

new postdoc positions (update)

2009-06-23T14:34:00.000-07:00

A couple of weeks ago I announced two new postdoc jobs (each of 3 years duration) in Algorithmic Game Theory, on the project Efficient Decentralised Approaches in Algorithmic Game Theory (to be run by me and colleagues at Liverpool, and Artur Czumaj at Warwick). At that time, we made preliminary announcement web pages here and here.

Here is the official ad (went live today) for the one at the University of Liverpool and here is the official ad for the one at the University of Warwick (See another copy here.) For both of these the closing date for applications is July 17th.

Here and here are the EPSRC summary pages for the grants for this joint project.

perpetual motion at Sainsbury's

2009-06-15T06:13:00.000-07:00

This article caught my eye in the Guardian's technology section: a branch of Sainsbury's supermarket is installing speed bumps that harvest energy "for free" from the cars passing over them.

Hang on a minute. You can only get energy from passing vehicles if you slow them down as they pass. I guess this could validly produce energy that would otherwise be wasted, strictly provided the speed bumps are installed on a stretch of road where most drivers would brake (this is not pointed out in the article). Although for me, in my Toyota Prius, when you brake the car is supposed to recycle that energy by using it to recharge the battery, so if I pass over those speed bumps I lose out -- ending up powering the supermarket and not the car battery.

Mac switchover

2009-06-12T06:04:00.000-07:00

Today I finally got around to getting my desktop PC replaced with a Mac that has been waiting in the wings while I come to terms with giving up much of the software I've gotten used to. My laptop is already a Mac, so now the switchover is complete; my souvenir of Windows is a couple of aging laptops left over from earlier.

The switchover was mainly driven by peer pressure; now I can whole-heartedly join in the discussions about the deficiencies of Windows (mainly the start-up time; one of my laptops actually "runs" Vista but I never used it because of a shortage of time).

New degree course in e-Finance

2009-06-10T15:10:00.000-07:00

My interest in this new degree programme dates back to just under a year ago, when my head of department asked me to be in charge of setting it up. Luckily, various colleagues at CS and University of Liverpool Management School (ULMS) are also involved, this is not the sort of thing you want to do on your own.

So, it's a 3-year undergraduate course to be taught jointly with ULMS, and it was formally approved a couple of weeks ago. Here is a link that has recently shown up, actually I should get some minor errors fixed in some of the information it contains.
I did not blog about it in case something went horribly wrong with the approval process (approval processes are there to make us resist the urge to set up degree programmes without due care and consideration); we have been under time pressure to get it started up for this September.

Background: lots of students at XJTLU (Liverpool's partner university in China) spend their first 2 years over there and then another 2 years over here. There are about 20 of them who will want to take this new course. Starting in 2010 we will accept new students (mainly UK and EU) to start in year 1 of the course; we don't know how many students it will attract but the students coming from China are enough to justify setting it up.

There is more work to be done, includes setting up a new taught module in CS (probably to be titled "electronic markets") but I'm happy we got the degree approved in time for the first cohort of XJTLU students. Credit must go to Ullrich Hustadt (CS dept expert on XJTLU, and on setting up new degrees) and Frank Steffen (main contact at ULMS). This degree should help to develop further collaborations between the two departments.

European elections

2009-06-08T05:33:00.000-07:00

The way that votes within a region are converted into a set of winning candidates is described in a rather unintuitive way here -- here is the relevant passage:

Once the vote count is complete and confirmed:

1. The party with the highest number of votes is allocated the first seat. The candidate at the top of the party's list is elected.
2. The votes of the party winning the first seat are then divided by the number of seats they have won + 1 ( i.e. 2 ) and the resultant number of votes go forward to be compared with the number of votes for the other parties and candidates to decide who wins the next seat.
3. The exercise is then repeated. As each successful party wins its first seat, its votes are divided by 2. This divisor is then increased by 1 each time this party wins a further seat. (NB it is the total number of votes cast for the party which is divided by the divisor, NOT the number resulting from the previous division.)
4. In the event that an independent candidate is elected or all the candidates on a party's list have been elected, the votes cast for that party are excluded from the remainder of the exercise.

This generalises plurality to election of k representatives: scale the votes obtained by each party by dividing them by a common factor chosen so that, when you round the new numbers down to the nearest integers, they add up to k. That's how many representatives each party gets.

My region (North-west England) has suffered the embarrassment of having elected a BNP candidate (one of 8 representatives) with the Green party narrowly failing to edge them out. Note that the number of votes obtained by the BNP actually went down. In my opinion, by putting up their leader as candidate in our region, we were unfairly targeted by them, and this result has more to do with low voter turnout. Both the Greens and the Lib Dems deserved to do better than they did.

MFI'09

2009-06-02T10:15:00.000-07:00

I am at the 5th Modeles Formels de l'Interaction; tomorrow I give a talk on the PPAD-completeness of computing Nash equilibrium. The meeting is in Lannion, in Brittany, I gather it's following the Dagstuhl approach of being out of the way in order for people to socialise. Although, getting there by train is pretty straightforward, even allowing for the poor quality of the web site that sells the tickets; it's not as out-of the-way as the Estonia winter school in March. Today I attended some talks on computational social choice and met up with some of the people who came to COMSOC. Air France lost my suitcase and my time spent online will be brief to conserve battery of laptop (the charger is in the suitcase.) Any questions by email relating to recent job announcements will have to wait until Friday.

Putting the VC into VCG

2009-05-25T23:19:00.000-07:00

There's a problem with blogging about papers you've read recently - actually there are two problems - maybe the paper was one that you had to review anonymously for a conference or journal, or else it was one that relates to current research (and so co-authors may be displeased if you tell all about the research problem of interest). But, the following paper seems to escape those.

This paper appeared recently on arxiv (VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension; Authors: Elchanan Mossel, Christos Papadimitriou, Michael Schapira, Yaron Singer). So, it relates to 2 topics of interest to me, i.e. mechanism design and the Vapnik-Chervonenkis dimension. The following is a summary of my sketchy understanding of the paper, concluding with a wild guess at a future research direction that may arise.

So, the VCG mechanism requires one to find the socially optimum outcome of an auction. Suppose a bunch of items are being sold to 2 bidders, who have limited budgets, which means you impose a ceiling on the value they may assign to any set of items. Finding the social optimum is now hard, I guess because it can encode a SUBSET SUM type of problem, i.e. you could easily find yourself trying to identify a bundle of items that just fits some bidder's budget, and if you overshoot, you end up undershooting for the other bidder.

In looking for an approximately optimal mechanism, you might try for a maximal in range mechanism, in which you simply delete from consideration some of the possible outcomes - if there are n items being sold, there are 2ⁿ ways to share them between the bidders (these are the outcomes) - now suppose you restrict to a limited subset of those, you still have a truthful mechanism, and the question becomes, can you find such a subset that results in an approximately optimal mechanism. What you need to do is, find a set of partitions such that, if the socially optimal partition is not a member of your set, there exists one that is close.

The way to argue that you still need exponentially many partitions, is to consider valuations in which, for some target partition, one bidder assigns unit value to each of his items, and the other bidder assigns unit value to each of the other items. The approximation quality of any alternative partition, will correspond to its Hamming distance from the target partition, and for distances less than n/2, the hamming balls only contain a very small fraction of the 2ⁿ partitions...

So you still have to optimize over a large number of the partitions. So many in fact, that there exists a set of sqrt(n) of the items such that any partition of those sqrt(n) items can be realised by one of the partitions that is being used by the maximal-in-range mechanism. This is the part that uses results about the VC dimension (defined on Wikipedia so no need for me to repeat the def; the VC dimension is a combinatorial measure of a set system, and in the context of learning theory, mainly comes in handy when the set system is infinite; in this paper the key result being used, by contrast, is about the VC dimension of specifically finite set systems).

Finally, what this leaves us with, is a (standard, unrestricted) budget-limited auction for sqrt(n) items (since all other items can be given zero value). This is polynomially related, so you are back where you started. Conclude that maximum-in-range mechanisms cannot both give a good approximately-optimal solution, and alleviate the computational difficulty.

Where to go from here? While Roberts Theorem suggests that your options are rather limited in designing a truthful mechanism, it applies to auctions where there are no restrictions on the values that bidders can give to outcomes. But, the 2ⁿ outcomes are resulting from only 2n valuations, so there is actually a lot of structure in the valuations that has so far gone unexploited. Maybe some clever ad-hoc mechanism could have better approximation than the crude one mentioned in the paper (where you just bundle all n items together and sell them all to one of the bidders.)