Budget-balanced and strategy-proof auctions for multi-passenger ridesharing : Leilões à prova de estratégia e orçamento-balanceados para compartilhamento de viagens com múltiplos passageiros

Abstract

Resumo: Serviços de compartilhamento de viagens se popularizaram, e a precificação de viagens é um problema crucial para estes sistemas. Nesta dissertação, nós propomos e analisamos um novo mecanismo orçamento-balanceado e à prova de estratégia, o leilão \emph{Weighted Minimum Surplus} (WMS), para o problema de compartilhamento de viagens dinâmico com múltiplos passageiros por viagem. Também propomos e analisamos uma versão orçamento-balanceado do mecanismo VCG (Vickrey-Clarke-Groves), o $\mathrm{VCG}_s$. Sob a hipótese de alternativas \emph{downward closed}, obtemos um limitante inferior para o bem-estar social excedente e o lucro excedente do WMS. Apresentamos um algoritmo exato baseado em programação linear inteira para resolver estes leilões. Resultados experimentais encorajadores são obtidos para o lucro e bem estar social tanto do WMS como do $\mathrm{VCG}_s$

Abstract: Ridesharing and ridesourcing services have become widespread, and the pricing of rides is a crucial problem for these systems. In this thesis, we propose and analyze a novel budget-balanced and strategy-proof mechanism, the Weighted Minimum Surplus (WMS) auction, for the dynamic ridesharing problem with multiple passengers per ride. We also analyze a budget-balanced version of the well-known VCG (Vickrey-Clarke-Groves) mechanism, the $\mathrm{VCG}_s$. Under the assumption of downward closed alternatives, we obtain a lower bound for the surplus welfare and surplus profit of the WMS. We present an exact algorithm based on integer linear programming to solve these auctions. Encouraging experimental results for profit and welfare were obtained for both the WMS auction and the $\mathrm{VCG}_s$