Author Archives: wilson.mark.c

COMSOC Days 0, 1

NOTE: The entire conference report is available as a guest post on Noam Nisan’s blog.

I am in Dusseldorf for COMSOC 2010. The LOGICC tutorial day was yesterday and the first full day today. It is a good way to meet many people in a short time. The organizers are doing a good job overall. All talks today had a good or very good standard of presentation. The most interesting talks in my opinion:

Nicholas Tideman: after long experience, claims that spatial models are the best for modelling real voter behaviour. Discussed difficulties of obtaining real data and had plenty of computational problems to offer the audience, often involving Gaussian quadrature. Challenged us to generate fake elections that he could not distinguish from real ones.

Gabrielle Demange: has a new ranking method which she has characterized axiomatically. Ranking methods focus attention of the rankers, and there is a dynamic process which converges in some cases.

Tyler Lu: interpolate between social choice and full personalized recommendations. Isomorphic to theory of fully proportional representation. Hardness results, greedy algorithms, approximation algorithms.

Matthew Jackson: in experiments, if you offer people $100 now or $200 in 2 years, most take the $100. But if you offer $100 in 6 years or $200 in 8 years, they take the $200. This is inconsistent with standard rational models. Main idea is that perhaps each person has several “personalities”, some with more patience than others. He showed that in that case, this kind of inconsistency is basically inevitable (impossibility result like Arrow, but easier to prove).

Toby Walsh is giving a ridiculously large number of talks. One good idea he had is a standard library of benchmark election data for testing algorithms.

Plenty of complexity and especially parametrized complexity results.

An interesting new Mahonian permutation statistic

While studying the standard method for random permutation generation I discovered a function whose distribution on a uniformly random permutation of fixed length is the same as that of the number of inversions. Such things are called Mahonian permutation statistics.

This statistic appears to be new, but this is not as easy to show as I would like. After several attempts to find out by reading papers, asking experts and doing database searches, I concluded that it probably was and submitted the paper to the arXiv and for publication. Almost immediately I got email from Dennis White at University of Minnesota pointing out a connection with a paper by him and Galovich in 1996. This raises some questions: how much responsibility do we have in the modern research environment to check novelty? why is there no standard database of numerical values of all important functions, and how do we achieve one?

Abstract: The standard algorithm for generating a random permutation gives rise to an obvious permutation statistic $stat$ that is readily seen to be Mahonian. We give evidence showing that it is not equal to any previously published statistic. Nor does its joint distribution with the standard Eulerian statistics $des$ and $exc$ appear to coincide with any known Euler-Mahonian pair.
A general construction of Skandera yields an Eulerian partner $ska$ such that $(ska, stat)$ is equidistributed with $(des, maj)$. However $ska$ itself appears not to be a known Eulerian statistic.
Several ideas for further research on this topic are listed.

Download author copy

My French university experience

As part of an academic couple I have had my share of applying for jobs, but not recently. However this year I applied for a position at a university in Paris. The whole experience was interesting and frustrating. France really seems quite different from anywhere else I have dealt with. I did a lot of background reading and have seen that the current government have tried to shake up the university system substantially – it is underfunded, poorly adapted to student needs and overly rigid, perhaps exacerbated by the existence of the grandes ecoles. On the positive side, French research is still very good in many areas.

Academics at French universities are civil servants with many things about the job completely prescribed. For example, the number of hours of teaching, the salary and the application procedure. The last was unusual – fill in an online form, but also send 3 copies of the application by snail mail; send a CV but no letters of recommendation or even names of referees. Included in this is the requirement that the PhD degree certificate be translated – I did this myself and took to the head of the French department here, who said “Oh, I thought you had French” and proceeded to rewrite for me. My application was rejected because of the failure to meet the 3 snail mail copies requirement – luckily, some apologies and merging of two applications (I had applied for a related job on the advice of my local contact) saved the day. The selection procedure involved a committee of about 16 people, many of whom were researchers at the university concerned but with several other specialists in the research area from other nearby institutions. This was unusual in my experience and seems like a good idea. I was chosen for an interview in Paris, but since no costs for travel are reimbursed (apparently a standard French procedure!) I opted for a “visioconference” which was held at 11pm in Auckland (1pm in Paris). In my 20 minute presentation and interview I managed to speak French well enough to convince them I could handle teaching there, and was ranked first in this “concours”. Another very unusual feature was that the rankings of the candidates were semi-publicly available – surely against privacy laws in many countries. I was asked to accept or reject the offer during a fixed week, several weeks after I had been told that I would be offered it. In all that time, I never managed to find out the exact salary and benefits that would be offered, and was told that it would not be decided exactly until after I had been working there for a while!

In the end personal reasons meant I had to turn down the offer. From the point of view of experiencing Europe and being less isolated in research, not to mention the challenge of teaching in French, I have some feelings of regret. However, I am sure there would have been many negatives. I have gained some good experience for the future.

Recommending research articles

Challenge for AGT researchers: come up with a good mechanism to help the most noteworthy papers get the most notice!

As a start, Noam Nisan is trying an experiment to get people to recommend interesting papers in Algorithmic Game Theory/Economics. Journals no longer serve well in disseminating results quickly – is it possible to dispense with them altogether by using another way to give a signal of quality and noteworthiness?

I have doubts that this particular proposal will succeed, because of incentive compatibility problems. When we cite a paper when writing our own, it is usually taken as a recommendation (negative citations do occur, but relatively infrequently I guess). If we don’t cite it, a referee or the author may notice and our reputation will suffer. If we do cite it, our paper is probably more likely to get published. So there are some incentives to participate in that form of “recommendation”. However, recommending papers via Noam’s proposed scheme doesn’t seem to me to have as strong an incentive to participate. Who has the time to do it, if the recognition obtained for good recommendations is so low? Still, it’s good to have a first step, and I am sure with enough time and money a nice system could be devised that cuts out the for-profit journal publishers.

Ranking universities

Ranking universities according to “quality” or “impact” (mostly of research) has become a major enterprise in recent years (see Wikipedia page). There is even a blog devoted solely to the topic. Administrators at universities seem to be taking the rankings very seriously (at least when the results are favourable to them). Apparently, recent low rankings of French universities helped politicians to decide on reforms to the system.

The most famous rankings are those published by Times Higher Education and by Shanghai Jiao Tong University. THE used the company QS for its rankings until this year, when it has switched to Thomson Reuters. QS is continuing to rank.

The rankings have attracted much criticism. In particular, from what I have read the Shanghai ones seem to be not reproducible using the stated methodology, and the THE-QS relied heavily (40% weighting) on a survey of academics about reputation, which only attracted about 3500 participants. THE this time is trying for 25000.

I received an invitation to be one of the reputational survey participants, and I filled in the survey. There were many questions that required me to name (unprompted) up to 10 universities worldwide that I considered to be excellent in research (in my self-chosen area of expertise) or teaching, or would recommend students to attend (match the first few characters of the user input, with an option to write in places not in their database). The same thing was done for a geographic area with which I claimed the most familiarity. One drawback of this survey for me was that it is not possible to go back and change any answers. Once I had mistakenly selected North America to rank, I couldn’t change my mind after deciding I really knew Australasia better.

I was also asked which features of universities were most important in rankings, and given (I think – haven’t received anything) a free subscription to THE for 6 weeks for the effort. They will also send me a preview of the survey results.

Turing Centenary

2012 is the centenary of the birth of Alan Turing. Every time I read about him I find some new and amazing thing he has done, for example running a marathon in well under 3 hours. For someone who died at about the age I am now, he achieved an enormous amount.

Many activities to commemorate him and his contributions are being planned and a website giving a good overview is available.

East Coast humour

Late last year I had a trip to Philadelphia, New York and New Jersey. A few humorous things I saw there:

Newspaper headline: State police forces shrink ( to do what? )

Congratulations Albert Greenfield school for making adequate yearly progress

Welcome to Philadelphia – Mayor Mike Nutter

Recent talks I have given

“Higher order asymptotics from multivariate generating functions” was presented at University of Pennsylvania, Rutgers University, University of California Berkeley and University of California Davis.

“Measuring manipulability of voting rules” was presented at University of Rochester and Union College.

These and others can be found on my archive of talks.