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.

翻译：为了实现这一潜力,需要建立最佳分配车辆和为骑车者提供恰当奖励的机制;然而,许多现有办法都考虑到限制环境(例如,每辆车辆只有一名骑手或所有骑车者的共同来源),此外,天真地应用标准办法,如维克雷-克拉克-格罗夫斯或贪婪机制等,无法实现多时制、真实、个别合理和预算平衡的机制;为解决这一问题,我们提出一个一般的搭车问题,并采用机制设计,以建立一个满足所有四种特性的新机制,其社会成本平均在最佳成本的8.6%之内。