VCG under Sybil (False-Name) Attacks – A Bayesian Analysis
Authors: Yotam Gafni, Ron Lavi, Moshe Tennenholtz1966-1973
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we introduce for the first time, to the best of our knowledge a Bayesian equilibrium analysis of VCG under false-name bids. In service of that we use a bare-minimum model: an auction of two identical items, and single-minded bidders. Namely, each bidder is interested in a single item or in the pair of items. The Bayesian setting is given by a per-item valuation distribution, and a probability q for a bidder to have a single-item demand. As we will see, the analysis of such a model already brings out intricate techniques and conclusions, which are essential to address the problem. To obtain our results, we present a criterion we name Granularity threshold to measure the effect of the granularity of bidders demands on the mechanism s Bayesian truthfulness. Our main results state that for two bidders (n = 2) and two items (m = 2) there is a truthful Bayesian equilibrium whenever the probability q of a bidder to demand one item rather than two is at least 2 3, with any valuation distribution (Section 3). We then show that for any larger number of bidders (n > 2), such a global granularity threshold can no longer be derived and valuation distributions do matter (Section 4). Given the above, we consider general beta distributions over per-item valuations. This family includes many natural distributions, and is used widely in statistics and economic theory (Gupta and Nadarajah 2004; Krishnamoorthy 2016). Interestingly, it admits useful connections to computer algebra techniques, which allows us to provably present good granularity thresholds, i.e. low q values, in tested cases (Section 5). Lastly, we focus on an important attack form we call the split attack. We also wish to thank Doron Zeilberger and Christoph Koutschan for their kind advise regarding symbolic identity proving. |
| Researcher Affiliation | Academia | Yotam Gafni, Ron Lavi, Moshe Tennenholtz Technion Israel Institute of Technology Haifa 32000 Israel yotam.gafni@campus.technion.ac.il, {ronlavi, moshet}@ie.technion.ac.il |
| Pseudocode | No | No pseudocode or algorithm blocks were found in the paper. |
| Open Source Code | Yes | The Mathematica and Maple files to attain and verify the figures exact values independently can be found at https://github.com/yotam-gafni/vcg_bayesian_fnp. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments on empirical datasets; therefore, it does not involve publicly available datasets for training. |
| Dataset Splits | No | This paper is theoretical and does not conduct experiments on empirical datasets; therefore, it does not specify training/test/validation splits. |
| Hardware Specification | No | No specific hardware details (e.g., GPU/CPU models, memory) used for computations were mentioned in the paper. |
| Software Dependencies | No | The paper mentions 'Maple (Chen and Moreno Maza 2016)', 'RISCErgo Sum s Guess package (Kauers 2009)', and 'RISCErgo Sum s Holonomic Functions Mathematica package (Koutschan 2009)' but does not specify version numbers for these software components. |
| Experiment Setup | No | This paper is theoretical and does not describe empirical experiments with hyperparameters or system-level training settings. |