Achieving Location Truthfulness in Rebalancing Supply-Demand Distribution for Bike Sharing
Abstract
Recently, station-free Bike sharing as an environment-friendly transportation alternative has received wide adoption in many cities due to its flexibility of allowing bike parking at anywhere. How to incentivize users to park bikes at desired locations that match bike demands - a problem which we refer to as a rebalancing problem - has emerged as a new and interesting challenge. In this paper, we propose a solution under a crowdsourcing framework where users report their original destinations and the bike sharing platform assigns proper relocation tasks to them. 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. Therefore, we design a two-stage heuristic mechanism which selects an independent set of locations in the first stage and allocates tasks to users in the second stage. We show analytically that the mechanism satisfies location truthfulness, budget feasibility and individual rationality. In addition, extensive experiments are conducted to demonstrate the effectiveness of our mechanism. To the best of our knowledge, we are the first to address 2-D location truthfulness in the perspective of mechanism design.
Recommended Citation
H. Lv et al., "Achieving Location Truthfulness in Rebalancing Supply-Demand Distribution for Bike Sharing," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11343 LNCS, pp. 256 - 267, Springer Verlag, Dec 2018.
The definitive version is available at https://doi.org/10.1007/978-3-030-04618-7_21
Meeting Name
12th International Conference on Algorithmic Aspects in Information and Management, AAIM 2018 (2018: Dec. 3-4, Dallas, TX)
Department(s)
Computer Science
Keywords and Phrases
Bike sharing; Location truthfulness; Mechanism design
International Standard Book Number (ISBN)
978-303004617-0
International Standard Serial Number (ISSN)
0302-9743
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2018 Springer Verlag, All rights reserved.
Publication Date
01 Dec 2018
Comments
This work was supported in part by the National Key R&D Program of China 2018YFB1004703, in part by China NSF grant 61672348, 61672353, and 61472252.