1    repeated game

1.1    tit-for-tat

Pepsi and Coke are in competition in the soft drink market. The two Örms play a game that is repeated over an inÖnite future. In each stage of the game, each Örm simultaneously chooses either to sell at a low price or a high price.  The pricing decisions of both Örms determine the products for both Örms. The game played in each stage is depicted below.

Pepsi

Low price High price

Coke

Low price 20,20       5,40

High 40,5  30,30

price

Both Örms have a discount factor where 0 < 6 < 1. Tell me all values of 6 so that the "tit-for-tat" strategy is a subgame perfect equilibrium.

2    Bayesian game

2.1    one sided incomplete information

Consider the following static game of incomplete information.  Nature selects the type  (c) of player  1, where c  =  2 with probability 2=3 and c  =  0 with probability 1=3. Player 1 observes c (he knows his own type), but player 2 does not observe c.  Then players make simultaneous and independent choices and receive payo§s as described by the following matrix.

player

Player 2 X

1    A    0; 1

B     1; 0

Y

1; 0

c; 1

1.  Draw the Bayesian normal form matrix for the game, i.e., a normal form matrix that makes it explicit that player 1 has two choices to make.

2.  Compute the Bayesian equilibrium.

2.2    dispute

Two people are involved in a dispute. Person 1 does not know whether person 2 is strong or weak; she assigns probability a to person 2ís being strong. Person 2 is fully informed.  Each person can either Öght or yield.  Each person get the payo§ of 0 if she yields (regardless of the other personís action) and a payo§ of 1 if she Öghts and her opponent yields; if both people Öght, then their payo§s are (-1,1) if person 2 is strong and (1,-1) if person 2 is weak.  Formulate this situation as a Bayesian game and Önd its Nash equilibria if a  < 1=2 and if a > 1=2:

2.3    election

Whether candidate  1 or candidate 2 is elected depends on the votes of two citizens.  The economy may be in one of two states, A and B.  The citizens agree that candidate 1 is best if the state is A and candidate 2 is best if the state is B.  Each citizen gets a payo§ of 1 if the best candidate for the state wins (obtains more votes than the other candidate), a payo§ of 0 if the other candidate wins, and payo§of 1/2 if the candidates tie; both citizens are expected value maximizers. Citizen 1 is informed of the state, whereas citizen 2 believes it is A with probability 0.9 and B with probability 0.1. Each citizen may either vote for candidate 1, vote for candidate 2, or not vote.

1.  Formulate this situation as a Bayesian game.   (Construct the table of payo§s for each state.)

2.  Show that the game has exactly two pure Nash equilibria, in one of which citizen 2 does not vote and in the other of which she votes for 1.

3.  Show that an action of one of the players in the second equilibrium is weakly dominated.

4. Why is ìswing voterís curseîan appropriate name for the determinant of citizen 2ís decision in the Örst equilibrium?

2.4    double auction (di¢ cult)

(Double auction) A single seller and a single buyer may trade 0 or 1 unit of a good.  The seller (player 1) has cost c, and the buyer (player 2) has valuation v, where v and c both are private information and are uniformly distributed in [0; 1].  The seller and the buyer simultaneously and independently choose bids b1 ;b2   e  [0; 1] : If b1   s b2 , the two parties trade at price t =  (b1  + b2 )=2.   If b1  > b2 ; the parties do not trade. The sellerís payo§ is thus u1  = (b1 +b2 )=2 - c

if b1  s b2 , and 0 if b1  > b2 ; the buyerís payo§ is u2  = v - (b1 + b2 )=2 if b1  s b2 ; and 0 if b1  > b2 .  Suppose each playerís strategy is a strictly increasing, linear function of his type.   Solve for the equilibrium.

2.5    ex boy friend still a friend?

Bill used to be Annís boyfriend. Today it is Annís birthday. Bill can either not give a gift to Ann or give her a nicely wrapped gift.  If o§ered a gift, Ann can either accept or reject. Ann does not know if Bill is still a friend or has become an enemy.  If he is a friend, she expects a nice present from him.  If Bill is an

enemy, she expects to Önd a humiliating thing in the box.

