A Polynomial-Time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism
Abstract
Ridesharing has great potential to improve transportation efficiency while reducing congestion and pollution. To realize this potential, mechanisms are needed that allocate vehicles optimally and provide the right incentives to riders. However, many existing approaches consider restricted settings (e.g., only one rider per vehicle or a common origin for all riders). Moreover, naive applications of standard approaches, such as the Vickrey-Clarke-Groves or greedy mechanisms, cannot achieve a polynomial-time, truthful, individually rational and budget balanced mechanism. To address this, we formulate a general ridesharing problem and apply mechanism design to develop a novel mechanism which satisfies all four properties and whose social cost is within 8.6% of the optimal on average.
Cite
Text
Iwase et al. "A Polynomial-Time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/38Markdown
[Iwase et al. "A Polynomial-Time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/iwase2021ijcai-polynomial/) doi:10.24963/IJCAI.2021/38BibTeX
@inproceedings{iwase2021ijcai-polynomial,
title = {{A Polynomial-Time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism}},
author = {Iwase, Tatsuya and Stein, Sebastian and Gerding, Enrico H.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2021},
pages = {268-275},
doi = {10.24963/IJCAI.2021/38},
url = {https://mlanthology.org/ijcai/2021/iwase2021ijcai-polynomial/}
}