---
title: "Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions"
authors:
  - "Piotr Krysta"
  - "Orestis Telelis"
  - "Carmine Ventre"
doi: ""
url: "https://ijcai.org/proceedings/2015/608"
pdf: "https://ijcai.org/proceedings/2015/0608.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "4275-4280"
track: "Best Papers from Sister Conferences Track"
keywords:
---

# Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions

Piotr Krysta, Orestis Telelis, Carmine Ventre

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, 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.