The Opt-In Radius Auction: An Exact Two-Sided Hypergraph- VCG Mechanism for Multi-Passenger Ride-Sharing

Abstract Ride-sharing platforms usually apply a single pickup radius to every passenger and price pooled trips with one common rule, although passengers differ in how far they will travel to be picked up and in how much they value sharing. This paper proposes the Opt-In Radius Auction (ORA), an exact two-sided hypergraph Vickrey–Clarke–Groves (VCG) mechanism in which each passenger reports a solo valuation, a shared-ride valuation, a maximum pickup distance, and a maximum detour, and each driver reports a private reservation value. Under exact winner determination, quasi-linear utilities, and genuine hard acceptability bounds, ORA is dominant-strategy incentive compatible and ex-post individually rational on both sides; budget balance is not imposed and the platform deficit is reported as an outcome. The mechanism is evaluated on paired synthetic markets and on semi-synthetic Manhattan demand estimated from 15.15 million New York City Taxi and Limousine Commission trip records. At a 2.0 km global radius, a VCG ablation raises nominal welfare from 92.85 to 112.25 and the match rate from 59.17% to 75.50%, but serves 33.23% of its passengers beyond their true pickup limits, against 0% for ORA. The computational bottleneck at larger scale is the Clarke-payment counterfactuals rather than the allocation itself.

Authors

Institutions

Publication Details

Journal
Research Square
Published
2026-11-12
DOI
https://doi.org/10.21203/rs.3.rs-11409488/v1
Primary Topic
Transportation and Mobility Innovations
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The Opt-In Radius Auction: An Exact Two-Sided Hypergraph- VCG Mechanism for Multi-Passenger Ride-Sharing

Sandhya Parasnath Dubey, Shailendra Kumar Tiwari, Mario Verdyguer Cuevas
Research Square
Transportation and Mobility Innovations
preprint

The Opt-In Radius Auction: An Exact Two-Sided Hypergraph- VCG Mechanism for Multi-Passenger Ride-Sharing

Sandhya Parasnath Dubey, Shailendra Kumar Tiwari, Mario Verdyguer Cuevas
preprint en

Abstract

Abstract Ride-sharing platforms usually apply a single pickup radius to every passenger and price pooled trips with one common rule, although passengers differ in how far they will travel to be picked up and in how much they value sharing. This paper proposes the Opt-In Radius Auction (ORA), an exact two-sided hypergraph Vickrey–Clarke–Groves (VCG) mechanism in which each passenger reports a solo valuation, a shared-ride valuation, a maximum pickup distance, and a maximum detour, and each driver reports a private reservation value. Under exact winner determination, quasi-linear utilities, and genuine hard acceptability bounds, ORA is dominant-strategy incentive compatible and ex-post individually rational on both sides; budget balance is not imposed and the platform deficit is reported as an outcome. The mechanism is evaluated on paired synthetic markets and on semi-synthetic Manhattan demand estimated from 15.15 million New York City Taxi and Limousine Commission trip records. At a 2.0 km global radius, a VCG ablation raises nominal welfare from 92.85 to 112.25 and the match rate from 59.17% to 75.50%, but serves 33.23% of its passengers beyond their true pickup limits, against 0% for ORA. The computational bottleneck at larger scale is the Clarke-payment counterfactuals rather than the allocation itself.

Research Square
Manipal Academy of Higher Education (IN), Universidad Politécnica de Madrid (ES)
Sustainable cities and communities
Transportation and Mobility Innovations
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon