Optimal shill bidding in the VCG mechanism

Itai Sher

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

This paper studies shill bidding in the Vickrey-Clarke-Groves (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 (Yokoo et al. Games Econ Behav, 46 pp. 174-188, 2004). 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.

Original languageEnglish (US)
Pages (from-to)341-387
Number of pages47
JournalEconomic Theory
Volume50
Issue number2
DOIs
StatePublished - Jun 2012

Fingerprint

Vickrey-Clarke-Groves mechanism
Shill bidding
Bid
Incentives
Combinatorial auctions
Cost minimization
Multiple identities
Decision maker
Winner determination
Submodularity
Sponsoring
Auctions
Efficient allocation

Keywords

  • Collusion
  • Combinatorial auctions
  • Shill bidding
  • VCG mechanism
  • Winner determination problem

Cite this

Optimal shill bidding in the VCG mechanism. / Sher, Itai.

In: Economic Theory, Vol. 50, No. 2, 06.2012, p. 341-387.

Research output: Contribution to journalArticle

Sher, Itai. / Optimal shill bidding in the VCG mechanism. In: Economic Theory. 2012 ; Vol. 50, No. 2. pp. 341-387.
@article{18f46dc8669e4984a021f6f8ae619ac5,
title = "Optimal shill bidding in the VCG mechanism",
abstract = "This paper studies shill bidding in the Vickrey-Clarke-Groves (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 (Yokoo et al. Games Econ Behav, 46 pp. 174-188, 2004). 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 = "Collusion, Combinatorial auctions, Shill bidding, VCG mechanism, Winner determination problem",
author = "Itai Sher",
year = "2012",
month = "6",
doi = "10.1007/s00199-010-0566-6",
language = "English (US)",
volume = "50",
pages = "341--387",
journal = "Economic Theory",
issn = "0938-2259",
publisher = "Springer New York",
number = "2",

}

TY - JOUR

T1 - Optimal shill bidding in the VCG mechanism

AU - Sher, Itai

PY - 2012/6

Y1 - 2012/6

N2 - This paper studies shill bidding in the Vickrey-Clarke-Groves (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 (Yokoo et al. Games Econ Behav, 46 pp. 174-188, 2004). 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.

AB - This paper studies shill bidding in the Vickrey-Clarke-Groves (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 (Yokoo et al. Games Econ Behav, 46 pp. 174-188, 2004). 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.

KW - Collusion

KW - Combinatorial auctions

KW - Shill bidding

KW - VCG mechanism

KW - Winner determination problem

UR - http://www.scopus.com/inward/record.url?scp=84861358703&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84861358703&partnerID=8YFLogxK

U2 - 10.1007/s00199-010-0566-6

DO - 10.1007/s00199-010-0566-6

M3 - Article

VL - 50

SP - 341

EP - 387

JO - Economic Theory

JF - Economic Theory

SN - 0938-2259

IS - 2

ER -