The preferences are as follows:  Billís favorite outcome (payo§ = 1) occurs when he o§ers a gift and it is accepted.  He prefers having not extended a gift (payo§ = 0) to enduring the humiliation of a rejected gift (payo§ = -1).  Ann prefers accepting a gift coming from a friend  (payo§ =  1) to refusing a gift (payo§ = 0); the worst outcome for her (payo§ = -1) is one where she accepts a gift from an enemy. Ann attaches probability p (with 0 < p < 1) to the event that Bill is a friend (and 1 - p to Bill being an enemy); however, Ann knows that Bill knows whether he is a friend or an enemy. Everything that Ann knows is common knowledge between Ann and Bill.

1.  Draw an extensive-form game tree with nature choosing Billís type at the beginning.

2.  Find all the pure-strategy perfect Bayesian equilibria and classify them as either pooling or separating.

3.  Suppose that p = 1=4.  Is the outcome associated with a pure-strategy perfect Bayesian equilibrium Pareto e¢ cient?

2.6    two-sided incomplete information

Consider the situation of two-sided incomplete information illustrated below (where the true state is a).

Player 1ís information partition is {{a} ; {β;7}} and when he is in information set {β;7} he believes he is in state β with probability 3/4 and in state 7 with probability 1/4. Player 2ís information partition is {{a;β} ; {7}} and when he is in information set {a;β} he believes he is in state a with probability 1/3 and in state β with probability 2/3. Represent this incomplete-information situation as an extensive-form game. Be explicit about how you calculated the probabilities

for Nature.  (Answer:  Natureís probabilities, pa  = 3=11;p8  = 6=11; and py  = 2=11, are obtained by solving = ; = and pa + p8  + py  = 1:)

3    auction and mechanism design

For all the questions in this section, agents are risk neutral unless otherwise stated.

3.1    equilibrium strategy for Örst bid auction

Consider  a Örst price  sealed-bid  auction between n  di§erent bidders,  where n > 3 The biddersívaluations, vi  are uniformly distributed between 0 and 1. Each bidder knows its true value, but does not know the values of the other bidders.  The equilibrium bidding strategy for all bidders is given by bi  = avi ; where a is some unknown constant.  Find the equilibrium bidding strategy for all the bidders (that is, determine the value for the constant a).  (answer:

n - 1

n

for i = 1; 2;:::;n:

3.2    revenue equivalence

There are one seller with an indivisible item for sale and two buyers with valu- ations x1  and x2  identically and uniformly distributed between [0; 100].

1.  Calculate the expected revenues under the second price sealed bid auction and the Örst price sealed bid auction.  (Remark:  you cannot directly use the fomulae for expected renvenues found in class.  You have to do the calculations from Örst principles. However, there is no need to derive the equilibrium strategies.) Verify that they are indeed equal.

2.  Suppose it happens that x1  = 20 and x2  = 80.  What are the revenues under the two auctions? Are they the same?

3.  Suppose it happens that x1  = 40 and x2  = 60.  What are the revenues under the two auctions? Are they the same?

4.  Reconcile the results you found in (1) to (3).

3.3    one seller one buyer

There are one seller with an indivisible item and one buyer.   The item is of no value to the seller and the buyerís valuation for the good, denoted by x, is believed to be uniformly distributed in [0;!].  Instead of using auction, the seller decides to give a take-it-or-leave-it o§er  y (i.e., if accepted by the buyer, they will trade with the buyer paying y; if not accepted by the buyer, they will not trade and the game ends.) Set up the proÖt maximization problem for the seller and Önd out this optimal y. Discuss the answer in relation to the "virtual valuation" for the buyer.

3.4    optimal mechanism: ex ante identical buyers

There are one seller with an indivisible item and N buyers whose valuations x1 ;:::;xN  are independently and uniformly distributed from the [0;$] interval. Describe the optimal direct mechanism whereby the seller attempts to sell her item. How is the reserve price related to N?

3.5    optimal mechanism:  heterogeneous buyers

There are one seller with an indivisible item and 2 buyers with valuations x1 and x2 , where x1  is uniformly distributed between [0; 100] and x2  is uniformly distributed in [0; 200]. Describe the optimal direct mechanism for the seller.

4    signaling and Bayesian extensive form games

4.1    hunt or not hunt

Consider N villagers i = 1;:::;N; each of whom is privately informed of the cost he must incur if he goes hunting.  This cost, denoted ci , is a priori uniformly distributed on  [0; 1 + "], where " is some positive number, and the ci  are in- dependently distributed across villagers. If all hunt together, they will catch a deer, which yields a value 1 to each of them. On the other hand, if some villager decides to stay at home, the other will not be able to catch the stag and will have a payo§ of zero.  All villagers are risk neutral.  Except for the costs of hunting, all components of the model are commonly known.

1.   (a)  Find all Nash equilibria of this game.

(b)  Now consider a modiÖed game as follows.   In the Örst stage each villager announces  ìyesîor  ìnoîto all the others, and announcing itself is costless (hence we are considering a cheap talk game). In the second stage each of them decides whether to go hunting. Show that in this modiÖed game there exists an equilibrium in which in the Örst stage each villager announces ìyesîif and only if his private cost ci is lower than 1. Completely describe this equilibrium.

4.2    education signaling: discrete choices I

Consider a game of asymmetric information played between a student and a Örm. The student can have one of two ability levels: high or low. The student knows its own ability level, while the Örm does not. All the Örm knows is that 75% of students are of high ability and 25% of students are of low ability.  The student sends a signal by deciding whether or not to attend college. The cost of college for a high ability student is 4, while the cost of college for a low ability student is 8. There is no cost associated with the decision not to attend college. The Örm forms beliefs about a studentís ability level and then must decide to

either o§er the student high wages or low wages. High wages are value 10, while low wages are value 1. The payo§s to the Örm are as follows:

Payo§ = 1    if o§er High wages to High ability OR Low wages to Low ability Payo§ = 0    if o§er High wages to Low ability OR Low wages to High ability

The payo§ for the student is simply Payo§ = Wages - Cost of Education. Draw the game tree. Does there exist a perfect Bayesian equilibrium (PBE) in which both ability levels choose to attend college? Show all work to justify your answer.

4.3    education signaling: discrete choices II

Consider a game exactly as in the previous question, except now that 50% of students are of High ability and 50% of students are of Low ability. An additional di§erence is that now the cost of college for a high ability student is 5, while the cost of college for a low ability student is 10.  All other facts are identical to those described in the previous question.  Draw the game tree.  Does there exist a perfect Bayesian Nash equilibrium (PBE) in which only students of High ability go to college, while students of Low ability do not?  Show all work to justify your answer.

4.4    education most costly for high able workers

Consider the following modiÖcation to the education game studied in class: the cost of education for a i-type worker is 9i e where 9i  is his ability and e is his education choice.  Answer the following and you must state the belief system for each equilibrium.

1.  Does a separating perfect Bayesian equilibrium exist such that H-type worker chooses eH   with probability one and L-type worker chooses eL with probability one?

2.  Does a pooling perfect Bayesian equilibrium exist such that both types of worker choose e = 0?

3.  Does a pooling perfect Bayesian equilibrium exist such that both types of worker choose e > 0?

4.5    insurance

Consider an insurance market with two risk-neutral insurance companies and risk-averse individuals.  The individuals are of two types:  High (H) and Low (L): Both types have wealth W = 6 and in the bad states (b) of the world su§er a loss of R = 8 (in the good states (g), there is no loss). The high type su§ers a loss with probability pH  = 1=2 and the low type su§ers a loss with probability pL  = 2=5. The individuals have utility u() = ln(); so the payo§ functions are:

Payo§(H)   =   pH × u(cH;b ) + (1 - pH ) × u(cH;g )

Payo§(L)   =   pL × u(cL;b ) + (1 - pL )u(cL;g )

The insurance companies o§er two contracts:  (MH ;DH ) and (ML ;DL ); where M is the premium and D is the deductible. With asymmetric information, solve for the optimal contracts that are o§ered by the insurance companies.  (Note: Önd out the meaning of premium and deductible if you are not sure.)(Solution: The contract (MH;DH) will be selected by the high risk types and (ML;DL) will be selected by the low risk types.  Both contracts are determined so that the insurance companies earn zero proÖt:  元H  = MH  - pH (R - DH ) = 0 and 元L   = ML  - pL (R - DL ) = 0.   ....the contracts are:  (MH ;DH ) =  (4; 0) and (ML ;DL ) = (2; 3).)

4.6    limit pricing

Suppose there is an incumbent Örm with monopoly power in period 1, and this Örm chooses Örst period price p.  Then, in period 2, Örm 2 decides whether to enter or to stay out. If Örm 2 enters, there is a duopoly for that period and the game is over. Otherwise, Örm 1 remains a monopoly.

Suppose both Örms have constant marginal costs and no Öxed costs. More- over, marginal cost takes two values, high (c = ch ) or low (c = cl ). The entrant has high costs and the incumbent can have low costs with probability q, or high costs with probability 1 - q.  Let mh (p) be the incumbentís monopoly proÖt when he charges p and c = ch   and let ml (p) be the incumbentís monopoly proÖt when he charges p and c = cl .   Let pm(l)  and pm(h)  denote the monopoly prices charged by the incumbent when marginal cost is low or high ( i.e., the monopolistís proÖt-maximizing price).

Let ml  = ml（pm(l)） and mh  = mh（pm(h)） be the incumbentís proÖt when he maximizes short run proÖts, depending on his type.   Suppose the incumbent knows his cost, and the entrant learns the incumbentís cost after entering the market and committing himself to production.  Thus, the duopoly price is in- dependent of Örst-period prices. We denote the entrantís duopoly proÖts by dh when costs are high and dl  when costs are low.  We assume that dh  > 0 > dl , so the entrant would enter only if the incumbentís costs are high (otherwise the problem is trivial).

One way that the incumbent can deter the entry of the entrant is through charging a low price pl (which may be even lower than pm(l)).  Of course, if the entrant believes that a monopolist would charge this low price even if c = ch , then observing the low price would have no e§ect on the entrantís decision. We say a perfect Bayesian equilibrium is a separating equilibrium if the incumbentís action reveals his type; otherwise we say the equilibrium is a pooling equilibrium.

1.  Prove that pm(l)  < pm(h) .

2.  Under what conditions do we have a separating equilibrium?

3.  Give an example of a separating equilibrium.

4.7    bad reputation

(Is reputation always good?) Start a one-shot model of an agent and a principal.

Think of them as a car mechanic and car owner. The car owner does not know

which type of repair is needed:  either to have the engine replaced, or just to have a tune-up.  But he knows that they are of equal probability.  The payo§ to the car owner is u if the right repair is taken and is -w otherwise, where w > u > 0.  The car mechanic has expert knowledge so that he knows exactly which kind of repair is needed once the car is seen. But there are two types of car mechanicsñhe can be either good or bad. If the car mechanic is a good one, his payo§ is exactly the same as the car owner. When the right repair is made, his payo§ is u; when the wrong repair is made, his payo§ is -w. In case the car is not given to the mechanic for repair, both partiesís payo§s are zero.  If the car mechanic is a bad one, he is one who always replace engine.  (Hence, a bad mechanic is like a machine always doing the same thing.) The prior probability that the car mechanic is bad with probability u.

1. Will the car owner bring his car to the car mechanic if u = 0? Will he do so u > 0 but su¢ ciently close to zero?

2.  Now consider an inÖnite horizon model with one inÖnite-lived car mechanic

and a sequence of car owners who arrive and live one period only. Let the prior probability that the car mechanic is bad be probability u0  > 0. The type of the car mechanic remains unchanged over time.  We assume that decisions to bring cars to the mechanic and repair decisions are observable and are used for future car owners to updating their belief about the type of the car owner.  (Whether a repair turns out to be good or bad is not observable, however).  Show that in any perfect Bayesian equilibrium, no car owner will ever bring his car to car mechanic. Show that, however, if u0  = 0, there exists a perfect Bayesian equilibrium in which car owners always bring their cars to the mechanic.   (This type of result is called "discontinuity at zero.")

5    Cooperative Game Theory

1.  The convex hull of a Önite set of points is the smallest convex set that contains the points. Depict graphically the corresponding convex hull for each of the following cases.

(a)  (0; 0); (1; 0); and (0; 2).

(b)  (0; 0); (0; 1);and (1; 0)

(c)  (0; 0); (1; 0); (1=2; 1=2); and (0; 1=2).

2.  Consider a bargaining between Gary and Francis on the division of an ice cream.   Garyís utility level is x2  if his fraction of ice cream is x, while Francisís utility level is  ,y  if his fraction is y.   If they donít come to

an  agreement,  each will receive zero fraction of the ice cream.   What is the feasible set of utility pairs [randomization permitted]? What is the disagreement point? Find the Nash bargaining solution (in terms of utility levels). What contract(s) can support this solution?

3.  Consider a function g(x1 ;x2 ) = ,x1 +,x2 .  For the bargaining solution that assigns to each bargaining problem (S;d）the (unique) maximizer of g(s1  - d1 ;s2  - d2 ) over {s e S : s > d}.  This function can be shown to satisfy PAR, IIA, and SYM [proof not requested]. However it violates INV. Illustrate this violation by the following problem (S;d） where d = (0; 0) and S is the convex hull of the points (0; 0); (1; 0); and (0; 2).

4.  For any bargaining problem (S;d）, the solution fa  assigns to it the utility pair

arg         max         (s1 - d1 )a (s2 - d2 )1 _a :

(d1 ;d2 )S(s1 ;s2 )∈S

This family of solution {fa }a∈(0 ; 1);a0 :5  is known as the family of asym- metric Nash solutions.   Every solution fa  satisÖes INV, IIA, and PAR [proof not requested],  but violates  SYM. Use the following bargaining problem to illustrate the violation.  d = (0; 0) and S is the convex hull of (0; 0); (1; 0); and (0; 1).

5.  For any bargaining problem (S;d）, let si  be the maximum utility Player i gets in {s e S : s > d} ; for i =  1; 2.   Consider the solution fKS (S;d) that assigns to (S;d）the maximal member of S on the line joining d and (s1 ; s2 ). This bargaining solution is known as Kalai-Smorodinsky solution. Show that the solution satisÖes both SYM and PAR. [It also satisÖes INV, but proof is not requested.]  Use the following bargaining problem (and related bargaining problems) to illustrate that it violates IIA. d = (0; 0) and S is the convex hull of (0; 0); (1; 0); (1=2; 1=2); and (0; 1=2).

6.  Consider the solution fd  deÖned by fd (S;d) = d. Show that this solution satisÖes INV, SYM, and IIA, but violates PAR.

7. Verify whether the following characteristic function is superadditive, and whether the game is convex.  There are three players:  1,2,3.  v (6) = 0; v ({1}) = v ({2}) = v ({3}) = 0; v ({1; 2}) = v ({1; 3}) = 6; v ({2; 3}) = 3; v ({1; 2; 3}) = 10:

8.  There  are two characteristic functions:   v  (as described in question 4) and u; where u(6) = 0; u({1}) = u({2}) = 4;u({3}) = 0; u({1; 2}) = 4;u({1; 3}) = 6; u({2; 3}) = 12; u({1; 2; 3}) = 20: Let w = v + u be a characteristic function being the sum of v and u. Write down u completely.

9.  Recall example 3  (with four players) we used in class to motivate the concept of Shapley value.   Write down the characteristic function, and calculate the cost allocation to the four players according to Shapley value.

10. In the case of two sellers with unequal reserve prices, 100 for S1 , and 150 for S2 , and one buyer B with a willingness to pay of 300, show that in a core allocation, the respective surpluses x1 , x2  and y must satisfy x1  s 50, x2  = 0, and y > 150.  Verify that this outcome means that S1  sells his house for a price between 100 and 150.

11.  There are four sellers and three buyers.  Each seller has one unit to sell and a reserve price (i.e., minimum willingness to sell) of 100. Each buyer wishes to buy one unit. One is willing to pay up to 400; each of the other two, up to 300.  Find the market equilibrium (i.e., the outcome at which both sellers and buyers are price taking) by drawing a Ögure.  Find the core by setting up and solving all the no-blocking inequalities.

12.  An airport runway is going to be used by four types of planes:  small corporate jets and commercial jets of the narrow-body, wide-body, and jumbo varieties. A corporate jet needs a runway 2,000 feet long, a narrow- body 6,000 feet, a wide-body 8,000 feet, and a jumbo 10,000 feet.  The cost of constructing a runway is proportional to its length.  Considering each type of aircraft as a player, use Shapley value to allocate the costs of constructing the 10,000-foot runway among the four types.  Is this a reasonable way to allocate the costs?

13.  Greatest lower bound and least upper bound.  If S is a set of real numbers, we say that b is an upper bound for S if for each x e S we have x s b. A number c is called a least upper bound, or supremum, for S if it is an upper bound for S and if c s b for each upper bound b of S. We write c = supS.  Similarly, the concept of greatest lower bound, or inÖmum, written as inf S is deÖned. Note that the supremum and inÖmum to a set of real number are unique as long as they exist. Find out the supS , inf S , maxS, and minS to each of the following cases.

(a)  S = {6:4; 1997; -2}

(b)  S = {1; 1=2;:::; 1=n;:::}

(c)  S = [0; 1)