Tuesday, January 27, 2015

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.

Monday, January 26, 2015

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.

Thursday, January 22, 2015

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.

Friday, January 16, 2015

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.

Saturday, January 10, 2015

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.

Sunday, January 04, 2015

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

Monday, November 17, 2014

Oxford Algorithms: faculty position, studentships

Oxford University will shortly be announcing a (permanent) faculty position in Algorithms and Complexity. The official advertisement will appear on our web page http://www.cs.ox.ac.uk/research/algorithms/ early in 2015.

The department also has a bunch of new doctoral studentships advertised here. Quoting the ad: Following a generous donation by Google, the Department of Computer Science at the University of Oxford is delighted to invite applications for up to 15 fully-funded DPhil (Oxford’s PhD) studentships tenable from 1st October 2015.

The studentships are available for research in any area represented in the department.