Strategy Proof Mechanism for Bike-Sharing Maintenance Accomplishment Probability

doi:10.3778/j.issn.1673-9418.2010071

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

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)

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

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

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

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

Abstract

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:

TP391

LI Lianxin, SHI Bing, YUAN Han. Strategy Proof Mechanism for Bike-Sharing Maintenance Accomplishment Probability[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(3): 608-620.

李连欣, 石兵, 袁菡. 共享单车维护任务完成概率防策略机制设计[J]. 计算机科学与探索, 2022, 16(3): 608-620.

Figures/Tables 10

Fig.1 Workflow of platform and users

Table 1 Symbol definition

符号	描述	备注
$D$	空间上一个大区域集合,可分为不交叉重叠的 $n$ 个小区域	$D = {D 1, D 2, ⋯, D n}$
$T$	平台发布的单车维护任务集合	$T = {t 1, t 2, ⋯, t T}$
$l j$	第 $j$ 个任务 $t j$ 的位置信息	$t j = (l j, n j, p r j)$
$n j$	第 $j$ 个任务 $t j$ 的单车数量信息	$t j = (l j, n j, p r j)$
$p r j$	第 $j$ 个任务 $t j$ 的最低任务完成概率	$t j = (l j, n j, p r j)$
$M$	用户集合	$M = {m 1, m 2, ⋯, m M}$
$T i$	用户 $m i$ 投标的可完成任务集合	$T i ⊆ T$
$r i$	用户 $m i$ 的活动半径	$T i = {t j \| dis (l i, l j) ≤ r i, t j ∈ T}$
$c i$	用户 $m i$ 提交给平台的任务完成成本
$p i$	平台计算给用户 $m i$ 的酬劳
$u i$	用户 $m i$ 的效用
$pr ˆ i, j$	用户 $m i$ 对于任务 $t j$ 的真实任务完成概率
$p r i, j$	用户 $m i$ 提交给平台的任务完成概率
$b i$	用户 $m i$ 向平台提交的投标信息	$b i = (T i, c i, {p r i, j \| t j ∈ T i})$
$b$	平台收到的所有投标信息集合	$b = (b 1, b 2, ⋯, b M)$
$p$	所有用户的酬劳集合	$p = (p 1, p 2, ⋯, p M)$
$M$	被平台选中分发任务的获胜用户集合
$T M$	被分发到用户的任务集合	$V (M) = ∑ v j$
$q i, j$	用户 $m i$ 对任务 $t j$ 的完成度
$Q j$	任务 $t j$ 所需的最小完成度之和

Table 1 Symbol definition

符号	描述	备注
$D$	空间上一个大区域集合,可分为不交叉重叠的 $n$ 个小区域	$D = {D 1, D 2, ⋯, D n}$
$T$	平台发布的单车维护任务集合	$T = {t 1, t 2, ⋯, t T}$
$l j$	第 $j$ 个任务 $t j$ 的位置信息	$t j = (l j, n j, p r j)$
$n j$	第 $j$ 个任务 $t j$ 的单车数量信息	$t j = (l j, n j, p r j)$
$p r j$	第 $j$ 个任务 $t j$ 的最低任务完成概率	$t j = (l j, n j, p r j)$
$M$	用户集合	$M = {m 1, m 2, ⋯, m M}$
$T i$	用户 $m i$ 投标的可完成任务集合	$T i ⊆ T$
$r i$	用户 $m i$ 的活动半径	$T i = {t j \| dis (l i, l j) ≤ r i, t j ∈ T}$
$c i$	用户 $m i$ 提交给平台的任务完成成本
$p i$	平台计算给用户 $m i$ 的酬劳
$u i$	用户 $m i$ 的效用
$pr ˆ i, j$	用户 $m i$ 对于任务 $t j$ 的真实任务完成概率
$p r i, j$	用户 $m i$ 提交给平台的任务完成概率
$b i$	用户 $m i$ 向平台提交的投标信息	$b i = (T i, c i, {p r i, j \| t j ∈ T i})$
$b$	平台收到的所有投标信息集合	$b = (b 1, b 2, ⋯, b M)$
$p$	所有用户的酬劳集合	$p = (p 1, p 2, ⋯, p M)$
$M$	被平台选中分发任务的获胜用户集合
$T M$	被分发到用户的任务集合	$V (M) = ∑ v j$
$q i, j$	用户 $m i$ 对任务 $t j$ 的完成度
$Q j$	任务 $t j$ 所需的最小完成度之和

Fig.2 Demand of weekdays and weekends

Fig.3 Density of bicycles

Table 2 Experimental parameters

参数	描述
任务成功概率	0.75、0.80、0.85、0.90、0.95
用户数量	250、300、350、400、450、500、550、600、650、700
用户任务完成概率	[0.8, 1.0]
平均车辆数目	每个区域中平均车辆数量从1到100
用户活动半径	分为1.5、2.0、2.0、3.0、3.5这5档

Fig.4 Task accomplishment cost of different number of users

Fig.5 Average expected utility of users

Fig.6 Critical_Alpha

Fig.7 Expected utility probability density (users number=250)

Fig.8 Expected utility probability density (users number=700)

References 30

[1]	SHIV A. Analysis of last mile transport pilot: implementa-tion of the model and its adaptation among local citizens[J]. International Design Business Management, 2018, 12(11): 45-67.
[2]	SATHISHKUMAR V E, PARK J, CHO Y. Using data mining techniques for bike sharing demand prediction in metropo-litan city[J]. Computer Communications, 2020, 153: 353-366. DOI URL
[3]	HOLIENČINOVÁ M, KÁDEKOVÁ Z, HOLOTA T, et al. Smart solution of traffic congestion through bike sharing system in a small city[J]. Mobile Networks and Applica-tions, 2020, 25(3): 868-875.
[4]	JIA H F, MIAO H Z, TIAN G D, et al. Multiobjective bike repositioning in bike-sharing systems via a modified artifi-cial bee colony algorithm[J]. IEEE Transactions on Automa-tion Science and Engineering, 2020, 17(2): 909-920.
[5]	吴垚, 曾菊儒, 彭辉, 等. 群智感知激励机制研究综述[J]. 软件学报, 2016, 27(8): 2025-2047.
	WU Y, ZENG J R, PENG H, et al. Survey on incentive mechanisms for crowd sensing[J]. Journal of Software, 2016, 27(8): 2025-2047.
[6]	童咏昕, 袁野, 成雨蓉, 等. 时空众包数据管理技术研究综述[J]. 软件学报, 2017, 28(1): 35-58.
	TONG Y X, YUAN Y, CHENG Y R, et al. Survey on spatiotemporal crowdsourced data management techniques[J]. Journal of Software, 2017, 28(1): 35-58.
[7]	邱晗光, 周愉峰. 基于嵌套Logit选择模型的城市配送自提柜选址-路径问题[J]. 计算机应用, 2018, 38(2): 582-588.
	QIU H G, ZHOU Y F. Reception box locating-vehicle routing problems in urban distribution based on nested Logit model[J]. Journal of Computer Applications, 2018, 38(2): 582-588.
[8]	KAZEMI L, SHAHABI C. GeoCrowd: enabling query ans-wering with spatial crowdsourcing[C]// Proceedings of the 20th International Conference on Advances in Geographic Information Systems, Redondo Beach, Nov 7-9, 2012. New York: ACM, 2012: 189-198.
[9]	KAZEMI L, SHAHABI C, CHEN L. GeoTruCrowd: trust-worthy query answering with spatial crowdsourcing[C]// Proceedings of the 21st SIGSPATIAL International Confe-rence on Advances in Geographic Information Systems, Orlando, Nov 5-8, 2013. New York: ACM, 2013: 314-323.
[10]	张志强, 逄居升, 谢晓芹, 等. 众包质量控制策略及评估算法研究[J]. 计算机学报, 2013, 36(8): 1636-1649.
	ZHANG Z Q, PANG J S, XIE X Q, et al. Research on crowdsourcing quality control strategies and evaluation al-gorithm[J]. Chinese Journal of Computers, 2013, 36(8): 1636-1649.
[11]	MYERSON R B. Optimal auction design[J]. Mathematics of Operations Research, 1981, 6(1): 58-73. DOI URL
[12]	VICKREY W. Counterspeculation, auctions, and competi-tive sealed tenders[J]. The Journal of Finance, 1961, 16(1): 8-37. DOI URL
[13]	CLARKE E H. Multipart pricing of public goods[J]. Public Choice, 1971, 11(1): 17-33. DOI URL
[14]	GROVES T. Incentives in teams[J]. Econometrica: Journal of the Econometric Society, 1973, 41(4): 617-631. DOI URL
[15]	FENG Z N, ZHU Y M, ZHANG Q, et al. TRAC: truthful auction for location-aware collaborative sensing in mobile crowdsourcing[C]// Proceedings of the 2014 IEEE Confe-rence on Computer Communications, Toronto, Apr 27-May 2, 2014. Piscataway: IEEE, 2014: 1231-1239.
[16]	CHEUNG M H, SOUTHWELL R, HOU F, et al. Distri-buted time-sensitive task selection in mobile crowdsensing[C]// Proceedings of the 16th ACM International Sympo-sium on Mobile Ad Hoc Networking and Computing, Hang-zhou, Jun 22-25, 2015. New York: ACM, 2015: 157-166.
[17]	KANG Q M, HE H, WEI J. An effective iterated greedy algorithm for reliability-oriented task allocation in distribu-ted computing systems[J]. Journal of Parallel and Distribu-ted Computing, 2013, 73(8): 1106-1115.
[18]	SINGLA A, SANTONI M, BARTÓK G, et al. Incentivizing users for balancing bike sharing systems[C]// Proceedings of the 29th AAAI Conference on Artificial Intelligence, Aus-tin, Jan 25-30, 2015. Menlo Park: AAAI, 2015: 723-729.
[19]	BAN S, HYUN K H. Designing a user participation-based bike rebalancing service[J]. Sustainability, 2019, 11(8): 2396. DOI URL
[20]	MA L, KANG Y J, LIU J P. Network information security privacy protection system in big data era[C]// Proceedings of the 3rd EAI International Conference on Advanced Hybrid Information Processing, Nanjing, Sep 21-22, 2019. Cham: Spinger, 2019: 65-73.
[21]	GEHRMANN C, GUNNARSSON M. An identity privacy preserving IoT data protection scheme for cloud based ana-lytics[C]// Proceedings of the 2019 IEEE International Con-ference on Big Data, Los Angeles, Dec 9-12, 2019. Piscata-way: IEEE, 2019: 5744-5753.
[22]	RODRIGUEZGARCIA M, BATET M, SÁNCHEZ D, et al. Utility-preserving privacy protection of nominal data sets via semantic rank swapping[J]. Information Fusion, 2019, 45(7): 282-295. DOI URL
[23]	PAPAKONSTANTINOU A, ROGERS A, GERDING E, et al. Mechanism design for eliciting probabilistic estimates from multiple suppliers with unknown costs and limited precision[C]// Proceedings of the 2009 Workshop on Agent-Mediated Electronic Commerce: Designing Trading Strategies and Mechanisms for Electronic Markets, 2009: 102-116.
[24]	ZHANG X, XUE G L, YU R Z, et al. Truthful incentive mechanisms for crowdsourcing[C]// Proceedings of the 2015 IEEE Conference on Computer Communications, Hong Kong, China, Apr 26-May 1, 2015. Piscataway: IEEE, 2015: 2830-2838.
[25]	IHARA T, TSURUTA S, TODO T, et al. Strategy-proof cake cutting mechanisms for all-or-nothing utility[J]. Fun-damenta Informaticae, 2018, 158: 41-61.
[26]	FUDENBERG D, TIROLE J. Game theory[M]. Cambridge: MIT Press, 1991.
[27]	NISAN N, ROUGHGARDEN T, TARDOS E, et al. Algo-rithmic game theory[M]. New York: Cambridge University Press, 2007.
[28]	NEDERLOF J. Algorithms for NP-hard problems via rank-related parameters of matrices[M]// Treewidth, Kernels, and Algorithms. Cham: Springer, 2020: 145-164.
[29]	ZHENG Z Z, YANG Z X, WU F, et al. Mechanism design for mobile crowdsensing with execution uncertainty[C]// Proceedings of the 37th IEEE International Conference on Distributed Computing Systems, Atlanta, Jun 5-8, 2017. Washington: IEEE Computer Society, 2017: 955-965.
[30]	WU W W, WANG W Y, LI M M, et al. Incentive mechani-sm design to meet task criteria in crowdsourcing: how to determine your budget[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(2): 502-516. DOI URL

Strategy Proof Mechanism for Bike-Sharing Maintenance Accomplishment Probability

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 30

Related Articles 1

Recommended Articles

Metrics