Call for Nominations: EATCS FELLOWS 2016

European Association for Theoretical Computer Science (EATCS) Fellows 2016

• VERY IMPORTANT: all nominees and nominators must be EATCS Members
• Proposals for Fellow consideration in 2016 should be submitted by DECEMBER 31st, 2015 by email to the EATCS Secretary (secretary@eatcs.org). The subject line of the email should read "EATCS Fellow Nomination - surname of candidate".

REQUIREMENTS FOR EATCS NOMINATION:

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 http://www.eatcs.org/.

The EATCS Fellows-Selection Committee consists of

- Rocco De Nicola (IMT Lucca, Italy, chair) 
- Paul Goldberg (Oxford, UK)
- Anca Muscholl (Bordeaux, France)
- Dorothea Wagner (Karlsruhe, Germany)
- Roger Wattenhofer (ETH Zurich, CH)

INSTRUCTIONS:

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 2016 must be received by December 31, 2015.

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): Name(s); Affiliation(s), email and postal address(es), phone number(s)

advice for would-be PhD students

I recommend the article 10 steps to PhD failure in the Times Higher. The authors are based in Canada and are in the social sciences, but their list of 10 things to avoid, is something that would be useful to many prospective doctoral students I’ve come across. The most important ones, appropriately listed first, are

• Stay at the same university
• Do an unfunded PhD
• Choose the coolest supervisor

In what follows, I’ll assume you have read the article, and I just add some more notes. That first item, “Stay at the same university” refers to the practice of doing the PhD at the same university where you did your previous degree(s). My take on this is slightly different from the authors of the article. It’s not so much that staying the same university is intrinsically a weakness, but it raises the concern that you may have started on a doctoral degree for the wrong reason, i.e. geographical inertia, rather than the right reason which is that the research topic is of consuming interest. At the point that a prospective student is applying for PhD places, it looks a bit weak to only apply at one’s current university; a student who is bent on doing research should communicate that by maximising his chances of getting to do research — i.e. apply more widely, rather than maximising his chances to continue to live in the same town.

Concerning the “coolest supervisor” point, similar to “same university”, it is not necessarily wrong to end up with the coolest supervisor, but there exists the risk that the coolest supervisor was chosen for the wrong reason (coolness) rather than the right reason (you have a good working relationship, and the supervisor is good at what he does). Of course, finding the right supervisor is a notoriously hard problem and is very hit-and-miss. The risk is best mitigated by applying at multiple institutions, which gives you the opportunity to go for interview and meet potential supervisors, which gives you the opportunity to see whether you have a rapport.

(added 2 days later:) Some follow-up: I followed the steps to PhD failure and came out with a doctorate, and an older article said to be “trending”: 10 truths a PhD supervisor will never tell you.

Peyton fest

I write to thank the organisers of Peyton Young’s 70th birthday symposium, held in Oxford last week. The great thing about birthday symposia is that they are not rational in the economic sense (they do not make money) so they feel like taking a stand against the bean-counting mentality. Through celebrating the work of one of the research community’s well-known figures, we celebrate the community itself, and the intrinsic interest of the topic. Here’s a couple of thoughts on rationality. Vince Crawford’s talk made a point that explains one reason why game theory usually focuses on rational agents rather than boundedly-rational ones: I am tempted to call it the Anna Karenina principle: that rational agents are all alike, but every irrational agent is irrational in its own way. Hence, the study of irrational agents becomes diffuse, with a difficulty to reach agreement on what kind of irrationality to allow. (e.g.: I care about what values of ε one could compute ε-Nash equilibria in polynomial time, and one could argue endlessly about what constant value of ε might be considered acceptable. This is why a PTAS would be so nice.) Prior to hearing that point being made, when asked to explain why economists focus on rational agents, I’d note the basic requirement of economic mechanisms that they should function well in the presence of rational agents, and in general it’s too much to ask that they should perform well in the presence of irrational ones. The other item: in Peyton’s speech at the end, he considered possible future directions for game theory, and proposed that adaptability to changing conditions may become the new rationality: an agent should be judged on how well it handles change rather than whether it best-responds to a fixed environment.

group photo

and the programme

unimportant email

I’ve been getting quite a lot of journal spam recently. I wonder what sort of people would take the following seriously; it has an entertaining aspect (subject line: “Possible chance of publishing”).

