Taming the big to small: efficient selfish task allocation in mobile crowdsourcing systems

This paper investigates the selfish load balancing problem in mobile distributed crowdsourcing networks. Conventional methods heavily relied on cooperation among users to achieve balanced resource utilization in a platform-centric view. In achieving fairly low communication and computational overhead, this work leverages the d-choice method based on Ball and Bin theory for effective balancing under limited information and the Proportional Allocation scheme for selfish load balancing, maintaining good load balancing property among selfish users. Even with limited information, the balancing performance could be improved significantly. Moreover, theoretical analysis has been presented in convergence property. Extensive evaluations have been made to show that Chance-Choice outperforms several existing algorithms. Typically, comparing with Proportional Allocation scheme, it could decrease the load gap between the maximum and the minimal in system by 50% to 80% and reduce the overhead complexity from O(n) to O(1) comparing with the Max-weight Best Response algorithm, where n denotes the number of mobile users in a crowdsourcing system.