计算机科学与探索

作者：李连欣, 石兵, 袁菡

单位：武汉理工大学 计算机科学与技术学院,武汉 430070

关键词：机制设计,共享单车维护,激励相容,用户定价,任务分发

基金：国家自然科学基金(61402344);教育部人文社会科学研究一般项目(19YJC790111);教育部哲学社会科学后期资助项目(18JHQ060)

共享单车作为一种绿色低碳的出行方式,给人们的出行带来便利。然而,人们自由使用单车给共享单车的维护带来许多问题（例如需要将某个区域无序放置的单车送到某个指定位置）,因此,共享单车平台可能需要雇佣用户去完成单车维护任务,同时平台需要给予用户合理的报酬以激励用户完成任务。当存在多个用户竞争时,用户可能谎报任务完成概率来获得更高的报酬,从而导致平台最终不能完成所有的维护任务。考虑用户在任务完成概率方面的策略行为,在满足一定任务完成概率的情况下,设计防策略性机制,实现完成维护任务完成成本最小化。该机制包括任务分发算法和用户定价算法,其中任务分发机制采用贪心算法思想进行设计,而用户定价算法则通过迈尔森定理来设计。理论证明该机制满足激励相容性和个体理性,接着进一步基于摩拜单车数据集来评估该机制的性能,主要包括任务完成成本、用户平均期望效用、用户期望效用概率密度等评价指标。通过与VCG机制相比较,该机制能够达到常数倍的近似比,任务完成成本更低,用户平均期望效用更高,并且能够防止用户在任务完成概率方面的策略行为。

来源：2022年第3期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2022年第3期