ML Anthology

Mechanisms for Multi-Unit Auctions

Shahar Dobzinski, Noam Nisan
JAIR 2010 pp. 85-98
doi:10.1613/JAIR.2950 /jair/2010/dobzinski2010jair-mechanisms/

Abstract

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.

PDF JAIR Semantic Scholar

Cite

Text

Dobzinski and Nisan. "Mechanisms for Multi-Unit Auctions." Journal of Artificial Intelligence Research, 2010. doi:10.1613/JAIR.2950

Markdown

[Dobzinski and Nisan. "Mechanisms for Multi-Unit Auctions." Journal of Artificial Intelligence Research, 2010.](https://mlanthology.org/jair/2010/dobzinski2010jair-mechanisms/) doi:10.1613/JAIR.2950

BibTeX

@article{dobzinski2010jair-mechanisms,
  title     = {{Mechanisms for Multi-Unit Auctions}},
  author    = {Dobzinski, Shahar and Nisan, Noam},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {2010},
  pages     = {85-98},
  doi       = {10.1613/JAIR.2950},
  volume    = {37},
  url       = {https://mlanthology.org/jair/2010/dobzinski2010jair-mechanisms/}
}