DSIC Auctions Are Convex, Part II

Let's pick up where we left off in the last post. This time, instead of allocating at most one item to each bidder, we'll allocate some amount of "stuff" to them. This amount––and the associated payment––will be determined by solving an optimization problem.

Example: selling compute

Imagine you're selling compute; let's say FLOPs capacity over the next day. You have a number of machines you can rent out. Some have the latest and greatest GPUs, and some have older models. Some have NVIDIAs, and some have AMDs. Some have lots of memory, and some do not. While the machines differ, they all have the ability to multiply lots of matrices together.

You want to squeeze as many buyers onto as many machines as possible. But these buyers aren't all the same. Some only want NVIDIA GPUs. Some have minimum memory requirements. Some have location preferences. But they all ultimately receive some amount of the same thing: compute. You want to clear this market to maximize the total utility of all buyers.

In this post, we'll construct the optimization problem that clears this type of market, and a payment rule that ensures incentive compatibility. In doing so, we'll also specify a bidding language for the buyers. ^[1]

The market-clearing mechanism

Let's formalize a market for a single divisible good, where there is one seller and $n$ buyers.

Each buyer submits a utility function $u_i: \mathbf{R}_+ \to \mathbf{R}_+$ , ^[2] which maps the amount of stuff they get, $x_i$ , to their dollar value $u_i(x_i)$ . ^[3] In other words, the utility function specifies the maximum amount they're willing to pay some amount of this good. (And we don't want them to lie about their value; more on this later.) We also allow buyers to specify constraints on the type of stuff they want to buy. For example, they might say "I will only buy FLOPs from NVIDIA GPUs."

The seller can allocate any amount of the good to each buyer, subject to several constraints. Allocations must be nonnegative: $x_i \ge 0$ , and the seller cannot allocate more then they have: $\sum_{i=1}^n x_i \leq q^\mathrm{total}$ . The seller might also want to impose additional constraints, such as a maximum amount of stuff that can be allocated to any individual buyer: $x_i \le x^\mathrm{max}$ . We collect all of the constraints from the buyers and the seller in the set $S$ .

The optimization problem

The market-clearing mechanism finds a utility-maximizing allocation that satisfies all the constraints in $S$ . The optimal allocation is the solution $x^\star$ ^[4] to the optimization problem

\begin{aligned} &\text{maximize} && \sum_{i=1}^n u_i(x_i) \\ &\text{subject to} && x \in S. \end{aligned}

If the utility functions are concave and the set $S$ is convex, then this problem is a convex optimization problem. We'll write the objective value of this optimization problem as a function of the set of bids (utility functions) $u = \{u_1, \dots, u_n\}$ :

F(u) = \sup_{x \in S} \left(\sum_{i=1}^n u_i(x_i)\right).

Despite the switch to functional spaces, the setup is essentially the same as in the previous post. Our goal now is to construct a payment rule for this mechanism that encourages bidders to truthfully report their utility functions.

The payment rule

The payment rule for buyer $i$ is

P_i(u) = F(u_{-i}) - \sum_{j \neq i} u_j(x^\star_j),

where $u_{-i}$ is the set of utility functions for all buyers except $i$ and $x^\star$ is the optimal allocation for (2). Like last time, 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. We have to solve $n+1$ convex programs to determine payments––one for the allocation $x^\star$ and one for each buyer's payments.

Dominant strategy incentive compatibility

The payment rule is DSIC by a similar argument to the one in the previous post. The payoff difference is

\underbrace{\left( u_i^\mathrm{true}(x^\star_i) - F(u_{-i}) + \sum_{j \neq i} u_j(x^\star_j) \right)}_{\text{profit under truthful bidding}} - \underbrace{\left( u_i^\mathrm{true}(\tilde x^\star_i) - F(u_{-i}) + \sum_{j \neq i} u_j(\tilde x^\star_j) \right)}_{\text{profit under any other bidding}},

where $x^\star$ is the optimal allocation for (2) under truthful bidding and $\tilde x^\star$ is an optimal (and therefore feasible) allocation for (2) under any alternative bidding. This expression simplifies to

\sup_{x \in S} \left(\sum_{i=1}^n u_i(x_i)\right) - \sum_{j=1}^n u_j(\tilde x^\star_j) \ge 0.

This quantity is nonnegative because the supremum is at least as large as the objective value of any feasible allocation.

Sybil attacks

Unfortunately, this mechanism is vulnerable to sybil attacks: where a buyer submits multiple bids, under several "aliases," to gain an advantage. ^[5] Certain conditions on the auction and assumptions on the goods can prevent these attacks (see this paper for details), but these conditions may be unrealistic in practice. For example, we can't enforce a per-buyer maximum allocation in the presence of sybils. In practice, the payment rule depends more on the context. If sybils might be a problem, a market may be better off using a first-price auction (everyone pays their bid). ^[6]

Some final thoughts

In this post and the last post, we started at a second-price auction and ended up looking at more general market-clearing mechanisms for divisible goods, market-clearing mechanisms which can be modeled via continuous optimization. Divisible, semi-fungible goods appear all over the place, from collectibles to GPU FLOPs to bond yield. I'm excited to see the future of optimization-based market design. If you're interest in this type of stuff and want to read more, check out my recent paper.

Thank you to Kshitij Kulkarni for helpful comments on a draft of this post.

Footnoes

[1]	While I say "market" here, I know there's only one seller. Perhaps it's more accurate to say "a method for AWS to allocate its GPUs."

[2]	This setup resembles bidding in power markets, where buyers submit how much power they are willing to buy at a given price (i.e., a demand curve). We could have specified the problem in terms of these curves instead.

[3]	I am fairly certain that no engineer wants to actually do this. For compute, it's probably better to just dynamically adjust the prices, as in this paper. But compute markets are hot right now.

[4]	We'll assume the solution is unique for this post, but the argument works in the more general case. Check out section 4.2 of this paper for details.

[5]	Identity and reputation systems also help prevent these attacks. That said, these systems are notoriously difficult to design.

[6]	And if there are enough bidders, this mechanism will be close to a first price auction anyway.