Limited Verification of Identities to Induce False-Name-Proofness

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.