《基于多Agent技术的异质社会网络群组形成方法研究_王万元_第二章基于激励相容机（17）.docx》由会员分享，可在线阅读，更多相关《基于多Agent技术的异质社会网络群组形成方法研究_王万元_第二章基于激励相容机（17）.docx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章基于激励相容机制的社会网络群组形成 第二章基于激励相容机制的社会网络群组形成 社会网络环境下群组形成的主要目标是建立专业的，社会关系紧密的并且工作成本个体 群组。然而如果系统仅仅关注这些目标，一些社会个体可能会提供一些虚假的私人信息来恶 意攻击系统，譬如夸大自身的专业技能，社会合作关系以及工作成本，来提高自身报酬。这 种不诚实的行为不仅会增加任务请求者完成任务的预算，而且会减少诚实个体获得任务的机 会，进而可能导致群组形成失败。基于此，本文致力于设计激励相容机制来保证社会个体在 诚实的提供他们私人信息的情况下能够获得最多的报酬。本章节首先从理论上分析了该激励 相容机制的正确性，然后通过实
2、验验证了该机制不仅能够产生可观的社会效益，同时适用于 大规模的群组形成应用。 2.1引言 i 群组形成，不仅能够在完成任务效率方面优于单独个体，甚至能够完成单独个体所不能 完成的任务。例如在最近兴起的众包 （ Crowdsourcing)应用中 106，任务请求者通常希望 招募由若干个工人组成群组（在本文中，术语 “ 个体 ” ， “ 工人 ” 以及 “ 用户 ” 意思相同）来 提高任务完成成功率以及质量，包括提高图片标注正 确率 107，语言翻译正确率 149以及 产品评价客观性 150。另外，有些任务本身需要具有多种不同专业技能的工人合作才能完成， 譬如为了满足软件项目开发的多样化技能需求
3、，任务请求者需要招募到一组具有需求分析， 代码实现，调试和数据分析等不同技能的工程师团队 41-42。然而任务能否成坊的完成，不 仅取决于群组成员是否具有相关的专业技能，同时也取决于群组成员能否高效的合作 27。 例如在软件项目开发应用中，执行测试任务的工程师需要和执行程序实现的工程师不断的进行交 流和调试来优化软件。如果由于工作 风格的不同或者地理位置相距较远不方便交流等原因导致他 们不能高效的合作，该团队将很难按时完成软件开发任务。所以，如何建立一组专业的、合作高 效的群组是任务请求者面临的一个非常重要的问题。 随着社交软件的广泛使用，社会网络给专业的、合作高效的群组形成带来了新的机遇。
4、一方面，社交网络平台每时每刻都会有成千上万的活跃用户，这些具有相关专业技能的用户 可以帮助任务请求者随时随地建立专业的群组 108。另一方面，用户之间积极的社交关系可 以代表一种高效合作性指标 16, 27。例如，在开源软件项目开发网站 Github上，互相连接 的用户可能曾经共同合作过开源项目。这种具有项目合作经历的工人可能在共同完成新的任 务时合作更加高效 28。受社会网络的上述两种优势的驱动，我们考虑在社会网络环境下形 成专业并且合作高效群组来完成任务请求者的任务，其中专业性是指群组工人能够满足任务 的所有技能需求，高效合作性是指群组成员紧密连接从而使得他们能够高效的进行合作协调。 社会
5、网络环境下群组形成可以通过一个反拍卖模型实现。在该模型下，任务请求者首先 9 东南大学博士学位论文 通过在线众包平台（譬如 Amazon Mechanical Turk1, Guru2， Upwork3以及 Linkedln)发布任 务所需要的技能。然后工人开始竞标获得完成任务的机会，竞标的内容包括该工人可以提供 的技能服务，工作报酬以及邻居工人（即能够高效合作的同伴）。基于工人的竞标信息，众包 平台为任务请求者建立最经济的（即能够产生最大社会效益的群组），专业的并且合作高效的 工人群组。然而，如果众包平台仅仅考虑到最大化社会效益这一目标，一些工人可能会通过 竞标虚假的信息来提高他们自身的收益
6、，例如，工人可能通 过夸大自身的专业技能，社会合 作关系以及工作成本来提高获得更髙报酬的可能性 87。这种不诚实性行为，一方面可能减 少哪些诚实提供私人信息的工人受聘机会；另一方面，这种提高工作成本的欺骗行为同样会 增加任务请求者完成任务的预算。社会网络环境下的群组众包应用，如果没有足够的工人参 与并且完成任务的成本高，最终会导致群组形成的失败 109。因此，设计激励相容机制来保 证每个工人都诚实的提供他们的私人信息对于社会网络环境下的群组众包应用的健壮发展是 非常有必要的 110。 然而直接运用传统的社会网络群组形成方 法 16, 27, 30, 54-56, 59, 62是不可行的， 因为
7、这些方法不能够保证工人的诚实性。直接运用传统的以建立最优工人群组为前提条件并 且能够保证工人诚实性的 VCG(Victory-Clarke-Groves)机制 111-113也是不可行的，因为形 成专业的、合作高效的群组问题是 NP难问题，建立最优群组需要指数级 O(W)的计算复杂度， 这里代表工人数目，大代表任务所需要的技能数目。基于此，我们提出两种低计算复杂度 激励机制来解决不同规模的社会网络群组形成应用。对于任务规模较小的群组形成应用，本 章提出一种固定参数 （ fixed-parameter)计算复杂度为 0(24fc)的激励机制。该机制首先将社会 网络转换成二叉树网络，然后在该二叉树
8、网络上利用动态规划方法形成最优工人群组。对于 任务规模较大的群组形成应用，本章提出一种基于贪心思想的多项式 0(P)计算复杂度机制。 该机制根据工人的社交结构和技能来建立合适的可行性群组。本章最后利用真实众包网站中 工人和任务数据来验证本章提出的机制性能。实验结果表明了固定参数机制产 生的社会效益 非常接近经典的 VCG机制产生的社会效益，并且贪心机制能够在损失少量社会效益的同时能 够较好的扩展到大规模应用中。 2.2问题描述 任务 d壬务请求者首先发布任务请求 r=， 其中 FT表示如果任务 r能够成功完成， 任 务 请求者将会获得的经济收益；表示任务 r所需要的技能，例如 java编程和
9、数据分析等技能。我们用表示任务的规模，即 所需要的技能数目，这里函数 w表示 集合 X的基数。 社会网络 :我们用 SN=表示社会网络系统，其中 = /, 2,., 表示工人集合，二元 组 e五 表 示 工 人 和 q之间存在高效合作关系。每个工人可以通过三元组 表 1 2 3 10 第二章基于激励相容机制的社会网络群组形成 示，其中兄 .eCV表示工人拥有的技能，换言之，如果技能 尺 .，那么工人能够提供技能 服务印成本变量 C,表示工人 被招募并且提供技能服务的最低薪酬（即工作成本），譬如， 一个工人一旦被雇佣（不管该工人提供哪些技能服务），任务请求者可能需要支付给该工人每 小时 $
10、20薪水； M表示工人 ,.能够高效合作的同伴，换言之，幻。接下来我们 将通过一个反拍卖模型具体描述众包平台如何构建该社会网络系统 SN。 基于反拍卖的社会网络群组形成模型： 该模型可以概括如下：任务请求者首先向所有的 工人发布任务技能需求 Or,然后每个工人提交他们各自的竞标标 5,.= (， c,， M),其中尺 ，说， .,以表示个体 能够提供的技能服务， C，表示提供这些技能服务 &的最低薪酬要求， M表示他的邻居合作伙伴。任务请求者收集到工人提供的竞标信息后，就可以构建整个社会 网络网络系统，包括工人拥有的技能服务，社会合作关系以及薪酬要求。这些信息都是由工 人自身决定的，可能并不一
11、定代表工人真实的私人信息，设计激励相容机制的目标就是使得 每个工人真实的提供他们的私人信息兄，和 M。 我们用从 =(咖表示激励相容机制，其中群组形成函数 1=;2， .表示工人是否被 选为群组成员，其中 x； =l， 表示工人 a,被选中， x/=0表示未被选中。我们用集合 表示被选中的群组工人。为了能够成功的完成任务乃形成的群组 S必须满足下壶两个条件 . 1)专业性 ：任务的每个技能需求必须至少能被一个工人满足，换言之，队 30疋； 2)高效合作性： 在群组 0中，每个群组工人必须有至少一个邻居同伴在该群 组中，即由群组工人 2组成的子网络必须是连通的。报酬函数 P,p2， .,外 表示
12、任务完 成后，支付给每个工人的报酬。对于那些被选中的群组工人该工人的净收益的可以表 示为获得的报酬 A和技能服务成本 c,之间的差值，即在工人真实的提供私人信息情 况下的也等于内 -c,。 而对于那些未被选中的工人办他们的净收益斤。当任务成功的完成 并且工人报酬己经支付，那么任务请求者获得的净收益则为任务自身产生的收益 &和完成任 务所要支付给群组工人报酬之间的差值，即 我们进一步定义系统的社会效益 （ Socia丨 Welfare, 5TF)为任务请求者的收益与工人的收 益之 和 等 同 于 任 务 完 成 收 益 6 与 被 选 中 群 组 I人薪酬 i要求的差值， 即 = 6 - 本 文
13、 主 要 考 虑 社 会 效 益 最 大 化 目 标 ， 接 下 来我们将形式化社会网络下群组形成问题。 定义 2. 1社会网络群组形成问题 （ Social Team Formation Problem, STFP)。 给定任务 r=,工人竞标信息 S= 尽， 52,. .A和以工人竞标信息建立的社会网络系统 SN=， 社会网络群组形成问题希望建立能够最大化社会效益的、专业的、合作高效的工人群组 2， 形式化表示为 Maximize fVr (21) 受限于 yu = x,ys; e - 1SJ e T (2_2) 11 东南大学博士学位论文 x, +xj-r,wr /=1表示能够提 供，
14、&= 表示不能提供。约束条件 （ 2-3) - (2-5)目标建立连通的工人群组使得他们能够高 效的合作完成群组任务。在约束 （ 2-3)中，表示工人仍和 之间的合作关系 (办巧 )被选 中当且仅当这两个合作伙伴和巧被选为群组成员。在约束 （ 2-4)中， w,表示工人 a,是否 是群组中拥有最小下标的工人， w,=l表示是，叫 =0表示不是。对于拥有最小标号的群组工人 即我们称该工人为根节点工人，如果始终存在一条连接路径顺着从 &可以到达任 意其他被选中的节点卜那么建立的群组是连通的。约束条件 （ 2-5)表示，一个工 人能够被被选中，那么对于任意一个包含根节点工人的集合 *S， 当前仅当该
15、工人满足下面两 个条件之一 （ 1)所有被选中的工人 加尸 1包含在 中（即 /心 4)=丨），要么至少存在一条割边 (aH,av)e%S)在这些被选中的工人节点中。函数 /CS， 為 ) 定 义 如 下 ： 如 果 那 么 , 否 则 。 然 后 ，函 数 表 示 被 割 集 （ &4以 ） 断 开 的 边 ， 即 ，对于任 意其 他 的 竞 标 信 息 并 且 对 于 任 意 的 其 他 工 人 竞 标 信 息 可 以 得 到 那么该社会网络群组形成机制是激励相谷的。 对于这种单参数的机制设计问题，其中每个工人 ， 只有工作成本 c， 私人信息，机制 是激励相容的当前仅当社会群组形成函数
16、X是单调的并且支付函数 P吵是基于阈 值支付的 114。 定义 2.3单调的群组形成函数和阈值支付函数 ：群组形成函数义是单调的，当且仅当对 于任意的工人及其工作成本 c , ,，如果 x,(B,， 5-,)=l,那么； e/尽，凡 ,户 1，其中及 夺 =。阈值支付函数则要求支付给工人化的报酬灼是免所能竞标的并且能够被 选中的最高报价，即乃足 ,)=1。 Victory-C丨 arke-Groves (VCG)机制的缺陷 ：对于高效的激励相容机制 M=(X， /V),除 了要满足激励相容性，还要满足群组形成函数 X和支付函数都是计算可行的。因此，传 统的 VCG机制 115，以最大化社会效益
17、为前提条件来设计阈值支付函数满足激励相容性， 是计算不可行的因为社会网络群组形成问题 STFP是 NP难的。我们可以将带权的集合覆盖问 题 116规约到简化的社会网络群组形成问题 STFP， 其中社会网络是全连通的。事实上，即 使利用当前最先进的群组形成技术 65，都要花费指数级别 0 /)的时间开销形成最优群组。 该方法在任务规模 5,网络规模 60的问题规模下是计算不可行了。基于此 ,t沐章 2. 3节 和 2. 4节分别提出了两种适用 于一般问题规模和任意问题规模的激励相容机制。 2. 3面向小规模任务的社会网络群组形成机制 面向小规模任务的群组形成机制的主要思想如下：给定社会网络系统
18、SN,我们不直接在 该社会网络 SN中建立最优群组，而是首先将该社会网络转换成二叉树网络，然后在该二叉 树网络中设计出固定参数的群组形成机制。在计算复杂度领域 116，一个依赖于参 数的指数级复杂度算法，如果灸是固定、较小值的数，而且该算法的时间复杂度随着的 变化增长比较小，那么该算法仍然是计算可行的。 2. 3.1树网络结构抽取 给定社会网络系统 SN， 我们目标是从 SN中抽取出一棵树网络 r,并且能够保证该树网 络尽可能的保留原社会网络 SN中的合作关系信息。直观的讲，我们目标是这样的，在原社 会网络 SN中，如果两个工人是紧密相连的，那么在抽取的树网络 r中，这两个工人仍然要 13 东
19、南大学博士学位论文 算法 2.1树网络结构抽取 （ Tree Extraction,/) 输入：社会网络 输出：树网络 r。 a=0, chj max=Q; fordo 3. 计算印的紧密度 d(知 SN户成 ASN); 4. If CLiaSNmaXy then max=CL(ai,SN)f ar-an end for 6 7 8 r=ruar； while A0 do for Va,A: da r,a)=d do A=A-ai), rrUla/, d=dv /*在树 r中，工人 ai的双亲节点是从心到 1 丨最短路径 (.爪 1瓜 上丨的上一个节点 ai-n */ 10. end for
20、11. end while 紧密相连。保留这些合作关系信息使得我们仍然能够在树网络 r中，形成专业的、合作高效 的群组。基于社会网络科学的相关定义 117，我们首先定义网络和工人节点的社会合作紧密 度。 定义 2. 4网络紧密度和工人节点紧密度： 给定社会网络 SN=,我们目标从 SN中抽取树结构 网络 r，使得 r尽可能多的保留原网络 SN中的社会合作关系信息，即最小化 |cx(SN)-cx(r)|。 不难发现，在网络 SN中删除一条合作连接不会增加网络紧密度，那么我们可以得到 CL(SN它 cz(r)。 树结构抽取问题也就等同于从 SN中抽 取出一颗最优树亡使得尸的紧密度最 大，即 rka
21、rgmaXrCZ(r)。 这种树网络紧密度最大化问题是一个经典的 NP难网络设计问题的 变种 115。但是传统的网络设计问题 118与树网络结构抽取的目标不同，所以他们的方法 并不适用。基于此，我们提出了一种多项式时间的近似树结构抽取算法，具体参考算法 2.1. 在算法 2.1，步骤 2-5中，我们目标找到树网络 r的根节点。在步骤 3中，对于每个节点印， 我们首先计算该节点的紧密度 CX(a,， SN)。在步骤 6中，我们选择拥有最大紧密度节点 &为树 r的根节点。然后，在步骤 7-U中，我们采用广度优先搜索策略来建立树 r:首先将与 &社 4如果 4和 是不连通的，那么 J(化外 SN)=
22、0, 1/成叫力 SN)可以赋值为一个较大的实数。 14 第二章基于激励相容机制的社会网络群组形成 图 2.1(a)-(b):将社会网络 （ a)转换成树网络 （ b); (b)-(c):将树网络 （ b)转换成二叉树 （ c) 会合作距离为 1的节点加入到 a； 的第一层孩子节点集合 Ozl中，即 VoieC/jl,成弘 SNM。 然后，将与外社会合作距离为 2的节点加入到 &的第二层孩子节点集合 CA2中。对于第二层 中孩子节点 aieC7i2， 他的双亲节点就是沿着 &到 a;的最短路径上 a,.的钱一个节点，也就是 说，在原网络 51中，如果 &到印 .的最短路径为 办 ,.,取 ;,
23、以，那么印在树中的双亲节点就 是化 /。我们持续利用这种广度优先构造树程序直到所有节点都被加入到树 r中（步骤 7)。 接下来，我们分析一下算法 2.1的近似度。 定理 2.1:用 cz(r) 和 分 别 表 示 由 近 似 算 法 2.1和最优算法得到的树结构网络紧密 度。那么，算法 2.1的近似度 cz(r)/cz(rvai),其中变量 D表 示 原 网 络 的 直 径 ， 即 Z max/ a,為 .， SN)。 证明 :用符号 r和 &分别表示算法 2. 1 得 到 的 树 结 构 及 其 根 节 点 。 用 式 和 分别表示节点和 在原网络 SN和树 r中的最短距离。在树 r中，每个
24、不同于 的节点 到所有其他节点的最短距离满足： l- - - ( - + - ) (2-7) d(a丨 ,aj,F) d(at,ar,r) + d(ar,arr) 2D + 2 danar,Y) dar,apT) 式 （ 2-7) 中 第 二 个 不 等 式 成 立 是 因 为 办 ， r),成 &， +r： D。 那么节点 a,在树 r中的紧密 度满足 CL(ai,D = a 1 n-2 +CL(ar,T) diaaY) 2D+ 2 d(anar,T) 其中表示原网络 SN中工人数目。现在我们可以得出树 r的紧密度为 : n-2 cz( )=iu(,， r) 2D + 2 2Z) + 2 2
25、(n-)CLar,Y) (Z a- danarS) (n-)CL(ar,D D + l + nCL(ar,F) (2-8) (2-9) 另一方面，对于最优的树结构尸，我们有如 ,SN)sCL(r)， 其中第二个不等 式可以从算法 2. 1 直接得到， g卩 CL(ar,r)=CZ(flr， SN)并且 SN)SC7： (ar， SN)。 最后， 我们可以得到算法 2.1的近似度 cx(rycz(r(-i)/(D+i)j足够大时近似等于 I/(ZHI)。 图 2. 1 (a)和 2. 1 (b)直观的描述了算法 2. 1如何从从一个社会网络 SN抽取出树网络 r。 抽取出树网络 r之后，下一步我
26、们将用动态规划的方法在该树 r中建立最优的群组。动态规 15 东南大学博士学位论文 划的主要思想可以概括如下：对于根节点 &及其所有 &子孙节点，主要考虑下面两种选择情 况。第一种情况，不选择节点办作为群组成员。在这种情况下，我们需要从 &的孩子树中， 即中建立群组来满足任务 r的技能需求，其中办是叫的孩子节点。在本章中，树 r，表示 为由根节点 ,和所有印子孙节点构成的树网络。例如，图 2.1(13)中， 12= 2, 6, 7,8。第二 种情况，根节点 &被选为群组成员。在这种情况下，我们需要将剩余的未被满足的技能丨凡 以最优的方式分配到外的孩子树中。然而，找到这种最优划分需要的计算复杂度
27、，其中 /是根节点 &的孩子节点数目。显然，这种昂贵的时间开销将导致动态规划算法失效。为了 减少技能划分的计算复杂度，在下一章节，我们尝试将任意的树网络 r等同的转换成二叉树 网络在二叉树中，每 个节点只有两个孩子节点。 2. 3. 2二叉树转换 我们通过以下步骤将一般的树网络 r转换成二叉树网络卩。我们从一般树网络 r的根节 点 开始操作，假设办拥有 / (2)个 孩 子 节 点 我 们 用 深 度 为 l g2/| + l, 以办 为根节点， 1,电 .沖 为叶子节点的二叉树来代替原树 r中节点和丨叫 , 2， .,， 。在构造的 二叉树卩中，根节点 &和叶子节点 丨，仍， .,印 之间新
28、增加的辅助节点既没有任何技能也不没 有任何工作成本。另外，一旦这些辅助节点的双亲节点被选中，那么这些节点也都会被选中。 我们对树 r中所有其他的非叶子节点重复这种二叉树构造操作之后，最终就会得到包含所有 工人节点的二叉树卩。图 2. 2 (b)和 2. 1 (C)直观的展示了如何将一般树网络转换成二叉树的。 这种二叉树构造具有两个比较好的性质： 1)二叉树卩中新增加的辅助节点数目是有限的； 2) 二叉树卩在最大化社会效益方面等同于原一般树 r的社会效益。下面我们具体说明这两个性 质。 引理 2.1:对于拥有个节点的一般树网络 r， 那么其对应的二叉树的节点数目至多为 3。 证明： 对于树 r中
29、 的 任 意 节 点 假 设 该 树 r拥有，个孩子节点，那么我们至多需要增 加 辅 助 节 点 。 因 此 在 二 叉 树 卩 中 ， 总 共 需 要 增 加 的 辅 助 节 点 数 目 至 多 为 其 中 撕 表 示 树 r中非叶子节点数目。因此，转换的二叉树卩的总节 点数至多为 2+n=3。 口 引理 2.2:在树 r中最大化社会效益的最优群组等同于在卩中最大化社会效益的最优群 组。 这是因为在二叉树卩中新增加的辅助节点的数目不提供任何技能，并且一旦他们的双亲 节点被选为群组成员，他们也同样会被选为群组成员，并且不要求任何报酬。 2. 3.3二叉树网络中的最优激励相容机制 在本章节，我们
30、将提出在二叉树网络卩中最优的群组形成机制 M=，其中群组形 成函数X是基于动态规划的最优群组形成机制，支付函数 /是阈值支付函数。 16 第二章基于激励相容机制的社会网络群组形成 算法 2. 2面向小规模应用的社会网络群组形成机制设计 （ OPT-Tree) 输入：社会网络 SNzc ， 工人竞标信息 A和任务所需技能 CV= 输出 ：群组 ,社会效益和工人报酬 P呼。 1. rr)， W(fl,， l， Or)。 我们分别用和分别表示动态规划算法得到的最优群组及其社会效益，那么对于任 意被选中的节点 a,基于 VCG机制，支付给，的报酬为： A : (%+0 - max(H 17 (2-12
31、) 东南大学博士学位论文 其中 =VT-I s表示群组 21的效益，表示在印的右子树 rf(fli)中形成的 rria,) 最优群组。同样的 ， w =F -y e表示在左子树 ra)中形成的最优群组的效益。 K-,、 T J 然后 表示在树中形成的最优群组的社会效益。该树 rG是 通过在原二叉树卩中删除掉子树 r; 得 到 的 。 最 后 ， 变 量 表 示 在 不 考 虑 节 点 的技能 报酬的情况下，原二叉树卩中的最优群组的社会效益。需要注意的是，支付给节点 fl,的报酬 A是能够竞标的最高的并且仍然能够被动态规划算法选中的薪酬标准。这是因为，如果 fl, 薪酬标准报价超过内，那么动态规
32、划算法肯定能在树 rfw， 或者 rfl 建立一个不包括 的社会效益更高的群组，并且该群组不包含节点 ,。 最后，算法 2.2 (OPT-Tree)给出正式的面向小规模应用的群组形成机制设计。接下来， 我们分析算法 OPT-Tree的计算复杂度和激励相容性。 定理 2.2:给定社会群组形成问题，其中任务需要 克 个服务技能并且社会网络系统拥有 个工人，那么算法 OPT-Tree的计算复杂度为 024k)。 证明 ：算法 OPT-Tree的计算开销主要包含在两个部分：步骤 1-3,利用动态规划求解最 优群组形成函数 X和步骤 5 - 8,计 算 工 人 报 酬 函 数 在 求 解 Z的过程中，对
33、于每个工人 需要考虑到2： =0(2幻种可能的技能组合来计算如何将技能集合最优的分配到 的左孩子树和右孩子树中。此外，求解 X需要建立一个 23的表格，表格中的每个元素 用来存储三种变量：决策变量 ;c,决定是否选中该工人为群组成员，每棵子树 的最优社会效 益奶 ， 1,或啊 &0,)和对技能 /的最优划分。因此，求解群组形成函数 X的计算复杂度为 0(3_2，工人竞标信息 心 .，凡丨和任务所需技能 输出：群组 2,社会效益 。 1. 初始化根节点乂 = argmaxfl ， & ); 2. 创建群组队列 Queue(0; 3. 将根节点 ar加入到群组 2中， 0尸 4. 5. 6. 7.
34、 4. 9. 10 while 70 do for Vaj&Q do 1 = UflEg ax axeNi n(ax, ) 0； end for a = argmax0e/ ,Or ) ； 将新成员 ,加入 il卩入到群组 0中 , end while 2. 4.1基于贪心的群组形成算法 通过分析发现，社会网络群组形成问题属于网络化的集合覆盖问题的变种 116,那么基 于工人性价比 (marginal contribution-per-cost)的贪心思想比较适用，因为按照工人性价比排序 进行群组工人选择能保证群组形成单调性。 定义 2. 6工人的边界贡献和边界性价比： 给定技能集合每个工人印
35、相对于技能 t/ 的边界贡献可以定义为 ?r( ,， i7)=|t/n尺 |，即 a,能够满足 C7的技能数目；并且该工人 a,相对于 f/ 的性价比可以定义为边界贡献和成本之间的比值，即 ,11)=屯 /,。 算法 2. 3 (Greedy)描述形式化的描述了基于工人结构和性价比的贪心群组条成机制。在 算法 2.3,步骤 1中我们首先定位对于任务 T， 拥有最大的性价比的工人 &为群组的根工人 节点。当找到该根节点之后，在步骤 2-10中，我们围绕 &的周围邻居工人建立连通的工人 群组。在建立该连通的群组之前，我们首先创建队列结构来管理群组成员（步骤 2-3)。 这种队列结构用来记录每个工人
36、加入群组的顺序。然后，在步骤 5-8中，我们选择拥有最大 性 价 比 的 群 组邻近工人 a= argmax00a, ， Or) 加 入 群 组 ， 其 中 工 人 集 合 7= U e e e M:, 汾 , ，工人竞标信息 A， 任务技能 7-.而 和贪心群组 输出：支付报酬 /qy。 1. 0； 2. for V/m ax ffiax=Tt(al9Uj)/B(ap Uj)； 10. end if 11. end for 12. pai=max; 13. end for 2. 4. 2基于阈值的报酬支付算法 算法 2. 4描述了基于阈值的群组成员报酬支付函数，其中群组成员通过算法 2. 3
37、得到。 在算法 2.4步骤 1中，对于每个工人 a,e儿初始化他的报酬为内 =0。在步骤 2中，我们用 0 表示贪心算法2.3得到的群组，接下来我们为每个群组成员计算其应获得的报酬。在步骤 3 中，我们用 A表示第 /个加入群组 0的工人。支付给 &的阈值报酬就是 a,的最高并且仍然能 够被算法 2. 3选为群组成员的工作成本报价。为了得到该阈值，我们采用并且改进文献 120 提出的阈值报酬计算规则。我们首先 简单的介绍文献 120的报酬计算规则：首先在不考虑工 人 &参与群组形成的情况下，利用算法2. 3得到另外一个群组 0 。然后根据性价比的排序， 我 们 可 以 计 算 出 工 人 要
38、想 能 够 被群组 0 选 中 并 且 取 代 0 中 的 第 个 工 人 ，他 的 最高报价值，该值即为支付给的阈值报酬。相比于文献 117的考虑到 0 中所有工人 l， |g|J 来计算 4的阈值报酬计算规则，我们接下来提出的报酬计算规则只需要考虑到规模更小的工 人集合其中 /表示工人 ,+加入群组 0的顺序。值得注意的是，我们的报酬计算规则不 仅是激励相容的而且相比较于文献 117能够一定程度上减少计算复杂度。接下来，我们就具 体阐述我们的方法如何计算每个群组成员 A的阈值报酬 &，的（步骤 5-12)。假设 尝试取代 群组 0 中的第 y(iC l)个工人，那么他能够竞标的最高报价为
39、=,j=;r(n)/外 ， /彡，其 中 R是前尸 1个工人形成群组后，剩余的未被满足的技能，即 /;=丨 |1_/_-1卜其中 表示群组 g中第 X个群组成员（步骤 7)。由于边界技能贡献 ;r(a,， y7)和 ti价比G)关于 y 都 是 单 调 的 ， 那 么 关 于 y可 能 不 是 单 调 的 。 因 此 ， 选 择 所 有 中 的 最 大值作 为的最高 报价并且仍然能够被选为群组成员（步骤 8-9)，以该最大报价作为报酬支付给 即是阈值报酬支付规则（步骤 12)。 20 第二章基于激励相容机制的社会网络群组形成 引理 2. 4:算法 2. 4支付每个群组成员阈值报酬。 证明 :我
40、们用！ 2表示算法 2. 3 得 到 的 群 组 ， 表 示 群 组 成 员 加 入 群 组 g的顺序。 我们用 g 表示在不考虑 fl,参与群组形成的情况下，算法 2. 3得到的另外一个群组， /et/， |0| 表示在该位置 /&，那 他将不会被群组选中。首先，我们分析竞标高 于的工作成本 &将导致叫不会在丨 轮被选中。这是因为是 能够在 /,旧 | 轮中能够被选中的最高报价。下面我们将要证明竞 标高于 的工作成本 &同样导致 a,不会在 1,/-1轮中被选中。利用反正法，假设体竞标高价 &并且能够在中的某一轮 _/被选中 (假设 1)。我们用 Wy表示群组中的第 _/个群组 成员，那么我
41、们可以得出 也是群组 0中的第个成员。基于假设 1，我们可以得到 二然而在群组 0 中 ， 工 人 是 在 第 / ( / ) 轮 才 加 入 的 ， 产 生 这 种情况只 有如下两个理由，理由 1):在群组 g中， 在第 y轮是群组邻近的，但是他的性价比大于在 第 y轮 被 选 中 的 工 人 ， 即 硪 (/; ) 。 对 于 这 种 情 况 ， 我 们 可 以 得 到 矛 盾 。最后一个不等式成立是因为支付给群组成员 a, 的报酬 /?a,+大 于工人的真实报价因此，在这种情况下 ，一 个高于办 ,的报价将导致 a, 不 会 在 轮 被 选中。理由 2):在群组 0中的第 _/轮，虽然免
42、的性价比高于第 _/个工人，但是印不是群组 0 邻近的。在这种情况下，竞标高于仏 ,的报价只会推迟在群组中被选中的 -序，同样可 以表明 也不会在 f中的第 U-1轮被选中。至此，我们可以得到办 ,就是必可以竞标的并且 能够被选中 的最高工作成本报价，也就是阈值报酬。口 定理 2.4:包含贪心群组形成算法（算法 2.3)和基于阈值报酬的支付算法（算法 2.4) 的大规模群组形成机制是激励相容的并且与任务规模 A:和网络规模成多项式 0(从 2)计算复 杂度关系。 2. 5实验验证和分析 2. 5.1实验环境设置 数据收集及分 析：我们通过在线众包网站 Gum上收集数据，主要收集到 887个任务
43、数据 和 28808工人数据，这些工人以及任务数据都是关于丨 T领域的。对于任务数据，我们主要统 计两种信息：1)该任务所需要的技能数目 （ number of skills)和该任务的预算 （ budget， 分 布信息记录在图 2. 2中。从图 2. 2(a)技能信息分布图中，我们发现大约 95%的任务所需的技 能数目小于 12,并且所有任务所需要的技能数目都少于 20。从图 2. 2(b)预算信息分布图中， 21 东南大学博士学位论文 10000 150 Budget($) (b) 图 2. 2网站 Gum上的任务数据信息分布 Working Cost ($hr) (b) :、 00:X
44、i Number of Skills (a) Number of Skills (a) 一 Guru Data 图 2. 3网站 Guru上的工人数据信息分布 我们得到绝大多数任务的预算小于 $2500。对于工人数据我们同样主要统计两种个人信息： 1) 他们自身拥有的技能数目， 2)他们要求的时薪 （ working cost， $hr)， 图 2. 3详细描述了统 计记录。从图 2. 3 (a)中，我们发现绝大多数工人所拥有的技能数目少于 30,从图 2. 3(b)中， 我们可以发现，工人的薪酬要求呈现不均匀的分布。 实验设计： 我们主要通过选取任务最常使用的 40种技能筛选出 928个工人
45、。然后通过我 们三种典型的社会网络结构，即小世界，无标度和随机网络结构来模型这些工人节点之间的 网络拓扑结构，每一种网络结构度设置为 8。我们首先介绍这三个网络结构的构建过程 ： 小世界网络 （ Small-World, SMW):这种结构从一个规则的环形网格结构开始，其中 每个节点跟与他最邻近的 8个节点连接，并且每条边以 0. 2的概率进行重连 121。 无标度网络结构 （ Scale-Free， SF):这种无标度网络结构首先构建初始化网络，利用 mo-1条边连接的个节点。然后，我们一步一步的向该初始网络中添加节点，并且 允许每一步新添加的节点随机的跟网络中己有的 Wl个节点进行连接。新
46、节点 v跟己 有节点连接的概率跟节点 w的度成正比 122。 随机网络结构 (Random):随机网络的构建可以通 过任意两个网络节点之间以 p=0.004 的概率添加连接边的形式形成 123。 我们将本文提出的社会群组形成机制，即基于树结构面向小规模应用机制 （ OPT-Tree) 和基于贪心的面向大规模应用机制 （ Greedy)和传统的基于暴力搜索的最优机制 （ OPT)在 社会效益 （ Social Welfare)指标进行比较。实验图中的每个记录结果都是运行 100个实例的 平均值，这些平均值的标准差分布在 0.15和 0.4之间。对应每个实例，我们从收集的任务数 $250 it G
47、uru Data $500 0oooooo 1852963 2111 SMSEljosiNoQ 74 22 oK)Qooooloooo- 2086142108164222111-11 SJjseKoJaqEnz l* 0080000000080000002018161412108642 SJa)IJoMiol_3qEnz 22 第二章基于激励相容机制的社会网络群组形成 (a)随机网络 （ b)小世界网络 （ c)无标度网络 图 2. 4不同社会网络群组形成机制在不同网络结构下产生的社会效益 表 2.1网络结构特征 特征 网络结构 网络直径 平均最短路径长度 聚类系数 随机网络 6.0 3.5 0.01 小世界网络 6.5 4.0 0.28 无标度网络 5.0 3.2 0.