摘要论文：Rahman H, Roy S B, Thirumuruganathan S, et al. Task assignment optimization in collaborative crowdsourcing[C]//2015 IEEE International Conference on Data Mining. IEEE, 2015: 949-954.
许多新兴应用程序，例如合作文档编辑，句子翻译和公民新闻，要求具有互补技能和专业知识的工作人员组成小组并在复杂任务上进行协作。虽然现有研究已经调查了知识密集型众包的任务分配，但他们往往忽略了工人之间协作的方面，这对于此类任务的成功至关重要。行为心理学研究表明，大型团体阻碍了成功的合作。考虑到这一点，我们的工作是第一个调查和正式化工人之间的合作概念和现在的理论分析，以了解优化任务分配的硬度。我们提出了具有可证明的理论保证的高效近似算法，并通过使用真实世界和合成数据集的全面实验证明了我们的算法的优越性。最后，我们使用Amazon Mechanical Turk进行真实世界的协作句翻译应用程序，我们希望提供一个模板，用于评估基于微任务的众包平台中的协作众包任务。
简介：
协作众包，其中一组具有互补技能的工人组成团队并协作执行复杂的任务，如编辑，产品设计，民众科学被认为是下一代众包的关键组成部分[1]。协作在小组活动中的协同效应在社会心理学研究和传统的团队活动中被广泛接受。尽管具有巨大的潜力，但“合作”的变革效应仍未得到充分发掘。
协作人群的任务分配优化：任务分配优化的目标是通过为适当的工作人员分配适当的任务来最大限度地提高任务质量并最大限度地降低成本。这些复杂的任务通常是协作性的，要求具有互补技能的工人建立在彼此的贡献之上。除了描述个体工人的特征，即人为因素，如工人的技能和工资，我们还必须考虑各种基于团队的因素。从现有的社会心理学研究，我们已经确定了两个需要成功合作的关键因素。工人 - 工人的亲和力代表了在同一任务上一起工作的工人的“舒适程度”。成功的团队成员彼此之间具有高度的亲和力。低亲和力的团队往往生产率低，完成任务需要更长的时间。第二个因素是上临界质量，这是对群体规模的约束，超过这个群体，协作效力就会降低。在这项工作中，我们首次尝试将任务分配优化形式化，同时考虑到这些基于团队的因素以及个人因素。在认识到这些因素的情况下执行任务分配会影响许多众包应用，例如协作编辑，公民新闻，公民科学。
新颖性和挑战：群体大小的这一方面（形式化为上临界质量）使得我们的问题公式与这些先前的工作大不相同。因此，现有的团队形成解决方案无法解决我们的问题。事实上，我们提出的公式更复杂，计算更难。我们工作的另一个新颖贡献是设计涉及来自亚马逊 Mechanical Turk 的真正工作人员的实验，我们希望这些实验提供一个模板，用于评估基于微任务的众包平台中的协作众包任务。据我们所知，之前没有关于团队组建的工作已经努力进行这样的评估。
本文工作的主要贡献是：
- 我们开始调查协作众包的任务分配优化，并展示如何以原则方式结合基于团队的因素（如亲和力和上临界质量）。
- 我们分析了我们问题的计算复杂性，并提出了一个有原则的分阶段解决方案，我们开发了具有可证明边界的高效近似算法。
- 我们提供了一套全面的实验结果，包括一个真实的数据实验，涉及来自亚马逊机械土耳其人（AMT）的工作人员，证明了我们提出的解决方案的有效性，以及设计大规模合成实验。
我们选择句子翻译这一流行的写作众包应用程序做为研究协作优化的入手点。句子翻译是一项协作任务，因为它涉及纠正他人的错误并完成彼此的翻译。这种工作流程需要高亲和力才能获得高质量和稳定的翻译而无需编辑战争。我们进行相关的建模、算法分析和结果展示，对技能值，工资和成对亲和力等人为因素进行分析。并展示了每个域的最低技能和任务t的最大成本预算要求；以及上临界质量约束。提出了一个有原则的分阶段解决方案，并开发了具有可证明边界的高效近似算法Grp＆Splt。
因素建模：在这一部分中，我们介绍了复杂协作任务优化的三个因素的具体表示。
因素1（个人人为因素 - 技能和工资）众包环境中的个体工人以其技能和工资为特征。技能专业知识反映了工人的贡献为任务带来的质量。工资代表工人愿意完成任务的最低补偿金额。
因素2（基于群体的人为因素 - 亲和力）工人之间的亲和力是实现有效合作的关键因素。我们采用类似于社会网络中的群体形成的亲和力模型。其中亲和力在建模时分为成对亲和力、组内亲和力、组间亲和力。
算法和策略：
由于AffAware-Crowd是NP-Complete问题，我们提出了另一种策略，称为Grp＆Splt。Grp＆Splt将原始问题分解为两个阶段：在Grp阶段，形成满足技能和成本阈值的单个组，但忽略上临界质量约束。然后，在Splt阶段，我们将这个大组分成一组子组，每个子组满足上临界质量约束，使得所有对间距离的总和最小化。这是一种广泛使用的算法设计策略，用于解决难题。请注意，对于许多任务，Grp阶段本身可能已足够，我们可能永远不需要执行Splt。
Grp算法：问题Grp仍然是NP-Complete，减少类似于原始问题。我们提出了一个具有 2 近似因子的算法ApprxGrp，只要该距离满足三角不等式属性即可。
该算法依赖子程序GrpCandidateSet：该子例程的输入是一组n个工作者和一个任务t（特别是技能和t的成本约束），并且输出是满足技能和成本约束的工人组。我们使用有效的修剪策略来避免可能以更快的速度终止的不必要的计算。它计算一个表示可能的搜索空间的二叉树，考虑到任意顺序的节点，树中的每个节点都是一个工人u并且有两个可能的边（1/0，分别代表你是否包括在组中）。该树中的根到叶路径表示工作组。
近似算法ApprxGrp：我们提出了Grp的2 近似算法。主算法ApprxGrp考虑距离值的排序（升序）列表L（表示平台中可用工作者对之间的所有唯一距离）并对该列表执行二进制搜索。它调用一个子程序（GrpDia），其距离值α可以运行最多n次。在子程序内部，它考虑第i次迭代中的工人ui来检索以ui为中心的满足距离α的星形图，如下图所示：
星形的节点是工人，边缘是每个工作者对之间的距离，因此检索到的图形中没有边缘具有边缘>α。
其算法过程如下图：
我们使用真实数据和合成数据进行两种不同类型的实验。
真实数据的实验：我们使用协作句翻译（CST）作为应用程序，其任务是以三种语言（法语，泰米尔语和孟加拉语）生成英语视频的字幕。我们评估所提出的优化模型和亲和力计算技术的有效性以及上临界质量值的影响。该研究分三个阶段进行：工人概况分析；工人对任务的分配；任务评估：完成的任务再次众包，以评估其质量。共有120名AMT工人参加了CST。雇佣的工作人员将被引导至Google文档以执行任务。
合成数据的实验：我们使用IBM CPLEX 12.5.1为ILP在具有6 GB RAM的Intel核心I5机器上进行合成数据实验。我们使用了一个用Java实现的人群模拟器来生成一个真实的众包环境，我们的算法在这个环境中进行了评估。模拟运行14400个模拟单元，最多5000名工人。我们使用正态分布（均值为0.8和方差0.15）对工人概况（技能，工资）进行建模。我们使用欧几里德距离来测量亲和力。临界质量的默认值为7.同样，任务质量和成本也使用15和方差1的正态分布生成。我们将工人和任务到达建模为泊松过程，到达率μ为每分钟5和1每10分钟一次。
实验结果：真实数据实验总结：我们观察到有效协作对于确保协作复杂任务的高质量结果至关重要，结果展现了亲和区域产生高正确性和完整性。上临界质量K似乎在CST中起重要作用。当K = 10时，质量从K = 5增加到K = 7并且随着统计显着性而降低。我们观察到更多的工作者通过撤消彼此的编辑来引发编辑战争。
合成数据实验总结：由于空间不足，我们提供了从实验中收集的关键见解。首先，Grp＆Splt被证明是一种合理的替代方案，可以在质量和效率方面解决AffAware-Crowd，因为整体ILP不具有可扩展性，并且不会超过20名工人。其次，我们提出的Grp＆Splt 近似算法既高效又有效，并且明显优于其他竞争对手。最后，我们提出的 AffAware-Crowd是优化复杂协作编辑任务的有效方法。
结论：在本文中，我们研究优化“协作”，这种协作自然适合许多复杂的人类密集型任务。我们调整对复杂协作任务至关重要的各种基于个人和群体的人为因素，并提出一组优化目标。我们提供严格的分析来理解所提出问题的复杂性，并提出一系列具有可证明保证的有效算法。 最后，我们使用真实世界的应用程序和合成数据进行详细的实验研究。
本文主要贡献：本文通过调查和正式化工人之间的合作概念和相关理论分析，开发了一套用于评估基于微任务的众包平台中的协作众包任务的模板。本文的主要贡献在于（1）调查协作众包的任务分配优化。（2）分析问题的计算复杂性，并提出了一个有原则的分阶段解决方案，开发了具有可证明边界的高效近似算法。（3）提供了一套全面的相关实验和实验结果。
致谢本转述工作部分得到国家重点研发计划“信息产品及科技服务集成化众测服务平台研发与应用 (2018YFB1403400)”资助
