Stat155 Game Theory - Homework 2: Auction, Allocation and Payment Rules
Problem 2.2 Suppose a subset S of the bidders in a second-price single-item auction decide to collude, meaning that they submit their bids in a coordinated way to maximize the sum of their utilities. Assume that bidders outside of S bid truthfully. Prove necessary and sufficient conditions on the set S such that the bidders of S can increase their combined utility via non-truthful bidding.
Exercise 3.1 Use the “payment difference sandwich” in (3.4) to prove that if an allocation rule is not monotone, then it is not implementable.
Exercise 3.4 Consider the following extension of the sponsored search setting described in Section 2.6. Each bidder i now has a publicly known quality βi, in addition to a private valuation vi per click. As usual, each slot j has a CTR αj, and α1 ≥ α2 ··· ≥ αk. We assume that if bidder i is placed in slot j, then the probability of a click is βiαj. Thus bidder i derives value viβiαj from the jth slot.
Describe the welfare-maximizing allocation rule in this general- ized sponsored search setting. Prove that this rule is monotone. Give an explicit formula for the per-click payment of each bidder that ex- tends this allocation rule to a DSIC mechanism.
Problems
Problem 3.1 Recall our model of sponsored search auctions (Sec-
tion 2.6): there are k slots, the jth slot has a click-through rate
(CTR) of αj (nonincreasing in j), and the utility of bidder i in slot j is αj(vi − pj), where vi is the (private) value-per-click of the bid- der and pj is the price charged per-click in slot j. The Generalized Second-Price (GSP) auction is defined as follows:
The Generalized Second Price (GSP) Auction
1. Rank advertisers from highest to lowest bid; assume without loss of generality that b1 ≥ b2 ≥ · · · ≥ bn.
2. For i = 1,2,...,k, assign the ith bidder to the i slot.
3. For i = 1,2,...,k, charge the ith bidder a price of bi+1 per click.
The following subproblems show that the GSP auction always has a canonical equilibrium that is equivalent to the truthful outcome in the corresponding DSIC sponsored search auction.
(a) Provethatforeveryk≥2andsequenceα1 ≥···≥αk >0of CTRs, the GSP auction is not DSIC.
(b) (H) Fix CTRs for slots and values-per-click for bidders. We can assume that k = n by adding dummy slots with zero CTR (if k < n) or dummy bidders with zero value-per-click (if k > n). A bid profile b is an equilibrium of GSP if no bidder can increase her utility by unilaterally changing her bid. Verify that this condition translates to the following inequalities, under our standing assumption that b1 ≥ b2 ≥ · · · ≥ bn: for every i and higher slot j < i,
αi(vi − bi+1) ≥ αj(vi − bj);
and for every lower slot j > i,
αi(vi − bi+1) ≥ αj(vi − bj+1).
(c) A bid profile b with b1 ≥ ··· ≥ bn is envy-free if for every bidder i and slot j ̸= i,
αi(vi − bi+1) ≥ αj(vi − bj+1). (3.9)
(d) (H) A bid profile is locally envy-free if the inequality (3.9) holds for every pair of adjacent slots—for every i and j ∈ {i−1,i+1}. By definition, an envy-free bid profile is also locally envy-free. Prove that, for every set of strictly decreasing CTRs, every locally envy-free bid profile is also envy-free.
(e) (H) Prove that, for every set of values-per-click and strictly decreasing CTRs, there is an equilibrium of the GSP auction in which the assignments of bidders to slots and all payments-per- click equal those in the truthful outcome of the corresponding DSIC sponsored search auction.
(f) Prove that the equilibrium in (e) is the lowest-revenue envy-free bid profile.
Exercise 4.1 Consider an arbitrary single-parameter environment, with feasible set X. Prove that the welfare-maximizing allocation rule
is monotone in the sense of Definition 3.6
[Assume that ties are broken in a deterministic and consistent way , such as lexicographically.]
