Friday, April 30, 2010

Experiments with envy-prone cake cutting

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.

Sunday, April 25, 2010

On May 6th, I'm voting for France

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.

Saturday, April 24, 2010

3 papers for my reading list

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.

Friday, April 23, 2010

impact of the election (or vice versa)

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.

Monday, April 12, 2010

email addresses with/without academic domain names

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