Learning Revenue-Maximizing Auctions With Differentiable Matching

Here we define common bidder demand constraints which are used in the experiments.

The value of a bundle of goods for a unit-demand bidder is equal to the maximum value of a single item in the bundle: $v_{i}(S)=\max_{j\in S}v_{i}(j)$. In this sort of auction, there is no need to consider allocations of more than one item to each bidder since those provide that same utility as only allocating the most desirable item within that bundle to that bidder. Thus, by restricting allocations to allocate at most one item per bidder, we can again treat bidder utility as quasilinear. More generally, there can be $k$-unit-demand auctions where a bidder’s value of a bundle of goods is the sum of the top $k$ items in the bundle [56].

We also consider exactly-one demand, where each bidder must be assigned exactly one item. In this setting, the bidder cannot be assigned more or fewer than one item and receives the value of the assigned item. Additionally, this demand-type can be extended to a more general exactly-$k$ demand setting where each bidder must be allocated $k$ items.

In all these settings, in general allocations might be randomized so that bidders can receive items with different probabilities. This corresponds to allowing fractional allocations, so that in the unit-demand and exactly-one-demand settings, the one item the bidder receives can be a mixture of fractions of multiple items.

The RegretNet architecture consists of two neural networks, the allocation network (denote it $g$) which outputs a matrix representing the allocation of each item to each agent and payment network (denote it $p$) which outputs the payments for each bidder [14].

RegretNet guarantees individual rationality by making the payment network use a sigmoid activation, outputting a value $\tilde{p}\in[0,1]$. The final payment is then $\left(\sum_{j}v_{ij}g_{ij}\right)\tilde{p}$, ensuring that the utility of each bidder is non-negative.

[14] present network architectures to learn under additive, unit-demand and combinatorial valuations. Their architecture utilizes a traditional feed-forward neural network with modifications in the output layer to ensure a valid allocation matrix. In the additive setting, the allocation probabilities for each item must be at most one: this is enforced by taking a row-wise softmax on the network outputs. For unit-demand auctions, each bidder wants at most one item, so the network takes a row-wise softmax of one matrix and a column-wise softmax of another to ensure item allocation is less than one. The final output is then the elementwise min of these two, ensuring that both item allocation and unit-demand constraints are enforced.

For training, the RegretNet architecture uses gradient descent on an augmented Lagrangian which includes terms to maximize payment while also containing terms to enforce the constraint that regret should be zero:

Here $\widehat{\operatorname{rgt}}_{i}$ denotes an empirical estimate of regret produced by running gradient ascent on player $i$’s portion of the network input to maximize their utility, computing their possible benefit from strategically lying. During training, the Lagrange multipliers $\lambda$ are gradually maximized, incentivizing the minimization of regret.

For marginal vectors $\bm{a}$ and $\bm{b}$ – here representing constraints for agents and items respectively, each with a dummy component that represents no item or no agent – the optimal transport problem is as follows.

By specifying $\bm{a}$ and $\bm{b}$, we can specify the demand constraints of the problem:

• •

  $k$-demand: $\bm{a}_{i}=k$, $\bm{a}_{n+1}=m$, $\bm{b}_{j}=1$, $\bm{b}_{m+1}=kn$

• •

  exactly-$k$-demand: $\bm{a}_{i}=k$, $\bm{a}_{n+1}=m-kn$, $\bm{b}_{j}=1$, $\bm{b}_{m+1}=0$

Here the $n+1$ and $m+1$ values of the marginals represent the dummy agent and item respectively. More complex constraints, such as different $k$ for different agents, can also be accommodated. Also, note in the exactly-$k$-demand settings there must be at least $kn$ items, so $m\geq kn$. An optimal solution to the matching LP will always be a permutation matrix [6], or more generally on one of the extreme points of the constraint set.

The problem in Equation 2 can be solved as a linear program. However, [11] observed that by adding an entropy penalty to the problem, it can be solved in a practical and scalable way using the matrix-scaling Sinkhorn algorithm. The new objective of the problem is

Given marginals and a cost matrix, [11] provides an iterative algorithm to solve this problem. It can be implemented in a variety of ways; we use the following stabilized log-domain updates [42]:

where $\bm{P}_{i,j}=e^{\bm{f}_{i}/\epsilon}e^{-C_{ij}/\epsilon}e^{\bm{g}_{j}/\epsilon}$. In addition to enabling the use of the iterative algorithm, the regularization term makes the problem strongly convex. Thus, the derivative of the optimal solution with respect to the cost matrix is well-defined. To approximate this derivative, we choose to unroll several iterations of the Sinkhorn updates (which consist only of differentiable operations) and use automatic differentiation.

The $\epsilon$ parameter controls the strength of the regularization. If it is large the output $\bm{P}$ will be nearly uniform; as it goes to zero we recover the original problem and $\bm{P}$ will be a permutation matrix. For our purposes, we set $\epsilon$ large enough to avoid vanishing gradients, but small enough that the output allocations are still nearly permutation matrices.

Our architecture, like RegretNet, uses a pair of networks to compute allocations and payments. We denote the allocation and payment networks $g^{w}$ and $p^{w}$ respectively, where $w$ are the network weights.

The main distinction from RegretNet is in the allocation mechanism. Like RegretNet we utilize a traditional feedforward neural network that takes all given bids as input. We use the output of the network as the cost matrix $\bm{C}_{ij}$ to the Sinkhorn algorithm (if there are dummy agents or items, they receive cost 0). Marginals are specified separately depending on the problem setting.

Finally, the output of the Sinkhorn algorithm (after truncating the row and column for dummy variables) provides the final probabilities $g^{w}_{ij}$ of allocating item $j$ to bidder $i$.

As in RegretNet, the final payment for bidder $i$ is $\left(\sum_{j}v_{ij}g_{ij}\right)\tilde{p}^{w}_{i}$ where $\tilde{p}^{w}_{i}\in[0,1]$ is the $i$th output from a feedforward payment network. This ensures that the mechanism is individually rational as the bidders will never be charged more than their utility gained from the allocated items.

RegretNet provides three different architectures depending on bidder demand type and valuation functions. For its unit-demand and combinatorial architectures, it employs a “min-of-softmax” approach to ensure both that agents receive at most 1 item or bundle, and items are not overallocated.

We particularly emphasize the case of exactly-$k$ demand, which describes the situation where the auction designer is obligated to ensure that every participant receives $k$ items, no matter what they bid. This captures, for instance, an offline version of the classic Display Ads setting [17], without free disposal, where every ad buyer is contractually guaranteed a certain number of ad slots. For multiple agents and multiple items, RegretNet cannot represent this demand type via the min-of-softmax approach.

(In some special cases, ad-hoc changes could be made to the original RegretNet architecture to support settings beyond additive and unit-demand. For example, to enforce “at-most-$k$” demand, one can just scale the unit-demand outputs by a factor of $k$. In the special single-agent case, it is possible to produce exactly-$k$ demand by removing the dummy item which allows for the possibility of allocating no item.)

By contrast, in multi-agent settings with exactly-$k$ demand, the Sinkhorn-based architecture can ensure feasible outputs by simply specifying the correct marginals. Our network architecture is also independent of the demand type since only the marginals change rather than the entire network output structure.

Like RegretNet, our training objective is Equation 1. For each batch we estimate the empirical regret, $\widehat{\operatorname{rgt}}_{i}(w)$ by performing gradient ascent for each bidder on the network inputs, approximating a misreport for each bidder.

In our experiments, the network for both the payment and allocation network had 2 hidden layers of 128 nodes with Tanh activation functions, optimized using the Adam optimizer [28] with a learning rate of $10^{-3}$. The training set consisted of $2^{19}=524,288$ valuation profiles. We used batch sizes of 4,096 and ran a total of 100 epochs. For each batch, we computed the best misreport using $25$ loops of gradient ascent with a learning rate $0.1$. We also incremented $\rho$ every two batches and and updated the Lagrange multipliers, $\lambda$, every 100 batches. Experiments were all run on single 2080Ti GPUs, on either a compute node or workstation with 32GB RAM, using PyTorch [39].

For evaluation, we used 1,000 testing examples and optimized the misreports of these examples for 1,000 iterations with learning rate $0.1$. For each of the 1,000 samples we use ten random initialization points for the misreport optimization and use the maximum regret from these. At both train and test time we used the Sinkhorn algorithm with an $\epsilon$ parameter of $0.05$, and a stopping criterion of a relative tolerance of $0.01$. Additionally we used an $\epsilon$ schedule (as suggested by [47, 12]) of 10 steps from $1$ down to the final value of $0.05$. Pseudocode for computing the allocation network output is given in algorithm 1.

We start by recovering two known optimal mechanisms in the single bidder case. We emphasize that if the only goal were to learn single-agent auctions, architectures such as RochetNet [14] or that of [48] would work better. Our architecture works for both single-agent and multi-agent auctions. Following previous work [14, 44, 43], we use these single-agent experiments as a test case to make sure it recovers some known optimal mechanisms, before continuing on to multi-agent settings where optimal auctions are not known and where RochetNet or [48] cannot work.

We now experiment in settings where the optimal strategyproof mechanism is unknown. Specifically, we study 2 bidders and either 3 or 15 items where valuations for each item are drawn from $U[0,1]$. A typical analytic baseline is a separate Myerson auction for each item, but this only works in additive settings. Instead, as a baseline, we compute the revenue from an [51, 7, 24]. The VCG auction is strategyproof, and maximizes welfare rather than revenue. It works by charging each bidder the harm they cause to other bidders, which in the settings we test may be very small or even close to zero. Table 2 contains the revenues for both mechanism (unsurprisingly higher for the learned auction) as well as the average observed regret on the testing sample, while figures 3(a) and 3(b) show training plots for the two agent, 3 item, exactly-one demand case.

RegretNet is capable of representing unit-demand auctions, but not the exactly-one setting. We compare performance to it in this case; results are shown in Table 2. (Runtimes are significantly faster than those reported in [14] likely due to our much larger batch sizes.) For the one-agent, two item setting, both architectures approximate the optimal mechanism so performance is similar. Performance is also similar for the 2 agent, 3 item setting. In the 15-item setting, revenue with the Sinkhorn architecture is somewhat smaller. In all cases the computational cost of RegretNet is significantly lower, as it requires only two softmax operations instead of many iterations of the Sinkhorn algorithm.