In open, anonymous settings such as the Internet, agents can participate in a mechanism multiple times under different identities. A mechanism is false-name-proof if no agent ever benefits from participating more than once. Unfortunately, the design of false-name-proof mechanisms has been hindered by a variety of negative results. In this paper, we show how some of these negative results can be circumvented by making the realistic assumption that obtaining additional identities comes at a (potentially small) cost. We consider arbitrary such costs and apply our results within the context of a voting model with two alternatives. © 2014 Springer-Verlag Berlin Heidelberg.