Dear Dr. Paul Goldberg,

Greetings from International Journal of Innovative Research in Computer and Communication Engineering!

Hope this mail finds you in a jovial mood.

Assuming that you may have received our previous correspondence we are sending this as a polite reminder request to you. To know more about the journal, please visit here:

We would like to invite you to contribute a manuscript to be considered in the forthcoming issue of International Journal of Innovative Research in Computer and Communication Engineering (IJIRCCE).

(remainder not quoted)

“polite reminder”? I’m feeling more jovial by the second…

It reminds me of a fairly reliable rule about email, which is that there is an inverse relationship between the importance of a message, and the quantity of formatting (colours, fonts, links etc.) that it contains.

(added 16.5.15:) Another similar item of journal spam (subject “Publish your research”; includes request to be notified when you read the message):

Dear Dr. Paul Goldberg

Greetings from International Journal of Biomedical Data Mining!

Hope this mail finds you in a pink health!

We are enthralled to know about your scientific contribution in the area of Artificial Intelligence, Data mining and would like to invite you as a potential author.

(remainder not quoted)

(added 7.7.15:) The following comes from an address ending in katsura.letstogether.org, with a reply-to address of sas@seipub.org. Subject is *Solids and *Structures(SAS):

Dear *NAME*,

Your paper, Revenue maximization in a Bayesian double auction market, draws our attention.

Introduction

Solids and Structures(SAS) is an internationally refereed journal dedicated to publishing the latest advancements in solids and structures research.

Indexing

Google	ckan
World Cat	getCITED
Academia.edu	pub zone
Bible	Scribd.
Linker	Deepdyve
Aol.	ULRICHSWEB
Rice St	ARCHIVE
WIPO	Cloud D
AcademicKeys	…

Submission deadline

July. 26, 2015

Tips: accepted paper which is submitted before the deadline can enjoy a discount on registration fee.

That last example uses the new-ish technique of making reference to one of the recipient’s papers, presumably to gain his attention. Shame about the salutation, Dear *NAME*.

tempted by a cut to 6k tuition fees?

I have as many ill-informed opinions as the next voter, but luckily the only ones I consider writing up here are the ones directly relevant to academia.

A well-publicised Labour manifesto policy is to cut tuition fees from 9k/year to 6k/year, and this is meant to be a positive selling-point of their package.  Much as I disliked the change to the current regime, I can’t get excited about this proposal. Thinking about why not:

• A reduction of 3k is not a very big discount on 9k plus living expenses.
• The 6k proposal lacks detail about the repayment terms and interest rates (I did read the relevant part of the manifesto). Thus, we’re being offered a pig in a poke.
• There is no proposal to refund the students who have been required to take on 9k of debt per year. This shows a regrettable tolerance of unfairness to people who have ended up in greater debt due to sheer bad luck. The 6k tuition fee proposal is not so much about righting a wrong, as about a headline-grabbing policy proposal.
• This article seems to be showing that the current fees have at least brought in more money to UK universities, which is being spent on students. This takes place at a time of considerable international competition between universities, and we cannot afford not to spend more money on facilities at universities.
• While the current fees regime in unsustainable, we should welcome a transient period of stability (“meta-stability” for readers who know about Markov chain mixing…); I think we’re suffering from change-fatigue.

None of the above is supposed to be taken as supportive of the current 9k fees. I could actually feel supportive of this proposed cut to 6k, if it was presented as a step in the right direction; some kind of down-payment on the way to the abolition of fees. But that’s not how it’s being presented.

Added 16.10.15: THES article: Student voters had ‘less impact than expected’ on general election; sub-headline: Lack of enthusiasm for Labour £6K fees policy could have been factor, says Hepi report

Rating my co-authors

I feel like I’m something of a late-comer to the Rate My Co-author community (I include a link below, for completeness) and now feel like I should have joined earlier. It looks like one of these things whose user base reaches a critical mass, and then everyone has to join in. To be honest, I’m rather annoyed at how many of my co-authors seem to have claimed more than their fair share of the credit for various papers I worked with them on; now it seems I have to choose between making a counter-claim (and rely on Procaccia and Goldman’s fair division algorithms to moderate), or else enter into a costly dispute that may leave me worse off than if I just cave in and accept the lower share of credit. Their plan to integrate with Google scholar to produce the “world’s most accurate measure of an individual’s research contribution” is worrying. On the other hand, the fun aspect is seeing quite how many well-known papers seem to have dragged their authors into protracted disputes, to the extent that the authors end up with fewer “good co-author” points, than if only they had originally accepted a smaller share of the credit!

Anyway, the thing I like is the way you get to rate co-authors on about a dozen useful, but distinct skills. For example: Finding a fruitful line of research, Problem-solving, Being an optimist, Choosing a good venue, etc. There is clearly a big win to be had when it comes to team-building: we can now look up the skills of a potential research team, and check we’ve got everything covered. Previously I thought that Linkedin endorsements were the only available resource for this, but I admit to having been reluctant to endorsing my colleagues for (say) Latex skills, in case they take it the wrong way and demand endorsements for Algorithms, or Game theory.

Tutorial talks, and a reminder that total search problems are not NP-complete

Here is a link to recordings of invited and tutorial talks at the recent STACS 2015 conference. (Slides are available here.) These recordings include my tutorial talk on algorithmic game theory, all 3 hours of it, which may possibly be of use to writers of articles with titles like The Top Ten Mistakes you make When Giving a Technical Talk.

Possibly the commonest mistake (other than dressing badly) is to assume too much knowledge on the part of the audience. This mistake wastes the opportunity for a “big win” in which you present some fact or result that most people in the room don’t already know, but which should by rights be ingrained in their DNA. I got to do that via presenting Megiddo’s 1988 result that NP total search problems cannot be NP-complete unless NP=co-NP. To be clear, an NP total search problem is one where every instance has an easy-to-check solution, for example FACTORING, where the output is a prime factorization of an input number, or NASH, where the output is a Nash equilibrium of a given bimatrix game. This is the reason why we don’t bother to look for an NP-hardness result for NASH, and have to use an obscure-looking complexity class like PPAD.

It's possible to write a convincing proof sketch as follows. Consider what would it would mean if an NP total search problem (like FACTORING) was NP-complete. There should then be a poly-time reduction from (say) SAT to FACTORING. That is, an algorithm A that can solve SAT efficiently, provided that it has access to an efficient solver for FACTORING. Now consider what happens when pass a non-satisfiable formula Φ to A. What you end up concluding is that any run of A must constitute a (short) certificate that Φ is not satisfiable, implying NP=co-NP. A will process Φ, from time to time constructing instances of FACTORING that it can solve “for free”. Since every such instance of FACTORING must have a solution, A cannot fail for reasons of presenting the FACTORING oracle with an unsolvable instance, so must run its course. If it ends without finding a satisfying assignment, there isn’t one.

Game theory and cool-kidology

It would appear that there’s a substantial academic literature on social groupings amongst adolescents at schools. I learned about this while attending a seminar by Robert Akerlof on Social norm formation: the role of esteem. The paper considers a simplified model of social interaction between adoloscents¹ in which (in a 2-player version) each player makes 3 choices: effort at 2 activities (academic achievement versus rock music), which one to value, and whether to interact with the other player. There are exogenous costs of effort and of interaction; the latter may be positive or negative. If both players choose to interact with effort at the same activity, then the weaker player grants esteem to the other player; self-esteem may also be derived from valuing the activity you really prefer. Esteem is what everyone wants. The model is somewhat reminiscent of social network models of opinion adoption, but without an underlying graph and neighbourhood structure.

The paper aims to be “the first model to capture the conflict between conformity and differentiation, which is at the heart of social interaction in many economic settings”. One key feature of the real world that the model aims to capture is the way we give up on activities where there are poor prospects of being competitive; competition for academic achievement is high amongst pupils of similar ability, but a big disparity may cause the weaker ones to switch to something else entirely. Apparently this can be used to explain why Catholic schools have lower drop-out rates; the lower cost of interaction helps (according to the equilibrium of the simultaneous-move game) pupils who are weak academically, and would be most likely to drop out. The model also predicts a “smart set”, and a “cool set” who have high self-esteem, and the middle, who have low self-esteem. That was probably you, if you read this far.

¹No jokes now. I’m willing to accept that it’s possible to simplify interaction amongst adolescents.

Not just a little local difficulty

