Econ 431: David Reiley
Due: Wednesday, 2 May 2007

Problem Set #9

1. (10 points) DS, question 15.2.
2. (10 points) DS, question 15.4.
3. (15 points) DS, question 15.5.
4. (20 points) DS, question 15.6. This question is somewhat ambiguous in the way skaters are ranked on each program. It should say that "a skater's ranking depends on the number of judges placing her first. In case of a tie, then the second-place votes break the tie. If needed, third-place votes could be used as additional tiebreakers, and so on."
5. (15 points) DS, question 15.8.
6. (15 points) DS, question 15.9.
7. (15 points) DS, question 16.4.
8. (10 points) DS, question 16.5.
9. (10 points) DS, question 16.6.
10. (30 points) In this problem, we consider a special case of the first-price sealed-bid auction and show what the equilibrium amount of bid-shading should be. Consider a first-price sealed-bid auction with N risk-neutral bidders. Each bidder has a private value independently drawn from a uniform distribution on [0,1] - that is, for each bidder all values between 0 and 1 are equally likely. The complete strategy of each bidder is a "bid function" that will tell us, for any value v, what amount B(v) that bidder will choose to bid. Deriving the equilibrium bid functions requires solving a differential equation, and since this sort of mathematics is beyond the scope of this course, I will instead propose what the answer should be and have you check that it is indeed a Nash equilibrium.
    
    I claim that the equilibrium bid function is B(v) = [(N-1)/N]v for each of the N bidders. That is, if we have two bidders, each should bid half her value, which represents considerable shading. If we have nine bidders, then each should bid 9/10 of her value, and so on.
    
    To verify this claim, let's start with the case N=2.
    1. (3 points) Suppose you're bidding against just one opponent whose value is uniformly distributed on [0,1], and who always bids half her value. What is the probability that you will win if you bid b=0.1? If you bid b=0.4? If you bid b=0.6?
    2. (2 points) Putting together the answers to the previous question, what is the correct mathematical expression for Pr(win), the probability that you win, as a function of your bid b?
    3. (5 points) Find an expression for the expected profit you make when your value is v and your bid is b, given that your opponent is bidding half her value. Remember that there are two cases: either you win the auction, or you lose the auction, and you need to average the profit between these two cases.
    4. (3 points) What is the value of b that maximizes your expected profit? This should be a function of your value v.
    5. (2 points) Use your results to argue that it is a Nash equilibrium for both bidders to follow the same bid function B(v)=v/2.

       Now consider the general case of N bidders.

    6. (3 points) Now there are N-1 other bidders bidding against you, each using the bid function B(v)=[(N-1)/N]v. For the moment, let's focus on just one of your rival bidders. What is the probability that she will submit a bid less than 0.1? Less than 0.4? Less than 0.6?
    7. (2 points) Using the above results, find an expression for the probability that the other bidder has a bid less than your bid amount b.
    8. (3 points) Now remember that there are N-1 other bidders all using the same bid function. What is the probability that your bid b is larger than all of the other bids? That is, find an expression for Pr(win), the probability that you win, as a function of your bid b.
    9. (2 points) Use this result to find an expression for your expected profit when your value is V and your bid is b.
    10. (3 points) What is the value of b that maximizes your expected profit?
    11. (2 points) Use your results to argue that it is a Nash equilibrium for all N bidders to follow the same bid function B(v)=[(N-1)/N]v.
11. (10 points) DS, question 17.3.
12. (20 points) DS, question 17.6.
    (Hint for part (a): the fact that "B is twice as impatient as A" implies a simple relationship between r and s.)
    (Hint for part (b): the exact solutions are found on the top half of p. 585, while the bottom half of p. 585 shows how these solutions can be approximated.)
    
