Fair and resilient Incentive Tree mechanisms

We study Incentive Trees for motivating the participation of people in crowdsourcing or human tasking systems. In an Incentive Tree, each participant is rewarded for contributing to the system, as well as for soliciting new participants into the system, who then themselves contribute to it and/or themselves solicit new participants. An Incentive Tree mechanism is an algorithm that determines how much reward each individual participant receives based on all the participants' contributions, as well as the structure of the solicitation tree. The sum of rewards paid by the mechanism to all participants is linear in the sum of their total contribution. In this paper, we investigate the possibilities and limitations of Incentive Trees via an axiomatic approach by defining a set of desirable properties that an Incentive Tree mechanism should satisfy. We give a mutual incompatibility result showing that there is no Incentive Tree mechanism that simultaneously achieves all the properties. We then present two novel families of Incentive Tree mechanisms. The first family of mechanisms achieves all desirable properties, except that it fails to protect against a certain strong form of multi-identity attack; the second set of mechanisms achieves all properties, including the strong multi-identity protection, but fails to give participants the opportunity to achieve unbounded reward. Given the above impossibility result, these two mechanisms are effectively the best we can hope for. Finally, our model and results generalize recent studies on multi-level marketing mechanisms.