Econ 431: David Reiley

Due: Wednesday, 2 May 2007

- (10 points) DS, question 15.2.
- (10 points) DS, question 15.4.
- (15 points) DS, question 15.5.
- (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."
- (15 points) DS, question 15.8.
- (15 points) DS, question 15.9.
- (15 points) DS, question 16.4.
- (10 points) DS, question 16.5.
- (10 points) DS, question 16.6.
- (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.- (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 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?
- (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.
- (3 points) What is the value of b that maximizes your expected profit? This should be a function of your value v.
- (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.

- (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?
- (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.
- (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. - (2 points) Use this result to find an expression for your expected profit when your value is V and your bid is b.
- (3 points) What is the value of b that maximizes your expected profit?
- (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.

- (10 points) DS, question 17.3.
- (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.)

- (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.

- (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? - (5 points) What is the rollback equilibrium when
*V*=5? - (5 points) What is the rollback equilibrium when
*V*=10? - (5 points) What is the rollback equilibrium when
*V*=11? - (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.

- (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.) - (5 points) Suppose that V=5. What is the rollback equilibrium for any
possible values of
*a*and*b*? - (10 extra-credit points) For any whole-number values of
*a*,*b*, and*V*, what is the rollback equilibrium? - (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?

- (5 points) Let's start with a simple version. What is the rollback equilibrium
when
- (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).

- 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).

- 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.

- 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).

- 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

- 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.

- 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.

- 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!

- 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).
- (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.
- Plot graphs of b(v) for the case N=2 and for the case N=3.
- 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.
- 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.
- (Extra credit, 10 points) DS, question 18.2
- (Extra credit, 10 points) DS, question 18.5.