Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems. In mechanism design, it is generally assumed that an agent can submit any report at zero cost (with the occasional further restriction that certain types can not submit certain reports). More generally, however, an agent of type θ may be able to report θ', but only at a cost c(θ,θ'). This cost may reflect the effort the agent would have to expend to be indistinguishable from an agent that truthfully reports θ'. Even more generally, the possible reports (or signals) may not directly correspond to types. In this paper, we consider the complexity of determining whether particular social choice functions can be implemented in this context.