Modulo Errors

This entry first appeared as a writeup for Everything2.

Greedy pig is a simple maths game for groups that serves as an introduction to probability. I used it recently as a warm-up activity for a maths hour with local primary school children (around 11 years old), where it was well-received. For older students, it could provide the starting point for a discussion of topics such as the gambler’s fallacy or for a statistical investigation.

How to Play

A pair of dice are thrown, and their total recorded as a starting score for all participants. Play then proceeds in rounds. Before each round, players decide whether to stick with their current score, or continue playing. To play a round, roll a die; each player who is still in adds that many points to their score- unless a two is thrown, in which case they lose all their points. Play proceeds until all participants have decided to keep their score, or a two eliminates all remaining players. The winners of the game are the players with the highest score; it’s worth playing around three games and taking a combined total.

Practical issues when running the game

Keeping track of who’s in or out is most easily done by having students stand up if they wish to gamble or sit down if they wish to stick with their score. Apart from making it easy to spot when a player is trying to sneak back into the game, this is also good as it gives the students an idea of how confident their peers are to continue, and you’ll get lots of them wavering up and down as they try to decide!

Recording scores of players as they drop out is harder, but vital- children may try to cheat, or accuse each other of doing so, when it comes to declaring their final total. It’s definitely worth keeping a running tally of throws and totals on the blackboard -with the students doing the adding up! For smaller groups, you might be able to give out tokens or numbered cards as players save their score, but with larger groups (we had around 30 students per session) this would probably slow things down a lot. Perhaps give each student a piece of paper and a pen to write their score on (nice and large!) to hold up once they’ve sat down.

Some children are very risk adverse, and sit down almost immediately; others just stay standing until they get knocked out by a two. To make sure this isn’t due to misunderstanding the game, it’s worth doing a practice run first. It’s interesting to watch how strategies adapt as the players get more experience- particularly if the two is thrown surprisingly early or late in a game (we hit a total in the 70s for one session, which skewed things somewhat!)

Strategy

Can we say anything mathematically about when a player should sit down? That is, should we gamble a given total or not? You might want to think about this yourself before reading on.

To model this game, we can consider the expectation of a round- that is, the average outcome in the long run. Suppose then we have a total of N. Obviously, it’s only worth playing if our expected increase in the total offsets the risk of losing it all. One sixth of the time, a one will be thrown in the next round, leading to a gain of 1; with equal probability we might gain 3,4,5, or 6. So five sixths of the time, we gain some amount. But the remaining sixth of the time, we’ll hit a two and lose everything; this can be thought of as a ‘gain’ of minus N. So our expected gain by staying in is:

(1/6)*1+(1/6)*(-N)+(1/6)*3+(1/6)*4+(1/6)*5+(1/6)*6 = (1/6)*(1+3+4+5+6-N) = (19-N)/6.

Hence, for a play to be worthwhile, we need (19-N)/6 (and thus 19-N) to be positive. That is, we should be willing to gamble on a total of 19 or less, but a total of 20 or above should be banked.

Game Theory

However, as is always the case with expectation theory, this analysis depends on playing a large number of games and considering the total (or average) score across them. Playing just a few games tends to encourage an ‘all or nothing’ approach wherein players are more interested in winning in absolute terms (that is, being best in class) than the score attained in the progress.

Of course, the ideal time to bank is just before the two is thrown, thus leaving you with the maximum possible score (anyone who sat out earlier has less; anyone who stayed in scores zero). The problem is that by banking a score in a given round with the hope of winning that particular game, you are effectively gambling on it being the next throw being a two, and you’ll only be right one sixth of the time. The remaining five sixths of the time, you’ll be wrong and the others get a higher score- in a group situation, any of them could now retire with a better score than you, and in a 1-on-1 duel your opponent can bank immediately to guarantee the win.

But then, if everyone adopts this brinksmanship strategy of always staying in, then eventually they will all go over the brink and score zero. Depending on how the payoffs are modelled (which is of course crucial!) this two-player version of a round of Greedy Pig can be interpreted in game-theoretic terms as follows. If neither player has an advantage over the other, either by ending the game with a tied score, or by proceeding to another round, then assign them a score of 1, unless both players tied with zero, in which case score 0. Else, if one player wins the game this round and the other loses, the winner scores 2 and the loser 0. Mixing in the probabilities of winning or losing depending on a play of stick or gamble, we get a payoff bimatrix:

Notice that for player 1 the ‘gamble’ row dominates the ’stick’ row (and equivalently for player 2 in columns), and thus each player must gamble despite the fact that they each prefer the outcome of both sticking (score 1) to both gambling (score 5/6). Thinking of sticking as cooperating, and gambling as defecting, this is precisely the famous prisoner’s dilemma!

Variations

More advanced versions of Greedy Pig, and the resulting changes in optimal strategy, can be explored. For instance, you could cap the number of rounds to be played. A pair of dice could be used, scoring by either adding the total of both or taking their difference; this also allows for a range of elimination conditions: ending the game on a double, when either die is a 2, for a particular total etc. You could also vary the frequency with which players choose to gamble, such as commiting them to two throws of the die each round. But, particularly for younger children, beware of making the game too complicated at the expense of fun!

Based on my experiences running primary school workshops as part of the Science Communcation in Action scheme at the University of Edinburgh. Unfortunately, I do not know who deserves the original credit for this game.

Today I gave the first of this year’s postgraduate colloquia series, The Mathematics of Being Nice- cooperation in the Prisoner’s Dilemma. You can grab the slideshow as pdf here; since the potential audience was quite broad (and I’m no expert) I think it’s fairly light technically, and thus hopefully more accessible than many of my posts here. It’s essentially the talk version of my article for iSquared, so you should invest in a copy of that if you want something that’s more fleshed out!

A while ago I received a request for articles for a new magazine, iSquared, which seeks to cover mathematical topics, particularly real-world applications, at a level accessible to those not active in the field. This is quite a challenge, but a vital one. My own article, on the Prisoner’s Dilemma in game theory, appears in the first edition, so you can judge how well I did by buying a copy! I suspect I went overly-technical, but it’s a long time since I was an A-level student- although I remember reading New Scientist then and I don’t think the content is any more demanding in iSquared. Certainly I feel any scientifically literate undergrad with an interest in maths would find it rewarding, and at £10 for the year, educators have little to lose by picking up a subscription for a college library. For those of you more deeply involved in the subject, why not consider writing an article? Whichever category you fall into, please give it your support!

I’ve now converted the majority of my game theory project to E2nodes, through a dedicated account. The content has been significantly rearranged for some topics, to make better use of E2’s nodal structure; hopefully individual entries stand alone a bit better so that it isn’t necessary to read the entire report to understand what’s going on. I’ll also be adding more content to that account to clarify or expand upon the original document.

For my final year project (MA40128 at the University of Bath), I studied game theory, and now that I’ve completed it, I’m making the report available here. There’s a choice of [ps] or [pdf] format; I intend to node the whole thing at a later date. The report discusses Von Neumann’s minimax theorem; Nash’s theorem and equilibria; the Prisoner’s dilemma (including recent results on IPD tournaments); and Shapley value.

To assist with my upcoming project on game theory, I’ve put together some MATLAB functions to run iterated prisoner’s dilemma tournaments. In particular, this demonstrates the effects of the Southampton strategy I described a while ago on E2. MATLAB’s vector operations turned out to be particularly well suited to this, especially for handling unknown competition length or numbers of participants. The files are reasonably well documented, but I thought I’d offer some additional guidance.

Drop the files below into the same directory and run the tournament script to generate some sample output. Each program plays every other for the specified number of rounds, including itself, then a total score is obtained for each. The matrix returned gives the scores of individual pairings in the natural way; the vector is the scores. You can adjust the identities of the players by altering the vector Q defined in tournament; any number of players and any choice of strategies should work (including, of course, repeated instances of any given strategy).

play handles any given play of the game, that is, one round between two strategies, with their respective histories available. I’ve implemented always cooperate, always defect, tit-for-tat, grim, and the southampton master/slaves. Any unrecognised strategy code is treated as a random 50/50 choice, and the addition of further strategies should be fairly smooth- add another if condition that tests for your chosen number, then add that number into the player vector Q to see it in action.

I don’t know the precise details of the Southampton programs, but mine work along the same lines. A sequence of 8 moves codes for each; during the first 8 rounds, each program continues to play its signal moves unless the opponent has signalled incorrectly. From round 9 onwards, the programs will have identified their opponent as southampton slave, master or non-southampton. In the case of the latter, both strategies switch to permanent defection to reduce the opponent score. In a master-slave pairing, the master defects and the slave cooperates to maximise return to the master at the cost of the slave. Master-master or slave-slave pairings play out as mutual cooperation to bolster their scores.

The payoff matrix I use is consistent with my report, but not exactly standard. This of course can also be changed.

Source:
[iteratedpd.m][play.m][rounds.m][tournament.m]

Some recent developments in meta-gaming the Iterated Prisoner’s Dilemma cropped up on Wired (via Slashdot) recently; a team from Southampton Uni beating Tit for Tat in a competition celebrating the twentieth anniversary of that program’s emergence.

In the Journalism, not Journal writing vein, I added a discussion of this to E2, since the Wired article seems a bit confused and sifting through slashdot comments can often be painful. It ended up in my top five writeups, so I guess it was well received despite the depth of information already on the topic that the site had. My contribution is here, the parent node being here.

Matt (Ascorbic) then got in touch to point in the direction of an IPD site he put together. It allows you to try strategies of your own against an assortment of agents, or simply watch them compete amongst themselves; try it here.