CSCI 1440/2440 Introduction to Game Theory - Homework 3: Myerson’s Lemma - Welfare Maximization
Homework 3: Myerson’s Lemma
CSCI1440/2440
2022-02-10
Due Date: Tuesday, February 22, 2022. 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 Bayesian Constraints
Rather than insisting that incentive compatibility and individual rationality hold always, suppose we relax these requirements and ask only that these properties hold in expectation.
Define the interim allocation and interim payment functions, respectively, as follows:
xˆ(v)= E [x(v,v )], ∀i∈N,∀v∈T, (1)
pˆ(v)= E [p(v,v )], ∀i∈N,∀v ∈T. (2)
Further, define Bayesian incentive compatibility (BIC) to mean that bidding truthfully is, in expectation, utility maximizing:
vxˆ (v)−pˆ(v)≥vxˆ (t)−pˆ(t), ∀i∈N,∀v,t ∈T. (3)
Likewise, define interim individual rationaltiy (IIR) to mean that bidding truthfully, in expectation, leads to non-negative utility:
vxˆ(v)−pˆ(v)≥0, ∀i∈N,∀v,t ∈T. (4)
Myerson’s lemma also holds in the interim case, so a mechanism satisfies BIC and IIR iff
1. Interim allocations are monotone non-decreasing:
xˆ(v)≥xˆ(t), ∀i∈N,∀v ≥t ∈T. (5)
2. Payments take the following form:
pˆ(v)=vxˆ (v)− xˆ (z)dz, ∀i∈N,∀v ≥t ∈T. (6)
Suppose that we are designing a mechanism to auction off one item in a sealed-bid format, just like in first- and second-price auc- tions. The value vi of bidder i ∈ N, is a sample from distribution Fi, i.e., vi ∼ Fi, ∀i ∈ N, with all n values drawn independently.
- The interim allocation xˆ (v ) at v is the probability of winning iii
with value vi (assuming truthful bidding on the part of the others). Simplify the interim allocation function, and explain its meaning in words.
- Calculate the interim allocation function xˆ (v ), assuming two bid- ii
ders, each of whom draws their values from a U(0, 1) distribution. Show your work.
- What is the (closed-form) interim payment formula pˆ (v ) when ii
there are two bidders, each drawing their values from a U(0, 1) distribution? And what is the total expected interim revenue? Show your work.
- Extra Credit: Given n bidders, each drawing value from a U(0, 1) distribution, what are the interim allocations and payments, and what is the total expected interim revenue. Show your work.
2 Allocation Rule Discontinuity
Fix a bidder i and a profile v−i. Myerson’s lemma tells us that incentive 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:
pi(vi,v−i) = vixi(vi,v−i)− xi(z,v−i)dz, ∀i ∈ N,∀vi ∈ Ti,∀v−i ∈ T−i. (7)
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):
Observe that ties are broken in favor of bidder i.
homework 3: myerson’s lemma 2
Given this allocation rule, the payment formula tells us what i should pay, should they be fortunate enough to win:
pi(vi,v−i) = vixi(vi,v−i)− xi(z,v−i)dz
=vi(1)−
= vi(1)−(0+vi −b∗)
=b.
Alternatively, by integrating along the y-axis (i.e., f (b) f −1 (y)dy),2 bidder i’s payment can be expressed as follows: for ε ∈ (0, 1),
pi(vi,v−i)= z(0)dz+ z f (a) vi 0dz+ ∗ 1dz ε 1−ε dxi(z,v−i)0 ε dz 1−ε 1−ε ∗
= bdy ε ∗ ? 1−ε =b dy ε
= b∗,
because the inverse of the allocation function is b∗, for all y ∈ (0, 1), and limε→0 ? 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 continuous 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:
p(v,v )= z · jumpinx(·,v )atz . (8) ii−i∑j i−ij
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 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. 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.
2. 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.
4 The Knapsack Auction
The knapsack problem is a famous NP-hard3 problem in combinatorial 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,
max ∑ xivi
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 realworld application of a knapsack auction is the selling of commercial
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 welfare. 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. snippets in a 5-minute ad break (e.g., during the Superbowl).
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. 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.
