Math 170 lecture notes for February 13, 2003

Mathematics and politics
Lecture notes, 2/13/03

Announcement:

Rally/march against war in Iraq
Saturday, Feb. 15
March starts at 12:00, Broad St. and Spring Garden St.
Penn students meeting 10:30 am at 34th and Walnut

Project on conflict escalation

Analogous to North Korea exercise
To be assigned on Tuesday, due in two weeks
In-class presentations
Groups of three?
Study a real-life conflict escalation scenario, e.g.:
- U.S.-Colombia (recently)
- Israel-Palestine (recently)
- Cuban missile crisis (1962)
- etc.
Determine each side's preferences and options.
Make a decision tree.
Determine the optimal strategy.
Does your optimal strategy fit with what actually happened?

Current assignments:

A short homework assignment due on Tuesday, Feb. 18.

Today: O'Neill's Theorem

Optimizing strategy for the dollar auction
Lemmas needed for O'Neill's Theorem

Optimal strategy for the dollar auction: working backwards

Exercise:
Suppose you are playing the dollar auction with someone who you know is playing rationally and using the conservative convention. The prize is $1.00 and the bankroll is $5.00, with bids in nickel increments.

Clearly if the other player has just bid $5.00, you have to pass and the game ends.

Suppose the other player has just bid $4.95. What should you do?

Suppose the other player has just bid $4.90. What should you do? (Hint: use your answer to the previous question.)

Suppose the other player has just bid $4.85. What should you do? (Hint: use your answer to both previous questions.)

Notice a pattern?

At what point will this pattern stop working?

How does the pattern change?

You will be handing this in, as usual. Do as much as you can; don't worry if you can't get all of them.

We know what decision trees look like in general.
- The branches on the right are the smallest
- So they are the easiest to prune
- Let's work backwards from the right: start at the highest bid and work down

Example: Auction for $1.00, bidding in nickel increments, maximum bid of $5.00.
Assume both players maximize their benefit and use the conservative convention.
Suppose you are player one.
(Step 0) If player two has just bid $5.00, then of course you pass and he wins.

(Step 1) What if player two has just bid $4.95? What should you do?
- If you bid $5.00, you will lose $4.00.
- If you pass, you will lose whatever your previous bid was.
- So if your previous bid was at least $4.05, you should definitely bid $5.00.
- If your previous bid was at most $3.95, you should definitely pass.
- If your previous bid was $4.00, then you get the same outcome either way. Using the conservative convention, you pass.
- So if your previous bid was $4.05 or more, you should bid $5.00; otherwise you should pass.

(Step 2) What if player two has just bid $4.90? What should you do?
- If you bid $5.00 you still lose $4.00.
- If you pass you lose your previous bid.
- If you bid $4.95 then what will your opponent do?
  - (Step 1) tells him to bid $5.00 if his previous bid was greater than $4.05 (it was, since he just bid $4.90).
  - So you lose $4.95 which is definitely worse than passing or bidding $5.00.
- Thus you should definitely not bid $4.95.
- Again, if your previous bid was $4.05 or more, you should bid $5.00; otherwise you should pass.

(Step 3) (Express version) If player two has just bid $4.85:
- If you bid $4.95, player two will use (Step 1) to conclude he should bid $5.00, and you lose.
- If you bid $4.90, player two will use (Step 2) to bid $5.00, and you lose.
- Again you should bid $5.00 if your previous bid was $4.05 or more, and pass otherwise.

OK, we get the idea.
We will just keep building up a list of steps and each one will tell us to either bid $5.00 or pass, depending on our previous bid.
When does this stop working?

(Step 18) If player two has just bid $4.10, what should you do?
- If you bid anything between $4.15 and $4.95, player two will find it better to bid $5.00 and only lose $4.00 than to pass.
- So you should bid $5.00 if your previous bid was $4.05 and pass otherwise.

(Step 19) If player two has just bid $4.05, what should you do?
- Bidding between $4.10 and $4.95 will result in you losing it all, as player two will then jump to $5.00.
- You should not bid $5.00 because passing gives you the same loss and you are following the conservative convention.
- So you should definitely pass.

