JIN Qianqian,LI Boyang,CHENG Yurong,et al.Multi-round cross online matching in spatial-temporal crowdsourcing[J].Journal of Taiyuan University of Technology,2024,55(1):155-162.
滴滴等平台引领了时空众包服务的兴起,已经成为日常生活不可或缺的部分。其核心问题是如何合理地将实时的任务分配给自由移动的工人,从而提升用户满意程度和平台收入。现有研究主要关注独立平台的任务分配问题[1-3],即只接收本平台的实时数据,并使用算法找到最优任务分配结果。然而,由于用户和工人地理分布的差异,经常出现部分地区任务过多无法及时被服务,而其他地区工人闲置被浪费的情况。现有研究难以解决以上任务和工人供需不平衡的问题。
为了解决这些问题,跨平台在线匹配(cross online matching,COM)作为一种新兴解决方案应运而生[4]。在COM中,平台之间建立合作关系,无法被服务的任务会转发给多个提供类似服务的其他平台,由其他平台的闲置工人完成,从而提升任务被接受的概率。这种合作方式在诸如滴滴、高德地图和百度地图等平台中纷纷落地应用。类似地,文献[5-8]从数据隐私性、匹配公平性和定价合理性等角度进行研究,考虑通过充分利用全局服务供应来提高平台的收益。
在现有问题设定中,任务只被进行单轮次匹配,即任务被分配给其他平台后,如果没有被响应就会立即被拒绝服务。实际上,在其他平台响应任务的过程中,他们往往只考虑以自身利益最大化为目标,就会出现多个平台同时竞争同一个任务的情况。此时,只有一个平台可以赢得任务服务机会,而失败平台的工人资源和未被响应的任务却被白白浪费。这些平台通过合适的策略,可以避开互相竞争,共同提升收益。因此,如何为平台制定合适的策略,在多方竞争中找到利益共赢的局面是当前研究所面临的挑战。
基于以上挑战,本文基于实际场景提出基于多轮互动的跨平台在线匹配问题(multi-round cross online matching,MRCOM)。在MRCOM中,考虑引入多轮匹配机制,不同于现有研究的单次响应,平台可以将某个时间段内未被分配的任务进行多个轮次的再分配,从而最大程度地提高任务的接受率和任务的完成率。为了解决该问题,本文首先设计了基于贪心的多轮匹配算法,通过多轮迭代,每个参与平台尽可能选择高价值的任务来最大化自己的收益。更进一步,本文提出基于多方博弈的多轮匹配算法,将平台之间的协调问题建模为一个多方博弈过程,每个参与平台作为博弈参与者,通过选择接受或拒绝任务分配来追求自身的利益最大化。该算法考虑到参与平台之间的相互作用和竞争关系,通过分析平台的策略空间和收益函数来推导出最优的响应方式,并求得纳什均衡。本文在真实和合成数据集上进行实验,以评估本文提出的算法的效果和效率。实验结果表明,本文的算法可以在极短的延时内完成任务分配,并提高平台的总收入。
时空众包系统要求工人移动到特定的空间位置执行任务,并受到各种约束条件的限制[9]。例如,在满足任务截止日期的约束下,ZHAO et al[1]研究了一个目的地感知的任务分配问题。考虑到工作区域的约束以及工人的可靠性,SONG et al[3]研究了多技能感知任务分配问题,其目标是在技能约束下找到最佳的工人和任务分配方式。CHENG et al[4]首先提出了跨平台在线匹配,并提出了两种匹配算法来提高平台的收入。为了保护数据隐私,WANG et al[5]提出了基于联邦学习的任务分配算法。YANG et al[6]设计了一种保护用户和工人隐私的合作在线匹配框架,并提供了理论证明该框架满足差分隐私属性。然而,他们都只考虑了单轮的匹配过程,存在资源的浪费。本文中的MRCOM问题是在考虑工作区域等约束条件下解决多轮的跨平台任务分配,既可以充分考虑平台间的竞争关系,又可以充分利用任务和工人资源,从而最大化总收入,提高用户满意度。
与任务分配不同,一些研究侧重于设计激励机制来激励工人为任务服务。最常见的激励机制是给予工人货币奖励[10]。YANG et al[6]提出了一种基于博弈的激励机制,旨在有效招募移动用户参与群体感知任务,并提高感知数据的可靠性和质量。ZHAO et al[11]研究了时空众包中的联盟任务分配问题,提出了基于均衡的算法,工人按顺序形成联盟,并在轮到他们时更新策略(即选择最佳响应任务),以最大化自己的效用,直到达到纳什均衡。在本文的问题里,将博弈论激励机制应用于多轮的跨平台在线匹配中,考虑了参与者的奖励,以激发他们对执行合作任务的热情,并通过最优响应方法得到纳什均衡,以最大化总收入。
在本问题中,存在一个领导者和n个时空众包平台作为参与者。领导者将无法完成的任务分发给参与者,每个参与者接收任务并安排自身的闲置工人来提供服务。任务和工人在多个短时间段的匹配时间段下进行匹配。在每个时间段t内,每个任务o包含起始位置so、目的地位置do和任务报酬vo;工人w包含工人当前的位置lw,服务半径rw和工作平台pw.领导者将任务集转发给参与者,参与者根据自身闲置的工人集选择希望服务的任务,并将响应结果返回给领导者。领导者以ro=βvo作为参与者完成任务o的报酬[8],其中β为领导者和参与者的分配比例。总收益为领导者和参与者的收益之和,分别使用Rleader和Rp表示。因此,总收益表示为:
(1)
定义1(多轮跨平台在线匹配)给定一个领导者、一组参与者P及一组工人W、一组实时任务O和时间段T,MRCOM问题是在每个时间段t里,进行多轮的匹配,最终得到总收益最大化的匹配结果,该结果满足以下约束:
1) 空间限制。工人只能为服务半径内的任务提供服务。
2) 时间限制。工人只能为同一匹配时间段内的任务提供服务。
3) 唯一限制:任务和工人是一对一的。
在现有研究的问题设定中,只进行一次匹配,容易由于平台竞争难以求得全局的最优解。因此,本文提出的MRCOM考虑使用多轮交互匹配的形式,更加充分地利用工人资源。
为解决MRCOM问题,本文首先提出基于贪心的基础算法,进一步提出基于多方博弈的优化算法,优化算法可以求得满足纳什均衡的匹配策略,进一步提升平台收益。
本算法的主要思想是由平台采用贪心的方法选择对自身最有利的任务进行响应。当领导者对响应结果完成分配后,未被分配的任务将再次发送给参与者,直到满足迭代终止条件。考虑参与者服务任务的成本和意愿,本文将参与者对任务的响应概率设置为[4]:
(2)
式中,N是参与者p已完成的历史任务数量,领导者将ro作为参与者的回报,N(v≤ro)是历史任务中任务价值不大于ro的数量。本文使用公式(2)和阈值η来估计参与者p接受报酬为ro的任务的可能性。若pa(ro,p)≥η则p愿意以价格ro为该任务提供服务。算法1描述了G-MRCOM的主要过程。
算法1 G-MRCOM算法
---------------------------------------------------
输入:参与者集P,工人集W,任务集O,时间段集T
输出:分配结果M
1 初始化M=φ
2 FORt∈TDO
3 初始化Mt=φ
4 REPEAT
5 领导者将任务集Ot发送给所有参与者Pt
6 FORp∈PtDO
7 初始化p的可接受任务集AOp=φ
8 FORo∈OtDO
9 计算p的接受概率pa(vo,p)
10 生成一个随机数η∈[0,1]
11 IFpa(vo,p)≥ηTHEN
12 将o加入到AOp中
13 END IF
14 END FOR
15 END FOR
16 FORp∈PtDO
17p从AOp中选择最大化自身收益的策略
18 END FOR
19 领导者根据所有参与者的策略,得到该匹配轮次的分配结果加入到Mt中,并更新Ot
20 UNTILOt为空或达到循环终止条件
21M=M∪Mt
22 END FOR
23 RETURNM
---------------------------------------------------
在每个匹配时间段中,每个参与者p的局部匹配时间复杂度为
领导者的匹配时间复杂度为O(|Ot|×|Pt|).因此,时间复杂度为O(|W|×|O|+|O|×|P|),空间复杂度为O(|W|+|O|).
G-MRCOM的执行过程简单易实现,但每轮匹配时参与者仍存在较多的竞争冲突,没有为参与者设计合理的策略。因此,本文接着提出基于多方博弈的匹配算法,让参与者在互相竞争的局面中求得合适的响应策略。
为了更好地激励参与者,本节提出了基于多方博弈的多轮匹配算法(game-theoretic multi-round cross online matching,GT-MRCOM),可以迭代地调整参与者对任务的分配策略,直到达到纳什均衡。在纳什均衡分配中,任何单个参与者在其他参与者保持其匹配任务不变的情况下,无法通过单方面从匹配的任务转换到其他任务来提高它的效用,这使得参与者的选择策略达到一个稳定的局面。纳什均衡分配可以得到较高的总效用,因为每个参与者都被分配到稳定分配中的他的“最佳”任务集合。
本文将MRCOM问题建模成一个博弈过程,用元组〈Pt,{Xp}p∈Pt,{Up:×p∈PtXp→R}p∈Pt〉表示,其中Pt是匹配时间段t的参与者集。对于Ot,每个参与者p∈Pt根据自身可用的工人集
生成可行策略集Xp.xp是p的一种策略,xp={xp,1,…,xp,o,…,xp,|Ot|}∈Xp,其中xp,o=1表示参与者p接受任务o,xp,o=0则表示p拒绝o.给定xp和其他参与者的策略
的效用
是将接受任务的共享效用和接受任务所带来的潜在效用相结合。每个参与者p的目标是找到最大化自身总效用的策略xp,效用函数如方程(3)所示。
(3)
式中:α是归一化参数。将效用分为两个部分,第一部分是所分配的任务本身所带来的效用,第二部分考虑到完成所分配的任务之后所带来的未来潜在的效用。由于在最佳响应过程中,每个任务可能被多个参与者接受,将任务o的效用划分为no份共享,其中no是接受同一任务o的参与者的数量,每个尝试执行此任务的参与者都拥有一份效用。Dp,o表示参与者p的工人在完成任务o并到达目的地位置后,可能会遇到的未来需求任务集。rl是基于任务l∈Dp,o的预测的起止位置间的距离而预估的潜在报酬。当工人完成任务o后,他面临着|Dp,o|个潜在需求任务。为了公平地分配这些潜在的效用,将其均匀地分为|Dp,o|份,并将每一份效用均匀地分配到每一个他选择接受的任务上。因此,对于一个理性的参与者p,选择最大化他的总效用
是他的合理策略。
为了预估未来的任务需求,关键的挑战在于如何生成高度准确的任务需求数量地图。在实践中,由于个人和环境因素的不确定性,很难准确预测特定任务即将出现的位置和时间。在本文中,预测在给定的时间段内,某一特定区域(如方形或六边形的空间范围)的任务数量及其带来的潜在收益。为此,采用了先进的预测模型DeepST,利用其离线生成基于网格的任务需求数量地图[12-13]。具体而言,DeepST使用来自3个不同时间尺度的历史任务数量:接近度、周期性和趋势。其中,接近度表示最近的N个时间段的任务数量;周期性表示过去N天的同一时间段的任务数量;趋势表示基于过去N周同一时间段的任务数量。算法2展示了GT-MRCOM的主要过程。
算法2GT-MRCOM算法
---------------------------------------------------
输入:参与者集P,工人集W,任务集O,时间段集T
输出:分配结果M
1 初始化M=φ
2 FORt∈TDO
3 初始化Mt=φ
4 REPEAT
5 领导者将任务集Ot发送给所有参与者Pt
6 FORp∈PtDO
7 执行算法1中的第6-15行得到AOp,并生成可行策略集Xp
8p选择一种随机策略xp∈Xp
9 END FOR
10 REPEAT
11 FORp∈PtDO
12 maxU=-∞
13 FORxp∈XpDO
14 计算p的效用
18 END IF
19 END FOR
20 END FOR
21 UNTIL达到一个纳什均衡
22 领导者根据所有参与者的策略,得到该匹配轮次的分配结果加入到Mt中,并更新Ot
23 UNTILOt为空或达到循环终止条件
24M=M∪Mt
25 END FOR
26 RETURNM
---------------------------------------------------
在文献[14]中证明了对于有限的完全势博弈,最佳响应框架总是收敛到一个纯纳什均衡。通过在下面的定理中证明本文的策略是一个完全势策略,来证明基本博弈论方法的稳定性。请注意,Φ(X)与公式(3)中给出的效用函数不同,它仅在下文中用作分析的工具。
(4)
将任务o的效用分成(no+1)份。对于每个参与者p∈P,计算策略空间xp中除了参与者p选择接受的任务(xp,o=1)之外,其他任务(xp,o=0)的一个效用份额的总和。然后,将势函数Φ(X)定义为这些值的负值的和。
定理1多轮跨平台在线匹配构成了一个完全势博弈。
证明:对于参与者p,当他从当前策略xp更改为其最佳响应策略
并且对于其他参与者策略
的组合,只需满足以下条件成
对于p,假设nk和nk′分别是集合
中接受任务k和k′的工人数量,xp,k=1,xp,k′=0.同样地,
和
分别是集合
中接受任务k和k′的工人数量,xp,k=0,xp,k′=1.那么有
因此:
(5)
证毕。
由于MRCOM问题是一个完全势博弈,且策略集合X是有限的,参与者在改变策略有限次数后可以达到纳什均衡。为了估计GT-MRCOM方法实现纯纳什均衡的总轮数的上界,考虑一个目标函数取整值问题的缩放版本。具体来说,对于一个MRCOM问题实例的相应势博弈,假设存在一个具有势函数ΦZ(X)=d·Φ(X)的等价博弈,其中d是一个正的乘法因子,使得对于所有X,ΦZ(X)∈Z.通过这个缩放的势函数,可以证明GT-MRCOM方法执行的最多轮数为ΦZ(X*),其中X*是工人在MRCOM势博弈中可以选择的最佳策略(即ΦZ(X*)是目标函数的最优值与乘法因子d的乘积)。然后,可以证明以下引理。
引理1GT-MRCOM算法在每个时间段中收敛到均衡所需的轮数上界为O(d·min(∑o∈Otro,
证明:带有势函数ΦZ(X)=d·Φ(X)的缩放版本的GT-MRCOM算法在与GT-MRCOM算法相同的轮数内收敛到纳什均衡。GT-MRCOM算法在没有参与者改变策略时收敛,这意味着在每一轮至少有一个参与者改变策略。此外,每个参与者p从当前策略xp改变到更好策略
会使得缩放势函数至少增加1(即
这是因为:1) 对于完全势博弈,单个玩家由于自身策略变化而导致的效用变化与势函数的变化量完全相同;2) 缩放势函数的值是整数(ΦZ(X)∈Z).因此,轮数的上界是最大值Φmax减去最小值Φmin.由于Φmax≤0且
其中
是p的工人能完成的最高价值的任务集,因此收敛到纯纳什均衡所需的轮数上界为
证毕。
接着分析算法的时间复杂度和空间复杂度。对于每个参与者p,最佳响应需要计算最多|Xp|个可能的策略的个体效用函数。然而,与|Ot|和|Wt|相比,|Xp|是可以忽略的。因此,每个匹配时间段的时间复杂度为O(d·|Pt|·min(|Ot|,|Wt|)).领导者的匹配时间复杂度为O(|Ot|×|Pt|).所以,时间复杂度为
空间复杂度为O(|W|+|O|+|X|).
本文使用来自成都和西安两个城市的真实数据集[4,8]。每个数据集包含4个热门的打车平台:平台A是领导者,平台B-D是参与者。详细信息见表1.匹配时间段的时间间隔设置为60 s.本文根据日常经验和统计结果将每个工人的服务半径设为3.0 km.本文将α设为10,β设为0.8,单个匹配时间段内的匹配轮次数n设为3.根据真实数据集随机选择任务的起止位置,生成了不同规模的合成数据集来验证算法的可扩展性。合成数据集的统计信息显示在表2中,默认值用粗体表示。
表1 真实数据集
Table 1 Real datasets
(a) 成都的真实数据集
参数ABCD|O|200 046---|W|-1 7711 7891 811
(b) 西安的真实数据集
参数ABCD|O|115 385---|W|-1 8111 7771 783
表2 合成数据集
Table 2 Synthetic datasets
参数值|O|/10350, 100, 200, 500, 800|W|/1031, 2, 5, 8, 10rw/km1.0, 2.0, 3.0, 4.0, 5.0t/s30, 60, 120, 180, 300|P|3, 4, 5
本文将提出的算法(G-MRCOM和GT-MRCOM)与COM算法(DemCOM和RamCOM)[4]以及GTA算法(ImpGTA)[7]进行比较,并根据总收入(TR)、完成的任务数量(CO)、任务响应时间(RT)、内存消耗(MC)评估算法的有效性和效率。算法实验环境为Intel(R) Core(TM) i5-9500 CPU和16GB内存的计算机,使用Python编程语言。
实验结果(表3)表明,COM算法和ImpGTA只考虑了单轮的匹配过程,因此效果相对较差。GT-MRCOM算法能够考虑到不同平台之间的合作和竞争关系,通过优化任务的分配策略,使得每个平台都能获得更高的收入并提高任务的完成率。G-MRCOM算法更倾向于局部最优解,可能导致平台的一些任务无法得到及时服务。实验结果证明了本文所提算法的效果。
表3 真实数据集实验结果
Table 3 Experimental results on real datasets
(a) 在成都数据集上的实验结果
算法TR/106元CORT/sMC/MBDemCOM1.18939 4230.0016.95RamCOM1.21139 7120.0017.21ImpGTA1.37444 3790.0018.16G-MRCOM1.55250 8960.0019.07GT-MRCOM2.31486 2010.00312.29
(b) 在西安数据集上的实验结果
算法TR/106元CORT/sMC/MBDemCOM0.81239 2640.0013.78RamCOM0.87341 0430.0014.27ImpGTA0.93243 7760.0014.96G-MRCOM1.10845 5390.0026.85GT-MRCOM1.32654 7210.0058.45
在算法效率方面,G-MRCOM能够快速完成任务分配过程,因此在响应时间方面表现较好,同时内存需求较低。相比之下,GT-MRCOM需要更多的计算和协商时间,以确定最佳的任务分配策略,并且需要更多的内存空间。GT-MRCOM的最大响应时间约为0.005 s,在现实世界中可以忽略不计。考虑到GT-MRCOM所提供的总收入的显著改善,其内存成本是可以接受的。因此,这证明了本文所提算法是有效的。
工人总数|W|对总收入和完成的任务数量的影响如图1(a)、1(b)所示。算法都显示出总收入和完成的任务数量随|W|增加而增加。更多的工人意味着更多的人力资源可用于服务任务,从而增加了平台的收入。GT-MRCOM在工人分配和任务协调方面更加理智,因此在工人总数较多时,GT-MRCOM能够实现更高的总收入和完成的任务数量。任务总数|O|对总收入和完成的任务数量的影响如图1(e)、1(f)所示。算法都显示出总收入和完成的任务数量随|O|增加而增加。GT-MRCOM算法在优化资源分配和匹配策略方面更加灵活和高效,因此在任务总数较大时,GT-MRCOM算法能够生成更高的总收入和完成的任务数量。服务半径rw对总收入和完成的任务数量的影响如图1(i)、1(j)所示。较大的rw导致更多的任务可以被平台的工人所服务,因此会增加总收入和完成的任务数量。匹配时间段间隔t对总收入和完成的任务数量的影响如图1(m)、1(n)所示。合适的间隔可以更合理地进行任务分配和协商,从而有助于优化任务分配策略,提高总收入和完成的任务数量。然而,过长的间隔可能导致用户等待时间过长,从而导致任务被取消,影响总收入和完成的任务数量,降低用户对平台的满意度。参与者平台的数目|P|对总收入和完成的任务数量的影响如图1(q)、1(r)所示。更多的参与者能更好地协调资源,增加总收入和完成的任务数量。
图1 合成数据集实验结果
Fig.1 Experimental results on synthetic datasets
不同参数响应时间和内存成本的影响如图1的第三栏和第四栏所示。由于|O|、|W|和|P|的增加,需要进行更多的计算和存储操作,因此会增加响应时间和内存成本。在rw增加时,工人在服务半径内可服务的任务增加,导致更长的匹配时间,从而增加了响应时间。此外,更大的rw需要更多的存储空间来存储相关信息,从而增加了内存成本。在t变化时,较大的t意味着工人可服务的任务增加,导致更长的匹配时间,从而增加了响应时间。此外,由于工人可选的策略增加,需要更多的存储空间来存储这些信息,会导致更高的计算和存储负担,从而增加内存成本。
在这篇论文中,从实际场景出发,研究了基于多轮互动的跨平台在线匹配问题(MRCOM),该问题涉及在不同合作平台之间实现多轮的任务分配和协作。为了解决这一问题,本文提出了两种算法,分别是基于贪心的多轮匹配算法(G-MRCOM)和基于博弈的多轮匹配算法(GT-MRCOM)。本文对这两种算法进行了实验评估,使用真实数据和合成数据集进行测试。实验结果表明本文的算法是有效且高效的。未来工作中,将进一步提高其解决大规模问题的效率。
[1] ZHAO Y,ZHENG K,LI Y,et al.Destination-aware task assignment in spatial crowdsourcing:a worker decomposition approach[J].IEEE Transactions on Knowledge and Data Engineering,2019,32(12):2336-2350.
[2] SHI D Y,TONG Y X,ZHOU Z M,et al.Learning to assign:towards fair task assignment in large-scale ride hailing[C]∥Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery &Data Mining.New York,USA:Association for Computing Machinery,2021:3549-3557.
[3] SONG T,XU K,LI J,et al.Multi-skill aware task assignment in real-time spatial crowdsourcing[J].GeoInformatica,2020,24:153-173.
[4] CHENG Y R,LI B Y,ZHOU X M,et al.Real-time cross online matching in spatial crowdsourcing[C]∥2020 IEEE 36th International Conference on Data Engineering (ICDE).IEEE,2020:1-12.
[5] WANG Y S,TONG Y X,ZHOU Z M,et al.Fed-LTD:Towards cross-platform ride hailing via federated learning to dispatch[C]∥Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining.2022:4079-4089.
[6] YANG Y,CHENG Y,YUAN Y,et al.Privacy-preserving cooperative online matching over spatial crowdsourcing platforms[J].Proceedings of the VLDB Endowment,2022,16(1):51-63.
[7] LI B Y,CHENG Y R,YUAN Y,et al.Competition and cooperation:global task assignment in spatial crowdsourcing[J].IEEE Transactions on Knowledge and Data Engineering,2023,35(10):9998-10010.
[8] LI B Y,CHENG Y R,YUAN Y,et al.ACTA:autonomy and coordination task assignment in spatial crowdsourcing platforms[J].Proceedings of the VLDB Endowment,2023,16(5):1073-1085.
[9] TONG Y,ZHOU Z,ZENG Y,et al.Spatial crowdsourcing:a survey[J].The VLDB Journal,2020,29:217-250.
[10] WANG X,TUSHAR W,YUEN C,et al.Promoting users’ participation in mobile crowdsourcing:a distributed truthful incentive mechanism (DTIM) approach[J].IEEE Transactions on Vehicular Technology,2020,69(5):5570-5582.
[11] ZHAO Y,GUO J N,CHEN X H,et al.Coalition-based task assignment in spatial crowdsourcing[C]∥2021 IEEE 37th International Conference on Data Engineering (ICDE).IEEE,2021:241-252.
[12] ZHANG J B,ZHENG Y,QI D K.Deep spatio-temporal residual networks for citywide crowd flows prediction[C]∥Proceedings of the AAAI Conference on Artificial Intelligence,2017:1655-1661.
[13] WANG J,CHENG P,ZHENG L,et al.Demand-aware route planning for shared mobility services[J].Proceedings of the VLDB Endowment,2020,13(7):979-991.
[14] MONDERER D,SHAPLEY L S.Potential games[J].Games and economic behavior,1996,14(1):124-143.