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-29-12, Revised 2009
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

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)
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 ( this e-mail address is bad, please contact ).