VCG under Sybil (False-Name) Attacks - A Bayesian Analysis

Authors

  • Yotam Gafni Technion
  • Ron Lavi Technion
  • Moshe Tennenholtz Technion

DOI:

https://doi.org/10.1609/aaai.v34i02.5567

Abstract

VCG is a classical combinatorial auction that maximizes social welfare. However, while the standard single-item Vickrey auction is false-name-proof, a major failure of multi-item VCG is its vulnerability to false-name attacks. This occurs already in the natural bare minimum model in which there are two identical items and bidders are single-minded. Previous solutions to this challenge focused on developing alternative mechanisms that compromise social welfare. We re-visit the VCG auction vulnerability and consider the bidder behavior in Bayesian settings. In service of that we introduce a novel notion, termed the granularity threshold, that characterizes VCG Bayesian resilience to false-name attacks as a function of the bidder type distribution. Using this notion we show a large class of cases in which VCG indeed obtains Bayesian resilience for the two-item single-minded setting.

Downloads

Published

2020-04-03

How to Cite

Gafni, Y., Lavi, R., & Tennenholtz, M. (2020). VCG under Sybil (False-Name) Attacks - A Bayesian Analysis. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1966-1973. https://doi.org/10.1609/aaai.v34i02.5567

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms