# Optimal Auction Design for the Gradual Procurement of Strategic Service Provider Agents

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 71 references that are in the map.
- First posted on arXiv 25 Oct 2021.

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

- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [Trust-Based Mechanisms for Robust and Efficient Task Allocation in the Presence of Execution Uncertainty](https://mlsanity.com/paper/1401.3473/) (2014)
- [Fast Convex Decomposition for Truthful Social Welfare Approximation](https://mlsanity.com/paper/1408.2690/) (2014)
- [The Declining Price Anomaly is not Universal in Multi-Buyer Sequential Auctions (but almost is)](https://mlsanity.com/paper/1905.00853/) (2019)
- [Optimal Auctions vs. Anonymous Pricing: Beyond Linear Utility](https://mlsanity.com/paper/1905.04257/) (2019)

## Abstract (arXiv)

We consider an outsourcing problem where a software agent procures multiple services from providers with uncertain reliabilities to complete a computational task before a strict deadline. The service consumer requires a procurement strategy that achieves the optimal balance between success probability and invocation cost. However, the service providers are self-interested and may misrepresent their private cost information if it benefits them. For such settings, we design a novel procurement auction that provides the consumer with the highest possible revenue, while giving sufficient incentives to providers to tell the truth about their costs. This auction creates a contingent plan for gradual service procurement that suggests recruiting a new provider only when the success probability of the already hired providers drops below a time-dependent threshold. To make this auction incentive compatible, we propose a novel weighted threshold payment scheme which pays the minimum among all truthful mechanisms. Using the weighted payment scheme, we also design a low-complexity near-optimal auction that reduces the computational complexity of the optimal mechanism by 99% with only marginal performance loss (less than 1%). We demonstrate the effectiveness and strength of our proposed auctions through both game theoretical and numerical analysis. The experiment results confirm that the proposed auctions exhibit 59% improvement in performance over the current state-of-the-art, by increasing success probability up to 79% and reducing invocation cost by up to 11%.