Increasing VCG Revenue by Decreasing the Quality of Items

Authors

  • Mingyu Guo University of Adelaide
  • Argyrios Deligkas University of Liverpool
  • Rahul Savani University of Liverpool

DOI:

https://doi.org/10.1609/aaai.v28i1.8795

Keywords:

mechanism design, marking down, item burning, revenue maximization, VCG

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.

Downloads

Published

2014-06-21

How to Cite

Guo, M., Deligkas, A., & Savani, R. (2014). Increasing VCG Revenue by Decreasing the Quality of Items. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8795

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms