Pricing for Online Resource Allocation: Intervals and Paths

DOI10.1137/1.9781611975482.119MaRDI QIDQ5236305zbMATH OpenOpenAlexFDO

Authors Shuchi Chawla, J. Benjamin Miller, Yifeng Teng

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.00043

zbMATH Keywords

online allocation algorithmsonline resource allocationpricing mechanisms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Microeconomic theory (price theory and economic markets) (91B24) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: We present pricing mechanisms for several online resource allocation problems which obtain tight or nearly tight approximations to social welfare. In our settings, buyers arrive online and purchase bundles of items; buyers' values for the bundles are drawn from known distributions. This problem is closely related to the so-called prophet-inequality of Krengel and Sucheston and its extensions in recent literature. Motivated by applications to cloud economics, we consider two kinds of buyer preferences. In the first, items correspond to different units of time at which a resource is available; the items are arranged in a total order and buyers desire intervals of items. The second corresponds to bandwidth allocation over a tree network; the items are edges in the network and buyers desire paths. Because buyers' preferences have complementarities in the settings we consider, recent constant-factor approximations via item prices do not apply, and indeed strong negative results are known. We develop static, anonymous bundle pricing mechanisms. For the interval preferences setting, we show that static, anonymous bundle pricings achieve a sublogarithmic competitive ratio, which is optimal (within constant factors) over the class of all online allocation algorithms, truthful or not. For the path preferences setting, we obtain a nearly-tight logarithmic competitive ratio. Both of these results exhibit an exponential improvement over item pricings for these settings. Our results extend to settings where the seller has multiple copies of each item, with the competitive ratio decreasing linearly with supply. Such a gradual tradeoff between supply and the competitive ratio for welfare was previously known only for the single item prophet inequality.

Recommendations

• Online allocation and pricing with economies of scale
• An Online Mechanism for Resource Allocation and Pricing in Clouds
• Pricing and allocation for quality-differentiated online services
• Approximation algorithms and online mechanisms for item pricing
• Online resource allocation under partially predictable demand
• Optimal pricing and capacity sizing for online service systems with free trials
• scientific article; zbMATH DE number 1981035
• Optimal online pricing with network externalities

Cited in

(10)

• Web based capacity allocation strategies for customers with heterogeneous preferences
• Approximation algorithms for the partial assignment problem
• An Online Mechanism for Resource Allocation and Pricing in Clouds
• Online allocation and pricing with economies of scale
• Market pricing for matroid rank valuations
• Prophet inequalities for independent and identically distributed random variables from an unknown distribution
• An O(\log \log m) Prophet Inequality for Subadditive Combinatorial Auctions
• A robust optimization formulation for dynamic pricing of a web service with limited total shared capacity
• scientific article; zbMATH DE number 7765397 (Why is no real title available?)
• A Dual Approach for Dynamic Pricing in Multidemand Markets

This page was built for publication: Pricing for Online Resource Allocation: Intervals and Paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236305)