Title

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.

Department(s)

Computer Science

Comments

Article in press

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.

Share

 
COinS