Residential Collegefalse
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 Name2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2020
Source PublicationSIGMETRICS Performance 2020 - Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems
Pages11-12
Conference Date08-12 June 2020
Conference PlaceBoston MA USA
CountryUSA
PublisherASSOC 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.

DOI10.1145/3393691.3394201
URLView the original
Indexed ByESCI
Language英語English
WOS Research AreaComputer Science
WOS SubjectComputer Science, Hardware & Architecture ; Computer Science, Information Systems
WOS IDWOS:000834019400004
Scopus ID2-s2.0-85086999875
Fulltext Access
Citation statistics
Document TypeConference paper
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Corresponding AuthorTan Xiaoqi
Affiliation1.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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Tan Xiaoqi]'s Articles
[Sun Bo]'s Articles
[Leon-Garcia Alberto]'s Articles
Baidu academic
Similar articles in Baidu academic
[Tan Xiaoqi]'s Articles
[Sun Bo]'s Articles
[Leon-Garcia Alberto]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Tan Xiaoqi]'s Articles
[Sun Bo]'s Articles
[Leon-Garcia Alberto]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.