Game-theoretic analysis of transportation problems

Autor(es)

Francisco Jhonatas Melo da Silva

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2018-08-24

Membros da banca

Flávio Keidi Miyazawa; André Luís Vignatti; Carla Negri Lintzmayer

• Orientador: Flávio Keidi Miyazawa; Rafael Crivellari Saliba Schouery

Resumo

Problemas relacionados com meios de transporte são comumente encontrados na área de Otimização Combinatória, como, por exemplo, o Problema do Caixeiro Viajante e o Problema de Roteamento de Veículos. Nesta dissertação, consideramos um problema de transporte sob a perspectiva da teoria de jogos algorítmica onde todos os jogadores querem ser transportados a um destino em comum o mais rápido possível, e para isso eles devem escolher um dentre os ônibus disponíveis. Revisamos alguns resultados quanto à existência e à ineficiência de equilíbrios puros de Nash em relação a duas funções sociais. Então, apresentamos limitantes para o Preço de Anarquia para uma nova função social, chamada de função utilitária. Consideramos também o jogo na forma extensiva, o qual chamamos de jogos de transporte sequenciais e apresentamos limitantes para o Preço da Anarquia Sequencial considerando três funções sociais, para instâncias métricas e não-métricas (AU)

• Processo FAPESP: 17/05223-9 - Análise teórica de problemas de transporte sob a perspectiva da teoria dos jogos
• Beneficiário: Francisco Jhonatas Melo da Silva
• Modalidade de apoio: Bolsas no Brasil - Mestrado