13. (35 points) Consider two players who bargain over a surplus initially equal to a whole-number amount V, using alternating offers. That is, Player 1 makes an offer in round 1; if Player 2 rejects this offer she makes an offer in round 2; if Player 1 rejects this offer she makes an offer in round 3; and so on. Suppose that the available surplus decays by a constant value of c=1 each period. For example, if the players reach agreement in round 2, they divide a surplus of V-1; if they reach agreement in round 5, they divide a surplus of V-4. This means that the game will be over after V rounds, because at that point there will be nothing left to bargain over. (For comparison, remember the football-ticket example in the text, where the value of the ticket to the fan started at $100 and declined by $25 per quarter for four quarters.) In this problem, we will first solve for the rollback equilibrium to this game, and then solve for the equilibrium to a generalized version of this game where the two players can have BATNAs.
    
    1. (5 points) Let's start with a simple version. What is the rollback equilibrium when V=4? In which period will they reach agreement? What payoff x will Player 1 receive, and what payoff y will Player 2 receive?
    2. (5 points) What is the rollback equilibrium when V=5?
    3. (5 points) What is the rollback equilibrium when V=10?
    4. (5 points) What is the rollback equilibrium when V=11?
    5. (5 points) Now we're ready to generalize. What is the rollback equilibrium for any whole-number value of V? (Hint: you may want to consider even values of V separately from odd values.)
       
       Now consider BATNAs. Suppose that if no agreement is reached by the end of round V, Player A gets a payoff of a and Player B gets a payoff of b. Assume that a and b are whole numbers satisfying the inequality a+b<V, so that the players can get higher payoffs from reaching agreement than they can by not reaching agreement.
       
    6. (5 points) Suppose that V=4. What is the rollback equilibrium for any possible values of a and b? (Hint: You may need to write down more than one formula, just as you did in part (e). If you get stuck, try assuming specific values for a and b, and then change those values to see what happens. In order to roll back, you'll need to figure out on what turn V the value has declined to the point where a negotiated agreement would no longer be profitable for the two bargainers.)
    7. (5 points) Suppose that V=5. What is the rollback equilibrium for any possible values of a and b?
    8. (10 extra-credit points) For any whole-number values of a, b, and V, what is the rollback equilibrium?
    9. (5 extra-credit points) Relax the assumption that a, b, and V are whole numbers: let them be any nonnegative numbers such that a+b<V. Also relax the assumption that the value decays by exactly 1 each period: let the value decay each period by some constant amount c>0. What is the rollback equilibrium to this general problem?
14. (Extra credit, 20 points) In problem 10 above, we showed that the symmetric equilibrium where everyone uses the bid function B(v)=[(N-1)/N]v is indeed a Nash equilibrium when everyone has their values drawn from a uniform distribution on [0,1]. However, all we did was show that this solution was correct; we didn't show how to derive it. In this problem, we will show how to derive a first-price sealed-bid equilibrium bid function by solving a differential equation.
    
    Let's consider the general case where the distribution of bidder values has a CDF (cumulative distribution function) of F(v). That is, F(v) is the probability that a given bidder's value is less than or equal to the number v. For now, this will be a general, unspecified function. Later, we'll substitute in a specific function that corresponds to the case of a uniform distribution where all values between 0 and 1 are equally likely.
    
    Let's assume that there exists some strictly increasing bid function B(v) such that if all N bidders use this function, we will have a Nash equilibrium. We can use the definition of Nash equilibrium to figure out an equation that must be true for b(v).
    
    1. Let's start by finding the probability that I have the highest of the N values. If my value is v, then what is the probability that all N bidders have values less than mine? I'm asking you to use similar reasoning to part (h) of problem 4 above, but your probability expression should now contain the general function F(v).
       
    2. We have supposed B(v) to be strictly increasing in v, so it must have an inverse function. Let V(b) be this inverse function. This is the function that, for a given bid amount b, will tell you the value of the person who submitted the bid, assuming that person used the equilibrium bid function B(v). (For example, if B(v)=0.5v, then V(b)=2b.) Now suppose that I know everyone else is using the bid function B(v). Suppose I have a value of v, and I choose to bid some number b, which may or not be equal to B(v). Then, if someone else assumes I am following the bid function b(v), it will look as though I have a value of V(b).
       
       Since B(v) is strictly increasing, the highest bid among my rivals will be submitted by the bidder with the highest value. So to win the auction, I need to bid an amount b such that my apparent value V(b) is higher than all of my rivals' values. Thus, if we substitute v=V(b) into our answer for part (a), we should have an expression for the probability that I win the auction with bid amount b. Use this to write down an expression for my expected profit if I bid amount b. This should be similar to your answer for part (i) of question 4 above, but will use the general functions F and V.
       
    3. Now I want to choose my bid amount to maximize my expected profit. Write down the appropriate first-order condition. Since we are using general functions F and V, your first-order condition should include their derivatives F' and V'. You will also need to remember the chain rule from calculus class: the derivative of f(g(x)) with respect to x is equal to f'(g(x)) times g'(x).
       
    4. Now let's impose the Nash equlibrium condition. If the bid function B(v) is a symmetric Nash equilibrium, then I should want to follow it when everyone else does. That means that in the first-order condition in (c) for the optimal value of my bid b, if my value is v, I should want to bid b=B(v). Similarly, my apparent value V(b) will equal my actual value v. Substitute b=B(v) and V(b)=v into the above equation. Show how to rearrange your result into the following differential equation:
       
       B'(v) + (N-1)[F'(v)/F(v)]B(v) = (N-1)[F'(v)/F(v)]v
       
    5. The above equation is called a "differential equation" because it tells us a rule that must be satisfied by the unknown function B(v) for all possible values of v. Remember that F(v) is a known function that describes the distribution of bidders' values; we just haven't specified what F(v) is yet. On the other hand, B(v) is an unknown function. The above equation gives us the relationship that must always hold true for the relationship between the function B(v) and its derivative B'(v), for all values of v. Let's make an analogy to ordinary algebraic equations. When we look at an algebraic equation, we want to find the unknown value x that satisfies the equation. Here, we have something similar but more complicated:, we have an equation that must be satisfied by an unknown function, and we want to find the entire shape of this function.
       
       There is no general recipe for solving a differential equation; different techniques work well for different types of equations. This equation turns out to be one that can be solved by multiplying by an "integrating factor" and then integrating both sides of the equation.
       
       So, to solve this equation, multiply both sides by the factor F(v)^(N-1). Then integrate both sides of the equation. You should get an equation showing that B(v) equals some expression involving the function F(v) as well as an integral sign, plus some arbitrary constant C of integration. There shouldn't be any B on the right side of the equation.
       
    6. We haven't figured out yet the value of the arbitrary constant of integration. Restating this in math jargon, we haven't figured out the appropriate "boundary condition" for this differential equation. So our solution is not yet complete, because there are an infinite number of different values of C that we could use.
       
       It turns out to help to specify the integral on the right side as a definite integral, from the lowest possible value of 0 up to some arbitrary value v. Since the variable v currently appears both inside and outside the integral sign, we need to be careful. Inside the integral, you should replace v with some other variable u, to keep track of the fact that u is just a variable of integration, rather than being the same as the v outside the integral sign. Then the integral sign should have lower limit 0 and upper limit v, so that we are integrating over u from 0 to v.
       
       Now, what is the appropriate "boundary condition"? To figure this out, consider what a bidder with a value of 0 should do. If he bids more than 0, he risks winning the auction and getting a negative payoff,. so he wouldn't want to do that in equilibrium. But he can't bid less than zero, by the rules of the auction. So a bidder with v=0 must submit a bid of 0. That is, our boundary condition is B(0)=0.
       
       Substitute this boundary condition into our solution for B(v), and use this to find the appropriate value of the constant C.
       
       You should get a result saying that B(v) equals v, minus some bid-shading amount. The bid-shading amount is the ratio of two expressions. In the numerator is the integral of F(u)^(N-1), integrated from 0 to v. In the denominator is F(v)^(N-1).
       
       Note that this result gives us a general solution for a first-price sealed-bid auction. You tell me some probability distribution F(v) of values, and I'll tell you what the equilibrium bid function must be. F(v) can have any shape at all, so long as it is a valid CDF - it must start at F(0)=1, end at F(infinity)=1, and be weakly increasing for all v in between 0 and infinity.
       
    7. Now we have a general result, but this general function F(v) is rather abstract and hard to think about. So let's go back to the specific case of a uniform distribution of values from 0 to 1. Then F(v)=v. Substitute this value of F into your solution, and show that you get the same bid function B(v) as in problem 4. You have now derived the bid function from scratch!
       
15. (Extra credit, 15 points) By the time you read this, we will have played an all-pay auction in class. Unlike the discussion in Section 16.5, where the all-pay auction was for a good with a publicly known value, our all-pay auction involved different people having private values for the good. For the all-pay auction with a uniform distribution of values between 0 and 1 (similar to what we did in class), the Nash equilibrium bid function is b(v)=[(N-1)/N]v^N.
1. Plot graphs of b(v) for the case N=2 and for the case N=3.
2. Tell me whether the bids are increasing in the number of bidders, or decreasing in the number of bidders. Your answer might depend on N and v - that is, bids are sometimes increasing in N, and sometimes decreasing in N.
3. Prove that the function given in part (a) is really the Nash equilibrium bid function. Use a similar approach to that of problem 4 above. Remember that in an all-pay auction, you pay your bid even when you lose, so your payoff is v-b when you win, and -b when you lose.
16. (Extra credit, 10 points) DS, question 18.2
17. (Extra credit, 10 points) DS, question 18.5.