Hardness of and Approximate Mechanism Design for the Bike Rebalancing Problem
Abstract
Recently arose in the flourishing sharing economy, the bike rebalancing problem is a new challenge that concerns how to incentivize users to park bikes at system-desired locations that better meet bike demands. It can also be generalized to other location-based vehicle or tool sharing problems such as car, truck, drone, and trolley sharing. In this paper, we address this problem using an auction model under a crowdsourcing framework, where users report their original destinations and the bike sharing platform assigns proper relocation tasks to them in order to better balance the bike supply and demand. We first prove two impossibility results: (1) finding an optimal solution to the bike rebalancing problem is NP-hard, and (2) there is no approximate mechanism with bounded approximation ratio that is both truthful and budget-feasible. To overcome this barrier, we introduce two practical constraints and design a two-stage approximate mechanism that satisfies location truthfulness, budget feasibility, individual rationality, and achieves constant approximation ratio. To the best of our knowledge, we are the first to address two dimensional location truthfulness in the regime of mechanism design. In addition, our extensive experiments based on real-world dataset demonstrate that our proposed mechanism can effectively redress the imbalance of bike distribution.
Recommended Citation
H. Lv et al., "Hardness of and Approximate Mechanism Design for the Bike Rebalancing Problem," Theoretical Computer Science, vol. 803, pp. 105 - 115, Elsevier B.V., Jan 2020.
The definitive version is available at https://doi.org/10.1016/j.tcs.2019.07.030
Department(s)
Computer Science
Research Center/Lab(s)
Center for High Performance Computing Research
Keywords and Phrases
Approximate mechanism; Location truthfulness; Sharing economy
International Standard Serial Number (ISSN)
0304-3975
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2019 Elsevier B.V., All rights reserved.
Publication Date
10 Jan 2020
Comments
This work was supported in part by the National Key R&D Program of China 2018YFB1004703, in part by China NSF grant 61672348 and 61672353, in part by the Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing 2018A09, and in part by Alibaba Group through Alibaba Innovation Research Program.