Research map / Adversarial robustness and security / Attacks on text and graphs
VCG under Sybil (False-Name) Attacks - A Bayesian Analysis
Yotam Gafni, Ron Lavi, Moshe Tennenholtz
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase probability q of facing 1-type (single-item) bidders from below to at least 2/3 for n=2 | VCG with false-name bids · 2 items, n=2, any F | truthful BNE existence: q >= \frac{2}{3} | Improved |
| Set q to 1 (all adversaries are 1-type) | VCG with false-name bids · any F and n | attack benefit: q=1 | Improved |
| Add a third bidder (n>2) instead of n=2 | VCG with false-name bids · general distributions F | global granularity threshold q*: \frac{2}{3} -> 1 | Hurt |
| Increase number of bidders n | VCG with false-name bids, beta distributions beta=1 · fully verified beta distribution cases | granularity threshold q* | Hurt |
| Increase alpha of beta(alpha,1) distribution | VCG with false-name bids · beta distributions beta=1 | granularity threshold q* | Improved |
| Restrict per-item distribution to uniform for any n>=3 | VCG with false-name bids · uniform [0,1] | q* for 1-type and split attack: <= \frac{1}{2} | Improved |
| Use different per-item distributions F1 and F2 for 1-type and 2-type bidders | VCG with false-name bids, n=2 · constructed counter-example | truthful BNE existence: expected gain of attack >= 0.25(1-q) | Hurt |
| Replace split attack by attack (1,1),(1,0.2) for a 1-type bidder in a two-point distribution, n=3 | VCG false-name attack · F: 1 w.p. 0.5, 0.1 w.p. 0.5 | q*: 0.0845241 -> 0.225403 | Hurt |
| Replace 1-type adversary (1,0.15) by 2-type adversary (2,0.15) against attack(0.1,0.1) | 1-type attacker (1,1) · Example in Discussion | attacker utility loss vs truthful: 0.15 -> 0.7 | Hurt |
| Change adversary from 2-item demand to 1-item demand in intro example | bidder 2 type (2,0.5) false-name attack · intro example | payment change from attacking: 0.8 -> 0.6 | Hurt |
| Vary q for 2-type split attack on uniform: threshold monotone in q | split attack · uniform | monotonicity of benefit in q | Improved |
Closest papers by meaning
- Computing Perfect Bayesian Equilibria in Sequential Auctions with Verification (AAAI 2025 · similarity 0.85)
- Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (AAAI 2025 · similarity 0.84)
- On the Power of Randomization for Obviously Strategy-Proof Mechanisms (AAAI 2025 · similarity 0.84)
- Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions (ICML 2025 · similarity 0.84)
- Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization (NeurIPS 2025 · similarity 0.84)
- Locally Private and Robust Multi-Armed Bandits (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
