  We consider crowdsourcing problems where the users are asked to provide
evaluations for items; the user evaluations are then used directly, or
aggregated into a consensus value. Lacking an incentive scheme, users have no
motive in making effort in completing the evaluations, providing inaccurate
answers instead. We propose incentive schemes that are truthful and cheap:
truthful as the optimal user behavior consists in providing accurate
evaluations, and cheap because the truthfulness is achieved with little
overhead cost. We consider both discrete evaluation tasks, where an evaluation
can be done either correctly, or incorrectly, with no degrees of approximation
in between, and quantitative evaluation tasks, where evaluations are real
numbers, and the error is measured as distance from the correct value. For both
types of tasks, we propose hierarchical incentive schemes that can be effected
with a small amount of additional evaluations, and that scale to arbitrarily
large crowd sizes: they have the property that the strength of the incentive
does not weaken with increasing hierarchy depth. Interestingly, we show that
for these schemes to work, the only requisite is that workers know their place
in the hierarchy in advance.
