Fairness-aware task assignment in spatial crowdsourcing: Game-theoretic approaches

The widespread diffusion of smartphones offers a capable foundation for the deployment of Spatial Crowdsourcing (SC), where mobile users, called workers, perform location- dependent tasks assigned to them. A key issue in SC is how best to assign tasks, e.g., the delivery of food and packages, to appropriate workers. Specifically, we study the problem of Fairness-aware Task Assignment (FTA) in SC, where tasks are to be assigned in a manner that achieves some notion of fairness across workers. In particular, we aim to minimize the payoff difference among workers while maximizing the average worker payoff. To solve the problem, we first generate so-called Valid Delivery Point Sets (VDPSs) for each worker according to an approach that exploits dynamic programming and distance- constrained pruning. Next, we show that FTA is NP-hard and proceed to propose two heuristic algorithms, a Fairness-aware Game-Theoretic (FGT) algorithm and an Improved Evolutionary Game-Theoretic (IEGT) algorithm. More specifically, we formulate FTA as a multi-player game. In this setting, the FGT approach represents a best-response method with sequential and asynchronous updates of workers' strategies, given by the VDPSs, that achieves a satisfying task assignment when a pure Nash equilibrium is reached. Next, the IEGT approach considers a setting with a large population of workers that repeatedly engage in strategic interactions. The IEGT approach exploits replicator dynamics that cause the whole population to evolve and choose better resources, i.e., VDPSs. Using the property of evolutionary equilibrium, a satisfying task assignment is obtained that corresponds to a stable state with similar payoffs among workers and good average worker payoff. Extensive experiments offer insight into the effectiveness and efficiency of the proposed solutions.