# Truthful Multi-unit Procurements with Budgets

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2014.

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

- [FL-Market: Trading Private Models in Federated Learning](https://mlsanity.com/paper/2106.04384/) (2021)

## Abstract (arXiv)

We study procurement games where each seller supplies multiple units of his item, with a cost per unit known only to him. The buyer can purchase any number of units from each seller, values different combinations of the items differently, and has a budget for his total payment. For a special class of procurement games, the em bounded knapsack problem, we show that no universally truthful budget-feasible mechanism can approximate the optimal value of the buyer within ln n, where n is the total number of units of all items available. We then construct a polynomial-time mechanism that gives a 4(1+ln n)-approximation for procurement games with em concave additive valuations, which include bounded knapsack as a special case. Our mechanism is thus optimal up to a constant factor. Moreover, for the bounded knapsack problem, given the well-known FPTAS, our results imply there is a provable gap between the optimization domain and the mechanism design domain. Finally, for procurement games with em sub-additive valuations, we construct a universally truthful budget-feasible mechanism that gives an O(fraclog2 nlog log n)-approximation in polynomial time with a demand oracle.