Homework 3: Myerson’s Lemma CSCI1440/2440

2024-02-08

Due Date: Tuesday, February 20, 2024. 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 three problems. For 2000-level credit, you should solve all four problems.

1 The All-Pay Auction

In an all-pay auction, the good is awarded to the highest bidder, but rather than only the winner paying, all bidders i must pay their bid: i.e., ui = vixi − pi.

Using the envelope theorem, derive (necessary conditions on) the symmetric equilibrium of a symmetric all-pay auction in which the bidders’ values are drawn i.i.d. from some bounded distribution F.

2 Allocation Rule Discontinuity

Fix a bidder i and a profile v−i. Myerson’s lemma tells us that incen-

tive compatibility and individual rationality imply two properties: 1. Allocation monotonicity: one’s allocation should not decrease as

 one’s value vi increases.

2. Myerson’s payment formula:

Z vi 0

pi(vi,v−i) = vixi(vi,v−i)−

xi(z,v−i)dz,

∀i ∈ [n],∀vi ∈ Ti,∀v−i ∈ T−i. (1)

In a second-price auction, the allocation rule is piecewise constant on any continuous interval. That is, bidder i’s allocation function is a Heaviside step function,1 with discontinuity at vi = b∗, where b∗ is the highest bid among all bidders other than i (i.e., b∗ = maxj̸=i vj):

1, if vi ≥ b∗ xi(vi,v−i) =

0, otherwise. Observe that ties are broken in favor of bidder i.

1 This is the canonical step function, whose range is [0, 1].

Given this allocation rule, the payment formula tells us what i should pay, should they be fortunate enough to win:

Z vi 0

pi(vi,v−i) = vixi(vi,v−i)−

?Z b∗

xi(z,v−i)dz

=vi(1)−

= vi(1)−(0+vi −b∗)

= b∗.

Alternatively, by integrating along the y-axis (i.e., R f (b) f −1 (y)dy),2

f (a)

bidder i’s payment can be expressed as follows: for ε ∈ (0, 1),

2 As the allocation function, call it f , is not invertible, but is weakly

increasing and right continuous, we define f(−1)(y) = inf{x | f(x) ≥ y}: e.g., f−1(1/2) = b∗.

Z vi ?dx (z,v )? pi(vi,v−i) = z i −i dz

Z ε Z 1−ε ?dxi(z,v−i)? = z(0)dz+ z

Z vi ? 0dz+ ∗ 1dz

0b

homework 3: myerson’s lemma 2

0 dz

0 ε dz 1−ε Z1−ε ∗

= bdy ε

∗ Z 1−ε =b dy ε

= b∗,

because the inverse of the allocation function is b∗, for all y ∈ (0, 1),

and limε→0 R 1−ε dy = 1. Intuitively, we can conclude the following ε

from this derivation: pi(vi, v−i) = b∗ · [jump in xi(·, v−i) at b∗]. Suppose that the allocation rule is piecewise constant on the con-

tinuous interval [0, vi], and discontinuous at points {z1, z2, . . . , zl} in this interval. That is, there are l points at which the allocation jumps from x(zj, v−i) to x(zj+1, v−i) (see Figure 1). Assuming this “jumpy” allocation rule is weakly increasing in value, prove that Myerson’s payment rule can be expressed as follows:

l

pi(vi, v−i) = ∑ zj · ?jump in xi(·, v−i) at zj? . (2) j=1

3 Sponsored Search Extension

In this problem, we generalize our model of sponsored search to include an additional quality parameter βi > 0 that characterizes each bidder i. With this additional parameter, we can view αj as the probability a user views an ad, and βi as the conditional probability that a user then clicks, given that they are already viewing the ad. Note that αj, the view probability, depends only on the slot j, not

Z 1

dz+ z(0)dz

xi(z3, v−i) xi(z2, v−i) xi(z1, v−i)

Figure 1: Allocation Rule. Shaded area represents payment.

z1z2 z3 Value, vi

on the advertiser occupying that slot, while βi, the conditional click probablity, explicitly depends on the advertiser i.

In this model, given bids v, bidder i’s utility is given by: ui(v) = βivix(v) − p(v)

So if bidder i is allocated slot j, their utility is: ui(v) = βiviαj − p(v)

Like click probabilities, you should assume qualities are public, not private, information.

1.

2.

4

optimization. The problem can be stated as follows:

There is a knapsack, which can hold a maximum weight of W ≥ 0. There are n items; each item i has weight wi ≤ W and value vi ≥ 0. The goal is to find a subset of items of maximal total value with total weight no more than W.

Written as an integer linear program,

n

max ∑ xivi

x i=1

Define total welfare for this model of sponsored search, and then describe an allocation rule that maximizes total welfare, given the bidders’ reports. Justify your answer.

Argue that your allocation rule is monotonic, and use Myerson’s characterization lemma to produce a payment rule that yields a DSIC mechanism for this sponsored search setting.

The Knapsack Auction

The knapsack problem is a famous NP-hard3 problem in combinatorial

3 There are no known polynomial-time solutions.

homework 3: myerson’s lemma 3

Allocation, xi(vi, v−i)

subject to

n

∑xiwi ≤W i=1

xi∈{0,1}, ∀i∈[n]

The key difference between optimization and mechanism design problems is that in mechanism design problems the constants (e.g., vi and wi) are not assumed to be known to the center / optimizer; on the contrary, they must be elicted, after which the optimization problem can then be solved as usual.

With this understanding in mind, we can frame the knapsack problem as a mechanism design problem as follows. Each bidder

has an item that they would like to put in the knapsack. Each item is characterized by two parameters—a public weight wi and a private value vi. An auction takes place, in which bidders report their values. The auctioneer then puts some of the items in the knapsack, and the bidders whose items are selected pay for this privilege. One real- world application of a knapsack auction is the selling of commercial snippets in a 5-minute ad break (e.g., during the Superbowl).4

Since the problem is NP-hard, we are unlikely to find a polynomial- time welfare-maximizing solution. Instead, we will produce a polynomial- time, DSIC mechanism that is a 2-approximation of the optimal wel-

fare. In particular, for any set possible set of values and weights, we

aim to always achieve at least 50% of the optimal welfare.

We propose the following greedy allocation scheme: Sort the bid- ders’ items in decreasing order by their ratios vi/wi, and then allocate items in that order until there is no room left in the knapsack.

1. Show that the greedy allocation scheme is not a 2-approximation by producing a counterexample where it fails to achieve 50% of the optimal welfare.

Alice proposes a small improvement to the greedy allocation scheme. Her improved allocation scheme compares the welfare achieved by the greedy allocation scheme to the welfare achieved

by simply putting the single item of highest value into the knapsack.5 She then uses whichever of the two approaches achieves greater wel- fare. It can be shown that this scheme yields a 2-approximation of optimal welfare. We will use it to create a mechanism that satisfies individual rationality and incentive compatibility.

2. Argue that Alice’s allocation scheme is monotone.

3. Now use Myerson’s payment formula to produce payments such that the resulting mechanism is DSIC and IR.

4 Here, the weight of a commercial is its time in seconds.

homework 3: myerson’s lemma 4

5 Note that weakly greater welfare could be achieved by greedily filling the knapsack with items in decreasing order of value until no more items

fit. We do not consider this scheme, because it is unnecessary to achieve

a 2-approximation; however, it is an obvious heuristic that anyone solving this problem in the real world would of course implement.