[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Strategic Social Team Crowdsourcing: Forming a Team of Truthful Workers for Crowdsourcing in Social Networks

Published: 01 June 2019 Publication History

Abstract

With the increasing complexity of tasks that are crowdsourced, requesters need to form teams of professional workers that can satisfy complex task skill requirements. Team crowdsourcing in social networks (SNs) provides a promising solution for complex task crowdsourcing, where the requester hires a team of professional workers that are also socially connected can work together collaboratively. Previous social team formation approaches have mainly focused on the algorithmic aspect for social welfare maximization; however, within the traditional objective of maximizing social welfare alone, selfish workers can manipulate the crowdsourcing market by behaving untruthfully. This dishonest behavior discourages other workers from participating and is unprofitable for the requester. To address this strategic social team crowdsourcing problem, truthful mechanisms are developed to guarantee that a worker's utility is optimized when he behaves honestly. This problem is proved to NP-hard, and two efficient mechanisms are proposed to optimize social welfare while reducing time complexity for different scale applications. For small-scale applications where the task requires a small number of skills, a binary tree network is first extracted from the social network, and a dynamic programming-based optimal team is formed in the binary tree. For large-scale applications where the task requires a large number of skills, a team is formed greedily based on the workers' social structure, skill, and working cost. For both mechanisms, the threshold payment rule, which pays each worker his marginal value for task completion, is proposed to elicit truthfulness. Finally, the experimental results of a real-world dataset show that compared to the benchmark exponential VCG truthful mechanism, the proposed small-scale-oriented mechanism can reduce computation time while producing nearly the same social welfare results. Furthermore, compared to other state-of-the-art polynomial heuristics, the proposed large-scale-oriented mechanism can achieve truthfulness while generating better social welfare outcomes.

References

[1]
D. C. Brabham, “Crowdsourcing as a model for problem solving: An introduction and cases,” Convergence: Int. J. Res. Into New Media Technol., vol. 14, no. 1, pp. 75–90, 2008.
[2]
C. C. Yang, J. Yen, and J. Liu, “Social intelligence and technology,” IEEE Intell. Syst., vol. 29, no. 2, pp. 5–8, Mar./Apr. 2014.
[3]
Q. Zhang, Y. Wen, X. Tian, X. Gan, and X. Wang, “Incentivize crowd labeling under budget constraint,” in Proc. 34th IEEE Conf. Comput. Commun., 2015, pp. 2812–2820.
[4]
S. Goto, D. Lin, and T. Ishida, “Crowdsourcing for evaluating machine translation quality,” in Proc. 9th Int. Conf. Language Resources Eval., 2014, pp. 3456–3463.
[5]
G. Goel, A. Nikzard, and A. Singla, “Mechanism design for crowdsourcing markets with heterogeneous tasks,” in Proc. 2nd AAAI Conf. Hum. Comput. Crowdsourcing, 2014, pp. 77–86.
[6]
D. Yang, G. Xue, X. Fang, and J. Tang, “Crowdsourcing to smartphones: Incentive mechanism design for mobile phone sensing,” in Proc. 18th Annu. Int. Conf. Mobile Comput. Netw., 2012, pp. 173–184.
[7]
A. Singla, E. Horvitz, P. Kohli, and A. Krause, “Learning to hire teams,” in Proc. 3rd AAAI Conf. Hum. Comput. Crowdsourcing, 2015, pp. 34–35.
[8]
B. Golshan, T. Lappas, and E. Terzi, “Profit-maximizing cluster hires,” in Proc. 20th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2014, pp. 1196–1205.
[9]
D. Zhao, X.-Y. Li, and H. Ma, “Budget-feasible online incentive mechanisms for crowdsourcing tasks truthfully,” IEEE/ACM Trans. Netw., vol. 24, no. 2, pp. 647–661, Apr. 2016.
[10]
Y. Chen, B. Li, and Q. Zhang, “Incentivizing crowdsourcing systems with network effects,” in Proc. 35th Annu. IEEE Int. Conf. Comput. Commun., 2016, pp. 1944–1952.
[11]
K. Han, H. Huang, and J. Luo, “Posted pricing for robust crowdsensing,” in Proc. 17th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., 2016, pp. 261–270.
[12]
H. Xiong, D. Zhang, G. Chen, L. Wang, V. Gauthier, and L. E. Barnes, “iCrowd: Near-optimal task allocation for piggyback crowdsensing,” IEEE Trans. Mobile Comput., vol. 15, no. 8, pp. 2010–2022, Aug. 2016.
[13]
Y. Han, T. Luo, D. Li, and H. Wu, “Competition-based participant recruitment for delay-sensitive crowdsourcing applications in D2D networks,” IEEE Trans. Mobile Comput., vol. 15, no. 12, pp. 2987–2999, Dec. 2016.
[14]
T. Voice, S. D. Ramchurn, and N. R. Jennings, “On coalition formation with sparse synergies,” in Proc. 11th Int. Conf. Auton. Agents Multiagent Syst., 2012, pp. 223–230.
[15]
F. Bistaffa, A. Farinelli, J. Cerquides, J. Rodríguez-Aguilar, and S. D. Ramchurn, “Anytime coalition structure generation on synergy graphs,” in Proc. 13th Int. Conf. Auton. Agents Multiagent Syst., 2014, pp. 13–20.
[16]
T. Wolf, A. Schröter, D. Damian, L. D. Panjer, and T. H. D. Nguyen, “Mining task-based social networks to explore collaboration in software teams,”. IEEE Softw., vol. 26, no. 1, pp. 58–66, Jan./Feb. 2009.
[17]
J. Chamberlain, “Groupsourcing: Distributed problem solving using social networks,” in Proc. 2nd AAAI Conf. Hum. Comput. Crowdsourcing, 2014, pp. 22–29.
[18]
M. Xiao, J. Wu, and L. Huang, “Community-aware opportunistic routing in mobile social networks,” IEEE Trans. Comput., vol. 63, no. 7, pp. 1682–1695, Jul. 2014.
[19]
I. Lykourentzou, A. Antoniou, Y. Naudet, and S. P. Dow, “Personality matters: Balancing for personality types leads to better outcomes for crowd teams,” in Proc. 19th ACM Conf. Comput.-Supported Cooperative Work Soc. Comput., 2016, pp. 259–272.
[20]
M. L. Gray, S. Suri, S. S. Ali, and D. Kulkarni, “The crowd is a collaborative network,” in Proc. 19th ACM Conf. Comput.-Supported Cooperative Work Social Comput., 2016, pp. 134–147.
[21]
T. Lappas, K. Liu, and E. Terzi, “Finding a team of experts in social networks,” in Proc. 15th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2009, pp. 467–475.
[22]
A. Anagnostopoulos, L. Becchetti, and C. Castillo, “Online team formation in social networks,” in Proc. 21st Int. Conf. World Wide Web, 2012, pp. 839–847.
[23]
S. Datta, A. Majumder, and K. V. M. Naidu, “Capacitated team formation problem on social networks,” in Proc. 18th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2012, pp. 1005–1013.
[24]
M. Kargar and A. An, “Discovering top-k teams of experts with/without a leader in social networks,” in Proc. 20th ACM Int. Conf. Inf. Knowl. Manage., 2011, pp. 985–994.
[25]
M. Kargar, M. Zihayat, and A. An, “Finding affordable and collaborative teams from a network of experts,” in Proc. SIAM Int. Conf. Data Mining, 2013, pp. 587–595.
[26]
S. Tang, “Profit-driven team grouping in social networks,” in Proc. 31st AAAI Conf. Artif. Intell., San Francisco, USA, February 4–9, 2017, pp. 45–51.
[27]
S. Rangapuram, T. Buhler, and M. Hein, “Towards realistic team formation in social networks based on densest subgraphs,” in Proc. 22nd Int. Conf. World Wide Web, 2013, pp. 1077–1087.
[28]
A. Ghosh, “Game theory and incentives in human computation systems,” Handbook of Human Computation. New York, NY, USA: Springer, 2013, pp. 725–742.
[29]
N. Nisan, “Algorithmic Mechanism Design,” in Proc. 31st Ann. ACM Symp. Theory Comput., 1999, pp. 129–140.
[30]
S. Dobzinski and N. Nisan, “Limitations of VCG-based mechanisms,” in Proc. 39th Annu. ACM Symp. Theory Comput., 2007, pp. 338–344.
[31]
Q. Liu, T. Luo, R. Tang, and S. Bressan, “An efficient and truthful pricing mechanism for team formation in crowdsourcing markets,” in Proc. IEEE Int. Conf. Commun., 2015, pp. 567–572.
[32]
Z. Pan, H. Yu, C. Miao, and C. Leung, “Efficient collaborative crowdsourcing,” in Proc. 13th AAAI Conf. Artif. Intell., 2016, pp. 4248–4249.
[33]
H. Jiang and S. Matsubara, “Efficient task decomposition in crowdsourcing,” in Proc. 17th Int. Conf. Principles Practice Multi-Agent Syst., 2014, pp. 65–73.
[34]
L. Tran-Thanh, T. D. Huynh, A. Rosenfeld, S. Ramchurn, and N. R. Jennings, “BudgetFix: Budget limited crowdsourcing for interdependent task allocation with quality guarantees,” in Proc. 13th Int. Conf. Auton. Agents Multiagent Syst., 2014, pp. 477–484.
[35]
M. Wright and Y. Vorobeychik, “Mechanism design for team formation,” in Proc. 29th AAAI Conf. Artif. Intell., 2015, pp. 1050–1056.
[36]
W. Wang, J. Jiang, B. An, Y. Jiang, and B. Chen, “Towards efficient team formation for crowdsourcing in non-cooperative social networks,” IEEE Trans. Cybern., vol. 47, no. 12, pp. 4208–4222, Dec. 2017.
[37]
Y. Jiang and J. C. Jiang, “Understanding social networks from a multiagent perspective,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 10, pp. 2743–2759, Oct. 2014.
[38]
K. Zhu and E. Hossain, “Virtualization of 5G cellular networks as a hierarchical combinatorial auction,” IEEE Trans. Mobile Comput., vol. 15, no. 10, pp. 2640–2654, Oct. 2016.
[39]
M. Daltayanni, L. de Alfaro, and P. Papadimitriou, “WorkerRank: Using employer implicit judgements to infer worker reputation,” in Proc. 8th ACM Int. Conf. Web Search and Data Mining, 2015, pp. 263–272.
[40]
Z. Wang, Y. Yin, and B. An, “Computing optimal monitoring strategy for detecting terrorist plots,” in Proc. 30th AAAI Conf. Artif. Intell, 2016, pp. 637–643.
[41]
S. Jagabathula, L. Subramanian, and A. Venkataraman, “Reputation-based worker filtering in crowdsourcing,” in Proc. 27th Int. Conf. Neural Inf. Process. Syst., 2014, pp. 2492–2500.
[42]
T. Lappas, E. Terzi, D. Gunopulos, and H. Mannila, “Finding effectors in social networks,” in Proc. 16th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2010, pp. 1059–1068.
[43]
C. Dangalchev, “Residual closeness in networks,” Physica A: Statist. Mech. Appl., vol. 365, no. 2, pp. 556–564, 2006.
[44]
D. S. Johnson, J. K. Lenstra, and A. H. G. Rinnooy Kan, “The complexity of the network design problem,” Netw., vol. 8, no. 4, pp. 279–285, 1978.
[45]
Y. Singer, “Budget feasible mechanisms,” in Proc. 51th Annu. IEEE Symp. Found. Comput. Sci., 2010, pp. 765–774.
[46]
A. Archer and É. Tardos, “Truthful mechanisms for one-parameter agents,” in Proc. 42nd IEEE Symp. Found. Comput. Sci., 2001, pp. 482–491.
[47]
F. Bergenti, E. Franchi, and A. Poggi, “Selected models for agent-based simulation of social networks,” in Proc. 3rd Int. Conf. Social Networks and Multiagent Syst. Symp., 2011, pp. 27–32.
[48]
L. Mashayekhy, M. M. Nejad, and D. Grosu, “A PTAS mechanism for provisioning and allocation of heterogeneous cloud resources, “IEEE Trans. Parallel Distrib. Syst., vol. 26, no. 9, pp. 2386–2399, Sep. 2015.
[49]
F. Brandt, “Group-strategyproof irresolute social choice functions,” in Proc. 22nd Int. Joint Conf. Artif. Intell., 2011, pp. 79–84.
[50]
W. Wang, Z. He, P. Shi, W. Wu, and Y. Jiang, “Truthful team formation for crowdsourcing in social networks,” in Proc. Int. Conf. Auton. Agents Multiagent Syst., 2016, pp. 1327–1328.

Cited By

View all
  • (2024)Privacy Preserving Task Push in Spatial Crowdsourcing With Unknown PopularityIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.343497835:11(2039-2053)Online publication date: 1-Nov-2024
  • (2023)Multi-Task Diffusion Incentive Design for Mobile Crowdsourcing in Social NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2023.331038323:5(5740-5754)Online publication date: 30-Aug-2023
  • (2023)Online Crowd Learning Through Strategic Worker ReportsIEEE Transactions on Mobile Computing10.1109/TMC.2022.317296522:9(5406-5417)Online publication date: 1-Sep-2023
  • Show More Cited By

Index Terms

  1. Strategic Social Team Crowdsourcing: Forming a Team of Truthful Workers for Crowdsourcing in Social Networks
      Index terms have been assigned to the content through auto-classification.

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image IEEE Transactions on Mobile Computing
      IEEE Transactions on Mobile Computing  Volume 18, Issue 6
      June 2019
      245 pages

      Publisher

      IEEE Educational Activities Department

      United States

      Publication History

      Published: 01 June 2019

      Qualifiers

      • Research-article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 24 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Privacy Preserving Task Push in Spatial Crowdsourcing With Unknown PopularityIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.343497835:11(2039-2053)Online publication date: 1-Nov-2024
      • (2023)Multi-Task Diffusion Incentive Design for Mobile Crowdsourcing in Social NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2023.331038323:5(5740-5754)Online publication date: 30-Aug-2023
      • (2023)Online Crowd Learning Through Strategic Worker ReportsIEEE Transactions on Mobile Computing10.1109/TMC.2022.317296522:9(5406-5417)Online publication date: 1-Sep-2023
      • (2023)Tensor-Empowered Federated Learning for Cyber-Physical-Social Computing and Communication SystemsIEEE Communications Surveys & Tutorials10.1109/COMST.2023.328226425:3(1909-1940)Online publication date: 1-Jul-2023
      • (2021)Enhancing the Quality in Crowdsourcing E-Markets Through Team Formation GamesIEEE Intelligent Systems10.1109/MIS.2020.298777936:4(13-23)Online publication date: 1-Jul-2021
      • (2021)Task assignment for social-oriented crowdsourcingFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-019-9119-815:2Online publication date: 1-Apr-2021
      • (2020)Content Delivery NetworksACM Computing Surveys10.1145/338061353:2(1-34)Online publication date: 17-Apr-2020
      • (2020)Template-driven team formationProceedings of the 12th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1109/ASONAM49781.2020.9381478(258-265)Online publication date: 7-Dec-2020
      • (2020)Robust keyword search in large attributed graphsInformation Retrieval10.1007/s10791-020-09379-923:5(502-524)Online publication date: 1-Oct-2020
      • (2019)Multimedia Crowdsourcing With Bounded Rationality: A Cognitive Hierarchy PerspectiveIEEE Journal on Selected Areas in Communications10.1109/JSAC.2019.291644837:7(1478-1488)Online publication date: 14-Jun-2019

      View Options

      View options

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media