 NSFPAR ID:
 10240303
 Date Published:
 Journal Name:
 Proceedings of the ACM on Measurement and Analysis of Computing Systems
 Volume:
 4
 Issue:
 1
 ISSN:
 24761249
 Page Range / eLocation ID:
 1 to 23
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Large fractions of online advertisements are sold via repeated secondprice auctions. In these auctions, the reserve price is the main tool for the auctioneer to boost revenues. In this work, we investigate the following question: how can the auctioneer optimize reserve prices by learning from the previous bids while accounting for the longterm incentives and strategic behavior of the bidders? To this end, we consider a seller who repeatedly sells ex ante identical items via a secondprice auction. Buyers’ valuations for each item are drawn independently and identically from a distribution F that is unknown to the seller. We find that if the seller attempts to dynamically update a common reserve price based on the bidding history, this creates an incentive for buyers to shade their bids, which can hurt revenue. When there is more than one buyer, incentive compatibility can be restored by using personalized reserve prices, where the personal reserve price for each buyer is set using the historical bids of other buyers. Such a mechanism asymptotically achieves the expected revenue obtained under the static Myerson optimal auction for F. Further, if valuation distributions differ across bidders, the loss relative to the Myerson benchmark is only quadratic in the size of such differences. We extend our results to a contextual setting where the valuations of the buyers depend on observed features of the items. When upfront fees are permitted, we show how the seller can determine such payments based on the bids of others to obtain an approximately incentivecompatible mechanism that extracts nearly all the surplus.more » « less

Vidick, T. (Ed.)We study auctions for carbon licenses, a policy tool used to control the social cost of pollution. Each identical license grants the right to produce a unit of pollution. Each buyer (i.e., firm that pollutes during the manufacturing process) enjoys a decreasing marginal value for licenses, but society suffers an increasing marginal cost for each license distributed. The seller (i.e., the government) can choose a number of licenses to put up for auction, and wishes to maximize the societal welfare: the total economic value of the buyers minus the social cost. Motivated by emission license markets deployed in practice, we focus on uniform price auctions with a price floor and/or price ceiling. The seller has distributional information about the market, and their goal is to tune the auction parameters to maximize expected welfare. The target benchmark is the maximum expected welfare achievable by any such auction under truthtelling behavior. Unfortunately, the uniform price auction is not truthful, and strategic behavior can significantly reduce (even below zero) the welfare of a given auction configuration. We describe a subclass of “safeprice” auctions for which the welfare at any BayesNash equilibrium will approximate the welfare under truthtelling behavior. We then show that the better of a safeprice auction, or a truthful auction that allocates licenses to only a single buyer, will approximate the target benchmark. In particular, we show how to choose a number of licenses and a price floor so that the worstcase welfare, at any equilibrium, is a constant approximation to the best achievable welfare under truthtelling after excluding the welfare contribution of a single buyer.more » « less

null (Ed.)
A twopart tariff is a pricing scheme that consists of an upfront lump sum fee and a per unit fee. Various products in the real world are sold via a menu, or list, of twopart tariffsfor example gym memberships, cell phone data plans, etc. We study learning highrevenue menus of twopart tariffs from buyer valuation data, in the setting where the mechanism designer has access to samples from the distribution over buyers' values rather than an explicit description thereof. Our algorithms have clear direct uses, and provide the missing piece for the recent generalization theory of twopart tariffs. We present a polynomial time algorithm for optimizing one twopart tariff. We also present an algorithm for optimizing a lengthL menu of twopart tariffs with run time exponential in L but polynomial in all other problem parameters. We then generalize the problem to multiple markets. We prove how many samples suffice to guarantee that a twopart tariff scheme that is feasible on the samples is also feasible on a new problem instance with high probability. We then show that computing revenuemaximizing feasible prices is hard even for buyers with additive valuations. Then, for buyers with identical valuation distributions, we present a condition that is sufficient for the twopart tariff scheme from the unsegmented setting to be optimal for the marketsegmented setting. Finally, we prove a generalization result that states how many samples suffice so that we can compute the unsegmented solution on the samples and still be guaranteed that we get a nearoptimal solution for the marketsegmented setting with high probability.

Considerable work has focused on optimal stopping problems where random IID offers arrive sequentially for a single available resource which is controlled by the decisionmaker. After viewing the realization of the offer, the decisionmaker irrevocably rejects it, or accepts it, collecting the reward and ending the game. We consider an important extension of this model to a dynamic setting where the resource is "renewable'' (a rental, a work assignment, or a temporary position) and can be allocated again after a delay period d. In the case where the reward distribution is known a priori, we design an (asymptotically optimal) 1/2competitive Prophet Inequality, namely, a policy that collects in expectation at least half of the expected reward collected by a prophet who a priori knows all the realizations. This policy has a particularly simple characterization as a thresholding rule which depends on the reward distribution and the blocking period d, and arises naturally from an LPrelaxation of the prophet's optimal solution. Moreover, it gives the key for extending to the case of unknown distributions; here, we construct a dynamic threshold rule using the reward samples collected when the resource is not blocked. We provide a regret guarantee for our algorithm against the best policy in hindsight, and prove a complementing minimax lower bound on the best achievable regret, establishing that our policy achieves, up to polylogarithmic factors, the best possible regret in this setting.more » « less

We study gains from trade in multidimensional twosided markets. Specifically, we focus on a setting with n heterogeneous items, where each item is owned by a different seller i, and there is a constrainedadditive buyer with feasibility constraint ℱ. Multidimensional settings in onesided markets, e.g. where a seller owns multiple heterogeneous items but also is the mechanism designer, are wellunderstood. In addition, singledimensional settings in twosided markets, e.g. where a buyer and seller each seek or own a single item, are also wellunderstood. Multidimensional twosided markets, however, encapsulate the major challenges of both lines of work: optimizing the sale of heterogeneous items, ensuring incentivecompatibility among both sides of the market, and enforcing budget balance. We present, to the best of our knowledge, the first worstcase approximation guarantee for gains from trade in a multidimensional twosided market. Our first result provides an O(log(1/r))approximation to the firstbest gains from trade for a broad class of downwardclosed feasibility constraints (such as matroid, matching, knapsack, or the intersection of these). Here r is the minimum probability over all items that a buyer's value for the item exceeds the seller's cost. Our second result removes the dependence on r and provides an unconditional O(log n)approximation to the secondbest gains from trade. We extend both results for a general constrainedadditive buyer, losing another O(log n)factor enroute. The first result is achieved using a fixed posted price mechanism, and the analysis involves a novel application of the prophet inequality or a new concentration inequality. Our second result follows from a stitching lemma that allows us to upper bound the secondbest gains from trade by the firstbest gains from trade from the “likely to trade” items (items with trade probability at least 1/n) and the optimal profit from selling the “unlikely to trade” items. We can obtain an O(log n)approximation to the first term by invoking our O(log(1/r))approximation on the “likely to trade” items. We introduce a generalization of the fixed posted price mechanism—seller adjusted posted price—to obtain an O(log n)approximation to the optimal profit for the “unlikely to trade” items. Unlike fixed posted price mechanisms, not all seller adjusted posted price mechanisms are incentive compatible and budget balanced. We develop a new argument based on “allocation coupling” to show the seller adjusted posted price mechanism used in our approximation is indeed budget balanced and incentivecompatible.more » « less