(Step 20) Here's where it gets interesting. Suppose player two has just bid $4.00.
- Steps 1 through 19 tell player two to pass since his last bid was less than $4.05.
- So he cuts his losses with $4.00 rather than escalating to $5.00.
- Whatever you bid above $4.00, you will win. So you should bid $4.05 or pass.
- If your previous bid was at least $3.10, you should bid $4.05.
- Otherwise pass.

Keep working backwards...
If player two has just bid anything between $3.10 and $4.00, you should bid $4.05 if your previous bid was at least $3.10 and pass otherwise.
Notice: The only rational choices to bid so far are $4.05 and $5.00.
The next lowest rational choice will be $3.10.
Then $2.15.
Then $1.20.
Then $0.25.

So to start the game, you should bid $0.25. Then player two will pass and you win $0.75.
If you bid anything lower than this, player two will bid $0.25 and you will lose your bet.
If you bid anything higher than this, player two will pass and you will get less than $0.75 profit.

Suppose you have just bid $0.25 and player two has (irrationally) bid $0.35. What do you do?
First you have to persuade player two that his bid was irrational.
Show him the above explanation.
It might take a while.
Have him work out a couple of the examples on his own.
Once he is thoroughly convinced about the rationality of your strategy, you bid $1.20. He passes, you lose $0.20, he loses $0.35.

Question: Can't you "cheat"?
Tell player two that the rational strategy for you is to bid $1.20, which results in him losing $0.35 and you losing $0.25.
Agree that if you pass, he will collect $0.65 and split the proceeds with you.
Together you pay $0.60 = $0.25 + $0.35 and earn $1.00. So you split the difference and each get $0.20.
What's wrong with this?

Nothing, objectively.
But it doesn't fit in with the rules of the game that we've been working with.
We assumed that each player is trying to maximize his/her own benefit, without regard to the other player.
If you allow for the players to try to maximize their joint benefit (i.e. cooperate), you'll get a different set of strategies.

The idea behind the technique we used above is called "proof by induction."
Basic idea:
- The first step is easy.
- The second step is easy, if you already know the first step.
- The third step is easy, if you know the first and second step.
- etc.

Notice that we have essentially trimmed the decision tree by eliminating the branch that starts at $4.95 and leads to either Pass or $5.00.
This branch appears hundreds of times in the full decision tree and we've taken care of it all at once.
This is why we can actually solve this problem in less than 300 billion years.

Theorem (O'Neill, as presented by Taylor):
Suppose two players are bidding in the dollar auction and using the conservative convention, with stakes s and bankroll b. Construct "special numbers" by the following procedure: b, b - (s-1), b - 2(s-1), b - 3(s-1), etc. If the other player has just bid x, then your optimal strategy is to:
- bid the smallest "special number" higher than x, if your old bid was at least the previous "special number"; player two will then pass
- pass otherwise

In our previous case, b=100 units, s=20 units, and the special numbers are 100, 81, 62, 43, 24, 5, corresponding to the dollar amounts $5.00, $4.05, $3.10, $2.15, $1.20, $0.25. The theorem says that if player two's bid is between $4.05 and $4.95, then player one should bid $5.00 if her previous bid was at least $4.05, and pass otherwise. This is what we derived.

Corollary (O'Neill, as presented by Taylor):
If player one starts, then the optimal bid for player one is the smallest special number. Player two will then pass.

Exercise: Prove these Lemma, needed to prove O'Neill's theorem.
Lemma: You should never exceed your previous bid by s units, regardless of what the other player does.
Lemma: You should never exceed your previous bid by s-1 units, if you are using the conservative convention, regardless of what the other player does.

Exercise: Prove this Lemma, needed for O'Neill's theorem.
Lemma: Suppose there is a bid that you can make that
- does not exceed your previous bid by s-1, and
- will result in a pass by your opponent.
Then it is better to make this bid than to pass.