Residential College | false |
Status | 已發表Published |
Mechanism Design for Online Resource Allocation: A Unified Approach | |
Tan Xiaoqi1; Sun Bo2; Leon-Garcia Alberto1; Wu Yuan3; Tsang Danny H.K.2 | |
2020-06 | |
Conference Name | 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2020 |
Source Publication | SIGMETRICS Performance 2020 - Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems |
Pages | 11-12 |
Conference Date | 08-12 June 2020 |
Conference Place | Boston MA USA |
Country | USA |
Publisher | ASSOC COMPUTING MACHINERY, 1601 Broadway, 10th Floor, NEW YORK, NY USA |
Abstract | This paper concerns the mechanism design for online resource allocation in a strategic setting. In this setting, a single supplier allocates capacity-limited resources to requests that arrive in a sequential and arbitrary manner. Each request is associated with an agent who may act selfishly to misreport the requirement and valuation of her request. The supplier charges payment from agents whose requests are satisfied, but incurs a load-dependent supply cost. The goal is to design an incentive compatible online mechanism, which determines not only the resource allocation of each request, but also the payment of each agent, so as to (approximately) maximize the social welfare (i.e., aggregate valuations minus supply cost). We study this problem under the framework of competitive analysis. The major contribution of this paper is the development of a unified approach that achieves the best-possible competitive ratios for setups with different supply costs. Specifically, we show that when there is no supply cost or the supply cost function is linear, our model is essentially a standard 0-1 knapsack problem, for which our approach achieves logarithmic competitive ratios that match the state-of-the-art (which is optimal). For the more challenging setup when the supply cost is strictly-convex, we provide online mechanisms, for the first time, that lead to the optimal competitive ratios as well. To the best of our knowledge, this is the first approach that unifies the characterization of optimal competitive ratios in online resource allocation for different setups including zero, linear and strictly-convex supply costs. |
DOI | 10.1145/3393691.3394201 |
URL | View the original |
Indexed By | ESCI |
Language | 英語English |
WOS Research Area | Computer Science |
WOS Subject | Computer Science, Hardware & Architecture ; Computer Science, Information Systems |
WOS ID | WOS:000834019400004 |
Scopus ID | 2-s2.0-85086999875 |
Fulltext Access | |
Citation statistics | |
Document Type | Conference paper |
Collection | THE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU) |
Corresponding Author | Tan Xiaoqi |
Affiliation | 1.University of Toronto, Canada 2.HKUST, Hong Kong, China 3.University of Macau, Macau, China |
Recommended Citation GB/T 7714 | Tan Xiaoqi,Sun Bo,Leon-Garcia Alberto,et al. Mechanism Design for Online Resource Allocation: A Unified Approach[C]:ASSOC COMPUTING MACHINERY, 1601 Broadway, 10th Floor, NEW YORK, NY USA, 2020, 11-12. |
APA | Tan Xiaoqi., Sun Bo., Leon-Garcia Alberto., Wu Yuan., & Tsang Danny H.K. (2020). Mechanism Design for Online Resource Allocation: A Unified Approach. SIGMETRICS Performance 2020 - Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, 11-12. |
Files in This Item: | There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment