Saturday, August 25, 2012

How to Win Games Part 4: Counter Prudential Strategies

Last week, we talked about how to counter someone who plays spitefully by using your prudential strategy. However, what if you know someone is playing prudentially?

This week, we will conclude the four game theory posts by learning how to determine your counter prudential strategy, which does exactly what it says: counters the prudential strategy.

First, you will have to figure out their prudential strategy though. Let's go back to the police-criminal game from last week.

Crime Lay Low
Patrol
3, -5
0, 1
Donuts
-2, 3
2, 0

We had determined that the police's prudential strategy is 4/7 patrol and 3/7 donuts. So, what do the criminals do?

Well, this isn't their mixed-strategy equilibrium. Remember that the mixed-strategy equilibrium is a way to make the other player's payoffs equal so that they don't have an advantage by playing one way or another.

Since this is the prudential strategy, and therefore not the mixed-strategy equilibrium, the criminals do have an advantage by playing one way or another. So, let's determine the expected payoff of playing either strategy.

For committing crime, they will get -5 4/7 of the time and 3 3/7 of the time. So, we do:

-5(4/7) +3(3/7) = -11/7

For laying low, we do the same thing:

1(4/7) + 0(3/7) = 4/7

Since 4/7 is greater than -11/7, the criminals should lay low every single time for their counter prudential strategy.

Though this type of thing isn't a proof or pattern like I normally post about, I find it really cool that you can analyze games just like you analyze math. If you have a lot more time, you can analyze games like chess, poker, black jack, and even sports.

Answer: Here is the answer to July's problem of the week. Make sure you do last week's as well!

Easy:
e = 24
h = 30
m = 12
n = 18
A = 81

Hard:
t = 45
z = 4.5
s = 50
a = 1
b = -1250
c = 390625
x = 625
P = 50π

For the rope problem from the hard problem of Monday, you must first set both ends of one rope on fire and set only one end of the other rope. Half an hour later, your first rope has burned completely leaving your second rope with 30 minutes left. Now, set the other end, and put your plant over the flame for its fifteen minute cooking.

Friday, August 24, 2012

Problem of the Week Day 5: Week of 8/20/12 - 8/24/12

Today is the final day of the problem of the week. The answers will be going up in late September.

Easy: Take a trapezoid with an area of n and bases of lengths t and m^3. What is the height h of this trapezoid?

h =

Hard: Take a circle with radius a centimeters and a trapezoid with bases s and k centimeters and a height of (2n-8y-4)/5 millimeters. Find the perimeter of the shape with the bigger area in centimeters. Round to the nearest tenth of a centimeter.

p =

Thursday, August 23, 2012

Problem of the Week Day 4: Week of 8/20/12 - 8/24/12

Today is day four of the problem of the week. Good luck!

Easy: Solve for the next number n in this sequence:

x, sm^2, t, sgm, b, y, n

n =

Hard: Find the value of n in this sequence:

y, s-1, z, l, n, k-a-5,...

n =

Wednesday, August 22, 2012

Problem of the Week Day 3: Week of 8/20/12 - 8/24/12

Today is day three of the problem of the week. Unlike normal Wednesdays, I have decided to give a few probability questions. The easy one you should be able to figure out with some simple math, and the hard one is explained in a previous post on the math behind a card trick.

Easy: You and your friend decide to play a game where you take a b card deck and deal down a card. On each turn, you both bet a dollar out of the two twenties that you brought with you. If the card dealt is a face card, you win the money and if it is a number card, your friend wins the money. Whoever runs out of money first loses.

Before the game, you rigged the deck so that y% of the cards are face cards and x% of the cards are number cards, making it much easier for you to win. Based on this cheat, determine how many turns it will take before your friend runs out of money.

t =

If you can't figure out a way to solve this problem, you probably have the values of x and y wrong. If you do, go back and make sure you have checked for dominant strategies, and then a mixed strategy equilibrium.

Hard: First off, solve the following problem:

2g - s = k
k =

Your friend bets you f dollars that you can't win a game he made up, which you accept. The game is that he takes a k card deck with numbers from 1 to s written on them. You will randomly guess a number from 1 to s, and then see if the next card has that number on it. If you fall into a conscious pattern, your friend automatically gets the money. Your goal is to get through the whole deck and never guess a card correctly. Determine the odds that your friend will get your money and you will therefore lose. Round to the nearest full percent.

l = ___%

This problem seems pretty daunting, but we did go over it in a blog post (not a problem of the week). If you can find this post and your calculator, the problem won't be too difficult. Good luck.

Tuesday, August 21, 2012

Problem of the Week Day 2: Week of 8/20/12 - 8/24/12

Today is day 2 of the problem of the week. Remember to use yesterday's answers in today's problem.

Easy: For this problem, you will need to bring up yesterday's problem as well. Look at the matrix from yesterday and find the highest number there. Let's call that number g.

g =

Now, find the second highest number in the matrix. Let's call that number s.

s =

Finally, find the average of all of the numbers in the matrix. Round that to the nearest hundredth. That number will be called m.

m =

Now that we have those, we can begin the problem. Take a right triangle with the following side lengths. All of the measurements are in millimeters.

a = sgm + x
b = ___
c = y

Try to determine the length of b.

b =

Hard: This problem is trigonometric, but is also a real world problem. For my science fair experiment in 2011, I had to solve almost the same exact problem and it was actually really cool to see the real world application of trigonometry. I hope you find the applications of trigonometry as cool as I did while you complete this word problem. Before you begin, complete these two calculations:

f = x + (a + b)/(y + z)
f =

g = x + a + b
g =

Now for the fun part. Say you need to create a wooden ramp that is f meters long and is propped at an a° angle. You will prop it up with another piece of wood g centimeters up from the bottom and you want the support to make it an a° angle ramp. How many centimeters long should your support be to achieve this angle? Round to the nearest centimeter.

s =

Monday, August 20, 2012

Problem of the Week Day 1: Week of 8/20/12 - 8/24/12

Today marks the start of 2012's final problem of the week. Back in July, I gave hints for each problem. This month, it's all you now. I will just give the problem and you will find the answer. Remember to save your answer so you can plug it into the next day's problem.

Rather than kicking it off with triangles or puzzles, I decided to start with some game theory. We have gone over everything you will need to know in the past three weeks, so you will be all set. If you didn't read the posts of the past three weeks, it shouldn't take too long, and it is very useful, practical stuff.

Easy: Take the following game matrix:

a b
x
0, 6
2, 4
y
5, -6
3, 2

Determine player one's best strategy for this game. First, look for a dominant strategy. Otherwise, find the mixed strategy equilibrium. Round to the nearest tenth of a percent.

x = ____%
y = ____%

Hard: Take the following game matrix:

a b
x
5, 3
-1, 10
y
7, -4
0, 0
z
2, -1
3, -2

Determine both player's best strategies for this game. First, look for dominated strategies. Then, look for a mixed strategy equilibrium. Round to the nearest tenth of a percent.

a = ____%
b = ____%
x = ____%
y = ____%
z = ____%

You will need all five answers tomorrow, so make sure to save them all.

Saturday, August 18, 2012

How to Win Games Part 3: Playing it Safe

For the last couple of weeks, I have been showing how to incorporate some game theory into daily life, and choose what the best strategy is, which isn't always what it seems like. As you saw last week, the police can get away with patrolling very little because the criminals are risking such a loss by committing crime.
By playing the way we learned last week, we are playing less to make ourselves win and more to make the other player lose. We make their payoff at the bare minimum of what we can get away with so we have a better chance of winning. This is called playing spitefully.
What if you think the other player is playing spitefully? What do you do?
You could play spitefully as well. If you use the same logic, you can actually determine who will win the game. You determine both expected payoffs, and in some cases, you will be guaranteeing yourself a loss by playing spitefully.
Rather than playing spitefully back, you can use your prudential strategy, which is basically your best counter for spiteful play. And you solve for it almost the same way as solving for mixed strategy equilibria: what we learned last week.
Let's go back to the police and criminal game from last week.

Crime Lay Low
Patrol
3, -5
0, 1
Donuts
-2, 3
2, 0

Let's say you are the police, and you know that the criminal is playing spitefully. This means he is committing crime 2/7 of the time and laying low 5/7 of the time.

For the police's counter, you solve it by first realizing that the criminals are only using your payoffs to create their strategy. So, you can take that into consideration by pretending their payoffs are not what they are and instead the negative of your payoff (they want your payoff to be low, so they want the negative of yours to be high). The game then looks like this:

Crime
Lay Low
Patrol
3, -3
0, 0
Donuts
-2, 2
2, -2

This is called a zero sum game because if you add the two payoffs in each box, it equals zero.

Now, we solve for our mixed strategy equilibrium in this new game.

Police:

-3x + 2(1 - x) = 2 - 5x
0x - 2(1 - x) = 2x - 2

2x - 2 = 2 - 5x
7x = 4
x = 4/7

So, the police should patrol 4/7 of the time and eat donuts 3/7 of the time, which seems to make a little more sense. They are doing their job more often, and they will catch a lot more criminals.

But how does the criminal counter that? Shouldn't they shy away from committing crime then? Next week, we will conclude my game theory posts for now, and we will learn how to counter the prudential strategy.

Saturday, August 11, 2012

How to Win Games Part 2: Strategizing for Any Game

Today is part two of my game theory posts. Last week, we looked a game that had a saddle point, where there is a dominant strategy for each player. That made it fairly easy to solve, as each player should play a certain strategy every single time regardless of the other player's move.

Yet, not every game is so simple. Sometimes, there isn't a saddle point, and playing a single strategy will just make yourself predictable to the opponent. You need to mix it up, but not 50-50. That's predictable too. You need to determine how you should mix it up mathematically that will give you the best possible outcome.

For instance, let's look at the following game between the cops and the criminals. It is nighttime: the time the criminals commit crime. The police are trying to decide if they should go on patrol and try to catch criminals or socialize at the donut shop. The criminals are trying to decide if they should commit crime or lay low. The matrix would look something like this (assuming that the police are player one and the criminals are player two):

Crime Lay Low
Patrol
3, -5
0, 1
Donuts
-2, 3
2, 0

First, we said we would look for dominant strategies (formally called the pure strategy equilibrium), but there don't seem to be any. This sticks us with this 2x2 matrix that we have to solve for.

We will solve it with a mixed strategy equilibrium, where we figure out what probability we should play each strategy.

To do this, we first set our variables. Let's say that x of the time, we play patrol, meaning that 1-x of the time, we play donuts. Now, we must solve for the criminals' expected payoff for each of their strategies.

If the criminal commits crime:
-5(x) + 3(1 - x) = 3 - 8x

If the criminal lays low:
1(x) + 0(1 - x) = x