Last week I attended a debate on a proposal for work to be carried out to improve the appearance of the Castle Mill student residences at Oxford. This article reports the outcome of the debate, and the basics of the background to it. The proposal to remove the top floor of the residences was rejected with 210 votes in favour and 536 votes against. But (as reported here) supporters of the proposal are now requiring a postal vote of all approximately 4500 academics/senior admins who are eligible to vote. I’m glad I went along to the debate, even though my opinion was unchanged; I just became slightly more convinced that it would be daft to remove the top floor of the buildings. I would encourage anyone to read the transcripts of the speeches, that appear in this supplement to the latest issue of the university’s Gazette. I couldn’t give the debate a write-up that would do it justice; it touched on interesting and fundamental issues such as the extent which someone is obliged to remedy an accidentally bad outcome, what’s to be done about the shortage of housing, and the fundamental nature and purpose of Oxford (the city, as much as the university).

The following are a few points I took away. It was pointed out that the cost of implementing the proposal is a very small fraction of the university’s turnover. The counter-argument is that nearly all of the university's turnover (including philanthropic donations) is devoted to specific projects, and is not discretionary income; the cost of work on the residences would have to be met from discretionary funds. That’s a reminder, in turn, that such discretionary funds are very valuable, and should be carefully looked after. It was also pointed out that the 38 student rooms that would be lost by the proposal represents a very small fraction of the university’s estate (and an even smaller fraction of the total amount of student housing in Oxford). The counter-argument is that it is (or ought to be) pretty hard to demolish student rooms (at a substantial cost) at a time when Oxford is the most unaffordable place in the UK. It also occurs to me that due to the inelastic nature of housing demand, it could easily be the case that a small change in student housing availability could have a disproportionate effect on the price of student housing, one that would impact on the cost of living for all Oxford students. (Although Oxford’s absentee-landlords may cite a positive externality.)

I chose the title of this article since it notes the “bigger picture”, which I felt got slightly less attention in the debate than it deserved. It is taken from a speech by one of the supporters of the proposal, who argued that if it did not go ahead, that outcome would make the university appear uncaring about its surroundings, and it would be less favourably regarded by outsiders, including potential benefactors. Against that, the same problem arises with spending a lot of money in getting rid of high-quality student rooms. Another “bigger picture” point was made that the university has to change and evolve in order to maintain its leading position in the wider academic world. The city of Oxford’s raison-d’être has got more to do with an internationally-leading university than a nationally-competitive meadow. Personally I would have liked one or two speakers to emphasise the point that at a time of worsening housing shortage at the national level, decisions to build have to be made in a more hasty manner than may be desirable in an ideal world, and we sometimes have to make certain sacrifices in order to ensure that people have roofs over their head.

As a final note, surely the view of St. Barnabas Church is no great loss. I’m quite a fan of Victorian architecture, but the main reason to preserve St. Barnabas Church is as a reminder that occasionally the Victorians got things badly wrong. That picture on the Wikipedia page speaks more eloquently to that point than I possibly could.

Analysis of REF 2014 results

Here are a couple of recent articles I found interesting at Wonkhe (which as election time approaches deserves to be of interest to UK academics).

The hidden bang-for-buck heroes of UK research presents a (yet another) league table, this one ranking universities according to a measure of their research output, divided by their research income. I like the idea since it sometimes seems like universities and academics get judged by their research inputs more than by their research outputs. On the other hand (“be careful what you wish for”), there’s a downside to the pursuit of value for money: consider the way various airlines have gone low-cost; side-effects have been reductions in quality, reduced profitability, corner-cutting on safety, and they are less attractive as employers than they used to be.

Teaching and research: A zero-sum game? —the title caught my eye— shows a scatter plot of universities with research output on the x-axis, and teaching (National Student Survey) on the y-axis. I was unconvinced by the claimed positive correlation, but agree that there seem to be two clusters, with research output constituting the relevant attribute.

Game theory and anger

As a child, I recall learning the Latin tag “Ira furor brevis est” (Anger is a brief madness). It makes the point that anger is irrational; really, as game theorists we ought never to get angry. On the other hand, emotional modelling is important for us as computer scientists: the article Computationally Modeling Human Emotion was highlighted on the front cover of the December issue of the CACM. A recent article, The Commitment Function of Angry Facial Expressions, by Lawrence Ian Reed, Peter DeScioli, and Steven A. Pinker (RDP in what follows), provides a satisfying game-theoretic explanation. The clue is in the Latin tag: you may benefit from being irrational, if you can convince your opponent that you are irrational. This helps you get better payoff in the ultimatum game.

