# Mechanisms for Multi-Unit Auctions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2014.

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

- [Adaptive Oracle-Efficient Online Learning](https://mlsanity.com/paper/2210.09385/) (2022)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)

## Abstract (arXiv)

We present an incentive-compatible polynomial-time approximation scheme for multi-unit auctions with general k-minded player valuations. The mechanism fully optimizes over an appropriately chosen sub-range of possible allocations and then uses VCG payments over this sub-range. We show that obtaining a fully polynomial-time incentive-compatible approximation scheme, at least using VCG payments, is NP-hard. For the case of valuations given by black boxes, we give a polynomial-time incentive-compatible 2-approximation mechanism and show that no better is possible, at least using VCG payments.