The CK Auction
CSCI 1440/2440 2023-04-19
These lecture notes offer a high-level summary of two lectures from Professor Tim Roughgarden’s Frontiers in Mechanism Design (CS 364B) course, together with references to the relevant sections of his course notes for deeper coverage. The CS 364B lectures are:
• Lecture2:UnitDemandBiddersandWalrasianEquilibria • Lecture 3: The Crawford-Knoer Auction
Unit-Demand Valuations
The next two lectures pertain to the unit-demand setting, in which bidders are only interested in acquiring one good, but have prefer- ences over which good that might be. The goal of these lectures is to develop an EPIC ascending auction for this setting.
Before attempting to develop an EPIC ascending auction, there is a necessary sanity check—to confirm that there exists a polynomial- time DSIC direct mechanism, assuming unit-demand bidders, be- cause designing the former is at least as hard as designing the latter. Indeed, there exists a polynomial-time algorithm that computes the VCG outcome for the unit-demand setting.
The winner determination problem—the task of finding a welfare- maximizing allocation—can indeed be solved in polynomial time, by representing bidders and goods as a bipartite graph and solving for the maximum-weight matching. To compute VCG payments, we re- move each bidder from the graph in turn, and re-run the matching algorithm to find that bidder’s externality (Lecture 2, pp. 1–3).
Finding a maximum-weight matching in a bipartite graph, while polynomial, is still non-trivial. The question we are asking in this lecture is whether there exists a simple ascending-price auction that can recover a VCG outcome, and hence do the work of a matching algorithm (actually, O(n2) runs of a matching algorithm).
2 Crawford-Knoer (CK) Auction
The Crawford-Knoer (CK) auction1 is an ascending auction for the
unit-demand setting. The auction is formally described in Lecture 3, pp. 2–3. We reproduce the design here, for completeness:
• Initialize the price qj of all goods j to zero.
• Initialize all bidders’ assignments to ∅: i.e., at the start, no good is assigned to any of the bidders.
1 Vincent Crawford and Elsie Marie Knoer. Job matching with heteroge- neous firms and workers. Econometrica, 49(2):437–50, 1981
• Repeat forever:
– Issue demand queries to all bidders. Specifically, ask each bid- der to report one2 of her preferred goods at prices q + ε: i.e., j∈Di(q+ε)=. argmaxj{vi(j)−(qj+ε)}.
– If no unassigned bidder reports any demands (i.e., all unas- signed bidders demand ∅ at prices q + ε), then terminaute the auction with the current allocation and prices.
– Otherwise, pick an unassigned bidder i, and:
* Assign i her preferred good j.
* Mark whoever was previously assigned j as now unassigned.
* Increase the price of good j from qj to qj + ε (the price at
which i reported j to be one of her preferred goods).
By design, the CK auction, and other similar auctions, such as
the KC auction (named for Kelso and Crawford3),4 terminate at a Walrasian equilibrium (WE). A WE is an allocation and pricing such that each bidder ends up with a preferred good at the current prices (WE1); and a good is priced at 0, if it is unallocated (equivalently, if a good’s price is positive, then it is allocated; WE2).
Recall that VCG payments are an essential component of our EPIC auction design recipe. But fear not: In the unit-demand setting, any VCG outcome is a WE. Indeed, each one is a smallest WE (i.e., one with minimal WE prices), making VCG outcomes a natural contender for the outcome of an auction with ascending prices in this case!
Theorem 2.1. Assuming unit demand valuations, any vector of VCG payments corresponds to prices at a smallest WE.
This claim follows from two others. But first, observe that VCG payments, which are ordinarily associated with bidders, can just as well be associated with goods in a unit-demand setting, since each bidder is allocated at most one good. Now:
(1) VCG payments constitute WE prices (Lecture 2, Theorem 3.6).
The proof of this claim relies on Lemma 3.7, which states that the VCG price of an arbitrary good j in the unit-demand setting can be understood as the welfare gain achieved by injecting an additional copy of j into the market. If good j was allocated to bidder i, then this gain is exactly i’s VCG payment (i.e., j’s VCG price), because injecting an additional copy of good j into the market is akin to removing i from the market.
With this lemma in hand, we can argue that any VCG outcome is a WE as follows. WE2 is satisfied immediately, as VCG prices for unallocated goods are zero.
2 Note that ties are broken arbitrarily. It is remarkable that conflicts can still be resolved (i.e., an equilibrium still ensues), even with arbitrary resolution along the equilibrium path.
the ck auction 2
3 Alexander Kelso and Vincent Craw- ford. Job matching, coalition formation, and gross substitutes. Econometrica, 50(6):1483–1504, 1982
4 See Lecture 5: Gross Substitutes I.
To show WE1, assume a second copy l′ of some good l is injected in the market, and that bidder i who was allocated good j at some VCG outcome is now allocated l′. We can now reoptimize for all bidders other than i and for all goods j (although not l′, which
has been allocated to i). In this new extended market, the increase in surplus is bidder i’s value for l less bidder i’s value for j, plus bidder i’s VCG payment pj, which represents bidder i’s externality in the original market (i.e., the difference between the total welfare of all bidders other than i at an optimal allocation in the extended market without bidder i and their optimal total welfare in the original market).
By Lemma 3.7, the VCG price pl of good l is the welfare gain achieved by injecting an additional copy of l into the market. But this price is at least vi(l) − vi(j) + pj. In other words, vi(j) − pj ≥ vi(l) − pl, for all goods l other than i’s allocation, namely good j, so that WE1 is satisfied at the VCG outcome.
(2) VCG prices lower bound WE prices (Lecture 2, Theorem 3.5).
Remark 2.2. In other more general multiparameter environments, VCG payments do not necessarily correspdond to WE prices. This observation will preclude us from designing EPIC auctions for most valuations beyond unit demand.
3 The CK Auction is EPIC
Recall the EPIC auction design recipe outlined in the EPIC Ascending
Auctions lecture:
1. Design an auction whose allocation rule is welfare maximizing,
assuming sincere bidding.
2. Show that sincere bidding also yields VCG payments.
3. Assuming others bid sincerely, argue that no inconsistent bidding strategy is a profitable deviation from likewise bidding sincerely.
The following sequence of theorems uses this recipe to prove that
the CK auction is EPIC.
(1) Assuming sincere bidding, the CK auction terminates at an mε-WE (Lecture 3, Lemma 3.2). This result is straightforward, given the assumptions that bidders’ valuations are unit-demand together with the rules of the auction.
• Ifabidderiwinsagoodj,itisbecausejwas(oneof)i’spre- ferred option(s) when i bid on j. Moreover, j’s price did not
the ck auction 3
change since the time at which it was tentatively allocated to
i. But the prices of the other goods may have increased. So i can only possibly prefer j more now now than it did at the time when it bid on it, up to ε.5 Likewise, for all other bidders k ̸= i. Thus, WE1 holds.
• In the CK auction, a bidder cannot bid on a good, cause its price to increase, and then relinquish the good, leaving the price non- zero and the good unallocated. Thus, if a good is not allocated, it can only be because no one ever bid on it, in which case its price is necessarily zero. Thus, WE2 also holds.
Therefore, by a special case (Lecture 2; Proposition 3.4) of the First Fundamental Theorem of Welfare Economics, which shows that competitive markets allocate resources efficiently,6 giving support to Adam Smith’s “invisible hand” hypothesis, the CK auction terminates with an allocation that is welfare maximizing up to mε.
(2) Assuming sincere bidding, the CK auction terminates at WE prices up to δ. But then it likewise terminates at VCG prices up to δ, because they comprise a smallest WE.
As sincere bidding in the CK auction is welfare maximizing up to mε, and terminates at VCG payments up to δ, it follows that sincere bidding is an EPNE up to δ among consistent strategies (or up to mε, assuming m < n, which is usual).
(3) The final step in the proof that the CK auction is EPIC is to show that no inconsistent strategy is a profitable deviation from sincere bidding up to some additive error: i.e., no inconsistent strategy yields substantially greater utility than sincere bidding for any bidder (Lecture 3, Theorem 4.2).
The proof proceeds by showing that any deviation via an incon- sistent strategy can be replicated by a sincere one up to 2δ. Then, since sincere bidding is an EPNE up to δ among (only) consistent strategies, sincere bidding is an EPNE up to max{δ, 2δ} = 2δ among both consistent and inconsistent strategies (or up to 2mε, assuming m < n, which is usual).
The proof of this claim depends on two symmetric bounds (Lec- ture 3, Lemmas 3.4 and 3.5). The first states that the final price
of a good in the CK auction, assuming sincere bidding, is upper bounded by its VCG price plus δ = ε min{m, n}, while the second states that the price of a good in the CK auction is lower bounded by its VCG price minus δ: i.e., the final price qj of good j falls in the range [pj − δ, pj + δ], where pj is the VCG price for good j.
5 Technically, i’s preference for j does not change. But i might prefer other goods less.
6 Technically Pareto-efficiently, which is weaker than welfare maximization, but more broadly applicable, beyond the unit-demand setting.
the ck auction 4
Remark 3.1. Lemma 3.5 actually assumes something weaker than sincere bidding by all in the CK auction. Rather, it bounds ε-WE prices directly (however they might arise).
Theorem 3.2. The CK auction is EPIC up to 2δ = 2ε min{m, n}.
Proof. Assume valuations (vi,v−i), and that all bidders other than i bid sincerely. We must show that it does not benefit bidder i (very much) to bid insincerely.
If bidder i bids insincerely and does not win anything, then there was no benefit to bidding insincerely. Thus, it suffices to consider the case where bidder i wins good j.
Now consider the following valuation, vi′:
v′ =∞ k=j . ik
0 otherwise
A bidder who bids sincerely with valuation vi′ certainly wins good j, so i’s allocation in the latter setting is the same as in the former. The question, then, is whether i can do better (i.e., realize lower prices) by bidding inconsistently than it can by bidding sincerely.
The answer is no, as we now proceed to argue.
First, observe that the outcome of the CK auction is an ε-WE, assuming all other bidders bid sincerely while bidder i bids insin- cerely, and valuation profile (vi′,v−i). Bidder i wins her favorite good, namely j, since she is willing to bid up to ∞ for it. The other bidders also win their favorite goods (up to ε) at the final prices, because these goods were their preferred goods (up to ε) when they were al- located to them; their prices have not increased, since they have not been re-allocated; and the prices of other goods can only have in- creased (in case they have been re-allocated), making the allocations in question only more desirable. We have thus established WE1.
As for WE2, the only unallocated goods are those that are not bid on, but goods that are not bid on are priced at zero. Moreover, goods that are allocated, some at non-zero prices, cannot be relinquished.
We complete the argument as follows:
i’s utility at the ε-WE that arises when i bids inconsistently assuming sincere bidding by the others and valuations (vi′,v−i)
≤ i’s utility in a VCG auction assuming valuations (vi′,v−i), plus δ (1)
≤ i’s utility in a VCG auction assuming valuations (vi,v−i), plus δ (2)
≤ i’s utility at the ε-WE that arises assuming sincere bidding by all
the ck auction 5
and valuations (vi, v−i), plus 2δ (3)
Step 1 follows because bidder i’s allocation is the same in the VCG auction assuming valuation vi′ as it is when i bids inconsistently
in the CK auction. Thus, it suffices to compares prices only, when comparing i’s utility in these two settings. But any prices that arise at an ε-WE are at least VCG payments less δ (by Lemma 3.5, the lower bound, taking into account Remark 2.2).
Step 2 follows from the fact that VCG is DSIC, so it cannot benefit bidder i to bid according to vi′ rather than vi in a VCG auction.
Step 3 follows because any prices that arise as the outcome of sincere bidding in the CK auction are at most VCG payments plus δ (by Lemma 3.4, the upper bound on CK auction prices).
References
[1] Vincent Crawford and Elsie Marie Knoer. Job matching with heterogeneous firms and workers. Econometrica, 49(2):437–50, 1981.
[2] Alexander Kelso and Vincent Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50(6):1483–1504, 1982.
the ck auction 6
