Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T15:27:35Z (GMT). No. of bitstreams: 1
Curi_RafaelLima_M.pdf: 1469554 bytes, checksum: 8367cf52c9256338ee2963b9a9cdf41d (MD5)
Previous issue date: 2013 / Resumo: Neste trabalho estudamos Jogos de Roteamento. Esta subclasse de jogos e uma das mais estudadas na literatura e permite modelar de forma relativamente simples vários cenários realistas. Por exemplo, tráfego de veículos em rodovias, transporte de mercadorias, redes de telefonia, redes de computadores como a Internet, etc. Analisamos as principais variantes de jogos de roteamento, destacando suas diferenças. Comparamos jogos atômicos versus jogos não-atômicos, jogos com fluxo divisível versus jogos com fluxo indivisível, jogos com demanda uniforme versus jogos com demanda genérica e jogos com redes específicas versus jogos com redes genéricas. Focamos nosso estudo na existência, unicidade e quantificação da ineficiência de equilíbrios que emergem do comportamento independente e egoísta dos jogadores. Estudamos o equilíbrio de Wardrop para jogos não-atômicos e o equilíbrio de Nash para jogos atômicos. Na literatura, notamos que a existência e unicidade de um equilíbrio dependem basicamente de três fatores: pressupostos nas funções que definem os custos dos segmentos de uma rota, tipo dos jogadores (atômicos ou não-atômicos, com demandas iguais ou diferentes) e topologia da rede. Apresentamos também os principais resultados de ineficiência obtidos para as métricas Preço da Anarquia (PoA) e Limite de Bicritério. Nos resultados que vimos, observamos que jogos não-atômicos possuem um PoA menor que o de jogos atômicos, jogos com fluxo divisível possuem um PoA menor que o de jogos com fluxo indivisível e jogos com demanda uniforme um PoA menor que o de jogos com demanda genérica / Abstract: In this work, we study Routing Games. This subclass of games is one of the most studied in the literature and allows us to model several realistic scenarios, in a relatively simple way. For instance, road traffic, freight transportation, telephone networks, computer networks like the Internet, etc. We analyze the main variants of routing games, emphasizing their differences. We compare atomic games versus nonatomic games, unsplittable flow games versus splittable flow games, unweighted games versus weighted games and specific network games versus generic network games. We focus our study on the existence, uniqueness and quantification of the inefficiency of equilibria that emerge from the independent and selfish behavior of the players. We study the Wardrop equilibrium for nonatomic games and the Nash equilibrium for atomic games. In the literature, we note that the existence and uniqueness of an equilibrium depends basically on three factors: assumptions on the functions that define the costs of the segments of a route, type of the players (atomic or nonatomic, with equal or different demands), and network topology. We present the main results of inefficiency obtained for the metrics Price of Anarchy (PoA) and Bicriteria Limit. In the results we have considered, we noticed that nonatomic games have lower PoA than the atomic ones, splittable flow games have lower PoA than the unsplittable flow ones, and unweighted games have lower PoA than the weighted ones / Mestrado / Ciência da Computação / Mestre em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/275647 |
| Date | 22 August 2018 |
| Creators | Curi, Rafael Lima, 1985- |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Lee, Orlando, 1969-, Miyazawa, Flávio Keidi, Fernandes, Cristina Gomes |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 113 p. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0058 seconds