Recall that in the ultimatum game, player 1 gets (provisionally) a sum of money that he is to share with player 2. He does this by offering player 2 some percentage of the money, and if player 2 accepts, the money is divided accordingly, but if player 2 rejects, neither player gets anything. This means that a rational player 2 should accept even a derisory offer from player 1, but in experiments the money tends to be split more evenly. If player 2 can convince player 1 that he is not rational (will reject a derisory offer) he stands to do better.

The RDP paper tested the ultimatum game on several hundred players (over Amazon’s Mechanical Turk), in which player 1 got to see a video clip, purporting to come from player 2, announcing what player 2 would accept, either with or without an angry expression. A one-sentence summary of results is that the angry expression helps player 2 get a better offer from player 1. Player 2 wins by convincing player 1 he is irrational.

As a usage of game theory, does this still fall foul of Ariel Rubinstein’s critique of game theory, in which he says that some of the arguments for game theory do nothing more than attach labels to real life situations? I feel like it does help to justify the study of game theory, e.g. study of the ultimatum game for its own sake, since it would be hard to just devise it on ad ad-hoc basis, in the context of the RDP paper.

Finally, while the RDP paper concentrates on the appearance of anger, as opposed to its reality, it seems like a basis for explaining the existence of anger in the first place. That is, in a world where we worry that undervaluing someone else’s welfare may cause them to succumb to a “furor brevis” and do something you’ll both regret, we all cooperate more. There are articles like this one that seek to explain anger and advise people on how to deal with it, that miss this game-theoretic point. So next time you see someone lose their temper, explain to them that their behaviour is not a bug but a feature, that is against the interest of the individual but in the interest of the tribe. Then duck for cover.

Associate/Full Professor Position at Oxford in Algorithms or Complexity

The Department of Computer Science at the University of Oxford is planning to make an appointment at associate/full professor level with effect from 1 September 2015 or as soon as possible thereafter.

Applicants should hold a PhD in computer science or a related subject and have experience in any area related to algorithms or complexity.

The details are here. Please get in touch if you are thinking of applying, and have questions about the college system and its benefits.

Microeconomics and machine learning

A couple of recent article in The Economist discuss that in the age of big data, microeconomists may be able to gain some of the prestige that mainly goes to macroeconomists. A long way from dismal: microeconomics is fingered as the way forward in applying large data sets to the challenge of making economic predictions. Quotes:

But technology is lending them [microeconomists] clout. Armed with vast data sets produced by tech firms, microeconomists can produce startlingly good forecasts of human behaviour

The success of micro is its magpie approach, stealing ideas from psychology to artificial intelligence.

Another article: Meet the market shapers discusses examples of Silicon valley firms using microeconomic models to learn from data.

Can the golden triangle learn to share, just a little?

According to The Economist, Cambridge leaves Oxford trailing in its wake. The names refer to the cities rather than the universities. Over the past few years, Cambridge has attracted substantially more highly skilled people and jobs, and has built a lot more houses. It’s the shortage of housing in Oxford, and vested interests that resist building new houses, that are blamed for stifling Oxford’s growth.

I’ve lived in the North of England for long enough to find it repugnant that cities like Oxford and Cambridge should be encouraged to compete with each other to attract highly-skilled jobs. It’s not long ago that Astra Zeneca decided to move its research lab from Cheshire to Cambridge, at a time when there’s a valid concern that London (and the South-East) are sucking the economic life out of the rest of the nation. The article states: “Companies [in Oxford] complain that the exorbitant cost of housing is making it hard to hold onto workers.” The challenge is to translate this market force into action, and move some of these companies northwards.

(added 19.1.15:) See Cities Outlook 2015, newly released by the Centre for Cities, for more details on the importance of addressing the North-South divide, and how bad the problem has become.

(added 22.1.15:) Article with a strange message:

Universities minister Greg Clark has called on leading universities in the Midlands and North of England to do more to tackle a north-south divide in the number of school leavers entering leading universities.

Fine so far.

Analysis of government figures by the Sutton Trust for The Times has shown that all but one of 20 local authorities that send the most pupils to the most selective universities are from the London and the south east of England. The 20 sending the fewest school leavers to top universities are predominantly in the most deprived areas in the north and Midlands regions.

Well, since the selective unis are in London and the SE, to the extent that students are biased by locality, that disparity ought to exist.

Mr Clark said he wanted leading universities, particularly those in areas that send the least pupils into higher education, to work more closely with schools and be more creative in their efforts to raise aspirations among pupils. Citing Sheffield Hallam University as an example of an institution that is providing effective access support to schools and colleges in its region,...

This is the dodgy bit. It seems like Northern unis are supposed to facilitate the process of shipping the top students out to another part of the country. That is equal and opposite to what is needed to tackle the North-South divide.

The complexity of choosing a seat on a bus

My last blog post/question was such a useful source of answers that I have to try this one.

Suppose that you’re about to join a conference excursion with a bunch of game theorists, and the time comes to get on the bus. You join an orderly queue, and when you board the bus, you face a binary choice: either occupy one of an empty pair of seats, or occupy a seat next to someone else. (A standard bus divides its occupants into pairs.) In the latter case, you choose your favourite neighbour amongst people who do not currently have a neighbour, which is easy because, being a game theorist (or if you prefer, a computer scientist) you maintain a complete ranking of how much you like to sit next to each other person. To cover the possibility that the bus has extra space, let’s assume one of the items in the ranking is the case that you have no neighbour.

In order to make that original binary decision, you have to predict who will sit next to you if you occupy one of an empty pair of seats. Luckily, you know the preferences of all the other game theorists, in fact they are common knowledge, along with who precedes who in the queue. So, if you’re the penultimate person to get on, you simply check whether the last person would sit next to you given the opportunity, in which case you choose between him and the best other available person; if not, you choose between being alone and being with the best other available person. If there are 2 people behind you, you assume that the penultimate person would reason like that, and so on. Clearly there’s a unique solution, and… actually let’s say these people are game theorists rather than computer scientists, since I’d like to assume they are computationally unbounded. The question we face as computer scientists is to compute the solution.

All I know is that the problem is in PSPACE. It’s possible to come up with more general, on-steroids versions, such as choosing where to sit at a banquet, but the bus question will do for now.

How to share a box of chocolates

The following problem came up during the festive season: there was a box of chocolates to be shared out amongst family members, using the standard round-robin mechanism. The question that arises is which one should you choose when it’s your turn? If, say, you love marzipan and everyone else hates it, you should probably not choose marzipan right away; you should leave it until later and go for your second-favourite flavour on the grounds that the second-favourite might otherwise get taken. In an attempt to appear scholarly in considering this important question, I hunted around for literature on sharing indivisible goods. Unfortunately, this work seems to focus on topics like fairness and envy-freeness, rather than providing practical guidance to a player intent on manipulating the system^*. I did find this nice article by Steven Brams, at Plus Magazine, which has lots of articles aimed at getting a general audience interested in mathematical topics. Brams’ article addresses the question of how to allocate as many of the items as possible in an envy-free way, setting aside the other “contested” items, which perhaps then have to be handed out with some randomisation.

As in Brams’ article, I assume that players submit to the mechanism a ranking of the items to be shared, and then player 1 is allocated his highest-ranked item, then player 2 is allocated his highest-ranked item amongst the remaining ones, and so on. But now let’s not worry about envy, which is a potential problem whenever a player’s highest-ranked item gets taken; we just fix the mechanism and study the Nash equilibria. I’m pretty sure there’s a pure-strategy Nash equilibrium in which all players use the same ranking, as follows. Player 1’s favourite item is ranked highest, then player 2’s favourite item (amongst the remaining ones) is ranked second-highest, player 3’s favourite item from amongst the remaining ones is third, and so on. To justify this, note that player 1 should want to collect his favourite item right away, since it will certainly go if he takes some other one. The other players should be OK with ranking player 1’s favourite item highest, simply because that item will be taken by player 1, so it costs them nothing to rank it highest. And so on for the other items. It may be of some interest to consider alternative equilibria, but this solution has the benefit of being a pure-strategy solution that’s easy to compute. It also establishes a rational basis for demanding the same item that everyone else wants.

^*Lest we forget, this is the standard system for picking competing teams on the school playground, and it is claimed to be, if not exactly envy-free, at least a way of getting teams that are evenly-matched. (And I’d be prepared to bet that most game theorists would lament that they were not the sought-after items back in the day, which may explain the research interest in alternative mechanisms :-)