{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T16:33:03Z","timestamp":1783701183876,"version":"3.55.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Aalborg University Library"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>With the widespread use of networked and geo-positioned mobile devices, e.g., smartphones, Spatial Crowdsourcing (SC), which refers to the assignment of location-based tasks to moving workers, is drawing increasing attention. One of the critical issues in SC is task assignment that allocates tasks to appropriate workers. We propose and study a novel SC problem, namely Coalition-based Task Assignment (CTA), where the spatial tasks (e.g., home improvement and furniture installation) may require more than one worker (forming a coalition) to cooperate to maximize the overall rewards of workers. We design a greedy and an equilibrium-based CTA approach. The greedy approach forms a set of worker coalitions greedily for performing tasks and uses an acceptance probability to identify high-value task assignments. In the equilibrium-based approach, workers form coalitions in sequence and update their strategies (i.e., selecting a best-response task), to maximize their own utility (i.e., the reward of the coalition they belong to) until a Nash equilibrium is reached. Since the equilibrium obtained is not unique and optimal in terms of total rewards, we further propose a simulated annealing scheme to find a better Nash equilibrium. To achieve fair task assignments, we optimize the framework to distribute rewards fairly among workers in a coalition based on their marginal contributions and give workers who arrive first at the SC platform highest priority. Extensive experiments demonstrate the efficiency and effectiveness of the proposed methods on real and synthetic data.<\/jats:p>","DOI":"10.1007\/s00778-023-00802-3","type":"journal-article","created":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T11:01:58Z","timestamp":1688727718000},"page":"163-184","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Coalition-based task assignment with priority-aware fairness in spatial crowdsourcing"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0242-3707","authenticated-orcid":false,"given":"Yan","family":"Zhao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ziwei","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liwei","family":"Deng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bin","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Torben Bach","family":"Pedersen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,7,7]]},"reference":[{"issue":"13","key":"802_CR1","first-page":"1629","volume":"7","author":"Z Chen","year":"2014","unstructured":"Chen, Z., Fu, R., Zhao, Z., Liu, Z., Xia, L., Chen, L., Cheng, P., Cao, C.C., Tong, Y., Zhang, C.J.: gmission: a general spatial crowdsourcing platform. PVLDB 7(13), 1629\u20131632 (2014)","journal-title":"PVLDB"},{"key":"802_CR2","doi-asserted-by":"crossref","unstructured":"Cheng, P., Chen, L., Ye, J.: Cooperation-aware task assignment in spatial crowdsourcing. In: ICDE, pp. 1442\u20131453 (2019)","DOI":"10.1109\/ICDE.2019.00130"},{"issue":"8","key":"802_CR3","first-page":"2201","volume":"28","author":"P Cheng","year":"2015","unstructured":"Cheng, P., Lian, X., Chen, L., Han, J., Zhao, J.: Task assignment on multi-skill oriented spatial crowdsourcing. TKDE 28(8), 2201\u20132215 (2015)","journal-title":"TKDE"},{"issue":"10","key":"802_CR4","first-page":"1022","volume":"8","author":"P Cheng","year":"2015","unstructured":"Cheng, P., Lian, X., Chen, Z., Fu, R., Chen, L., Han, J., Zhao, J.: Reliable diversity-based spatial crowdsourcing by moving workers. PVLDB 8(10), 1022\u20131033 (2015)","journal-title":"PVLDB"},{"key":"802_CR5","doi-asserted-by":"crossref","unstructured":"Cui, Y., Deng, L., Zhao, Y., Yao, B., Zheng, V.W., Zheng, K.: Hidden poi ranking with spatial crowdsourcing. In: SIGKDD, pp. 814\u2013824 (2019)","DOI":"10.1145\/3292500.3330844"},{"key":"802_CR6","unstructured":"D., F., J., T.: Game Theory. MIT Press (1991)"},{"key":"802_CR7","doi-asserted-by":"crossref","unstructured":"Deng, D., Shahabi, C., Zhu, L.: Task matching and scheduling for multiple workers in spatial crowdsourcing. In: SIGSPATIAL, pp. 2101\u20132110 (2015)","DOI":"10.1145\/2820783.2820831"},{"issue":"6","key":"802_CR8","first-page":"2416","volume":"33","author":"L Deng","year":"2022","unstructured":"Deng, L., Lian, D., Huang, Z., Chen, E.: Graph convolutional adversarial networks for spatiotemporal anomaly detection. TNNLS 33(6), 2416\u20132428 (2022)","journal-title":"TNNLS"},{"key":"802_CR9","unstructured":"Fuat, B., Bugra, G., Hakan, F., Kun-Lung, W.: Fair task allocation in crowdsourced delivery. CoRR abs\/1807.02987 (2018). http:\/\/arxiv.org\/abs\/1807.02987"},{"key":"802_CR10","volume-title":"The Theory of Learning in Games","author":"D Fudenberg","year":"1998","unstructured":"Fudenberg, D., Levine, D.K.: The Theory of Learning in Games. MIT Press, New York (1998)"},{"key":"802_CR11","doi-asserted-by":"crossref","unstructured":"Gummidi, S.R.B., Pedersen, T.B., Xie, X.: Transit-based task assignment in spatial crowdsourcing. In: SSDBM, pp. 1301\u20131312 (2020)","DOI":"10.1145\/3400903.3400929"},{"key":"802_CR12","unstructured":"Jong, S.D., Tuyls, K., Verbeeck, K.: Artificial agents learning human fairness. In: AAMAS, pp. 863\u2013870 (2008)"},{"key":"802_CR13","doi-asserted-by":"crossref","unstructured":"Jong, S.D., Tuyls, K., Verbeeck, K., Roos, N.: Priority awareness: towards a computational model of human fairness for multi-agent systems. In: AAMAS, pp. 117\u2013128 (2008)","DOI":"10.1007\/978-3-540-77949-0_9"},{"issue":"1","key":"802_CR14","first-page":"1","volume":"1","author":"DE Kaufman","year":"1993","unstructured":"Kaufman, D.E., Smith, R.L.: Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. JITS 1(1), 1\u201311 (1993)","journal-title":"JITS"},{"key":"802_CR15","doi-asserted-by":"crossref","unstructured":"Kazemi, L., Shahabi, C.: Geocrowd: Enabling query answering with spatial crowdsourcing. In: SIGSPATIAL, pp. 189\u2013198 (2012)","DOI":"10.1145\/2424321.2424346"},{"key":"802_CR16","doi-asserted-by":"crossref","unstructured":"Kazemi, L., Shahabi, C., Chen, L.: Geotrucrowd: trustworthy query answering with spatial crowdsourcing. In: SIGSPATIAL, pp. 314\u2013323 (2013)","DOI":"10.1145\/2525314.2525346"},{"key":"802_CR17","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671\u2013680 (1983)","journal-title":"Science"},{"key":"802_CR18","doi-asserted-by":"crossref","unstructured":"Li, X., Zhao, Y., Guo, J., Zheng, K.: Group task assignment with social impact-based preference in spatial crowdsourcing. In: DASFAA, pp. 677\u2013693 (2020)","DOI":"10.1007\/978-3-030-59416-9_44"},{"issue":"4","key":"802_CR19","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s41019-020-00142-0","volume":"5","author":"X Li","year":"2020","unstructured":"Li, X., Zhao, Y., Zheng, K., Zhou, X.: Consensus-based group task assignment with social impact in spatial crowdsourcing. Data Sci. Eng. 5(4), 375\u2013390 (2020)","journal-title":"Data Sci. Eng."},{"key":"802_CR20","doi-asserted-by":"crossref","unstructured":"Li, Y., Zhao, Y., Zheng, K.: Preference-aware group task assignment in spatial crowdsourcing: a mutual information-based approach. In: ICDM, pp. 350\u2013359 (2021)","DOI":"10.1109\/ICDM51629.2021.00046"},{"key":"802_CR21","doi-asserted-by":"crossref","unstructured":"Liu, Y., Dong, L., Marks, R.J.: Common control channel assignment in cognitive radio networks using potential game theory. In: WCNC, pp. 315\u2013320 (2013)","DOI":"10.1109\/WCNC.2013.6554583"},{"issue":"1","key":"802_CR22","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1006\/game.1996.0044","volume":"14","author":"D Monderer","year":"1996","unstructured":"Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14(1), 124\u2013143 (1996)","journal-title":"Games Econ. Behav."},{"key":"802_CR23","volume-title":"Game Theory: Analysis of Conflict","author":"RB Myerson","year":"1997","unstructured":"Myerson, R.B.: Game Theory: Analysis of Conflict. Harvard University Press, New York (1997)"},{"issue":"1","key":"802_CR24","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"JF Nash","year":"1950","unstructured":"Nash, J.F., et al.: Equilibrium points in n-person games. Proc. Natl. Acad. Sci. 36(1), 48\u201349 (1950)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"802_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"N Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. MIT Press, New York (2007)"},{"key":"802_CR26","doi-asserted-by":"crossref","unstructured":"Song, T., Tong, Y., Wang, L., She, J., Yao, B., Chen, L., Xu, K.: Trichromatic online matching in real-time spatial crowdsourcing. In: ICDE, pp. 1009\u20131020 (2017)","DOI":"10.1109\/ICDE.2017.147"},{"key":"802_CR27","doi-asserted-by":"crossref","unstructured":"Tong, Y., She, J., Ding, B., Wang, L.: Online mobile micro-task allocation in spatial crowdsourcing. In: ICDE, pp. 49\u201360 (2016)","DOI":"10.1109\/ICDE.2016.7498228"},{"key":"802_CR28","doi-asserted-by":"crossref","unstructured":"Tong, Y., Wang, L., Zhou, Z., Chen, L., Du, B., Ye, J.: Dynamic pricing in spatial crowdsourcing: a matching-based approach. In: SIGMOD, pp. 773\u2013788 (2018)","DOI":"10.1145\/3183713.3196929"},{"issue":"11","key":"802_CR29","first-page":"1334","volume":"10","author":"Y Tong","year":"2017","unstructured":"Tong, Y., Wang, L., Zhou, Z., Ding, B., Chen, L., Ye, J., Xu, K.: Flexible online task assignment in real-time spatial data. PVLDB 10(11), 1334\u20131345 (2017)","journal-title":"PVLDB"},{"issue":"1","key":"802_CR30","first-page":"217","volume":"29","author":"Y Tong","year":"2020","unstructured":"Tong, Y., Zhou, Z., Zeng, Y., Chen, L., Shahabi, C.: Spatial crowdsourcing: a survey. PVLDB 29(1), 217\u2013250 (2020)","journal-title":"PVLDB"},{"key":"802_CR31","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2013","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2013)"},{"key":"802_CR32","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.neucom.2019.11.121","volume":"428","author":"Z Wang","year":"2021","unstructured":"Wang, Z., Li, Y., Zhao, K., Shi, W., Lin, L., Zhao, J.: Worker collaborative group estimation in spatial crowdsourcing. Neurocomputing 428, 385\u2013391 (2021)","journal-title":"Neurocomputing"},{"key":"802_CR33","doi-asserted-by":"crossref","unstructured":"Wang, Z., Zhao, Y., Chen, X., Zheng, K.: Task assignment with worker churn prediction in spatial crowdsourcing. In: CIKM (2021)","DOI":"10.1145\/3459637.3482301"},{"key":"802_CR34","doi-asserted-by":"crossref","unstructured":"Xia, J., Zhao, Y., Liu, G., Xu, J., Zhang, M., Zheng, K.: Profit-driven task assignment in spatial crowdsourcing. In: IJCAI, pp. 1914\u20131920 (2019)","DOI":"10.24963\/ijcai.2019\/265"},{"key":"802_CR35","doi-asserted-by":"crossref","unstructured":"Ye, G., Zhao, Y., Chen, X., Zheng, K.: Task allocation with geographic partition in spatial crowdsourcing. In: CIKM (2021)","DOI":"10.1145\/3459637.3482300"},{"key":"802_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.omega.2016.05.005","volume":"68","author":"QC Ye","year":"2017","unstructured":"Ye, Q.C., Zhang, Y., Dekker, R.: Fair task allocation in transportation. OMEGA 68, 1\u201316 (2017)","journal-title":"OMEGA"},{"key":"802_CR37","doi-asserted-by":"crossref","unstructured":"Zeng, Y., Tong, Y., Chen, L., Zhou, Z.: Latency-oriented task completion via spatial crowdsourcing. In: ICDE, pp. 317\u2013328 (2018)","DOI":"10.1109\/ICDE.2018.00037"},{"key":"802_CR38","doi-asserted-by":"crossref","unstructured":"Zhao, B., Xu, P., Shi, Y., Tong, Y., Zhou, Z., Zeng, Y.: Preference-aware task assignment in on-demand taxi dispatching: An online stable matching approach. In: AAAI, pp. 2245\u20132252 (2019)","DOI":"10.1609\/aaai.v33i01.33012245"},{"key":"802_CR39","doi-asserted-by":"crossref","unstructured":"Zhao, B., Xu, P., Shi, Y., Tong, Y., Zhou, Z., Zeng, Y.: Preference-aware task assignment in on-demand taxi dispatching: an online stable matching approach. In: AAAI, vol.\u00a033, pp. 2245\u20132252 (2019)","DOI":"10.1609\/aaai.v33i01.33012245"},{"key":"802_CR40","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Chen, X., Deng, L., Kieu, T., Guo, C., Yang, B., Zheng, K., Jensen, C.S.: Outlier detection for streaming task assignment in crowdsourcing. In: WWW (2022)","DOI":"10.1145\/3485447.3512067"},{"key":"802_CR41","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Guo, J., Chen, X., Hao, J., Zhou, X., Zheng, K.: Coalition-based task assignment in spatial crowdsourcing. In: ICDE (2021)","DOI":"10.1109\/ICDE51399.2021.00028"},{"key":"802_CR42","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Li, Y., Wang, Y., Su, H., Zheng, K.: Destination-aware task assignment in spatial crowdsourcing. In: CIKM, pp. 297\u2013306 (2017)","DOI":"10.1145\/3132847.3132894"},{"key":"802_CR43","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Xia, J., Liu, G., Su, H., Lian, D., Shang, S., Zheng, K.: Preference-aware task assignment in spatial crowdsourcing. In: AAAI, pp. 2629\u20132636 (2019)","DOI":"10.1609\/aaai.v33i01.33012629"},{"key":"802_CR44","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Zheng, K., Cui, Y., Su, H., Zhu, F., Zhou, X.: Predictive task assignment in spatial crowdsourcing: a data-driven approach. In: ICDE, pp. 13\u201324 (2020)","DOI":"10.1109\/ICDE48307.2020.00009"},{"key":"802_CR45","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Zheng, K., Guo, J., Yang, B., Pedersen, T.B., Jensen, C.S.: Fairness-aware task assignment in spatial crowdsourcing: game-theoretic approaches. In: ICDE, pp. 265\u2013276 (2021)","DOI":"10.1109\/ICDE51399.2021.00030"},{"key":"802_CR46","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Zheng, K., Li, Y., Su, H., Liu, J., Zhou, X.: Destination-aware task assignment in spatial crowdsourcing: a worker decomposition approach. In: TKDE, pp. 2336\u20132350 (2019)","DOI":"10.1109\/TKDE.2019.2922604"},{"key":"802_CR47","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Zheng, K., Yin, H., Liu, G., Fang, J., Zhou, X.: Preference-aware task assignment in spatial crowdsourcing: from individuals to groups. In: TKDE (2020)","DOI":"10.1109\/TKDE.2020.3021028"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00802-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-023-00802-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00802-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T20:15:32Z","timestamp":1729714532000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-023-00802-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,7]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["802"],"URL":"https:\/\/doi.org\/10.1007\/s00778-023-00802-3","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,7]]},"assertion":[{"value":"13 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}