# Procurement Auctions via Approximately Optimal Submodular Optimization

arXiv: https://arxiv.org/abs/2411.13513 · HTML: https://mlsanity.com/paper/2411.13513/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 80 references that are in the map.
- First posted on arXiv 20 Nov 2024.

## Builds on (most cited first, 6 of 6)

- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Regularized Submodular Maximization at Scale](https://mlsanity.com/paper/2002.03503/) (2020)
- [Adaptive Regularized Submodular Maximization](https://mlsanity.com/paper/2103.00384/) (2021)
- [Maximization of Approximately Submodular Functions](https://mlsanity.com/paper/2411.10949/) (2024)
- [Submodular Optimization Beyond Nonnegativity: Adaptive Seed Selection in Incentivized Social Advertising](https://mlsanity.com/paper/2109.15180/) (2021)
- [Nonbossy Mechanisms: Mechanism Design Robust to Secondary Goals](https://mlsanity.com/paper/2307.11967/) (2023)

## Built on by (most cited first, 1 of 1)

- [Accelerated Relax-and-Round for Concave Coverage Problems](https://mlsanity.com/paper/2605.06900/) (2026)

## Abstract (arXiv)

We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs. The quality of services is measured by a submodular function known to the auctioneer. Our goal is to design computationally efficient procurement auctions that (approximately) maximize the difference between the quality of the acquired services and the total cost of the sellers, while ensuring incentive compatibility (IC), individual rationality (IR) for sellers, and non-negative surplus (NAS) for the auctioneer. Our contributions are twofold: (i) we provide an improved analysis of existing algorithms for non-positive submodular function maximization, and (ii) we design efficient frameworks that transform submodular optimization algorithms into mechanisms that are IC, IR, NAS, and approximation-preserving. These frameworks apply to both the offline setting, where all sellers' bids and services are available simultaneously, and the online setting, where sellers arrive in an adversarial order, requiring the auctioneer to make irrevocable decisions. We also explore whether state-of-the-art submodular optimization algorithms can be converted into descending auctions in adversarial settings, where the schedule of descending prices is determined by an adversary. We show that a submodular optimization algorithm satisfying bi-criteria (1/2, 1)-approximation in welfare can be effectively adapted to a descending auction. Additionally, we establish a connection between descending auctions and online submodular optimization. Finally, we demonstrate the practical applications of our frameworks by instantiating them with state-of-the-art submodular optimization algorithms and empirically comparing their welfare performance on publicly available datasets with thousands of sellers.