Optimal Shill Bidding in the VCG Mechanism
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.
|Date of creation:||12 2008|
|Date of revision:||05 2009|
|Contact details of provider:|| Postal: 4-101 Hanson Hall, 1925 Fourth Street South, Minneapolis, MN 55455|
Web page: http://www.econ.umn.edu/
More information through EDIRC
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Babaioff, Moshe & Feldman, Michal & Nisan, Noam & Winter, Eyal, 2012. "Combinatorial agency," Journal of Economic Theory, Elsevier, vol. 147(3), pages 999-1034.
- Paul Milgrom, 2000.
"Putting Auction Theory to Work: The Simultaneous Ascending Auction,"
Journal of Political Economy,
University of Chicago Press, vol. 108(2), pages 245-272, April.
- Paul Milgrom, "undated". "Putting Auction Theory to Work: The Simultaneous Ascending Auction," Working Papers 98002, Stanford University, Department of Economics.
- Milgrom, Paul, 1998. "Putting auction theory to work : the simultaneous ascending auction," Policy Research Working Paper Series 1986, The World Bank.
- Soo Chew & Shigehiro Serizawa, 2007. "Characterizing the Vickrey combinatorial auction by induction," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 33(2), pages 393-406, November.
- Chew Soo Hong & Shigehiro Serizawa, 2005. "Characterizing the Vickrey Combinatorial Auction by Induction," ISER Discussion Paper 0631, Institute of Social and Economic Research, Osaka University.
- Green, Jerry & Laffont, Jean-Jacques, 1977. "Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods," Econometrica, Econometric Society, vol. 45(2), pages 427-438, March.
- Ruqu Wang & Emin Murat Dinlersoz & Parimal Kanti Bag, 2000. "More on phantom bidding," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 15(3), pages 701-707.
- Ruqu Wang & Parimal Kanti Bag & Emim Murat Dinlersoz, 1998. "More on Phantom Bidding," Working Papers 976, Queen's University, Department of Economics.
- Ausubel Lawrence M & Milgrom Paul R, 2002. "Ascending Auctions with Package Bidding," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 1(1), pages 1-44, August.
- Lawrence M. Ausubel & Paul Milgrom, 2002. "Ascending Auctions with Package Bidding," Working Papers 02004, Stanford University, Department of Economics.
- Marshall, Robert C. & Marx, Leslie M., 2007. "Bidder collusion," Journal of Economic Theory, Elsevier, vol. 133(1), pages 374-402, March.
- Yokoo, Makoto & Sakurai, Yuko & Matsubara, Shigeo, 2004. "The effect of false-name bids in combinatorial auctions: new fraud in internet auctions," Games and Economic Behavior, Elsevier, vol. 46(1), pages 174-188, January.
- Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
- Graham, Daniel A & Marshall, Robert C, 1987. "Collusive Bidder Behavior at Single-Object Second-Price and English Auctions," Journal of Political Economy, University of Chicago Press, vol. 95(6), pages 1217-1239, December.
- Lehmann, Benny & Lehmann, Daniel & Nisan, Noam, 2006. "Combinatorial auctions with decreasing marginal utilities," Games and Economic Behavior, Elsevier, vol. 55(2), pages 270-296, May.
- Robert Day & Paul Milgrom, 2008. "Core-selecting package auctions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 393-407, March.
- Milgrom,Paul, 2004. "Putting Auction Theory to Work," Cambridge Books, Cambridge University Press, number 9780521536721, Diciembre.
- Milgrom,Paul, 2004. "Putting Auction Theory to Work," Cambridge Books, Cambridge University Press, number 9780521551847, Diciembre.
- Moulin, Hervé, 2008. "Proportional scheduling, split-proofness, and merge-proofness," Games and Economic Behavior, Elsevier, vol. 63(2), pages 567-587, July.
- Deltas, George, 1999. "When does cheating on mail-in bids pay? A guide for the dishonest auctioneer," Journal of Economic Behavior & Organization, Elsevier, vol. 40(3), pages 313-323, November.
- Estelle Cantillon & Martin Pesendorfer, 2006. "Auctioning bus routes: the London experience," ULB Institutional Repository 2013/9003, ULB -- Universite Libre de Bruxelles.
- S.J. Rassenti & V.L. Smith & R.L. Bulfin, 1982. "A Combinatorial Auction Mechanism for Airport Time Slot Allocation," Bell Journal of Economics, The RAND Corporation, vol. 13(2), pages 402-417, Autumn.
- Graham, Daniel A. & Marshall, Robert C. & Richard, Jean-Francois, 1990. "Phantom bidding against heterogeneous bidders," Economics Letters, Elsevier, vol. 32(1), pages 13-17, January. Full references (including those not matched with items on IDEAS)
When requesting a correction, please mention this item's handle: RePEc:min:wpaper:2008-4. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Caty Bach)
If references are entirely missing, you can add them using this form.