Wednesday, October 23, 2013

article on privatisation of universities

I recommend the article Sold Out by Stefan Collini, in the London review of Books. It reviews two books about the process of privatisation/marketisation of higher education, that has taken place in the UK during the past roughly 30 years. Collini’s article provides a highly informative overview of the development and current state-of-play of private sector provision of HE, in the USA and UK. It then explains very lucidly the problems inherent in the current system of student funding, and is very convincing on why it cannot be expected to last. My only criticism: the article is passionate, but doesn’t propose remedial action. That may be because there’s a bigger picture (missing from the article) that includes, for example, the recent Royal Mail privatisation. According to this bigger picture theory, remedial action would not be specific to universities, but would involve a restoration of trust in public institutions and the public service ethic.

(added later:) ...And, this article (Economics students need to be taught more than neoclassical theory) in the Guardian looks relevant to the general topic. See also this earlier article (Economics students aim to tear up free-market syllabus). Their criticism of neoclassical economics is mainly that it failed to predict the financial crisis. It could also be blamed for an approach to student funding which takes the form of firstly, assuming all students are selfish agents, and secondly, repeatedly raising the price of higher education, in search of some kind of market equilibrium. 

Wednesday, October 09, 2013

What are the equilibria of this game?

In the course of writing a paper, we often construct examples of the sort of mathematical objects under analysis, as a means to figure out what’s true in general. Then the paper gets written, and the examples are stripped away, like the scaffolding from a completed building. Before it gets forgotten, I now provide an online description of the following game (that came up while writing this paper), since it sets you thinking about alternative solution concepts (exact/approximate Nash/correlated equilibria (well-supported or otherwise)), and which one(s) we are supposed to like best. Or maybe it could be used as part of a game theory exercise. (It may be helpful to point out that a well-supported ε-approximate equilibrium is one where no player ever uses a strategy that pays more than ε less than his best response. An approximate equilibrium that is NOT well-supported could allow some player to occasionally play a very poor strategy, provided that it’s with low probability.)

Suppose there are n players, numbered 1 through n. Each player has 2 pure strategies, call them a and b. Payoffs will be either 0 or 1, according to the following rule. Player 1 gets paid 1 to play a and 0 to play b, UNLESS all other players play a, in which case it’s the other way around. Meanwhile, for i>1, player i gets paid 1 to play the same way as player i−1 (otherwise is paid 0).

(If instead player 1 was paid to differ from player n, we would have a generalized Jordan game, with a unique Nash equilibrium where all players flip fair coins to choose a or b.)

So — spoiler alert — I reckon the answers are as follows. For exact Nash equilibrium, it’s not hard to see that players 1 and 2 can’t play pure strategies, and in fact players 1 and 2 should flip fair coins, meanwhile the other players all play 1. For exact correlated equilibrium, one solution (different from the NE) is for player 1 to flip a fair coin, while all the other players flip a single shared fair coin, ie they play the all-a’s vector or the all-b’s vector with equal probability. It looks like there is some freedom for any player to deviate slightly from this, while keeping it well-supported. In the neighbourhood of the original NE, only players 1 and 2 can deviate slightly, if we want the approximate equilibrium to be well-supported. (In fact, I think we can say more strongly, that all the well-supported Nash equilibria are in the vicinity of the exact NE.)

Interestingly, when we give up on the “well-supported” requirement for correlated equilibria, lots of other things become possible. Notably, all the players can play a with high probability 1−O(1/n), and this is what would start to happen if natural learning dynamics were applied to learn an equilibrium. Eventually, the dynamics should do something different; maybe converge to something in the region of the exact NE.

Tuesday, October 01, 2013

2 research posts in Algorithms and Complexity, Oxford

2 research positions in algorithms and complexity at the University of Oxford, each tenable for up to five years

Professor Leslie Ann Goldberg is looking for two postdoctoral researchers to join the ERC project Mapping the Complexity of Counting at the University of Oxford. (This post at Luca Aceto’s blog contains a link to the announcement of this and other ERC grants.) This is a five-year project from 1 Mar 2014 to 28 Feb 2019. The positions are available for the duration of the project (subject to satisfactory performance).

The salary range is £29,541 - £36,298, depending on experience.

Deadline for applications 15 Nov 2013
Details and application form at

The overall objectives of the project are:
  • To map out the landscape of computational counting problems (both exact and approximate), determining which problems are tractable, and which are intractable (quantifying the extent of tractability).
  • To discover complexity characterisations which elucidate the features that make counting problems tractable or intractable (telling us why each problem is tractable or intractable).

Within the context of these overall objectives, the goal is to study classes of counting problems which are as wide as possible (obviously including the problems that arise in practice), and within these classes, to develop complexity dichotomies/characterisations which are as precise as possible. The key problem domains that will be considered are graph homomorphism problems (including generalised weighted homomorphism problems), counting constraint satisfaction problems and holant problems. Key challenges include determining the effect of restrictions such as planarity, bipartiteness and bounded-degree constraints on the complexity of graph-theoretic counting problems.

Candidates should have a PhD in algorithms and complexity or in a closely related area of discrete mathematics.

Expertise in one or more of the following would be helpful: combinatorics or discrete probability, graph polynomials or partition functions, mixing rates of Markov chains, constraint satisfaction problems including algebraic methods for classifying their difficulty, holographic algorithms or holant problems.

REF submission deadline approaching

