School of Computer Science and Technology, Beijing Institute of Technology
School of Computer Science and Engineering, Northeastern University

【目的】为了解决传统单平台任务分配中的供需不平衡问题,跨平台在线匹配成为了一种新兴解决方案,它允许多个类似的平台建立合作关系,将无法完成的任务发送给其他平台,增加任务被接受的概率。然而,目前的跨平台在线匹配都只考虑了单轮的匹配过程,难以在多平台竞争中找到良好的决策结果。为了解决以上不足,研究了多轮跨平台在线匹配问题,并提出了基于贪心的多轮匹配算法和基于多方博弈的匹配算法。【方法】基于贪心的多轮匹配算法通过将任务进行多轮转发和匹配,由平台贪心地选择高收益的任务来完成,以提高任务完成的效率。基于多方博弈的匹配算法则通过建立合作平台之间的激励机制,计算满足纳什均衡的任务分配策略,让平台在竞争中寻找更优的策略,从而实现整体性能的提升。【结果】实验结果表明本文的算法可以提高平台的总收入,体现了本文工作的效果和效率。

【Purposes】 To address the imbalance between supply and demand in traditional sin-gle platform task assignment, Cross Online Matching (COM) has emerged as a novel solution that allows multiple similar platforms to establish cooperative relationships and send uncompleted tasks to other platforms, increasing the probability of task acceptance. However, current COM solutions only consider single-round matching processes, making it difficult to find optimal deci-sion results in multi-platform competition. To settle these limitations, the Multi-Round Cross Online Matching problem (MRCOM) is studied and Greedy-based Multi-Round Cross Online Matching (G-MRCOM) and Game-Theoretic Multi-Round Cross Online Matching (GT-MR-COM) algorithms are proposed. 【Methods】 G-MRCOM improves task completion efficiency by forwarding and matching tasks in multiple rounds, with platforms greedily selecting high-reward tasks to accomplish. GT-MRCOM, on the other hand, establishes incentive mechanisms among algorithms cooperating platforms, calculates task assignment strategies that satisfy Nash Equilibrium, and enables the platform to find better strategies in competition, thereby enhancing overall performance. 【Findings】 Experimental results demonstrate that the proposed algorithms can in-crease the total revenue of platforms, showcasing the effectiveness and efficiency of this study.

国家自然科学基金资助项目(62202046,U21B2007,U21A2051,61972077,62072087);辽宁省兴辽英才计划项目(XLYC2007079)

金倩倩,李博扬,成雨蓉,等.时空众包中的多轮跨平台在线匹配[J].太原理工大学学报,2024,55(1):155-162.

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.