Limited verification of identities to induce false-name-proofness

Vincent Conitzer

TL;DR

This paper tackles the challenge of "false-naming" in anonymous online mechanisms, where agents can use multiple identities to manipulate outcomes. The authors propose a novel approach: instead of full identity verification (which defeats anonymity) or relying solely on false-name-proof mechanisms (which have limitations), they introduce "limited verification." This involves strategically checking subsets of reports to ensure that agents have no incentive to use multiple identities, striking a balance between security and anonymity.

What Problem Does This Paper Address?

In many online systems, like auctions or voting, we rely on agents reporting their preferences. Ideally, we want mechanisms that are "strategy-proof" (agents can't benefit from lying about their preferences) and "individually rational" (agents are better off participating than not). However, in anonymous environments, a significant challenge arises: agents can use multiple identifiers (e.g., different email addresses) to submit multiple reports. This "false-naming" can undermine the mechanism's integrity, even if it's strategy-proof. For instance, in a combinatorial auction, a single agent might submit multiple bids from different identities to secure items at a lower price than they would if they used a single identity. Similarly, in voting, an agent could cast multiple votes for their preferred candidate.

Existing solutions have drawbacks. Designing "false-name-proof" mechanisms that inherently prevent this is often impossible or leads to inefficient outcomes. Full identity verification, on the other hand, sacrifices the anonymity that these systems often aim to provide. This paper seeks a middle ground: a way to deter false-naming without completely abandoning anonymity.

Methods

The core contribution is the introduction of a verification protocol that works in conjunction with an existing mechanism. Instead of verifying every single report, the protocol strategically selects subsets of reports to check. When a subset is checked, agents are asked to confirm their reports (e.g., by providing a real-world identifier). If an agent has submitted multiple reports within that subset, the protocol can detect this discrepancy. The key insight is that the protocol doesn't need to identify which specific reports came from the same agent; it only needs to ensure that for any set of reports that could be manipulated by a single agent (i.e., "requires verification"), at least two of those reports are confirmed to be from different agents.

The paper formalizes this by defining:

  • "Requires verification": A subset of reports $S$ requires verification if there exists a hypothetical agent type such that the agent would be better off submitting $S$ than a single truthful report, given the other agents' reports.
  • "Sufficient verification protocol": A protocol is sufficient if, for every subset of reports that requires verification, it eventually checks a subset that has at least two reports in common with it.

The paper then proves that a verification protocol induces "false-name-proofness" (meaning agents have no incentive to use multiple identities) if and only if it is "sufficient." This characterization leads to computational problems: how to choose the minimal set of subsets to check to achieve sufficiency, minimizing verification effort and maximizing anonymity.

Datasets

Not discussed in the paper. The paper focuses on theoretical mechanisms and computational problems, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "Middle Ground": The most significant insight is the development of a hybrid approach that balances anonymity and mechanism integrity. Limited verification offers a practical alternative to the extremes of full verification or no verification.
  • Focus on Discrepancy, Not Identity: The crucial realization is that we don't need to know who is using multiple identities. Simply detecting that some reports in a suspicious set came from different agents is enough to deter manipulation.
  • Characterization of Sufficiency: The formal link between a verification protocol's "sufficiency" and its ability to induce false-name-proofness provides a clear theoretical foundation for designing such protocols.
  • Connection to HITTING-SET: The paper elegantly demonstrates that the computational problems of minimizing verification effort are closely related to the well-studied NP-complete HITTING-SET problem. This allows for leveraging existing algorithmic techniques and understanding the inherent complexity.

Key Results

  • Characterization Theorem: The paper provides a precise characterization of when a limited verification protocol induces false-name-proofness for a given mechanism. This is achieved when the protocol "sufficiently verifies" reports, meaning for any set of reports that requires verification, the protocol checks a subset that has at least two reports in common with it.
  • Computational Complexity: The problems of minimizing verification effort (e.g., finding the smallest set of subsets to check) are shown to be computationally hard, closely related to the NP-complete HITTING-SET problem. This implies that finding optimal solutions might be intractable for large instances.
  • Approximation Algorithms: The paper suggests that algorithms for HITTING-SET can be adapted to provide approximation algorithms for the verification problems, offering practical solutions even if optimal ones are hard to find.

Limitations and Future Work

  • Assumptions: The analysis primarily focuses on mechanisms that are already individually rational (IR) and strategy-proof. Extending this to mechanisms that are only Bayes-Nash incentive compatible would be a valuable next step.
  • Randomized Protocols: The current work focuses on deterministic verification protocols. The authors suggest exploring randomized protocols, where there's a high probability that a manipulating agent's reports will be checked, which could offer further flexibility.
  • Efficiency of Minimal Subsets: While the paper characterizes the computational problems, the longer version (mentioned in the text) delves into efficiently determining the minimal subsets that require verification, which is crucial for practical implementation.
  • Specific Mechanisms: The paper uses combinatorial auctions (Clarke mechanism) and majority voting as examples. Applying the framework to a wider range of mechanisms and exploring how mechanism-specific structures might simplify the verification problem is a promising avenue.

Summary updated

Abstract

In open, anonymous environments such as the Internet, mechanism design is complicated by the fact that a single agent can participate in the mechanism under multiple identifiers. One way to address this is to design false-name-proof mechanisms, which choose the outcome in such a way that agents have no incentive to use more than one identifier. Unfortunately, there are inherent limitations on what can be achieved with false-name-proof mechanisms, and at least in some cases, these limitations are crippling. An alternative approach is to verify the identities of all agents. This imposes significant overhead and removes any benefits from anonymity. In this paper, we propose a middle ground. Based on the reported preferences, we check, for various subsets of the reports, whether the reports in the subset were all submitted by different agents. If they were not, then we discard some of them. We characterize when such a limited verification protocol induces false-name-proofness for a mechanism, that is, when the combination of the mechanism and the verification protocol gives the agents no incentive to use multiple identi- fiers. This characterization leads to various optimization problems for minimizing verification effort. We study how to solve these problems. Throughout, we use combinatorial auctions (using the Clarke mechanism) and majority voting as examples.
BibTeX
@inproceedings{conitzer2007limited,
  author = {Vincent Conitzer},
  title = {{Limited verification of identities to induce false-name-proofness}},
  booktitle = {TARK},
  year = {2007},
  doi = {10.1145/1324249.1324265},
}
Figure