Saturday, July 16, 2011

A class in Game Theory for Management students

My host, Prof. Yukari Shirota, had arranged that whilst at Gakushuin University I would give an undergraduate class in some topic of mathematics to students in the Department of Management. For such a one-off, I had a fairly free hand as to subject matter; what seemed to be considered most valuable for the students was the (rare) opportunity to hear a native speaker of English (though actually I'm ethnically less than half English).

I chose Game Theory, the subject made famous by John von Neumann and Oskar Morgenstern in their landmark work, Theory of Games and Economic Behavior. I first came across Game Theory whilst at secondary school. In fact I became quite engrossed, venturing into Birmingham Central library to conduct research for an extended essay on a typewriter [yes, it was a long time ago]! I was fascinated by its confluence of mathematics, economics and psychology; the last of these particularly intrigues me. On this occasion my main reference was Games, Theory and Applications (1st edition) by Lyn Thomas, which I used during my own undergraduate studies at Southampton University. For anyone wanting to further their study, I would strongly recommend a textbook like this.

Game Theory as a production of Economics, Mathematics and Psychology

Would you like to explore this topic in this slightly extended post?

Good! So on a Wednesday morning I gave a class in the Multimedia Mathematics series to about 25 4th year undergraduates, kindly assisted by Prof. Shirota who gave explanations (sometimes in English, sometimes in Japanese) and encouragement. Normally there would be hands-on for students, but things were kept simple so that I only had to give a presentation with software demonstrations. I read somewhere some statistic indicating that the Japanese have more slides per presentation than any other nation, so I armed myself with 70+ slides. That's excessive, probably more suitable for 2-3 classes, but I had only one at my disposal and I wanted to share sufficient material to give a reasonable feel of the mathematical methods involved, including inductive reasoning and aspects of probability. I also included quite a few pictures and came up with simple examples to show how many situations in life can be treated as a game - such as growing tomatoes or commuting.

At the same time it was important for me not to rush delivery - speaking more slowly than usual, there was no way I would cover all this material in one go, so I just used a selection of slides, starting with the main concepts and proceeding via a few hops to a couple of famous non-zero-sum case studies, the Prisoner's [really prisoners'] Dilemma and The Battle of the Sexes.

I also had another prop with me - some reasonably authentic-looking notes in Pounds Sterling (Casdon PlayCash that I bought from the local Boswells store). I used it as an ice-breaker:

(Thanks to the American Mathematics Society for this idea, which I first saw on 'Who wants to be a mathematician?' roadshow).

Yes, a £1,000 giveaway! Except it was a bit credit-crunched: as only £937 cash was in the bank, I tried to explain that the British banks are struggling at the moment and a cheque could make up the remainder, £63.

The students were divided into 6 teams, A-F, one team per island, each with a representative. Each team was a 'player'. Teams had to choose a number N>=1; a team that picked the highest number would receive a share of £1000/N. This game had two rounds as follows:

  • Round 1 [slide 3 above]: no communication
    We should have collected pieces of paper; as it was, numbers went something like: 20,50,80,100,50,52.
    Team D won £10.
  • Round 2 [see slide 4]: communication allowed
    Teams chatted about this and quite quickly came to a decision, yielding the optimal result: 1,1,1,1,1,1, so each team gained £1000/6!

I was struck by the smoothness in reaching this outcome (and lack of betrayal among the teams) and think this may reflect a general culture in Japan of collective action and perhaps conformity, something that has helped the country to become such a productive and powerful economy. Quite different from an individualistic view, where it would be seen as problematic. It was later related to me that when someone says, "Ne...?" ("Isn't that so?"), there is often a feeling of obligation to say, "Ne!" ("Yes, that's so."). This would tend to support a culture of opinion leaders and followers. Ne?

In terms of software demonstration, I used mainly two tools, both released under open source licenses. The first was Gambit, which is a dedicated Game Theory suite that provides for the analysis of non-zero-sum games in both normal and extensive form. It has options to carry out computation, particularly of Nash Equilibrium, though one of its current limitations is that it restricts itself to games where players have to choose their moves independently. The other tool was Maxima, a Computer Algebra System, which I used for the graphical visualisation of payoff regions. Maxima by itself has only a command line interface, but it can invoke gnuplot to render graphical output and there is a choice of graphical interfaces: in my case I ran wxMaxima. All these are bundled together in the distribution.

I find the topics of communication and cooperation to be of philosophical interest. A standard definition of a cooperative game is couched in terms of business contracts (in the UK we can think of the Co-op supermarket) and so in such games players are said to enter binding agreements. It is used accordingly as a basic binary categorization and its importance is evident in e.g. providing assurance for the mathematical calculations. However, it means communication becomes secondary and I'd argue that [human] communication is more fundamental - it's what made the huge difference in the giveaway of slides 3 and 4 and to my lay-person's thinking, co-operation was established through a collectively agreed strategy before it became binding. No ties are needed to work together! Communication doesn't imply cooperation, but it usually precedes it.

So, I should issue the caveat that my slides exhibit a natural personal bias to this voluntary sense of cooperation, illustrated, for example in the Battle of the Sexes, in which a young married couple have free time at the weekend for an outing. The only issue is that the husband prefers a sporting venue, whilst his wife prefers a concert (so the story goes), but the bottom line is that they'd both prefer to be together than go there separate ways - see slides 65-71.

In Gambit (using this source file), we can compute the Nash equilibrium points. If we assume x is the probability with which the husband choose the first venue and y is similarly the probability that the wife chooses the first venue, then the expected returns e1 and e2 are given respectively by:

  • e1(x,y)=5xy -4x -4y +4 - (eq1)
  • e2(x,y)=5xy -4x -4y +4 -(eq2)
  • where 0 <=x <=1, 0<= y <=1.

For minimax we set both of these equations to equal the value of the game. Gambit can do the calculation for us. The following screenshot shows the matrix used and underneath three equilibrium points.

Battle of the Sexes: equilibrium points computed in Gambit

The first of the equilibrium points are the respective the minimax strategies. But a value of 4/5 seems rather poor and would suggest - if the payoff matrix is a true reflection - that both 'battlers' will reason that settling on any venue would be better. Indeed, underneath are two other equilibrium points that return expected returns of 1 and 4 and vice versa.

However, the computation of individual points doesn't give a full picture. Just a few lines of Maxima instructions enables us to compute the region covered by all mixed strategies. It generates a 3D parametric plot, and we can initially set the z-axis to be constant, so with a bit of dexterity, you can rotate it to show the following:

Maxima rendering of Battle of the Sexes

The x and y-axes denote the respective expectations for husband and wife. I'm fascinated by the shape: the attentuation to the corners (1,4) and (4,1) - this particular graph reminds me of someone sitting in a hammock! Note that the point (4/5,4/5), which is the expected value of the game under minimax, lies a long way from those corners and it's also nested deeply in the region. It's certainly not on the boundary since in equations 1 and 2 above, if we set x=y=0.5, we get e1(x,y)=e2(x,y)=1.25.

It's a graph that assumes no cooperation, which is not a very optimistic view of a newly wed couple. We'd expect them to work something out in the form of a cooperative strategy, pure or mixed, so that whenever they have an outing they will go to one of these attractions together. If that's the case, then we can simplify the equations so that the (0,0) outcomes are factored out. The resulting graph is a line, the convex closure of the original region:

Maxima rendering of Battle of the Sexes, with convex closure

(Incidentally, I wonder if there is some metric indicating how far one is from cooperation in choosing minimax, perhaps defined in terms of the angle created by the expected returns with pairs of 'pure cooperative' vertices - the smaller the angle, the greater the missed opportunity for cooperation...?)

In the case of the Prisoner's Dilemma there is no minimax strategy. Geometrically, if you plot that graph you get a triangle, i.e. the set of points in Euclidean space is already convex.

Student Response and Feedback

In the event the class listened attentively and concentrated well. The opening game helped to stimulate interest, which they seemed to sustain for the duration. I was informed that they could understand most of what I said, which was a relief since preparing this class felt a bit like navigating in the dark. Certainly a few of the students gave responses that indicated they understood particular concepts. Although I didn't receive questions at the end (same kind of traditional response as Thai and other oriental students), facial expressions were not blank or bemused. This may have been helped in no small measure by Prof. Shirota, who produced (in one evening/night!) a translation into Japanese of some (possibly all?) of the slides. This would also encourage students in further reading and assist them in an assignment - a write-up about the Prisoner's Dilemma.

Whilst at Gakushuin, I also met Prof. Jun WAKO, who is a specialist in Game Theory. I hope he would approve of my presentation, but at least he may now have a few more enquiries from interested students...

No comments: