Game-theoretic analysis of transportation problems [recurso eletrônico] = Análise de problemas de transporte sob a perspectiva da teoria de jogos
Francisco Jhonatas Melo da Silva
DISSERTAÇÃO
Inglês
T/UNICAMP Si38g
[Análise de problemas de transporte sob a perspectiva da teoria de jogos]
Campinas, SP : [s.n.], 2018.
1 recurso online (49 p.) : il., digital, arquivo PDF.
Orientadores: Flávio Keidi Miyazawa, Rafael Crivellari Saliba Schouery
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
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...
Ver mais
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
Ver menos
Abstract: Problems related to transportation, such as the Traveling Salesman Problem and the Vehicle Routing Problem, commonly appear in the Combinatorial Optimization area. In this master¿s thesis, we present a game-theoretic analysis of a transportation game where all players want to be...
Ver mais
Abstract: Problems related to transportation, such as the Traveling Salesman Problem and the Vehicle Routing Problem, commonly appear in the Combinatorial Optimization area. In this master¿s thesis, we present a game-theoretic analysis of a transportation game where all players want to be transported to a common destination as quickly as possible and, in order to achieve this goal, they have to choose one of the available buses. We review some results concerned with the existence and inefficiency of Pure Nash Equilibria in relation with two social functions. Then, we give bounds on the Price of Anarchy to a new social function, called the utilitarian function. Furthermore, we consider the game in its extensive form, which we call sequential transportation games, and then we provide bounds for the Sequential Price of Anarchy considering three social functions in both metric and non-metric instances
Ver menos
Requisitos do sistema: Software para leitura de arquivo em PDF
Miyazawa, Flávio Keidi, 1970-
Orientador
Schouery, Rafael Crivellari Saliba, 1986-
Coorientador
Vignatti, André Luís
Avaliador
Lintzmayer, Carla Negri, 1990-
Avaliador
Game-theoretic analysis of transportation problems [recurso eletrônico] = Análise de problemas de transporte sob a perspectiva da teoria de jogos
Francisco Jhonatas Melo da Silva
Game-theoretic analysis of transportation problems [recurso eletrônico] = Análise de problemas de transporte sob a perspectiva da teoria de jogos
Francisco Jhonatas Melo da Silva