Abstract
We study procurement auctions, where an auctioneer seeks to acquire servicesfrom strategic sellers with private costs. The quality of services is measuredby a submodular function known to the auctioneer. Our goal is to designcomputationally efficient procurement auctions that (approximately) maximizethe difference between the quality of the acquired services and the total costof the sellers, while ensuring incentive compatibility (IC), individualrationality (IR) for sellers, and non-negative surplus (NAS) for theauctioneer. Our contributions are twofold: (i) we provide an improved analysis ofexisting algorithms for non-positive submodular function maximization, and (ii)we design efficient frameworks that transform submodular optimizationalgorithms into mechanisms that are IC, IR, NAS, and approximation-preserving.These frameworks apply to both the offline setting, where all sellers' bids andservices are available simultaneously, and the online setting, where sellersarrive in an adversarial order, requiring the auctioneer to make irrevocabledecisions. We also explore whether state-of-the-art submodular optimization algorithmscan be converted into descending auctions in adversarial settings, where theschedule of descending prices is determined by an adversary. We show that asubmodular optimization algorithm satisfying bi-criteria $(1/2,1)$-approximation in welfare can be effectively adapted to a descendingauction. Additionally, we establish a connection between descending auctionsand online submodular optimization. Finally, we demonstrate the practical applications of our frameworks byinstantiating them with state-of-the-art submodular optimization algorithms andempirically comparing their welfare performance on publicly available datasetswith thousands of sellers.