Budget-balanced and strategy-proof auctions for ridesharing

Author(s)

Schwarzstein, Leonardo Y. ; Schouery, Rafael C. S.

• Document type: Journal article
• Source: Computers & Operations Research; v. 151, p. 14-pg., 2023-03-01.

Abstract

Ridesharing services have become widespread, and pricing the rides is a crucial problem for these systems. We propose and analyze a budget-balanced and strategy-proof auction, the Weighted Minimum Surplus (WMS) auction, for the dynamic ridesharing problem with multiple passengers per ride. Under the assumption of downward closed alternatives, we obtain lower bounds for the surplus welfare and surplus profit of the WMS auction. We also propose and analyze a budget-balanced version of the well-known VCG mechanism, the VCG. Encouraging experimental results were obtained for both the WMS auction and the VCG (AU)

• FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
• Grantee: Flávio Keidi Miyazawa
• Support Opportunities: Research Projects - Thematic Grants