False Name Proof Mechanism Design

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 215 papers20 conceptsfrozen 2026-10-04

In classical mechanism design, we assume a fixed set of participants. Whether designing an auction or a voting system, the rule of thumb is "one agent, one voice." However, in modern decentralized environments—from online auctions to crowdsensing—this assumption collapses. An agent can easily create multiple digital identities, a tactic known as a Sybil attack or false-name bidding, to manipulate the outcome in their favor.

False-name-proof mechanism design seeks to create rules where an agent’s best strategy is to use a single identity and report their true preferences, even when creating fake accounts is costless.

The Failure of Traditional Strategy Proofness

A mechanism is "strategy-proof" if no agent can benefit by lying about their preferences. The famous Vickrey-Clarke-Groves (VCG) auction is the gold standard for this: it ensures that bidding your true valuation is always the optimal strategy.

However, as Vincent Conitzer points out in Comparing Multiagent Systems Research in Combinatorial Auctions and Voting, strategy-proofness does not imply false-name-proofness. In a multi-item auction, a bidder might find that by splitting their bid across two different identities, they can trick the VCG mechanism into charging them a lower total price. This happens because VCG calculates payments based on the "harm" an agent causes to others; by splitting identities, an agent can make it appear as though their individual impact is smaller than it actually is.

The Role of Revenue Monotonicity

Why does adding identities help a cheater? The answer often lies in a property called revenue monotonicity. Intuitively, if more bidders join an auction, the seller's revenue should stay the same or increase.

In Revenue Monotonicity in Combinatorial Auctions, Baharak Rastegari, Anne Condon, and Kevin Leyton-Brown prove a "no-free-lunch" theorem: any truthful, efficient auction mechanism will inevitably fail revenue monotonicity in some cases. This failure creates a security hole. If adding a bidder can decrease revenue, then a single bidder can simulate additional "fake" bidders to lower the price they eventually pay. Thus, revenue monotonicity is not just a financial desideratum; it is a necessary condition for protecting against identity-based manipulation.

Bayesian Resilience and Efficiency Trade-offs

If perfect false-name-proofness is mathematically difficult to achieve without sacrificing efficiency, can we find a middle ground?

Yotam Gafni, Moshe Tennenholtz, and Ron Lavi suggest that the classic VCG mechanism is more robust than it looks. In VCG Under Sybil (False-name) Attacks - a Bayesian Analysis, they introduce the granularity threshold. They show that if there is a high probability that your competitors only want a single item, the incentive to use false names vanishes. In these "Bayesian" settings, truth-telling remains the best strategy because the risk of a split-bid strategy backfiring outweighs the potential gains.

Furthermore, Colleen Alkalay-Houlihan and Adrian Vetta argue in False-Name Bidding and Economic Efficiency in Combinatorial Auctions that we shouldn't abandon VCG too quickly. They demonstrate that while VCG can be cheated, it still maintains high social welfare. Specialized "false-name-proof" mechanisms often have to be so restrictive that they end up wasting more economic value than the cheating would have cost in the first place.

Expanding the Scope: Facilities and Withdrawals

The challenge of false names extends beyond auctions into social choice and infrastructure. For example, when deciding where to build public facilities, a user might create fake identities to pull the chosen location closer to their actual home. Akihisa Sonoda, Taiki Todo, and Makoto Yokoo characterized the limits of False-name-proof Locations of Two Facilities, showing that such mechanisms must follow strict geometric patterns to remain unhackable.

Newer models also account for more complex cheating. In False-name-proofness with Bid Withdrawal, Mingyu Guo and Vincent Conitzer explore "bid and bolt" strategies. In anonymous online settings, a bidder might use multiple names to drive the price in a certain direction and then simply disappear (withdraw) if the outcome isn't favorable. They proposed the MMVIP mechanism to ensure that even this "ghosting" behavior provides no strategic advantage.

Summary of the Intuition

The core insight of this research area is that identity is a strategic variable. In a digital world, an agent's "size" is not fixed. To make a system robust, designers must ensure that:

  1. Aggregation is not penalized: An agent should not pay more for a set of goods than the sum of what their "fake identities" would pay.
  2. Participation is monotonic: Adding a new participant should never make the existing participants (or the system designer) worse off in a way that invites simulation.
  3. The cost of complexity is high: If the mechanism cannot be perfectly proofed, it should at least make the optimal "cheating" strategy computationally or statistically difficult to find.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 13 papers
  2. Version 1 · 2026-10-04 · 15 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_false_name_manipulation_5e4e690f,
  title = {false-name manipulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/false-name-manipulation/rdr_5e4e690f82d44d13b7ea695a3c7c1822},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_false_name_proof_mechanism_design_5e4e690f_v1,
  title = {False Name Proof Mechanism Design},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/false-name-proof-mechanism-design/rdr_5e4e690f82d44d13b7ea695a3c7c1822/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}