Please use this identifier to cite or link to this item:
Type: Conference paper
Title: Increasing VCG revenue by decreasing the quality of items
Author: Guo, M.
Deligkas, A.
Savani, R.
Citation: Proceedings of the ... AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence, 2014, vol.1, pp.705-711
Publisher: AAAI
Publisher Place: online
Issue Date: 2014
ISBN: 9781577356776
ISSN: 2159-5399
Conference Name: Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-14) (27 Jul 2014 - 31 Jul 2014 : Quebec)
Statement of
Mingyu Guo, Argyrios Deligkas and Rahul Savani
Abstract: The VCG mechanism is the standard method to incentivize bidders in combinatorial auctions to bid truthfully. Under the VCG mechanism, the auctioneer can sometimes increase revenue by "burning" items.We study this phenomenon in a setting where items are described by a number of attributes. The value of an attribute corresponds to a quality level, and bidders' valuations are non-decreasing in the quality levels. In addition to burning items, we allow the auctioneer to present some of the attributes as lower quality than they actually are. We consider the following two revenue maximization problems under VCG: finding an optimal way to mark down items by reducing their quality levels, and finding an optimal set of items to burn. We study the effect of the following parameters on the computational complexity of these two problems: the number of attributes, the number of quality levels per attribute, and the complexity of the bidders' valuation functions. Bidders have unit demand, so VCG's outcome can be computed in polynomial time, and the valuation functions we consider are step functions that are non-decreasing with the quality levels.We prove that both problems are NP-hard even in the following three simple settings: a) four attributes, arbitrarily many quality levels per attribute, and single-step valuation functions, b) arbitrarily many attributes, two quality levels per attribute, and single-step valuation functions, and c) one attribute, arbitrarily many quality-levels, and multi-step valuation functions. For the case where items have only one attribute, and every bidder has a single-step valuation (zero below some quality threshold), we show that both problems can be solved in polynomial-time using a dynamic programming approach. For this case, we also quantify how much better marking down is than item burning, and we compare the revenue of both approaches with computational experiments.
Rights: Copyright © 2014, Association for the Advancement of Artificial Intelligence ( All rights reserved.
Published version:
Appears in Collections:Aurora harvest 3
Computer Science publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Restricted Access567.7 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.