More Like this

1. Learning Multi-Item Auctions with (or without) Samples

   Daskalakis, Constantinos; Cai, Yang (January 2017, 58th IEEE Symposium on Foundations of Computer Science (FOCS))

   We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item multi-bidder settings, for a wide range of valuations including unit-demand, 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 max-min 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 sample-based 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 non-truthful auctions. Our results hold for valuation distributions satisfying the standard (and necessary) independence-across-items 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 unit-demand valuations using sample access to distributions. We generalize these results to the complete unit-demand, additive, and XOS setting, to i.i.d. subadditive bidders, and to the max-min 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
2. Streaming Weak Submodularity: Interpreting Neural Networks on the Fly

   Elenberg, E; Dimakis, A.G.; Feldman, M; Karbasi, A. (December 2017, Nips)

   In many machine learning applications, it is important to explain the predictions of a black-box classifier. For example, why does a deep neural network assign an image to a particular class? We cast interpretability of black-box classifiers as a combinatorial maximization problem and propose an efficient streaming algorithm to solve it subject to cardinality constraints. By extending ideas from Badanidiyuru et al. [2014], we provide a constant factor approximation guarantee for our algorithm in the case of random stream order and a weakly submodular objective function. This is the first such theoretical guarantee for this general class of functions, and we also show that no such algorithm exists for a worst case stream order. Our algorithm obtains similar explanations of Inception V3 predictions 10 times faster than the state-of-the-art LIME framework of Ribeiro et al. 

   more » « less
3. An Efficient epsilon-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization

   Cai, Yang; Oikonomou, Argyris; Velegkas, Grigoris; Zhao, Mingfei (January 2021, ACM-SIAM Symposium on Discrete Algorithms (SODA21))

   We consider the black-box reduction from multi-dimensional revenue maximization to virtual welfare maximization. Cai et al. [12, 13, 14, 15] show a polynomial-time approximation-preserving re-duction, however, the mechanism produced by their reduction is only approximately Bayesian incentive compatible (ε-BIC). We provide two new polynomial time transformations that convert anyε-BICmechanism to an exactly BIC mechanism with only a negligible revenue loss. (i) Our first transformation applies to any mechanism design setting with downward-closed outcome space and only requires sample accessto the agents’ type distributions. (ii) Our second transformation applies to the fully general outcome space, removing the downward-closed assumption, but requires full access to the agents’ type distributions. Both transformations only require query access to the originalε-BIC mechanism. Otherε-BIC to BICtransformations for revenue exist in the literature but all require exponential time to run in either of the settings we consider. As an application of our transformations, we improve the reduction by Cai et al. to generate an exactly BIC mechanism. 

   more » « less
4. An Approximation Algorithm for Network Revenue Management Under Nonstationary Arrivals

   https://doi.org/10.1287/opre.2019.1931  

   Ma, Yuhang; Rusmevichientong, Paat; Sumida, Mika; Topaloglu, Huseyin (May 2020, Operations Research)

   We provide an approximation algorithm for network revenue management problems. In our approximation algorithm, we construct an approximate policy using value function approximations that are expressed as linear combinations of basis functions. We use a backward recursion to compute the coefficients of the basis functions in the linear combinations. If each product uses at most L resources, then the total expected revenue obtained by our approximate policy is at least [Formula: see text] of the optimal total expected revenue. In many network revenue management settings, although the number of resources and products can become large, the number of resources used by a product remains bounded. In this case, our approximate policy provides a constant-factor performance guarantee. Our approximate policy can handle nonstationarities in the customer arrival process. To our knowledge, our approximate policy is the first approximation algorithm for network revenue management problems under nonstationary arrivals. Our approach can incorporate the customer choice behavior among the products, and allows the products to use multiple units of a resource, while still maintaining the performance guarantee. In our computational experiments, we demonstrate that our approximate policy performs quite well, providing total expected revenues that are substantially better than its theoretical performance guarantee. 

   more » « less
5. Simple, Credible, and Approximately-Optimal Auctions

   Daskalakis, C; Fishelson, M; Lucier, B; Syrgkanis, V; Velusamy, S (January 2020, 21st ACM Conference on Economics and Computation, EC 2020)

   null (Ed.)

   We identify the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. This is one instance of a more general framework for designing two-part 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 first-price, simultaneous second-price, and simultaneous all-pay auctions. If all-pay 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 second-price 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 all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments; an open question in the literature [RST17]. 

   more » « less