We propose a new architecture to approximately learn incentive compatible, revenuemaximizing auctions from sampled valuations. Our architecture uses the Sinkhorn algorithm to perform a differentiable bipartite matching which allows the network to learn strategyproof revenuemaximizing mechanisms in settings not learnable by the previous RegretNet architecture. In particular, our architecture is able to learn mechanisms in settings without free disposal where each bidder must be allocated exactly some number of items. In experiments, we show our approach successfully recovers multiple known optimal mechanisms and highrevenue, lowregret mechanisms in larger settings where the optimal mechanism is unknown.
more »
« less
The menucomplexity of ``oneandahalf'' dimensional mechanism design
We study the menu complexity of optimal and approximatelyoptimal auctions in the context of the ``FedEx'' problem, a socalled ``oneandahalfdimensional'' setting where a single bidder has both a value and a deadline for receiving an item [FGKK 16]. The menu complexity of an auction is equal to the number of distinct (allocation, price) pairs that a bidder might receive [HN 13]. We show the following when the bidder has $n$ possible deadlines:
1) Exponential menu complexity is necessary to be exactly optimal: There exist instances where the optimal mechanism has menu complexity $\geq 2^n1$. This matches exactly the upper bound provided by Fiat et al.'s algorithm, and resolves one of their open questions [FGKK 16].
2) Fully polynomial menu complexity is necessary and sufficient for approximation: For all instances, there exists a mechanism guaranteeing a multiplicative $(1\epsilon)$approximation to the optimal revenue with menu complexity $O(n^{3/2}\sqrt{\frac{\min\{n/\epsilon,\ln(v_{\max})\}}{\epsilon}}) = O(n^2/\epsilon)$, where $v_{\max}$ denotes the largest value in the support of integral distributions.
\item There exist instances where any mechanism guaranteeing a multiplicative $(1O(1/n^2))$approximation to the optimal revenue requires menu complexity $\Omega(n^2)$.
Our main technique is the polygon approximation of concave functions [Rote 91], and our results here should be of independent interest. We further show how our techniques can be used to resolve an open question of [DW 17] on the menu complexity of optimal auctions for a budgetconstrained buyer.
more »
« less
 Award ID(s):
 1717899
 NSFPAR ID:
 10069454
 Date Published:
 Journal Name:
 Symposium on Discrete Algorithms
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)We identify the first static credible mechanism for multiitem additive auctions that achieves a constant factor of the optimal revenue. This is one instance of a more general framework for designing twopart tariff auctions, adapting the duality framework of Cai et al [CDW16]. Given a (not necessarily incentive compatible) auction format A satisfying certain technical conditions, our framework augments the auction with a personalized entry fee for each bidder, which must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. Our framework can be used with many common auction formats, such as simultaneous firstprice, simultaneous secondprice, and simultaneous allpay auctions. If allpay auctions are used, we prove that the resulting mechanism is credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. If secondprice auctions are used, we obtain a truthful O(1)approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques. Our results for first price and allpay are the first revenue guarantees of nontruthful mechanisms in multidimensional environments; an open question in the literature [RST17].more » « less

We study the revenue guarantees and approximability of item pricing. Recent work shows that with n heterogeneous items, itempricing guarantees an O(logn) approximation to the optimal revenue achievable by any (buymany) mechanism, even when buyers have arbitrarily combinatorial valuations. However, finding good item prices is challenging – it is known that even under unitdemand valuations, it is NPhard to find item prices that approximate the revenue of the optimal item pricing better than O(√n). Our work provides a more finegrained analysis of the revenue guarantees and computational complexity in terms of the number of item “categories” which may be significantly fewer than n. We assume the items are partitioned in k categories so that items within a category are totallyordered and a buyer’s value for a bundle depends only on the best item contained from every category. We show that itempricing guarantees an O(logk) approximation to the optimal (buymany) revenue and provide a PTAS for computing the optimal itempricing when k is constant. We also provide a matching lower bound showing that the problem is (strongly) NPhard even when k=1. Our results naturally extend to the case where items are only partially ordered, in which case the revenue guarantees and computational complexity depend on the width of the partial ordering, i.e. the largest set for which no two items are comparable.more » « less

null (Ed.)We characterize revenue maximizing mechanisms in a common value environment where the value of the object is equal to the highest of the bidders' independent signals. If the revenue maximizing solution is to sell the object with probability 1, then an optimal mechanism is simply a posted price, namely, the highest price such that every type of every bidder is willing to buy the object. If the object is optimally sold with probability less than 1, then optimal mechanisms skew the allocation toward bidders with lower signals. The resulting allocation induces a “winner's blessing,” whereby the expected value conditional on winning is higher than the unconditional expectation. By contrast, standard auctions that allocate to the bidder with the highest signal (e.g., the first‐price, second‐price, or English auctions) deliver lower revenue because of the winner's curse generated by the allocation. Our qualitative results extend to more general common value environments with a strong winner's curse.more » « less

We provide algorithms that learn simple auctions whose revenue is approximately optimal in multiitem multibidder settings, for a wide range of valuations including unitdemand, additive, constrained additive, XOS, and subadditive. We obtain our learning results in two settings. The first is the commonly studied setting where sample access to the bidders' distributions over valuations is given, for both regular distributions and arbitrary distributions with bounded support. Our algorithms require polynomially many samples in the number of items and bidders. The second is a more general maxmin learning setting that we introduce, where we are given "approximate distributions," and we seek to compute an auction whose revenue is approximately optimal simultaneously for all "true distributions" that are close to the given ones. These results are more general in that they imply the samplebased results, and are also applicable in settings where we have no sample access to the underlying distributions but have estimated them indirectly via market research or by observation of previously run, potentially nontruthful auctions. Our results hold for valuation distributions satisfying the standard (and necessary) independenceacrossitems property. They also generalize and improve upon recent works, which have provided algorithms that learn approximately optimal auctions in more restricted settings with additive, subadditive and unitdemand valuations using sample access to distributions. We generalize these results to the complete unitdemand, additive, and XOS setting, to i.i.d. subadditive bidders, and to the maxmin setting. Our results are enabled by new uniform convergence bounds for hypotheses classes under product measures. Our bounds result in exponential savings in sample complexity compared to bounds derived by bounding the VC dimension, and are of independent interest.more » « less