DSIC Auctions Are Convex, Part I

Behind every dominant strategy incentive compatible (DSIC) auction mechanism lies a convex optimization problem.^[1] This perspective gives us––essentially for free––a simple way of constructing a large variety of DSIC auctions. In this first post, I'll define DSIC auctions and give a convex perspective on the classic second price auction. In a subsequent posts, I'll generalize this model to more types of auctions.^[2]

DSIC auctions

Let's say you're running an auction for some item.^[3] One idea: you ask everyone to bid, you give the item to the highest bidder, and they pay you their bid. This mechanism, called a first price auction, seems perfectly reasonable. Unfortunately, every participant who knows what they're doing will lie.^[4]

Take a simple example: two bidders, Alice and Bob. Alice thinks the item is worth $10. Bob thinks it's worth $1. If they both bid their valuations, Alice gets the item for $10 and makes a "profit" of $0. But, if Alice suspects Bob has a lower valuation she'll lower her bid ("bid shading," in industry lingo), increasing the profit she gets from the auction. In a first price auction, Alice needs to guess how Bob will bid. Add a few more players, hire a few econ PhDs, and this gets complicated fast.

The fix: a second-price auction. In this mechanism, the auctioneer charges the winner (Alice) the second-highest bid (Bob's). Now, no one is incentivized to lie in the auction.^[5] In other words, this auction is dominant-strategy incentive compatible: its in the bidders' best interest to be truthful. You can verify this via casework (see Claim 5.1 in Tim Roughgarden's excellent lecture notes), or read on for a proof via convex analysis.

Allocation and payment rules

In these examples, the auction functioned in the same way; the item was awarded to the highest bidder. These auctions had the same allocation rule. What differed was the payment rule: how much the winner has to pay.

In the remainder of this post, we'll construct the second-price auction allocation rule from a market-clearing mechanism defined by an optimization problem.

It's all convex optimization

Here's a (somewhat convoluted) representation of a single-item auction. Each buyer $i \in \{1, \dots, n\}$ submits a bid $b_i$ . The allocation rule is the solution $x$ to the following optimization problem:

\begin{aligned} &\text{maximize} && \sum_{i=1}^nb_ix_i \\ &\text{subject to} && x \in S = \{e_1, \dots, e_n\}, \end{aligned}

where $e_i$ is the $i$ th standard basis vector. You should quickly verify that when there is a unique highest bid, the optimal solution $x^\star(b)$ is $e_{\argmax_i b_i}$ (i.e., the item goes to the highest bidder). Additionally, the solution is unchanged if we replace $S$ with its convex hull. We can write the objective value of this optimization problem as a function of the bids:

F(b) = \sup_{x \in S} \left(\sum_{i=1}^nb_ix_i\right).

Since $F$ is a pointwise supremum over a set of convex (linear) functions of $b$ , the function $F$ is convex.

Payment rule

For the second-price auction, the payment rule for buyer $i$ is

P_i(b) = \begin{cases} \max_{j \neq i} b_j & i = \argmax_i b_i \\ 0 & \text{otherwise.} \end{cases}

In other words, the winner pays their externality. If the winner didn't participate, the second highest bidder would win this item, so the winner pays the second highest bidder's value of the item. More generally, we can define the payment rule for buyer $i$ to be

P_i(b) = F(b_{-i}) - \sum_{j \neq i} b_{j}x^\star_{j}(b),

where $b_{-i} = b - b_ie_i$ (zero in element $i$ , unchanged elsewhere). In other words, buyer $i$ pays their externality: the difference between the total "welfare" when they do not participate and the welfare of the other participants when they do.

In general, we might have to solve $n+1$ convex programs to determine payments––one for the overall allocation and one without each bidder for all $B$ bidders. The overall auction flow is below.

Proof of DSIC

Using the setup above, we can easily prove that this auction is DSIC. Let $b$ 's valuation for the item be $v_i$ . Define the truthful bid vector as $b^\mathrm{t} = b_{-i} + v_ie_i$ . Consider $b$ 's payoff under truthful bidding versus any other bidding strategy:

\underbrace{\left( v_ix^\star_i(b^\mathrm{t}) - F(b_{-i}^\mathrm{t}) + \sum_{j \neq i} b_{j}x^\star_{j}(b^\mathrm{t}) \right)}_{\text{profit under truthful bidding}} - \underbrace{\left( v_i{x}^\star_i(b) - F(b_{-i}) + \sum_{j \neq i} b_{j}{x}^\star_{j}(b) \right)}_{\text{profit under any other bidding}},

where $x^\star(b^\mathrm{t})$ and ${x}^\star(b)$ indicate the optimum under truthful and other bidding respectively. Note that $b^\mathrm{t}_{-i} = b_{-i}$ . Rearranging, we have

\begin{aligned} &v_ix^\star_{i}(b^\mathrm{t}) + \sum_{j\neq i} b_{j} x^\star_{j}(b^\mathrm{t}) - \left( v_i{x}^\star_{i}(b) + \sum_{j\neq i} b_{j}{x}^\star_{j}(b) + b_i{x}^\star_{i}(b) - b_i {x}^\star_{i}(b)\right) \\ &= F(b^\mathrm{t}) - F(b) - (v_i - b_i){x}^\star_{i}(b) \\ &\ge 0, \end{aligned}

where the last line follows from the first-order conditions for convexity and the fact that an allocation $x^\star(b)$ is a subgradient of $F(b)$ , i.e., $x^\star(b) \in \partial F(b)$ , illustrated below.

In other words, $i$ cannot be better off by bidding under their true value. This proof follows directly from the fact that subgradients of convex functions give underestimators.

Where to?

We just did a lot of work to prove a fairly straightforward result. Why? As a little taste of what's to come, let's consider the $k$ -item auction. We simply modify $S$ to be the set of vectors

S = \{x \in \{0,1\}^n \mid \mathrm{sum}(x) = k\}.

Everything else just carries through directly. If we work through the allocation and payment rules, we'll see that we should give items to the $k$ highest bidders for the $(k+1)$ th bid. In the next post, we'll see how to use this framework to construct more interesting DSIC auctions.

Thank you to Pranav Garimidi and Mallesh Pai for helpful comments on a draft of this post.

Footnotes

[1]	This blog has a theme.

[2]	This perspective is not new (see, for example, Mechanism Design: a Linear Programming Approach by Rakesh Vohra). That said, I don't see it discussed a lot, so I figured it's worth publicizing.

[2]	JPEGs were popular, once upon a time.

[3]	When you have lots of bidders and a liquid market, first-price auctions still work great in practice.

[4]	Well, at least none of the bidders. The auctioneer is another matter altogether.