CSCI 1440/2440 Introduction to Game Theory - Homework 2: Introduction to Auctions
Homework 2: Introduction to Auctions CSCI 1440/2440
2022-02-03
Due Date: Tuesday, February 8, 2021. 11:59 PM.
We encourage you to work in groups of size two. Each group need only submit one solution. Your submission must be typeset using LATEX. Please submit via Gradescope with you and your partner’s Banner ID’s and which course you are taking.
For 1000-level credit, you need only solve the first four problems. For 2000-level credit, you should solve the first four problems and the last. The All-Pay Auction problem is just for fun.
1
Bayesian Prisoners’ Dilemma
Mr. Burns: Remember, your job depends on your successful completion of Nuclear Physics 101. Oh, and one more thing... Mr. Burns: You must find the Jade Monkey before the next full moon. Smithers: Actually, sir, we found the Jade Monkey. It was in your glove compartment. Mr. Burns: And the road maps, and ice scraper? Smithers: They were in there, too, sir. Mr. Burns: Excellent! It’s all falling into place... -The Simpsons, Season 5, Episode 3: Homer Goes to College
Alice and Bob devise a plan to steal the jade monkey before the next full moon. They realize that it’s in a glove compartment, and decide to use a 3d-printed key to break in. However, Alice forgets to bring the key, so the pair gets caught and put into jail.
Alice and Bob are jailed in different cells, and cannot communicate with one another. The prosecutor tells each of the two that they can either: 1. stay silent, or 2. rat out the other.
We say that Alice and Bob cooperate (C) if they choose to stay silent. We say that Alice and Bob defect (D) if they choose to betray the other. The setup so far is identical to that of the standard Prisoners’ Dilemma, whose payoff matrix is shown in Figure 1, where Alice is the row player, and Bob is the column player.
C D
C 2,2 0,3
D 3,0 1,1
Figure 1: The payoff matrix for the Prisoners’ Dilemma.
But, there’s a new wrinkle. Alice and Bob are not just thieves; they are also students of moral philosophy. Alice, in particular, is fair and makes decisions using John Rawls’s maximin criterion. That is, when she makes decisions whose outcomes affect multiple people, she evaluates each outcome based on the well-being of the person who would be worst off. Thus, in this situation, her utility for each outcome is the smaller of her and Bob’s payoffs. Figure 2 shows Alice’s true utility for each outcome.
C D
C 2 0
D 0 1
Figure 2: The Rawlsian, and hence Alice’s, utilities for each outcome.
Alice is unsure about whether Bob is also fair in the Rawlsian sense. She believes he is fair with probability p, in which case he will play based on the fair payoff matrix, but unfair with probability 1 − p, in which case he will play based on the standard Prisoners’ Dilemma payoff matrix. The probability p is common knowledge, which means that Bob knows that Alice knows p, Alice knows that Bob knows that Alice knows p, and so on. The two possible payoff matrices of the game are depicted below, in Figure 3.
C D C D
C 2,2 0,0 C 2,2 0,3
D 0,0 1,1 D 0,0 1,1
Figure 3: LHS: Bob, like Alice, is Rawlsian; probability p. RHS: Bob is not Rawlsian, so his payoffs are those of the standard Prisoners’ Dilemma; probability 1 − p.
1. Assume p < 1/3. What is the only Bayes-Nash equilibrium in this game? Hint: Start by reasoning about what Bob does if he is not Rawlsian.
2. Now, assume p =1/3. Give a pure-strategy Bayes-Nash equilibrium that is different from the one that you found in part 1. 1
3. Now, assume p > 1/3. Find a mixed-strategy Bayes-Nash equilibrium. Prove that your solution is an equilibrium.
4. Compare your solutions to parts 1 and 3 above. Which Bayes-Nash equilibrium is preferable for Alice and Rawlsian Bob?
2 Collusion and Dishonesty in the Second-Price Auction
In class, we argued that in the second-price auction, no individual bidder has an incentive to deviate from bidding truthfully (i.e., re- porting their value), regardless of the other bidders’ behaviors. But the story is not quite so simple if bidders can collude, meaning submit bids in coordinated fashion.
Consider a second-price auction in which all but a subset S of the bidders bid truthfully. The members of S attempt to collude to in- crease their collective utility. State necessary and sufficient conditions on the values of the bidders in S relative to the others such that they can (strictly) increase their collective utility via non-truthful bidding. Argue for the correctness of your conditions.
3 The i.i.d. Assumption and First-Price Auctions
In class, we observed that at the unique symmetric equilibrium in a first-price auction where values are drawn i.i.d. from the uniform distribution on [0, 1], bidders shade their values, meaning they bid less than their values. Specifically, they bid n−1 times their value. Further, n this bid function is monotonically non-decreasing in value, so that a bidder with the highest value always wins the auction. In economic parlance, such an auction is called efficient.
More generally, the unique symmetric equilibrium strategy in a first-price auction where values are drawn i.i.d. from an arbitrary CDF F is given by:
Again, bidders shade their values, and again this bid function is monotonically non-decreasing in value.
As already noted, this equilibrium was derived under an important statistical assumption, namely that bidders’ values are independent and identically distributed (i.i.d.). That is, they are all drawn from the same distribution (i.e., F = Fi, for all bidders i), and no one bidder’s value depends on another’s (independence).
Show that the i.i.d. condition is necessary to guarantee (economic) efficiency in first-price auctions by constructing an example in which values are not drawn i.i.d. and the outcome is not efficient. In your example, different bidders’ values can be drawn from non-identical distributions, or they can exhibit dependencies, or both. Note, how- ever, that the distribution(s) from which values are drawn should, as is standard in Bayesian games, be common knowledge.
4 The Third-Price Auction
The first- and second-price auctions aren’t the only sealed-bid auc- tions that yield equivalent expected revenue. An auction in which the winner pays the third-highest bid is called a third-price auction. Whereas in a first-price auction, bidders shade their values at equi- librium; and in a second-price auction, bidders bid their true values at equilibrium; in a third-price auction, every bidder bids higher than their value at the unique symmetric Bayes-Nash equilibrium.
In answering the following questions, assume values are drawn i.i.d. from the uniform distribution on [0, 1].
1. Prove that a bid of bi(vi) = (n-1)vi/(n-2) by every bidder i is a symmetric Bayes-Nash equilibrium of the third-price auction.
Hint: In the lecture notes, we derive the expected value of the k-th order statistics of a random variable that is uniformly distributed on [0, 1]. More generally, the k-th order statistics of a random vari- able that is uniformly distributed on [0, z] is given by
2. Show that the expected revenue R3 at the symmetric equilibrium in the third-price auction is . . . drumroll . . . (n - 1) / (n+1)
3. What is the symmetric Bayes-Nash equilibrium strategy in a kth price auction: i.e., an auction where the winner pays the kth high- est bid? (You need only state how each bidder bids; you do not need to provide a detailed analysis or proof.)
5 The All-Pay Auction (Just for Fun!)
In an all-pay auction, the good is awarded to the highest bidder, but rather than only the winner paying, all bidders must pay their bid. In answering the following questions, assume values are drawn i.i.d. from the uniform distribution on [0, 1].
1. Prove that a bid of bi(vi) = by every bidder i is a sym- ni metric Bayes-Nash Equilibrium.
2. Show that the expected revenue RALL for the all-pay auction is ...drumroll ... (n - 1) / (n+1)
6 Linear Bidding in First-Price Auctions
Suppose you enter a first-price auction with n bidders. Once again, values are i.i.d. on the uniform distribution on [0, 1]. However, this time bidders don’t necessarily abide by the equilibrium. Instead, they have all chosen the (same) bid function θ(n), a linear function of their value. So, for each bidder j other than you, bj(vj) = θ(n)vj. Note that there is no constant term, which means that if a bidder values the good at 0, she will bid 0.
Imagine you are bidder i. Derive your optimal (i.e., expected utility-maximizing) bid bi in terms of vi, n, and θ(n). How does your optimal bid relate to the equilibrium of such a first-price auction (i.e., n bidders with values drawn i.i.d. on U[0, 1])?
