Exploring the VCG Mechanism in Combinatorial Auctions
The Threshold Revenue and the Threshold-Price Rule

Area 09 – Ingegneria industriale e dell'informazione

In this work we explore interesting potentialities of the Vickrey-Clarke-Groves (VCG) mechanism in the auctions context under the assumption of players with independent and private valuations and with no budget constraints. First we apply the VCG rule to a coalition of bidders in order to measure the minimum effort, in terms of submitted bids, that the coalition has to support to win, given the valuations systems of the opponents (i.e. the second price of the coalition). Then we introduce and formulate the problem ofdetermining that partition of players into coalitions which maximize the auctioneer’s revenue in the case whereby such coalitions take part to a VCG auction each one as a single agent; in particular, we providean NP-hard integer linear formulation of this problem. We also generalize this issue by allowing players to simultaneously belong to distinct coalitions in the case that players’ valuations systems are separable. Finally, we propose some applications of these theoretical results. For instance, we exploit them to define a class of new payment rules which are placed, in a sense, between the VCG rule and firstprice one, and to determine the highest losing bids in combinatorial auctions.

SINTESI