Defesa de Doutorado de Félix Carvalho Rodrigues

Título do Trabalho
Non-cooperative Facility Location Games and Cost Perception
Candidato(a)
Félix Carvalho Rodrigues
Nível
Doutorado
Data
Add to Calender 2017-10-16 00:00:00 2017-10-16 00:00:00 Defesa de Doutorado de Félix Carvalho Rodrigues Non-cooperative Facility Location Games and Cost Perception Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00
Local
Sala 85 IC 2
Orientador(a)
Eduardo Candido Xavier
Banca Examinadora
Banca Examinadora
Titulares (Professores Doutores) Unidade / Instituição
Eduardo Candido Xavier IC/UNICAMP
Andre Luís Vignatti DInf/UFPR
Cristina Gomes Fernandes IME/USP
Flávio Keidi Miyazawa IC/UNICAMP
Rafael Crivellari Saliba Schouery IC/UNICAMP
Suplentes (Professores Doutores) Unidade / Instituição
Lehilton Lelis Chaves Pedrosa IC/UNICAMP
Fábio Luiz Usberti IC/UNICAMP
José Coelho de Pina Junior IME/USP
Resumo

Esta tese de doutorado cobre a interseção entre problemas de localização de instalações e teoria dos jogos algorítmica não cooperativa, com ênfase em alterações da percepção de custos de cada jogador e seu efeito na qualidade de equilíbrios. O problema de localização de instalações é um dos problemas fundamentais em otimização combinatória. Em sua versão clássica, existe um conjunto de terminais e um conjunto de instalações, e cada terminal necessita ser conectado a uma instalação, para que esta providencie bens ou serviços. O objetivo é minimizar o total dos custos associados à abertura das instalações e a conexão dos terminais a essas instalações. Na prática, existem diversos cenários onde é inviável ou não é desejável que uma autoridade central única decida como clientes devem escolher as instalações às quais se conectam. Dessa forma, é importante estudar como a independência desses terminais pode afetar a eficiência social e a complexidade computacional para esses cenários. A teoria dos jogos algorítmica pode ser útil para tais cenários, em particular sua parte não cooperativa. A teoria dos jogos algorítmica preenche uma lacuna entre a ciência da computação teórica e a teoria dos jogos, e está interessada em questões como a complexidade computacional de se encontrar equilíbrios, o quanto o bem-estar social pode ser perdido devido ao egoísmo de jogadores e como desenvolver mecanismos para garantir que o melhor interesse dos jogadores se alinhe com o ótimo social.

Nesta tese, estudamos jogos de localização de instalações não cooperativas e algumas de suas variantes. Focamos em responder questões relativas a existência de equilíbrios de Nash puros e sobre as principais medidas de perda de eficiência, o preço da anarquia e preço da estabilidade. Apresentamos uma revisão das descobertas mais importantes para as variantes básicas, com novos resultados nos casos onde nenhum era conhecido. Para a versão capacitada desses jogos, mostramos que, enquanto a simultaneidade pode levar a uma perda de eficiência não limitada, quando se admite a sequencialidade de jogadores, é possível mostrar que a perda de eficiência tem limites.

Também investigamos como mudanças na percepção de custo podem afetar a quali- dade de seus equilíbrios de duas maneiras: através de jogadores altruístas e de esquemas de taxação. No primeiro, adaptamos resultados de jogos de compartilhamento justo de custos e apresentamos novos resultados sobre uma versão sem regras de compartilha- mento. No último, propomos um modelo de mudança na percepção de custos, onde os jogadores consideram um pedágio adicional em suas conexões ao calcular seus custos. Nós apresentamos limitantes para o custo total das taxas no problema de pedágios mínimo, onde o objetivo é encontrar o valor mínima de pedágios necessário para garantir que um determinado perfil de estratégia socialmente ótimo seja escolhido pelos jogadores. Mos- tramos algoritmos para encontrar pedágios ótimos para tal problema em casos especiais e conjecturamos que, para o caso geral, é NP-dificil encontrar pedágios ótimos para esse problema, apresentando algumas evidências dessa afirmação ao provar que um problema de emparelhamento relacionado é NP-difícil.