Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/355669
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: 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
Title Alternative: Leilões à prova de estratégia e orçamento-balanceados para compartilhamento de viagens com múltiplos passageiros
Author: Schwarzstein, Leonardo Yvens, 1994-
Advisor: Schouery, Rafael Crivellari Saliba, 1986-
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$
Subject: Teoria da computação
Teoria dos jogos
Teoria dos leilões
Language: Português
Editor: [s.n.]
Citation: SCHWARZSTEIN, Leonardo Yvens. 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. 2020. 1 recurso online (49 p.) Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP.
Date Issue: 2020
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Schwarzstein_LeonardoYvens_M.pdf595.16 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.