We want their expected payoffs to be equal (if they aren't equal, the criminals will just go for the higher of the two outcomes and receive more than they could have otherwise), so we will set the 3 - 8x equal to the x.

3 - 8x = x
3 = 9x
1/3 = x

Therefore, the police should patrol one third of the time, which may be surprising to you considering that donuts is risking a -2 while patrolling is only risking a zero.

The criminals can solve for their optimal strategy using the same logic:

Patrol:
3x - 0(1 - x) = 3x

Donuts:
-2x + 2(1 - x) = 2 - 4x

2 - 4x = 3x
2 = 7x
2/7 = x

The criminals should commit crime two sevenths of the time, which isn't as shocking, considering the risk of the -5.

This strategy works well, as you are making your opponent's outcome as low as possible. The problem is when you know your opponent is playing like this, you have no control over your own outcome. Regardless of how you play, you are going to get the same outcome. Your goal then becomes making your opponent's as low as possible so you can actually pull a win.

In game theory, this is called playing spitefully, where you are purposely trying to make your opponent's payoff low in order to win more easily. Next week, we will learn how to deal with spiteful players, and how to deal with players who think you are spiteful as well.

Answer: A little less than a month ago, I gave you the monk problem, which is another great puzzle. Here is the solution:

First off, remember how the head monk phrased it. There are "sinners" among us. This suggests that there are more than one. So, if you only saw one sinner, you would leave since you would be the second sinner.

The next day goes by, and there are still sinners. Now, if you saw two sinners, you would leave. This is because you know the other two would have seen each other and left unless they saw another sinner. You realize that you must have been that other sinner, and you leave.

The third day goes by and there are still sinners. Now, if you saw three sinners, you would leave. Same logic as before, you know that the three you saw would have left if there were truly three sinners. You then realize that you must be the fourth, and you leave.

Since there were no sinners on the fourth day, that means that there were four sinners, and they left on the third day because of the logic in the paragraph above.

Saturday, August 4, 2012

How to Win Games: Basic Strategy

As you may know, I just recently was at the Johns Hopkins Center for Talented Youth camp taking Game Theory and Economics. I did a few posts that discussed some stuff we were learning in class, but I never actually talked about how to win a game.

In mathematical terms, games are formatted with a table (known as a matrix), where player one is choosing a row and player two is choosing a column. The rows and columns are their strategies, or choices. Each box in the actual table is the payoff, which is how much they gain from the decision (points, profit, etc). The comma separates player one's payoff from player two's payoff.

Let's look at a quick example. Say Home Depot and Lowe's are selling wood, and they have to choose their price. Home Depot has a choice of:

\$5
\$7

Lowe's has a choice of:

\$4
\$6
\$8

There are 5000 lumber customers in the area, and if they both had the same price, they would be split equally between the two companies. However, every dollar less one company is than the other, they will steal 500 of the other company's customers. The matrix looks like this with the payoffs as how many thousand dollars the company makes:

\$4\$6\$8
\$5    10,12    15,12    20,8
\$7   7,16  14,18 21,16

This game is pretty easy to figure out which strategy each player should choose. First off, look at Lowe's choices.

If they choose \$8, they are always getting less profit than if they choose \$6 or \$4, regardless of which price Home Depot chooses. You can phrase this by saying \$6 dominates \$8, or \$4 dominates \$8. \$8 is then considered a dominated strategy.

Is \$4 or \$6 a dominated strategy? Well, all of \$6's numbers are greater than or equal to all of \$4's numbers, so \$4 is a dominated strategy as well. This leaves \$6, which is the dominant strategy.

Since Home Depot knows that Lowe's will choose \$6, they must determine their best price. They would prefer 15k to 14k, so they should choose \$5 as the price for their wood.

This point that they led to is called the saddle point. In games with a saddle point, it is very easy to choose your strategy because you just go with the strategy corresponding with the saddle point.

It is pretty simple to determine these saddle points and dominated strategies, and will give you a start in game theory. Next week, we will learn some strategy for games without saddle points.

Answer: A month ago, I gave the problem with the king and the dragon, where the dragon manages to pull through and take over the kingdom even though the king has enormous chances of killing him. Here is what the dragon did.

To stay alive, he drank water from well 1 first, which poisoned him. Then, he received the well 10 water from the king, which cured well one's poison rather than poisoning him.

To kill the king, he knew that the king would drink from well 10 after drinking the dragon's offering. Well 10 would cure any poison, but it still is a poison itself. So, the dragon served the king fresh, unpoisoned water. The king then went and poisoned himself with well 10's water, and died leaving the dragon to rule the kingdom.