An auction based task dispatching and pricing mechanism in bike-sharing

摘要

As an economical, low-carbon and convenient travel model, bike-sharing has become common in many cities around the world. However, the daily usage of shared bikes results in the dispatching problem, i.e., dispatching bikes to the specific destinations to satisfy riding demands. The bike-sharing platform can hire riders as workers and pay to incentivize them to accomplish the dispatching tasks. However, there exist multiple workers competing for the dispatching tasks, and they may strategically report their task accomplishing costs (which are usually private information only known by themselves) in order to make more profits, which may result in inefficient task dispatching results. In this paper, we first design a dispatching algorithm named GDY-MAX to allocate tasks to workers, which can achieve good performance. However, it cannot prevent workers strategically misreporting their task accomplishing costs. Regarding this issue, we further design a strategy proof mechanism under the budget constraint, which consists of a task dispatching algorithm and a worker pricing algorithm. We theoretically prove that our mechanism can satisfy incentive compatibility, individual rationality, budget constraint and a constant approximation ratio. Furthermore, we run extensive experiments to evaluate our mechanism based on a Mobike dataset. The results show that the performance of the proposed strategy proof mechanism and GDY-MAX is similar to the optimal algorithm in terms of the coverage ratio of accomplished task regions and the sum of task region value, and our mechanism has better performance than the uniform algorithm in terms of the total payment and the unit cost value.