Game theory:

I have not contributed much to game theory, but would like to do more, especially in the area of block games (see below). To date I have published three papers with relevance to game theory:

53. Cowan, R. The Allocation of Offensive and Defensive Resources in a Territorial Game. J. Appl. Prob. 29, 190-195 (1992)

60. Yu, P.L.H. and Cowan R. Statistical models of duplicate tournaments in games of luck and skill. Australian J. Statistics, 37, 1-17 (1995)

64. Cowan, R. , Yu, P .L. H. and Ferguson T. S. Restrictions on the saddle-point solution in the game of Teamball. J. Appl. Prob. 33, 443-447 (1996)

Papers #53 and #64: The problems considered here were stimulated by the game of Soccer, but similar issues arise in many ball games of a territorial nature. In such games, teams need to strike a balance between offence and defence. This balance is achieved through the allocation of players to either forward positions, mid-field positions or back positions.

To gain insight into the relative merits of differing resource allocations, I posed a simple game called teamball using Soccer as a guide, except that, in this study, a temporal element was not included. I assumed that the game is played until one team gets the ball across the other's goal line rather than for a fixed duration of time. The field is divided into an odd number of sectors. The match is between two teams, A and B, who have the problem of allocating their resources over the sectors so that the mix of offensive and defensive efforts is optimal.

The ball starts in the mid-field but moves randomly between sectors. The chance movement of the ball, either in favour of A or B, depends on the relative strength of the teams in the current sector - various sensible movement rules are used. Eventually, the ball will cross the goal-line at one end of the field and one of the teams wins. We investigate the saddle-point solution for the game.

Paper #60: Many games played between 2 contestants start with a random deal. This introduces luck from the deal. A concept of duplication, commonly employed in bridge tournaments, can be used to nullify this luck in a tournament. This paper poses a model for the contest between any two players and analyses this model for a tournament which employs this duplication principle. Interesting links with experimental design are evident. Two example tournaments on a new game are analysed.

Block games

If am dabbling in this area at the moment, trying to adapt the algorithmic work of Koller, Megiddo and von Stegel (Proc. 26th ACM Symposium on the Theory of Computing, 1994 and later publications) to these structures. Four examples,

• Odds and Evens
• Pai Kau, a Chinese casino game
• Truscott's paradox
• 3x3 mod(3)

explain the problems -- which are largely computational, once a simple conceptual structure is set in place.

Odds & Evens: Consider a game that I shall call "Odds & Evens" played with a deck of n cards, numbered 1, 2, ..., n. The two players, A and B, are each dealt k cards face down (2k<n), so neither knows the other's hand. Simultaneously, each player selects a card from his hand. These are turned face up and if the sum is odd, A wins the game; if the sum is even, B wins.

Consider n=8 and k=3. Each player can have one of four holdings: EEE, EEO, EOO or OOO. We list these along the boundary of the matrix of "payoff blocks", payoffs to A (whose holdings and possible choices of play are listed down the left side of the table).

The problem? How should each player randomise his choice of Even and Odd card, in the cases where he has a choice? If each plays optimally, what is A's chance of winning? (Hint: you can write this game in 4 x 4 "normal" form and apply the standard solution methods, but there are other ways which will, in larger games, be less explosive.)

Optimal strategies: Each player should, when having a choice, play the less prevalent of E and O in his hand with probability 2/3 and the more prevalent with probability 1/3. The game is not fair; A's chance of winning is 18/35. Download for more information.

The Chinese game of Pai Kau: In 1990 I was asked by the HK Government to investigate the game of Pai Kau played in the casinos of Macau (and elsewhere around the world). The investigation was in connection with a corruption case. A police officer, who had four large increments in his bank balance, was charged with "being a crown servant and being in control of pecuniary resources or property disproportionate to present or past official emoluments". He offered his gambling winnings playing Pai Kau as an explanation for his sudden wealth. I was asked how likely it was to win the sums involved from the amounts that the officer said he had taken to Macau on four occasions.

The game is too complicated to explain in detail (because of a few messy wild-card rules which affect the otherwise simple structure), so I shall explain a simpler (and hence slightly inaccurate) version. There is a deck of 32 tiles comprising 16 pairs numbered 1, 2, ..., 16. The tiles are randomly dealt to (up to) 8 players, a banker and (up to) 7 gamblers. Each player gets 4 tiles.

Each player must then (in secret) sort his hand into two groups of two -- a front duo and a back duo. The rules of the game specify a rank order for a group of two tiles. The best is the natural pair (16,16), then (15,15), ..., (1,1). After the natural pairs, two tiles (x,y) are ranked according to the size of (x+y) mod(10); the higher the sum mod(10) the higher the rank. If two duos have the same sum mod(10), the duo with the highest numbered tile is deemed better (so (16,2)>(5,3) because 16>5). If the tie is still unbroken, second-highest tiles in each duo are compared (so (13,11)>(13,1) since 11>1). There remains the possibility of a genuine tie if duos are exactly the same.

In sorting one's hand, one is constrained to make one's front duo of higher rank than one's back duo. So if a player is dealt (16,11,10,3) he has three choices of sorting:

Although there are many players, the game is effectively played as separate comparisons, banker's sorted duos versus each gambler's sorted duos. In each of these comparisons, the front duo of banker's hand is compared with the front duo of the gambler's; likewise the back duos are compared. If either player wins both the front and back comparisons, he wins the bet. If the success is shared, the game is a draw and the bet is annulled. If there is an exact tie in the comparison of duos, then the banker is deemed the winner of that comparison.

You may marvel at the very low bias in favour of the banker, but before thinking that the Macau casinos are very generous you should know that the casino is not the banker. The banker is one of the players bold enough to take on the role when his turn (by rotation about every 100 deals) comes up. The casino deals the tiles and supervises all the money flows AND takes a commission of 4% on each winning bet. They also underwrite the banker to a limited extent and cream off considerable profits when the banker wins a lot (see The role of the house in Pai Kau betting).

Anyway, the game between banker and gambler can be viewed in isolation and (guess what) it is a "block game" with a huge matrix of payoff blocks (see easier example in Odds & Evens). A glib figure is that each person can be dealt 3620 different hands so we are looking at a 3620 x 3620 matrix of payoff blocks which themselves can be 3 x 3 if three different sortings are available (as in the example above).

To see what happens now in a simpler setting, let us reduce the game from 32 tiles to 10 (comprising 5 pairs numbered 1, 2, ...,5). There are now 45 different hands that a person can be dealt, so there is a 45 x 45 matrix of payoff blocks. A classification of hands, showing that 3 choices are not always available, is:

These numbers can be reduced through some concepts of "inferiority" and "dominance". A sort S is inferior to a sort T if and only if it has a lower ranked duo on both the front and back position. Such a sort is clearly irrational. After the application of the inferiority concept:

"Dominance" is somewhat more elaborate than "inferiority" and more involved than in the text-book cases for games in normal form. For player A, a sort S is dominated by a sort T if and only if the expected payoff to A using sort T, under the worst possible sorts by player B, is greater than the expected payout to A using sort S, under the best possible sorts by B. "Worst" and "best" are from A's perspective for that sort alone and are not a reflection of the quality of B's strategic play overall.

The application of the dominance principle (to banker then non-banker iteratively until no further reduction is possible) reduces the yellow part of the table above to:

The actual choices differ between banker and non-banker. Thus, the matrix of payoff blocks, whilst still 45 x 45, has most blocks smaller than 3 x 3, many being 1 x 1. Game theoretical solution is still a non-trivial task. For the real game, the computations are huge since, even after the application of "inferiority" and "dominance", the sorting choices are:

Truscott's paradox: In the September 1988 edition of Bridge World, noted bridge writer Alan Truscott put forward a simple 3-trick end-game in bridge. Each player has 3 cards, all being diamonds. North, who is dummy, holds A53 in that suit, having discarded the 2 earlier. East has QJ4 and is on lead. Which card should he lead? Truscott suggests that a beginner might play the Q, a better player the 4 and an expert a random choice between the Q and J. Finally he has no conclusion, leaving it as a paradox. Anyone familiar with game theory would take a randomised view, assuming that East plays the Q, J or 4 with probabilities p, q and 1 - p - q.

The problem is not well posed. In order to start thinking about it mathematically, let us suppose there is no information gleaned from the bidding and early play which allows any of the 3 active players to deviate from an assumption that "the 6 cards I do not see are distributed totally randomly amongst the other two players". This would often be an unrealistic assumption in a real bridge game, since the actions of the players to that stage can make some holdings more or less likely.

Put ourselves in East's shoes first, as Truscott does. East reasons that if West holds either the K or the 10, it does not matter what East leads. So East restricts his thinking to the cases where South holds K10x (x = 9, 8, 7 or 6). We must now put ourselves in South's shoes in each of these 4 cases.

Holding K109, South wins 3 tricks if East leads the 4 from QJ4 (because he will clearly play the 10 or 9 on the 4 lead, even though he doesn't know East's other cards) but has two choices of play if East leads the Q or J:

• win with the K and finesse West for the other honour;
• win with the A and finesse East for the other honour.

Holding K108, only the second of these ploys is rational for South on an honour lead, but he has choices should East lead a low card < 8 (such as the 4).

• play the 10 hoping to make 3 tricks (if East led low from QJx, x<8);
• play the 8 hoping to make 3 tricks (if East led low from Q9x, x<8).

Holding K10x, x=7 or 6, South's only play with a low lead is the 10, hoping that East led from QJx (instead of the other holdings Qxx, Jxx or xxx).

We see that when East starts to consider South's strategic reasoning, he is forced to think how an East with Q9x, or one of the Qxx, Jxx or xxx holdings, would play, even though he knows that he does not have such a holding. An East with Q9x (say) would start to consider all the South holdings which are relevant to Q9x-strategies, and these contain holdings other than K10x -- a wider set than on East's initial line of thinking! Likewise for an East with Qxx, Jxx or xxx!

The situation snowballs and we soon find ourselves considering a complete matrix of possibilities -- all 84 possible East holdings each with 3 options of card to play and all 84 possible South holdings each with 3 cards -- in a "block" matrix similar to that in the Odds & Evens problem.

So now we get an 84 x 84 matrix of "3 x 3 payoff blocks" which, if written in "normal form" would result in a 3⁸⁴ x 18⁸⁴ matrix.

Why 18, you may ask, as if 3⁸⁴ is not big enough? Because South plays after seeing East's card! So for each of the possible leads from East (6 are feasible from South's viewpoint due to his knowledge of dummy and his own hand), South has a potentially different randomisation over his 3 choices of play at trick 11. (His later options seem to be an issue also, but his play on trick 12 is automatic given decisions and outcomes for trick 11.)

Even allowing some grouping of cases and the fact that many cases will be trivially simple, the mind boggles at the combination of detail and tedium involved! And the explosive size of the numbers involved!

And this is a trivial problem, compared to most bridge problems! To my knowledge, nobody has found p and q for the Truscott problem. This is understandable given that in order to get p and q one must actually find 588 pairs of (p,q) values -- 84 pairs to describe East's strategic behaviour and 84 x 6 pairs for South's (albeit with some obvious cases reducing the number of unknowns a little).

The 3x3 mod(3) game: A deck contains 3 suits each of 3 cards numbered 1, 2 and 3. Players A and B are each dealt 3 cards. Each player selects a card from his hand without knowledge of the opponent's choice (or hand). The payoff to A is (a+b)mod(3) - 1, where a and b are the chosen numbers. As an exercise, write down the 10 x 10 arrays of blocks and block-probabilities. To illustrate the nature of what "game theorists" call a "solution", I list it here.

B should:

• always choose a 1 from 112, card 2 from 233 and card 3 from holdings 223 or 133;
• randomise with a holding 113, playing 1 or 3 with probabilities 8/27 and 19/27;
• also randomise holding 122, playing 1 or 2 with probabilities 14/27 and 13/27;
• randomise with 123, playing 1, 2 or 3 with probabilities 7/54, 25/54 and 22/54.

Likewise, A's optimal policy is:

• always choose card 1 from 122, card 2 from 112 and card 3 from holdings 113 or 233;
• randomise with a holding 133, playing 1 or 3 with probabilities 19/27 and 8/27;
• also randomise holding 223, playing 2 or 3 with probabilities 13/27 and 14/27
• randomise with 123, playing 1, 2 or 3 with probabilities 22/54, 25/54 and 7/54.

The expected payoff to A under these optimal strategies of both players is zero.