Optimal Posted Prices for Online Resource Allocation with Supply Costs
Xiaoqi Tan, Alberto Leon‐Garcia, Danny H. K. Tsang · ACM SIGMETRICS Performance Evaluation Review · 2019
We study a general online resource allocation problem, where a provider sells multiple types of capacity-limited resources to heterogeneous customers that arrive in a sequential and arbitrary manner. The provider charges payment from customers who purchase a bundle of resources but must pay an increasing supply cost with respect to the total resource allocated. The goal is to maximize the social welfare, namely, the total valuation of customers for their purchased bundles, minus the total supply cost of the provider for all the resources that have been allocated. We adopt the competitive analysis framework and provide an optimal posted-pricing mechanism (PPM). Our PPM is optimal in the sense that no other online algorithms can achieve a better competitive ratio.