Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (3): 608-620.DOI: 10.3778/j.issn.1673-9418.2010071

• Artificial Intelligence • Previous Articles     Next Articles

Strategy Proof Mechanism for Bike-Sharing Maintenance Accomplishment Probability

LI Lianxin, SHI Bing+(), YUAN Han   

  1. School of Computer Science and Technology, Wuhan University of Technology, Wuhan 430070, China
  • Received:2020-10-26 Revised:2020-12-21 Online:2022-03-01 Published:2020-12-24
  • About author:LI Lianxin, born in 1998, M.S. candidate. Her research interests include reinforcement learning and mechanism design.
    SHI Bing, born in 1982, Ph.D., associate professor, member of CCF. His research interests include artificial intelligence and game theory.
    YUAN Han, born in 1995, M.S. candidate. Her research interests include reinforcement learning and mechanism design.
  • Supported by:
    National Natural Science Foundation of China(61402344);Humanity and Social Science Research Foundation of Ministry of Education of China(19YJC790111);Philosophy and Social Science Post-Foundation of Ministry of Education of China(18JHQ060)

共享单车维护任务完成概率防策略机制设计

李连欣, 石兵+(), 袁菡   

  1. 武汉理工大学 计算机科学与技术学院,武汉 430070
  • 通讯作者: + E-mail: bingshi@whut.edu.cn
  • 作者简介:李连欣(1998—),女,硕士研究生,主要研究方向为强化学习、机制设计。
    石兵(1982—),男,博士,副教授,CCF会员,主要研究方向为人工智能、博弈论。
    袁菡(1995—),女,硕士研究生,主要研究方向为强化学习、机制设计。
  • 基金资助:
    国家自然科学基金(61402344);教育部人文社会科学研究一般项目(19YJC790111);教育部哲学社会科学后期资助项目(18JHQ060)

Abstract:

As a green and low-carbon transportation way, bike-sharing provides lots of convenience in our daily life. However, the daily usage of sharing bike may result in some maintenance problems, such as bicycle dispatching to the specific destinations. The bike-sharing platform hires and pays to users in order to excite them to accomplish maintenance tasks. However, there are multiple users competing for the maintenance tasks, and they may strategi-cally report their task accomplishment probability in order to make more profits, which may result in inefficient task dispatching for the platform. In more detail, regarding users’ strategic behavior about reporting task accomplish-ment probability, this paper designs a strategy proof mechanism to ensure that the task accomplishment probability satisfies a certain threshold, and achieves the goal of minimizing the task accomplishment cost. The mechanism consists of a task dispatching algorithm and a user pricing algorithm. The task dispatching algorithm is based on a greedy method. The user pricing algorithm is based on Myerson’s themes. It is theoretically proven that the proposed mechanism can satisfy the properties of incentive compatible and individual rationality. Furthermore, the proposed mechanism is evaluated based on Mobike dataset in terms of task accomplishment cost, user average expected utility and user expected utility probability density. The results show that, compared with the VCG (Vickrey-Clarke-Groves) mechanism, the proposed mechanism can achieve a constant times of the approximate ratio, lower task accomplishment cost and a higher average expected utility for users. Moreover, it can prevent users’ strategic behavior in task accom-plishment probability.

Key words: mechanism design, bike-sharing maintenance, incentive compatibility, user pricing, task dispatching

摘要:

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

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

CLC Number: