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

DOI

Bibliographic Information

Other Title
  • 誘因両立性・個人合理性・予算制約を満たす多項式時間ライドシェアリングメカニズム

Abstract

<p>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 that satisfies all four properties and whose social cost is within 8.6% of the optimal on average.</p>

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top