Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions

Krysta, Piotr; Telelis, Orestis; Ventre, Carmine

Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions

Piotr Krysta, Orestis Telelis, Carmine Ventre

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Best Papers from Sister Conferences Track. Pages 4275-4280.

Abstract

We design and analyze deterministic truthful approximation mechanisms for multi-unit combinatorial auctions involving a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of items, i.e., for more than one unit per distinct good, that are expressed through their private valuation functions. Our objective is to determine allocations of multisets that maximize the Social Welfare approximately. Despite the recent theoretical advances on the design of truthful combinatorial auctions (for multiple distinct goods in unit supply) and multi-unit auctions (for multiple units of a single good), results for the combined setting are much scarcer. We elaborate on the main developments of [Krysta et al., AAMAS 2013], concerning bidders with multi-minded and submodular valuation functions, with an emphasis on the presentation of the relevant algorithmic techniques.

Piotr Krysta, Orestis Telelis, and Carmine Ventre. 2015. Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 4275–4280. https://ijcai.org/proceedings/2015/608

@inproceedings{ijcai2015p608,
  title     = {Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions},
  author    = {Krysta, Piotr and Telelis, Orestis and Ventre, Carmine},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {4275--4280},
  year      = {2015},
  month     = {7},
  note      = {Best Papers from Sister Conferences Track},
  url       = {https://ijcai.org/proceedings/2015/608},
}

TY  - CPAPER
TI  - Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions
AU  - Krysta, Piotr
AU  - Telelis, Orestis
AU  - Ventre, Carmine
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 4275
EP  - 4280
UR  - https://ijcai.org/proceedings/2015/608
ER  -