Mechanisms for Multi-unit Combinatorial Auctions with a Few Distinct Goods
Authors: Piotr Krysta, Orestis Telelis, Carmine Ventre
JAIR 2015 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design and analyze deterministic truthful approximation mechanisms for multiunit Combinatorial Auctions involving only a constant number of distinct goods, each in arbitrary limited supply. Our main results are for multiminded and submodular bidders. In the first setting each bidder has a positive value for being allocated one multiset from a prespecified demand set of alternatives. In the second setting each bidder is associated to a submodular valuation function that defines his value for the multiset he is allocated. For multi-minded bidders, we design a truthful Fptas that fully optimizes the Social Welfare, while violating the supply constraints on goods within factor (1 + ϵ), for any fixed ϵ > 0 (i.e., the approximation applies to the constraints and not to the Social Welfare). This result is best possible, in that full optimization is impossible without violating the supply constraints. For submodular bidders, we obtain a Ptas that approximates the optimum Social Welfare within factor (1 + ϵ), for any fixed ϵ > 0, without violating the supply constraints. This result is best possible as well. Our allocation algorithms are Maximal-in-Range and yield truthful mechanisms, when paired with Vickrey-Clarke-Groves payments. |
| Researcher Affiliation | Academia | Piotr Krysta EMAIL Deparment of Computer Science University of Liverpool, United Kingdom Orestis Telelis EMAIL Department of Digital Systems University of Piraeus, Greece Carmine Ventre EMAIL School of Computing Teesside University, United Kingdom |
| Pseudocode | Yes | 1. for ℓ= 1, . . . , m do: (a) define uℓ:= (1 + 1 (b) define Lℓ:= 0, 1, uℓ , u2 ℓ , . . . , u loguℓsℓ ℓ 2. for every subset T [n] of bidders, |T| t, do: 1 Run A with sℓ χℓunits from each good ℓ [m] and bidders in T. 2 Split the remaining χℓunits (if χℓ> 0) from each good ℓ [m] into 2n2 bundles (per good), each of max χℓ 2n2 , 1 units. 3 Find the optimal allocation of the equi-sized bundles among bidders [n] \ T. 3. Return the best allocation found. Figure 1: The Dobzinski-Nisan Method for multiple goods. |
| Open Source Code | No | The paper does not contain any statements about releasing code, links to repositories, or mentions of code being available in supplementary materials for the methodology described. |
| Open Datasets | No | The paper is theoretical and focuses on designing and analyzing auction mechanisms. It does not involve experimental evaluation using specific datasets; examples are illustrative rather than data-driven. |
| Dataset Splits | No | The paper is theoretical and does not perform experiments on datasets, therefore, there is no mention of training/test/validation dataset splits. |
| Hardware Specification | No | This paper is theoretical and analyzes mechanisms and algorithms; it does not describe experimental results or the hardware used for any computational tasks. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and analysis, rather than implementation details. Therefore, it does not specify any software dependencies or their version numbers. |
| Experiment Setup | No | As a theoretical paper focusing on mechanism design and algorithm analysis, there is no experimental setup, hyperparameters, or training configurations described. |