Maintenance Task Dispatching And User Pricing Mechanism Design In Bike-sharing

As a green and low-carbon transportation way,bike-sharing provides a lot of convenience in our daily life.However,using these sharing bikes may result in some maintenance problems,such as bicycle damage,bicycle dispatching and so on.The bike-sharing platform hires users to complete bike maintenance tasks,and pays to users in order to incentive them to accomplish maintenance tasks.However,there exist multiple users to compete for the maintenance tasks.They may strategically report their private information such as task completion cost or task completion probability in order to make more profits,which may result in inefficient task dispatching for the platform.In this thesis,we intend to address these issues by designing strategy proof mechanisms.In more detail,regarding users’ strategic behavior in the task completion cost,we design strategy proof mechanism under budget constraint,while maximizing the sum of task values(i.e.weights).Regarding users’ strategic behavior in the task completion probability,we design a strategy proof mechanism to ensure that the task completion probability satisfies a certain threshold,and achieves the goal of minimizing the task completion cost.The main research work of this thesis is as follows:(1)We first describe the basic settings of bike maintenance tasks.In more detail,we describe the basic settings of bike-sharing platform and users.Then,regarding users’ strategic behavior in the task completion cost,we provide the mathematical definition of bike maintenance task weight maximization under the budget constraints.Regarding users’ strategic behavior of task completion probability,we provide the mathematical definition of bike maintenance task completion cost minimization under the constraint that the task completion probability should satisfy a certain threshold.(2)Under the budget constraints,considering that users may lie about task completion cost information,we design a mechanism to meet the properties of incentive compatibility and individual rationality.The mechanism consists of task dispatching and user pricing algorithms,which is strategy proof in the task completion cost.We use a technique of linear programming to improve the classical greedy algorithm by introducing Max operation in the submodule maximization problem,and design a task dispatching algorithm satisfying the monotonicity.Then based on the critical price,we design a user pricing algorithm satisfying budget constraints.We theoretically prove that our mechanism can satisfy the properties of incentive compatible,individual rationality and budget balance.Furthermore we run extensive experiments to evaluate our mechanism based on a Mobike dataset.The results show that compared with the classical greedy algorithm,the approximate single pricing algorithm and the optimal algorithm,our mechanism can achieve performance similar to the optimal algorithm in the metrics of task area coverage,task weight sum,total cost for platform expenditure and unit cost weight sum,and is better than another two algorithms.(3)Under the condition of ensuring the probability of task completion achieving a certain threshold,we design a strategy proof mechanism to make sure that users report the probability of task completion truthfully,which consists of task dispatching and user pricing algorithms.In order to minimize the cost,we design a task dispatching algorithm based on a greedy method,which is monotonic.We then design a user pricing algorithm based on critical price.We theoretically prove that our mechanism can satisfy the properties of incentive compatible and individual rationality.Furthermore we run extensive experiments to evaluate our mechanism based on a Mobike dataset in terms of task completion cost,user average expected utility and user expected utility probability density.The results show that compared with the VCG mechanism,our mechanism can achieve a constant times of the approximate ratio,lower task completion cost and a higher average expected utility of users.