Hardness of and Approximate Mechanism Design for the Bike Rebalancing Problem


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.


Computer Science

Research Center/Lab(s)

Center for High Performance Computing Research


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.

Keywords and Phrases

Approximate mechanism; Location truthfulness; Sharing economy

International Standard Serial Number (ISSN)


Document Type

Article - Journal

Document Version


File Type





© 2019 Elsevier B.V., All rights reserved.

Publication Date

10 Jan 2020