报告题目： Mechanism Design for Online Resource Allocation with Supply Costs and Capacity Limits: A Unified Framework

报告人: 谭小琦 博士(University of Toronto)

报告时间：2020年1月3日星期五 16:00

报告地点：信息楼D119会议室

报告摘要:

In this talk, we present our recent progress on 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 our work is the development of a unified approach that achieves the best-possible competitive ratios for setups with different supply costs. Specifically, in the talk we will 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. We validate the theoretic results via empirical studies of online resource allocation in cloud computing. Our numerical results demonstrate that the proposed pricing mechanism is competitive and robust against system uncertainties and outperforms existing benchmarks.

报告人简介：

Xiaoqi Tan is currently a postdoctoral fellow at The Edward S. Rogers Sr. Department of Electrical and Computer Engineering, University of Toronto, Ontario, Canada, hosted by Prof. Alberto Leon-Garcia (IEEE Life Fellow, Fellow of Canada Institute of Technology). Prior to the current position, he received his Ph.D. degree in electronic and computer engineering from the Hong Kong University of Science and Technology in 2018, advised by Prof. Danny H.K. Tsang (IEEE Fellow). From October 2015 to April 2016, he was a visiting research fellow with the School of Engineering and Applied Science, Harvard University, hosted by Prof. Na (Lina) Li. He received his B.Eng. degree in information and communication engineering (first class honor) from Xi’an Jiaotong University, Xi’an, China, in 2012. His research broadly lies at the intersection of mechanism design, sequential decision-making, and machine learning, with a focus on applications in networked systems including computer networks, cloud computing, smart grid, and ridesharing systems. Dr. Tan has authored/co-authored more than 30 journal and conference papers, of which 11 are IEEE Transactions papers. He is currently a member of IEEE and ACM.