Abstract
With the pervasiveness of mobile devices, wireless broadband and sharing economy, spatial crowdsourcing is becoming part of our daily life. Existing studies on spatial crowdsourcing usually focus on enhancing the platform interests and customer experiences. In this work, however, we study the fair assignment of tasks to workers in spatial crowdsourcing. That is, we aim to assign tasks, considered as a resource in short supply, to individual spatial workers in a fair manner. In this paper, we first formally define an online bi-objective matching problem, namely the Fair and Effective Task Assignment (FETA) problem, with its special cases/variants of it to capture most typical spatial crowdsourcing scenarios. We propose corresponding solutions for each variant of FETA. Particularly, we show that the dynamic sequential variant, which is a generalization of an existing fairness scheduling problem, can be solved with an O(n) fairness cost bound (n is the total number of workers), and give an O(n/m) fairness cost bound for the m-sized general batch case (m is the minimum batch size). Finally, we evaluate the effectiveness and efficiency of our algorithm on both synthetic and real data sets.
- [online] didi chuxing. https://www.didichuxing.com.Google Scholar
- [online] nyc taxi fare. https://www1.nyc.gov/site/tlc/passengers/taxi-fare.page.Google Scholar
- [online] taskrabbit. https://www.taskrabbit.com.Google Scholar
- [online] Eleme. https://www.ele.me.Google Scholar
- [online] Seamless. https://www.seamless.com/.Google Scholar
- [online] trip record data from nyc taxi and limousine commission. http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml.Google Scholar
- [online] uber. https://www.uber.com.Google Scholar
- [online] uber: How does uber match riders with drivers? https://marketplace.uber.com/matching.Google Scholar
- G. Aggarwal, Y. Cai, A. Mehta, and G. Pierrakos. Biobjective online bipartite matching. In International Conference on Web and Internet Economics, pages 218--231. Springer, 2014.Google ScholarCross Ref
- M. Ajtai, J. Aspnes, M. Naor, Y. Rabani, L. J. Schulman, and O. Waarts. Fairness in scheduling. Journal of Algorithms, 29(2):306--357, 1998. Google ScholarDigital Library
- A. Borodin and R. El-Yaniv. Online computation and competitive analysis. cambridge university press, 2005. Google ScholarDigital Library
- R. E. Burkard, M. Dell'Amico, and S. Martello. Assignment problems, revised reprint, volume 125. Siam, 2009. Google ScholarDigital Library
- P. Cheng, X. Lian, Z. Chen, et al. Reliable diversity-based spatial crowdsourcing by moving workers. PVLDB, 8(10):1022--1033, 2015. Google ScholarDigital Library
- P. Cheng, H. Xin, and L. Chen. Utility-aware ridesharing on road networks. In SIGMOD, pages 1197--1210, 2017. Google ScholarDigital Library
- D. Coppersmith, T. Nowicki, G. Paleologo, C. Tresser, and C. W. Wu. The optimality of the online greedy algorithm in carpool and chairman assignment problems. ACM Transactions on Algorithms (TALG), 7(3):37, 2011. Google ScholarDigital Library
- M. T. Emmerich and A. H. Deutz. A tutorial on multiobjective optimization: fundamentals and evolutionary methods. Natural computing, 17(3):585--609, 2018. Google ScholarDigital Library
- H. Esfandiari, N. Korula, and V. Mirrokni. Bi-objective online matching and submodular allocations. In Advances in Neural Information Processing Systems, pages 2739--2747, 2016. Google ScholarDigital Library
- R. Fagin and J. H. Williams. A fair carpool scheduling algorithm. IBM Journal of Research and development, 27(2):133--139, 1983. Google ScholarDigital Library
- M. Furuhata, M. Dessouky, F. Ordóñez, M. E. Brunet, X. Wang, and S. Koenig. Ridesharing: The state-of-the-art and future directions. Transportation Research Part B: Methodological, 57:28--46, 2013.Google ScholarCross Ref
- M. R. Garey and D. S. Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979.Google Scholar
- U. U. Hassan and E. Curry. A multi-armed bandit approach to online spatial task assignment. In UTC-ATC-ScalCom. IEEE, 2014. Google ScholarDigital Library
- L. Kazemi and C. Shahabi. Geocrowd: enabling query answering with spatial crowdsourcing. In SIGSPATIAL. ACM, 2012. Google ScholarDigital Library
- L. Kazemi, C. Shahabi, and L. Chen. Geotrucrowd: trustworthy query answering with spatial crowdsourcing. In SIGSPATIAL. ACM, 2013. Google ScholarDigital Library
- N. Korula, V. S. Mirrokni, and M. Zadimoghaddam. Bicriteria online matching: Maximizing weight and cardinality. In International conference on web and internet economics, pages 305--318. Springer, 2013. Google ScholarDigital Library
- S. Mneimneh and S. Farhat. The offline carpool problem revisited. In International Symposium on Mathematical Foundations of Computer Science, pages 483--492. Springer, 2015.Google ScholarCross Ref
- M. Naor. On fairness in the carpool problem. Journal of Algorithms, 55(1):93--98, 2005. Google ScholarDigital Library
- L. Pournajaf, L. Xiong, V. Sunderam, and S. Goryczka. Spatial task assignment for crowd sensing with cloaked locations. In MDM, volume 1, pages 73--82. IEEE, 2014. Google ScholarDigital Library
- T. Song, Y. Tong, and et al. Trichromatic online matching in real-time spatial crowdsourcing. ICDE, pages 1009--1020, 2017.Google Scholar
- R. E. Tarjan. Dynamic trees as search trees via euler tours, applied to the network simplex algorithm. Mathematical Programming, 78(2):169--177, 1997. Google ScholarDigital Library
- H.-F. Ting and X. Xiang. Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching. Theoretical Computer Science, 607:247--256, 2015. Google ScholarDigital Library
- H. To, G. Ghinita, and C. Shahabi. A framework for protecting worker location privacy in spatial crowdsourcing. PVLDB, 7(10):919--930, 2014. Google ScholarDigital Library
- H. To, C. Shahabi, and L. Kazemi. A server-assigned spatial crowdsourcing framework. ACM TSAS, 1(1):2, 2015. Google ScholarDigital Library
- Y. Tong, L. Chen, and C. Shahabi. Spatial crowdsourcing: Challenges, techniques, and applications. PVLDB, 10:1988--1991, 2017. Google ScholarDigital Library
- Y. Tong, L. Chen, Z. Zhou, H. V. Jagadish, L. Shou, and W. Lv. SLADE: A smart large-scale task decomposer in crowdsourcing. IEEE Trans. Knowl. Data Eng., 30(8):1588--1601, 2018.Google ScholarDigital Library
- Y. Tong, J. She, and et al. Online mobile micro-task allocation in spatial crowdsourcing. ICDE, pages 49--60, 2016.Google ScholarCross Ref
- Y. Tong, L. Wang, and et al. Flexible online task assignment in real-time spatial data. PVLDB, 10:1334--1345, 2017. Google ScholarDigital Library
- Y. Tong, L. Wang, Z. Zhou, L. Chen, B. Du, and J. Ye. Dynamic pricing in spatial crowdsourcing: A matching-based approach. SIGMOD, pages 773--788, 2018. Google ScholarDigital Library
- Y. Tong, Y. Zeng, B. Ding, L. Wang, and L. Chen. Two-sided online micro-task assignment in spatial crowdsourcing. IEEE Transactions on Knowledge and Data Engineering, 2019.Google Scholar
- Y. Tong, Y. Zeng, Z. Zhou, L. Chen, J. Ye, and K. Xu. A unified approach to route planning for shared mobility. PVLDB, 11(11):1633--1646, 2018. Google ScholarDigital Library
- Y. Tong and Z. Zhou. Dynamic task assignment in spatial crowdsourcing. SIGSPATIAL Special, 10(2):18--25, 2018. Google ScholarDigital Library
- Y. Tong, Z. Zhou, Y. Zeng, L. Chen, and C. Shahabi. Spatial crowdsourcing: a survey. The VLDB Journal, 29(1):217--250, 2020.Google ScholarDigital Library
- T. Uno. Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In International Symposium on Algorithms and Computation, pages 92--101. Springer, 1997. Google ScholarDigital Library
- D. P. Williamson. [online] section 3.1.1, lecture notes on network flow algorithms. https://people.orie.cornell.edu/dpw/techreports/cornell-flow.pdf, 2004.Google Scholar
- D. P. Williamson. Network Flow Algorithms. Cambridge University Press, 2019.Google Scholar
- Y. Zeng, Y. Tong, and L. Chen. Last-mile delivery made practical: An efficient route planning framework with theoretical guarantees. PVLDB, 13(3):320--333, 2019. Google ScholarDigital Library
- Y. Zeng, Y. Tong, L. Chen, and Z. Zhou. Latency-oriented task completion via spatial crowdsourcing. In ICDE, pages 317--328, 2018.Google ScholarCross Ref
- B. Zhao, P. Xu, Y. Shi, Y. Tong, Z. Zhou, and Y. Zeng. Preference-aware task assignment in on-demand taxi dispatching: An online stable matching approach. In AAAI Conference on Artificial Intelligence (AAAI 2019), 2019.Google ScholarCross Ref
Recommendations
Task Assignment with Worker Churn Prediction in Spatial Crowdsourcing
CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge ManagementThe pervasiveness of GPS-enabled devices and wireless communication technologies flourish the market of Spatial Crowdsourcing (SC), which consists of location-based tasks and requires workers to physically be at specific locations to complete them. In ...
Destination-aware Task Assignment in Spatial Crowdsourcing
CIKM '17: Proceedings of the 2017 ACM on Conference on Information and Knowledge ManagementWith the proliferation of GPS-enabled smart devices and increased availability of wireless network, spatial crowdsourcing (SC) has been recently proposed as a framework to automatically request workers (i.e., smart device carriers) to perform location-...
Comments