Title: On Formal Models for Social Verification

Abstract:

In human computation, users are normally required to input answers for questions proposed by the system, e.g., descriptions about a picture or a song. Since users may bring up irrelevant inputs intentionally or carelessly, and often the system does not have “correct” answers, we have to rely on the users to verify answers from others. We call this kind of mutual verification of users’ answers “social verification.” We propose formal models for two fundamental social verification mechanisms, simultaneous verification and sequential verification, in human computation systems. By adopting a game-theoretic approach, we perform an equilibrium analysis which explains the effect of each verification mechanism on a system’s outcome. Our analysis results show that sequential verification leads to a more diverse and descriptive set of outcomes than simultaneous verification, though the latter is stronger in ensuring the correctness of verified answers.