Traditional mechanism design operates under a foundational assumption: the set of participants is fixed and verifiable. In classical economics, a coordinator can easily distinguish between individuals, ensuring that each person submits exactly one set of preferences.
However, in open, decentralized digital environments like the internet, this assumption completely breaks down. As Vincent Conitzer notes in Comparing Multiagent Systems Research in Combinatorial Auctions and Voting, verifying physical identities in open systems is often impossible or highly impractical. This anonymity enables a severe vulnerability known as a Sybil attack or false-name manipulation, where a single strategic actor creates multiple synthetic identifiers to distort the outcome of a protocol.
Standard "strategy-proof" mechanisms—which guarantee that participants cannot benefit by lying about their valuations—fail to prevent identity fraud. As Kevin Leyton-Brown explains in Algorithmic Game Theory and Artificial Intelligence, designing protocols that remain robust when users can participate under several aliases is a core challenge for modern multiagent systems.
Why Strategy-Proofness Fails: The Revenue Monotonicity Flaw
To understand why traditional mechanisms are vulnerable, consider a multi-item combinatorial auction. Intuition suggests that adding more bidders to an auction should increase competition and drive up the seller's total revenue. This property is called revenue monotonicity.
In Revenue Monotonicity in Combinatorial Auctions, Rastegari et al. prove a fundamental impossibility theorem: any deterministic, truthful auction mechanism that always allocates goods to the participants who value them most (maximizing social surplus) is mathematically guaranteed to fail revenue monotonicity. There will always be cases where adding a bidder counterintuitively decreases the total revenue.
This mathematical reality creates an immediate security loophole. If adding an extra bidder can lower the final prices, a single strategic agent can split their bids across multiple pseudonyms. By simulating artificial competition against themselves, the attacker tricks the mechanism into giving them a discount.
Even if we introduce randomization to bypass this impossibility result, the problem persists. Condon et al. demonstrate in Stepwise randomized combinatorial auctions achieve revenue monotonicity that while strategic randomization can successfully restore revenue monotonicity, it does not automatically make a mechanism resistant to false-name bidding.
The Mechanics of False-Name-Proof Auctions
To eliminate the incentive for identity splitting, an auction must be designed so that the marginal benefit of creating an additional pseudonym is always zero or negative. Researchers have approached this through both structural constraints and probabilistic market properties.
Structural Constraints: PORF and LDS
One way to guarantee safety is to restrict the pricing and allocation rules so that identity splitting cannot alter the payment landscape. In Characterization of Strategy/False-name Proof Combinatorial Auction, the authors introduce Price-Oriented, Rationing-Free (PORF) protocols. PORF protocols characterize the exact boundaries of false-name-proofness by ensuring that prices are set independently of individual identity configurations, removing the mathematical leverage an attacker needs to engineer a discount.
A concrete implementation of this idea is the Leveled Division Set (LDS) protocol. Introduced in Robust Combinatorial Auction Protocol against False-Name Bids, the LDS protocol structures possible bid bundles into a strict hierarchy and pairs them with reservation prices. This structure prevents agents from using multiple identities to bypass high bundle prices or to cherry-pick items at lower rates.
The Risk of Self-Competition: Granularity Thresholds
An alternative approach relies on the inherent risks an attacker faces when splitting their identity. In VCG under Sybil (False-Name) Attacks - A Bayesian Analysis, Gafni et al. evaluate the classic Vickrey-Clarke-Groves (VCG) mechanism under a Bayesian framework. They introduce the concept of a granularity threshold: the minimum probability that other participants in the market are only interested in single items.
If a market is sufficiently granular, an attacker who splits their identity into multiple pseudonyms faces a high probability of accidentally bidding against themselves for separate items. This self-competition drives up their own costs, making the Sybil attack economically unviable and rendering the standard VCG mechanism surprisingly resilient in practice.
Extending False-Name Proofness Beyond Auctions
The vulnerability to identity manipulation extends far beyond auctions. Any collective decision-making framework operating on the open internet must account for false-name behavior.
Social Choice and Voting
In online voting or facility location problems, agents can create fake accounts to shift a collective choice toward their preferred outcome. Sonoda et al. explore this in False-Name-Proof Locations of Two Facilities: Economic and Algorithmic Approaches. They show that to remain false-name-proof, facility location mechanisms must restrict their selections to "cyclically adjacent" peaks. This constraint imposes a severe trade-off, as it significantly increases the total social cost as the population grows.
To protect broader community decisions, Shahaf et al. propose anchoring decisions to the status quo in Sybil-Resilient Reality-Aware Social Choice. By requiring a higher burden of proof to change existing parameters, the mechanism ensures that synthetic identities cannot easily hijack collective choices.
Coalitional Games and Networks
When independent actors form coalitions to share costs or rewards, a single player might split into multiple entities to claim a larger share of the payout. To address this, Yokoo et al. formulate the anonymity-proof core in Coalitional Games in Open Anonymous Environments. This solution concept redefines game-theoretic stability, ensuring that rewards are distributed such that no agent can gain an advantage by hiding behind multiple pseudonyms or masking their true capabilities.
Finally, this vulnerability manifests in network-based information sharing. Modern diffusion auctions incentivize participants to invite their neighbors to join an auction. However, as Fang et al. point out in Multi-unit Auction over a Social Network, an agent can simply create a chain of fake identities along the network path to capture all the referral rewards. To neutralize this, the authors design the MUDAN mechanism, which uses graph exploration techniques to localize competition, ensuring that splitting an identity along a network path yields no structural advantage.
Key Foundational Work
Characterization of Strategy/False-name Proof Combinatorial Auction Protocols: Price-oriented, Rationing-free Protocol (2003) — contributed 1 concept elements to this direction.
Robust Combinatorial Auction Protocol against False-Name Bids (2000) — contributed 1 concept elements to this direction.