A Polynomial-time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism

Iwase, Tatsuya; Stein, Sebastian; Gerding, Enrico H.

doi:10.24963/ijcai.2021/38

A Polynomial-time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism

Tatsuya Iwase, Sebastian Stein, Enrico H. Gerding

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 268-275.

https://doi.org/10.24963/ijcai.2021/38

Keywords

Agent-based and Multi-agent Systems: Coordination and Cooperation
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems
Multidisciplinary Topics and Applications: Transportation

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.

Tatsuya Iwase, Sebastian Stein, and Enrico H. Gerding. 2021. A Polynomial-time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 268–275. https://doi.org/10.24963/ijcai.2021/38

@inproceedings{ijcai2021p38,
  title     = {A Polynomial-time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism},
  author    = {Iwase, Tatsuya and Stein, Sebastian and Gerding, Enrico H.},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {268--275},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/38},
  url       = {https://doi.org/10.24963/ijcai.2021/38},
}

TY  - CPAPER
TI  - A Polynomial-time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism
AU  - Iwase, Tatsuya
AU  - Stein, Sebastian
AU  - Gerding, Enrico H.
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 268
EP  - 275
DO  - 10.24963/ijcai.2021/38
UR  - https://doi.org/10.24963/ijcai.2021/38
ER  -