At the New Insights into Computational Intractability workshop, I find that some of our distinguished overseas speakers are blissfully unaware (or maybe: blissfully vaguely-aware) of ongoing work on submissions to the Research Excellence Framework. They’re unfamiliar with the heavy-duty administrative machinery that UK universities have set up to process the submissions, which will finally fall silent on the deadline of November 29th.  There are gaps in their knowledge about the functional dependence of the number of researchers a ‘unit of assessment’ (i.e., academic department) can submit, on the number of impact cases. They don't know that “evidence” is a verb, not just a noun. They don’t know the word “REF-able”. And so on.

My advice: it’s a time to indulge your UK colleagues when they gripe about REF. Especially if they’ve taken on any kind of responsibility for preparing a department’s REF submission. Buy them drinks. Appear sympathetic and remind that it’ll all be over in a few weeks. 

Sunday, September 29, 2013


Note: the EATCS Fellow scheme is new, so at this stage, there is no risk that anyone that you may be thinking of nominating for this recognition, already has it; the field is wide open! Here is the link on the EATCS web site.

Please note: all nominees and nominators must be EATCS Members

Submit by December 31 of the current year for Fellow consideration by email to the EATCS Secretary ( The subject line of the email should read "EATCS Fellow Nomination - <surname of candidate>".


The EATCS Fellows Program is established by the Association to recognize outstanding EATCS Members for their scientific achievements in the field of Theoretical Computer Science. The Fellow status is conferred by the EATCS Fellows-Selection Committee upon a person having a track record of intellectual and organizational leadership within the EATCS community. Fellows are expected to be "model citizens" of the TCS community, helping to develop the standing of TCS beyond the frontiers of the community.

In order to be considered by the EATCS Fellows-Selection Committee, candidates must be nominated by at least four EATCS Members.  Please verify your membership at

The EATCS Fellows-Selection Committee consists of
  • Rocco De Nicola (IMT Lucca, Italy)
  • Paul Goldberg (Oxford, UK)
  • Anca Muscholl (Bordeaux, France, chair)
  • Dorothea Wagner (Karlsruhe, Germany)
  • Roger Wattenhofer (ETH Zurich, CH)


A nomination should consist of answers to the questions below. It can be co-signed by several EATCS members. At least two nomination letters per candidate are recommended. If you are supporting the nomination from within the candidate's field of expertise, it is expected that you will be specific about the individual's technical contributions.

To be considered, nominations for 2014 must be received by December 31, 2013.

1 Name of candidate
Candidate's current affiliation and position
Candidate's email address, postal address and phone number
Nominator(s) relationship to the candidate

2 Short summary of candidate’s accomplishments (citation — 25 words or less)

3 Candidate’s accomplishments: Identify the most important
contributions that qualify the candidate for the rank of EATCS Fellow
according to the following two categories:

A) Technical achievements
B) Outstanding service to the TCS community

Please limit your comments to at most three pages.

4 Nominator(s):
Affiliation(s), email and postal address(es), phone number(s)

Tuesday, September 17, 2013

Books on display

A visitor is pleased to see a copy of Mas-Colell, Whinston, and Green on my office bookcase. Admittedly I have not read much of it, but it’s the thought that counts. It, and other books, are a conversation-starter. A book collection on display is a way to talk about yourself, and your interests, in an acceptable, take-it-or-leave-it way. If we all stop using paper books and switch to e-books, there will be a downside. There is not much on-line worrying about this downside of e-books (maybe I used the wrong search terms), but there are a few articles on the merits of bookcases that other people can look at. This web page explains reasons why paper books are nice (as artifacts), but doesn’t quite make the point about books as a personal statement. The bookshelf as a personal statement is discussed in this article which has a link to a website where you can upload a picture of your bookshelf.

Just for balance, this article “Breaking The Sentimental Attachment To Books” offers advice on helping you get rid of books you don’t need.

Friday, September 13, 2013

improving text by cutting it down

In making revisions to a paper that was accepted to a journal, I was told to make sure the abstract had no more than 150 words. Of course, my immediate assumption was that the abstract had already been perfected, and having to cut about 40 words could only make it worse. In the event I managed to improve the text as a result, and was left admitting that it was a useful exercise, purely for the purpose of good writing. Maybe I should always cut my text by 20% as part of the process of polishing the writing.

Yet I’m still reluctant to put that idea into practice. It’s probably due to some kind of ingrained resistance to the idea that you can improve something by making an economy. Economising isn’t supposed to be beneficial, it’s supposed to be onerous, right? Maybe the worry is that if I cut 20% voluntarily, I’ll be required to cut another 20%, and there must be some point at which the “less is more” principle stops applying...

Monday, September 09, 2013

Postdoc positions in algorithmic game theory at the University of Oxford

Three postdoc positions in Algorithmic Game Theory are available at the University of Oxford funded by the ERC Advanced Grant "Algorithms, Games, Mechanisms, and the Price of Anarchy" (Principal Investigator: Elias Koutsoupias). The researchers will be based in the Department of Computer Science and will be part of the newly-established Algorithms group in Oxford (  Work for these posts includes investigating, designing, and analyzing mechanisms; extending the theory of the price of anarchy and stability; investigating game-playing issues that arise by applying the algorithmic approach (e.g. limitations in computation and communication) to classical game theory.

Candidates should have a first degree and a doctorate in computer science or related discipline and a record of research in algorithmic game theory or a related area.
Area: Algorithmic Game Theory
Number of positions: 3
Duration: 1 year (extendable to 5 years)
Deadline for applications: 12 noon on 10th October 2013
Further information and applications:

Informal inquiries are welcome and should be directed to Elias Koutsoupias (