EconPapers    
Economics at your fingertips  
 

Optimal Shill Bidding in the VCG Mechanism

Itai Sher ()

No 2008-4, Working Papers from University of Minnesota, Department of Economics

Abstract: This paper studies shill bidding in the VCG mechanism applied to combinatorial auctions. Shill bidding is a strategy whereby a single decision-maker enters the auction under the guise of multiple identities (Sakurai, Yokoo, and Matsubara 1999). I formulate the problem of optimal shill bidding for a bidder who knows the aggregate bid of her opponents. A key to the analysis is a subproblem--the cost minimization problem (CMP)--which searches for the cheapest way to win a given package using shills. An analysis of the CMP leads to several fundamental results about shill bidding: (i) I provide an exact characterization of the aggregate bids b such that some bidder would have an incentive to shill bid against b in terms of a new property, Submodularity at the Top; (ii) the problem of optimally sponsoring shills is equivalent to the winner determination problem (for single minded bidders)--the problem of finding an efficient allocation in a combinatorial auction; (iii) shill bidding can occur in equilibrium; and (iv) the problem of shill bidding has an inverse, namely the collusive problem that a coalition of bidders may have an incentive to merge (even after competition among coalition members has been suppressed). I show that only when valuations are additive can the incentives to shill and merge simultaneously disappear.

Keywords: VCG mechanism; combinatorial auctions; winner determination problem; collusion. (search for similar items in EconPapers)
JEL-codes: C72 D44 (search for similar items in EconPapers)
Pages: 52 pages
Date: 2008, Revised 2009
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed

Downloads: (external link)
https://docs.google.com/a/umn.edu/viewer?a=v&pid=s ... o1YWQxMWJhNDQ2ZjllZQ First version, 2008 (application/pdf)

Related works:
Journal Article: Optimal shill bidding in the VCG mechanism (2012) Downloads
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:min:wpaper:2008-4

Access Statistics for this paper

More papers in Working Papers from University of Minnesota, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Caty Bach ().

 
Page updated 2020-05-15
Handle: RePEc:min:wpaper:2008-4