There are lots of ways to look at the North Korean situation through the lens of game theory and this post looks at what various commentators have been saying.

Evan Osnos has written in the New Yorker that Kim is a dangerous wildcard but that China will continue to support him because having him in charge is preferable to the Americans or South Koreans taking charge in North Korea.

Gregory Boyce thinks that this is a game of chicken where Kim is trying to responding to internal pressures from his military leaders.

Tyler Cowen looks at the situation from the American standpoint saying that they have to take the position they do in support of the South Koreans to give confidence to their other allies such as Israel. The Americans don’t really support South Korea that much but they use their support to send a message to others.

Don Rich also brings Israel into the analysis. He also raises the tricky problem of how Kim can keep the domestic support he gains from his aggressive stance if he then backs down. It is all made more difficult by cultural differences and the risk that Kim Jong-Un may not be acting rationally at all.

This brings me to the final article by Tim Worstall who says that in his experience of dealing with the North Koreans, including handing over £10,000 in cash to get a rail freight deal concluded, shows that they might just be crazier than anyone gives them credit for!

Having read these it is my view that China are the key to the situation. They support North Korea because they would not want to see the Americans occupy the land. It is this Chinese support that gives Kim the confidence to sabre-rattle so loudly without worrying about a US invasion, but equally they won’t want him to actually start a war which they would either have to get involved in or let him lose.

How do you think the game will play out?

Image courtesy of Stuart Miles / FreeDigitalPhotos.net

The post Game theory and North Korea appeared first on Game Theory Strategies.

A (very generous!) casino offers you a game where the pot starts at $1 and on each turn a (fair) coin is tossed. If it comes up heads then the pot is doubled, if it comes up tails then you win whatever is in the pot.

How much would you pay to play this game?

Half the time a tail comes up on the first coin toss and you win $1. Half the time you get a head, the pot doubles to $2, and you get to toss the coin again.

On the second toss, half the time you get a tail and win the $2 and half the time you get a head again and the pot doubles to $4 and you get to toss again.

Overall you get the following pattern. Half the time you win $1, a quarter of the time you win $2, one eighth of the time you win $4, etc. The amount you win gets bigger and bigger, but the chance of winning that amount gets smaller and smaller.

This means that you should expect to win:

(1/2 x $1) + (1/4 x $2) + (1/8 x $4) + (1/16 x $8) …

There are an infinite number of terms in this equation.

which is

50c + 50c + 50c …

which is the same as an infinite number of 50 cents, which is infinity.

So using an expected value argument you would pay an infinite amount to play the game because you will win an infinite amount.

However you almost certainly wouldn’t pay a massive amount to play the game. There have been a number of arguments put forward to explain this:

Daniel Bernoulli in 1738 was the first to attempt to resolve the paradox. He suggested that because each extra bit of money means less to you then you won’t value the later money you could win as much. Basically, if you have nothing then $1,000 is a lot of money, if you have $100 million then an extra $1,000 is irrelevant.

Another argument is that people don’t imagine that such a long string of heads is possible. Most people instinctively imagine that after a long run of heads a tail is more likely, even though it isn’t. That’s why casinos show all the recent numbers that have come up on a roulette table, because people are looking for patterns to base their next bet on.

One more argument is that the casino only has a limited amount of money and cannot payout an infinite amount. If the casino is willing to risk $1,000,000 on the bet then the expected payout drops dramatically. It takes a run of 20 heads to take the payout to over $1,000,000, this means that the expected payout drops to a bit over $10. The high expected value normally comes from having some incredibly rare but extraordinarily high payouts, without these the value drops substantially.

Which explanation do you prefer for the paradox, or do you have your own?

Image courtesy of marin / FreeDigitalPhotos.net

The post St Petersburg paradox explanation appeared first on Game Theory Strategies.

Royal Crescent Bath

I am lucky to live in the beautiful city of Bath in the south-west of England. Bath is renowned for its Roman Baths and Georgian architecture but its council has fallen into a prisoners dilemma.

The city has three main recycling centres to encourage people to recycle as much waste as possible. At the moment anyone can use the centres whether they live in Bath or not. Equally anyone in Bath can also use a centre in another city if they want to. I sometimes use a centre in another area because it is on my way to work.

I don’t know how much they spend on the recycling service but let’s assume it is £100,000 (it’s always good to use a nice round number!).

If 10% of people come from other areas and they are banned from using the sites then the cost will fall to £90,000, but the council will now have to pay the cost of monitoring who is using the sites. Let’s say monitoring cost is £5,000, then the cost for the council becomes £95,000. The council has saved £5,000 by stopping people from other areas from using the service. The neighbouring council now has more people to deal with because no-one from their area can go to Bath anymore. Their cost goes up to £110,000.

This is fine for Bath until the neighbouring councils do the same thing. When that happens then the 10% of people who were going from Bath to another area (like me) can only use the Bath centres. This now adds £10,000 back onto the Bath cost bringing it up to £105,000. This is the original cost of the service plus the cost of monitoring who is using it.

Showing the game in a grid looks like this:

We can see that this is a classic prisoners dilemma.

If the other council is accepting others then Bath is better off if it restricts its service to residents only (a cost of £95,000 rather than £100,000).

The alternative is that the other council limits its service and then Bath’s best response is also to limit its service (a cost of £105,000 rather than £110,000).

Either way the best response is to limit the service even though this leads to a worse result for both than if they both kept an open service.

That’s explains why they have decided to restrict the service to residents, but why has this only just started to happen when the service has been running for years?

The answer is because the councils have changed the game they are playing. Before the ‘Great Recession’ the councils based their service around maximising the amount of waste that is recycled. When this is their priority then they have no reason to restrict who uses the service, all that matters is that the waste is recycled.

Now the council’s are playing the game using money as the measure of success. This has changed the game into a prisoners dilemma and the councils are now trapped.

This is a real life example where changing what is important in the game has changed the outcome.

What you measure matters because it changes the game

The post Trapped by a prisoners dilemma appeared first on Game Theory Strategies.

What strategy do you follow to be able to survive when this happens?

You look around and, although it is risky, you know that you need to be one of the ants to go out and look for a new nest site.

You leave your damaged nest and bravely step out into the sunshine, you are looking for another crevice between rocks that will be an ideal site for a new nest. Other brave ants are also leaving the nest to search out a new site.

You find a new site and look around. Would this make a good nest? You check out whether it is the right size, how many openings it has, whether there are already any dead ants here and then run back to the nest.

When you get back you wait for some other ants to join you before you head back to the nest you have found to show them the potential site. The key to the strategy is that you wait longer if you have found a poor site and less time if you have found a good site.

The ants that follow you to the potential site also make a judgement of how good it is and return to the nest. They then wait for some other ants to join them, again waiting longer for a poor site and less time for a good one.

Once you have shown your site to others then you look around the damaged nest and find another ant who takes you to a different potential site. You then judge this site and head back to the nest once again.

Very quickly a lot of ants are making judgements about different sites. You meet up with another ant and go to look at another site. The ant that you are with now had only just arrived back in the old nest before he headed out again, you must be going to a good site.

When you arrive you find that the new site is packed with ants. You sense that there are enough ants here for this to be the place to make the new nest. Everyone else senses the same thing and you all go back to fetch the main brood of ants who are protecting your queen.

By working together the ants are able to quickly check out a lot of new sites and identify the best one for a new nest.

The strategy works because the ants wait less time to go back to a good site which means that ants are arriving there more often then they are arriving at a poor site. An ant coming from a good site will go back there almost immediately taking other ants with him. One coming from a poor site might wait a minute before going back, in that time a lot more ants will have returned to the good site. After a while a lot more ants end up at the good site, which is then selected.

Amazingly this co-operative behaviour is really how some ants work when then need to find a new nest site.

I wonder if it has any applications to crowd-sourcing solutions to problems?

Image courtesy of sweetcrisis / FreeDigitalPhotos.net

The post Amazing story of co-operation amongst ants appeared first on Game Theory Strategies.

She is learning her letters and also learning to write. I guess they have to learn to write but as an adult I hardly write anything any more, everything I do is typed on a keyboard of one sort or another.

This got me thinking about how early a child should learn to type and then whether even that will be worth doing if the method of inputting changes in the next 10-15 years. Maybe we’ll move on to something beyond keyboards, or maybe we’ll move away from QWERTY keyboards to something else.

How do we know that we are teaching our kids something that will really be useful for them in the future?

It is possible that we won’t be using keyboards in the future, but if we are they will almost certainly be QWERTY ones – because of game theory.

Although the QWERTY keyboard is by far the best known layout of the keys there are other options available. One of the best known alternatives is the Dvorak keyboard which puts the most commonly used keys on the middle line of keys which then minimizes the amount of finger movement that is required to type. It is arguably a better layout than the standard QWERTY keyboard.

But choosing a keyboard layout is really a big co-ordination game. If I decide to change to the Dvorak keyboard because I think it is better then I can change my own computers but every other keyboard I come across in my day will still be a QWERTY one so I will need to be able to type on both which will be harder work.

If everyone changed to Dvorak then we would all be better off but whilst the vast majority stay with QWERTY it is better to stay with that, even if it is a slightly worse layout.

A new product has to be significantly better if it is to break into a market where it is better for everyone to be using the same product. Another example is with social networks. A challenger to Facebook has to be good enough to convince enough people to change even though at first not all their friends will be on the new network. Once the new product reaches a tipping point then take up will be quick but getting to the tipping point can be nearly impossible.

Image courtesy of imagerymajestic / FreeDigitalPhotos.net

The post Keyboards, kids and game theory appeared first on Game Theory Strategies.

The game is played by two players who each take turns to pick up matches from two separate piles. The rules allow a player to take any number of matches from one of the piles when it is their turn. The winner is the player that takes the last match. This post explains the winning strategy.

This version of Nim is quite easy to work out the correct strategy for but there are versions where things get more difficult.

What about a game where there is one pile of matches and the first player can take can any number of matches up to one less than the total. For moves after that each player can only take a number of matches that is less than, or equal to, the number that was taken by the other player in their previous turn.

So if player one takes two matches then player two can take one or two. If player two then takes one, then player one can only take one match in their next turn. Each turn from then on will be to take only a single match.

If there are an odd number of matches in the pile then the solution is easy. Player one takes one match which leaves an even number of matches. Player two is only allowed to take one match since they cannot take more than their opponent took on the previous turn. This leaves an odd number of matches again. This game continues until player one take the final match and wins.

So the more interesting case is when there is an even number of matches in the pile. No player wants to leave an odd number of matches in the pile otherwise the other player will just take one and then each player will only be able to take one match each turn until the player that left an odd number of matches in the pile loses. This means that we know that player one’s first move must be to take an even number of matches, and he must take fewer than half the matches. If he takes more than half then player two will simply take all the remaining matches to win.

Looking at some examples should start to show the pattern.

We know that player one wins if there are an odd number of matches. Looking at the even numbers:

Start with 2 – player one must take one, player two then takes the last one to win. Player two wins

Start with 4 – player one loses if he takes an odd number so he must take two, player two then takes the final two and wins. Player two wins

Start with 6 – player one must take two to have a chance as it is the only even number less than half of six. This leaves four and is the case above, player two can take one or two and either way they lose. Player one wins

Start with 8 – player one must take two again which gives the same as starting with six but with player two to play so: Player two wins.

Start with 10 – If player one takes four then six are left and, as above, player two wins. But if player one takes two then eight are left, following the logic above, Player one wins.

Start with 12 – Player one takes four and will win. Player one wins

Start with 14 –  Player one takes six and will win. Player one wins

Start with 16 – Player one cannot bring the number down to eight again otherwise player two will take all the eight remaining matches and win. Player one must take a number less than eight, we know that odd numbers will lose, and taking two, four or six leaves the cases above for 10,12 and 14 but we know that whoever goes first with a pile of 10, 12 or 14 will win, so Player two wins

We can now see the pattern and the strategy

Player two wins when the pile contains a number of matches that is a power of two (2, 4, 8, 16, etc) and player one wins otherwise. The winning strategy is to reduce the pile to a power of two that is more than half the remaining pile.

More complicated games can still be worked out by working up from the simplest cases.

The post Nim game solution appeared first on Game Theory Strategies.

The natural reaction is to say ‘no’, of course you don’t want the value of your shares to be reduced after the takeover.

In fact, the promise to make a big payout might be necessary to make the deal happen in
the first place.

The corporate raider is presumably buying the company because he thinks he can add value to the business. This could be through following a different strategy or through running the existing business more efficiently. Either way he will be hoping to increase the value, and therefore the share price of the company after the takeover.

You are a small shareholder so you have effectively no influence on whether the takeover will happen or not. You see that if the takeover does happens then the price will be higher and you should wait until then to sell. Unfortunately, if all the shareholders think like that then no-one sells and no-one benefits from the higher share price.

This is a free rider problem. Everyone waits for someone else to sell, so no-one ends up selling. The only price that any shareholder would accept is the post-takeover price, but if the raider pays that then he makes no profit.

One of the ways round this is for the raider to promise to take a large payment for himself after the takeover. This will lower the post-takeover price to a point which is still higher than the current price, and so attractive to the current shareholders, but he gets his profit as well.

This problem was originally studied by Grossman & Hart in 1980.

The post Game theory of takeovers appeared first on Game Theory Strategies.

This can lead to some very interesting and unexpected results.

Imagine that there are four people owning 100 shares in a company (each share with one vote). Owner A has 44 shares, B has 29 shares, C has 20 shares and D has 7 shares.

If a simple majority is required to win a vote then the Shapley Shubik index gives A 50% of the power and B, C and D are all equal with 16.7%. Even though D has far fewer shares they are still key to the others reaching 50% of the votes.

Now C has a bright idea and decides to bring in a partner (E) and splits their 20 shares with them so C now has 10 shares and E also has 10 shares.

Recalculating the power index shows that A increases to 60% with the other four all equal on 10%. So C with 20 shares had 16.7% of the power but C and E with 10 shares each control 20% of the power between them. By splitting their shareholding C has more power than before (as long as they can trust E)

This is not always the case. A might see what C has done and decide to split their 44 shares so they have 22 shares and a new owner, F, also has 22 shares. Unfortunately for A this gives them 26.7% of the vote and F also 26.7% of the votes. Combined they now have 53.3% of the power, less than the 60% that A controlled on their own.

Could someone use these ideas to really gain more power or are these are just mathematical tricks. What do you think?

The post Shapley Shubik power index part 2 appeared first on Game Theory Strategies.

The Shapley Shubik Power Index

With Lloyd Shapley having just won the Nobel prize  it seems like a good time to look at the Shapley-Shubik power index.

This is a way to measure how much power different voters have in a vote where they control a different number of votes. It is not necessarily the case that someone controlling 20% of the votes has twice as much power as someone controlling 10% of the votes. They may have more or they may have less depending on the overall situation.

How it works

The way that the Shapley Shubik power index works is by taking every possible combination of voters and working out how many times a particular voter is pivotal. With this index the order matters so if there are three voters A, B, and C then there are six possible combinations to consider (ABC, ACB, BAC, BCA, CAB, CBA).

To work out the pivotal voter we look at how many votes the first voter has. If this is enough to reach a majority (or whatever level is needed) then they are the pivotal voter. If they are not then we move on to the second voter in the combination. If they voted the same was as the first voter and this took the total number of votes passed a majority then the second voter would be the pivotal one. It is whichever voter is the one that tips the combination passes the number of votes needed to win.

For example, assume that there are 100 votes to be cast and voter A controls 15 of them, voter B controls 40, and voter C controls 45. In the ABC combination B is the pivotal voter. This is because A has 15 votes so they do not have enough votes to get to 50 on their own. Once we add in B’s 40 votes then we get up to 55 votes so A and B together control more than 50% of the votes. This means that with this order of voters, B is the pivotal voter that takes the total over 50%.

The pivotal voter for the other five combinations is as follows:

ACB – Pivotal voter is C

BAC - Pivotal voter is A

BCA - Pivotal voter is C

CAB - Pivotal voter is A

CBA - Pivotal voter is B

So across all six combinations, A, B and C are all pivotal twice, so they are considered to have the same amount of power, even though they have a different amount of votes. This is because they each need one other player to vote with them to gain a majority. It doesn’t matter whether it is a large majority, like when B and C combine or a small majority when A combines with either B or C.

Strategy – Divide and conquer

A player with an understanding of where power really lies in a vote can use a strategy of ‘divide and conquer’ to take a disproportionate amount of power from their rivals.

If we start with the game that is described above and then imagine that B is able to change the game by introducing a new player D who takes 11 of C’s votes. This leaves A still with 15 votes; B with 40; C is reduced to 34; and D with 11.

There are now 24 possible combinations shown below with the pivotal voter in each marked in bold.

ABCD; ABDC; ACBD; ACDB; ADBC; ADCB;

BACD; BADC; BCAD; BCDA; BDAC; BDCA

CABD; CADB; CBAD; CBDA; CDAB; CDBA;

DABC; DACB; DBAC; DBCA; DCAB; DCBA

A is pivotal 4 times out of the 24 combinations and so has 16.7% of the power. B is pivotal 12 times out of 24, or 50%. C and D are both pivotal four times, the same as A.

Remember in the first game each voter had an equal amount of power, so they had 33.3% each. By managing to introduce a new player to take some of C’s votes B has greatly increased their own power from 33% to 50%. With three players they all had an equal amount of power despite their different number of votes. Now B has reduced A and C’s power while increasing their own.

In the first game any two pairs of voters could form a coalition and win the vote. By giving some of C’s votes to a new player, D, it changed the game so that B could pair up with anyone else to get a majority but none of the other players could pair up to reach a majority. This put B in a much stronger position than the first game.

Divide and conquer in action!

Image courtesy of taoty / FreeDigitalPhotos.net

The post Divide and conquer appeared first on Game Theory Strategies.

Rather than me try to write about their work here are a few videos to enjoy.

Here you can see Al’s reaction to winning the prize and a brief explanation of his work.

This video explains the stable marriage problem a matching problem first studied by Lloyd Shapley and David Gale in 1962

This is Al Roth giving a Google Tech Talk on his work on market design (runs to just over an hour).

The post Roth and Shapley Nobel Prize winners appeared first on Game Theory Strategies.