Learning on a Budget: Posted Price Mechanisms for Online Procurement
Abstract
We study online procurement markets where agents arrive in a sequential order and a mechanism must
make an irrevocable decision whether or not to procure the service as the agent arrives. Our mechanisms
are subject to a budget constraint and are designed for stochastic settings in which the bidders are either
identically distributed or, more generally, permuted in random order. Thus, the problems we study contribute
to the literature on budget-feasible mechanisms as well as the literature on secretary problems and online
learning in auctions.
Our main positive results are as follows. We present a constant-competitive posted price mechanism when
agents are identically distributed and the buyer has a symmetric submodular utility function. For nonsymmetric submodular utilities, under the random ordering assumption we give a posted price mechanism that
is O(log n)-competitive and a truthful mechanism that is O(1)-competitive but uses bidding rather than
posted pricing