  This paper explores reward mechanisms for a query incentive network in which
agents seek information from social networks. In a query tree issued by the
task owner, each agent is rewarded by the owner for contributing to the
solution, for instance, solving the task or inviting others to solve it. The
reward mechanism determines the reward for each agent and motivates all agents
to propagate and report their information truthfully. In particular, the reward
cannot exceed the budget set by the task owner. However, our impossibility
results demonstrate that a reward mechanism cannot simultaneously achieve
Sybil-proof (agents benefit from manipulating multiple fake identities),
collusion-proof (multiple agents pretend as a single agent to improve the
reward), and other essential properties. In order to address these issues, we
propose two novel reward mechanisms. The first mechanism achieves Sybil-proof
and collusion-proof, respectively; the second mechanism sacrifices Sybil-proof
to achieve the approximate versions of Sybil-proof and collusion-proof.
Additionally, we show experimentally that our second reward mechanism
outperforms the existing ones.
