FenixEdu™

Dissertação

Locally Verifiable Labelings and Nash Equilibria EVALUATED

Detalhes: Esta tese aborda uma relação útil entre eoria dos jogos e teoria da computação distribuída e explora possíveis generalizações dessa conexão. Teoria dos jogos estuda as interações entre agentes racionais. Com origem em economia, tem aplicações nas ciências sociais, informática e lógica. É comum que agentes, ao interagirem, desejem mudar a sua estratégia a fim de melhorar a sua utilidade. Quando agentes racionais interagem de forma estável, ou seja, nenhum deles quer mudar a sua estratégia, eles estão em num Nash Equilibrium. Existem dois tipos de Nash Equilibria, puro e misto, dependendo nos tipos de estratégias que os agentes podem ter. Computação distribuída é um campo de computer science que estuda como vários computadores devem interagir para funcionar como um sistema distribuído. Em modelos distribuídos, nós computacionais, que podem representar computadores, produzem estados finais comunicando com os seus vizinhos numa rede. Locally Verifiable Labeling (LVL) é um tipo de problema onde, para cada nó, é atribuído um valor de um conjunto de valores possíveis, satisfazendo condições específicas. Esses problemas podem ser relaxados em formulações mais gerais onde o conjunto permitido de valores é infinito, chamado de relaxamento fracionário. Nesta tese, é fornecida uma prova negativa sobre a generalização da coneção entre estes conceitos e são explorados exemplos da utilidade de vincular as duas áreas de pesquisa.
Keywords: Teoria de jogos, Nash equilibria, computação distribuída, locally verifiable labeling, dilemma do voluntário, conjunto independente maximal

Discussão: dezembro 9, 2022, 9:0