Pricing for Online Resource Allocation: Beyond Subadditive Values
share
We consider the problem of truthful online resource allocation to maximize social welfare in a stochastic setting. Sequential posted pricing has emerged as a desirable mechanism for this problem that is at once simple, easy to implement in practice, as well as approximately optimal in several cases. In this mechanism, the seller uses his knowledge of the demand distribution to determine and announce prices for individual resources or bundles of resources. Buyers then arrive in sequence and can purchase their favorite bundles while supplies last. Previous work shows that sequential posted pricing achieves good approximations when buyers' values exhibit subadditivity. We consider settings where buyers desire bundles, that is, their values exhibit complementarities, and the seller faces a cost function for supplying the resource. We present both upper and lower bounds for the approximation factors achieved by sequential posted pricing in these settings.
READ FULL TEXT