Current assignments:

• The homework will be due Thursday, Feb. 13.

• (1.2) Decision trees: examples and exercises
• (1.3) Limitations on decision tree analysis

Decision Trees

• How to build a decision tree
• Start at the top
• List all the options for player one in the first row
• Every bid up to the bankroll, without passing.
• For each option available to player one, list all options available to player two and link them
• Every bid greater than the previous one, up to the bankroll, plus the option of passing
• For each option available to player two, list all options available to player one and link them
• Every bid greater than the previous one, up to the bankroll, plus the option of passing
• Continue until all options have been exhausted and all that remains are terminal nodes
• Example: Decision tree for b=4, s=2 (bidding for $2 with a maximum bid of $4) (Powerpoint file)
• How to prune a decision tree
• At each terminal node, write the payoff to each player
• Start at the bottom:
• Look at decisions just before the terminal nodes
• Which player is making the decision?
• What outcomes does each choice bring that player?
• Which outcome will the player choose?
• The choice is now determined, and this decision becomes a terminal node
• Cross off all other links leading to other terminal nodes
• Rewrite the payoff at this new terminal node
• Continue backwards until you get to the top of the tree
• Example: Optimal strategy for b=4, s=2, with the conservative convention
• (If two bids would yield the same result, bidder chooses the cheaper one)
• Example: Optimal strategy for b=4, s=2, with the aggressive convention
• (If two bids yield the same result, bidder chooses the more expensive one)
• Exercises: Do the following alone or in pairs. Write your name(s) on it, and hand it in.
1. Construct a decision tree for b=4, s=4, and determine the optimal strategy under the conservative convention.

   Solution (Powerpoint file)

2. Construct a decision tree for b=3, s=2. Suppose each player is trying to minimize the other player's benefit. If two bids lead to the same outcome, the player chooses what's best for him/herself. If two bids lead to the same outcome for both players, the bidder chooses the cheapest one. What is the optimal strategy?

   Solution (Powerpoint file)

Limitations of tree pruning: time estimate

• The real dollar auction consists of nickel-increment bids for $1.00, up to a maximum of $5.00
• This translates to stakes of s=20 units ($1.00 divided by $0.05) and bankroll of b=100 units ($5.00 divided by $0.05)
• This is a big decision tree
• The first row is 100 circles
• The second row is about 5,000 circles (exact calculation on the board)
• We can't do it by hand.
• Could a computer do it?
• Theoretically, yes; one programs it to do the "backward induction" algorithm to prune the tree
• But how long would it take?
• First question: how big is the tree? Call the answer N (number of terminal nodes)
• Second question: how long does it take the computer to process each node? Call the answer T (time per node)
• How long will it take in total? N multiplied by T
• Figure out N:
• The number of nodes depends only on the bankroll b, not on the stakes s. So we have a function N(b)
• If the bankroll is b = 2, then the tree has 3 terminal nodes
• If the bankroll is b = 3, the tree has 7 terminal nodes
• If b = 4, the tree has 15 terminal nodes
• What is the pattern?
• 3=2²-1, 7=2³-1, 15=2⁴-1...
• Looks like N(b) = 2^b-1...
• How can we prove this?
• Look at the decision tree for b=3.
• It includes two copies of the decision tree for b=2, plus an extra option to pass.
• So N(3) = 2N(2) + 1
• This works: 7 = 2×3 + 1
• Look at the decision tree for b=4.
• It includes two copies of the decision tree for b=3, plus an extra option to pass.
• So N(4) = 2N(3) + 1
• This works: 15 = 2×7 + 1
• This works no matter what b is. So
• N(5) = 2N(4) + 1 = 31 = 2⁵-1 ,
• N(6) = 2N(5) + 1 = 63 = 2⁶-1,
• etc.
• In general, check that N(b) = 2^b-1 satisfies
N(b+1) = 2 N(b) + 1
• We have N(b+1) = 2^b+1-1 and 2 N(b) + 1 = 2(2^b-1) + 1 = 2 × 2^b - 2 + 1 = 2^b+1-1
• Yay!
• So if b = 100, then N = 2¹⁰⁰-1.
• What is this?
• Well, 2⁵ = 32, so 2¹⁰ = 2⁵ × 2⁵ = 32 × 32 = 1024, which is about 1,000.
• So 2¹⁰⁰ = (2¹⁰)¹⁰ = (1000)¹⁰ = (10³)¹⁰ = 10³⁰
• Now how many operations can a computer perform in a second? State of the art is about one trillion, or 10¹²
• So if N = 10³⁰ operations and T = 10¹² operations per second, then a computer needs

• How many seconds are in a year?

• So the computer needs 10¹⁸ seconds divided by 31,536,000 seconds in a year or about 32,000,000,000 years. (32 billion)
• Ouch!
• Clearly we cannot find an optimal strategy by this "brute force" method.
• Instead we need to look for a pattern in the small examples and try to generalize.
• (Just like we did to count the number of terminal nodes in a tree!)