Locally Verifiable Labelings and Nash Equilibria
Loading...
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2022-07-29
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
43
Series
Abstract
This thesis showcases a useful relation between game theory and distributed computing theory, and explores possible generalizations of this connection. Game theory studies the interactions between rational agents. With origins in economics, it has applications on social sciences, computer science and logic. It is usual that agents, when interacting, want to change their strategy in order to improve their gain. When the rational agents interact in a stable way, meaning none of them wants to change their strategies, they are in a Nash equilibrium. This concept is widely studied. There are two types of Nash equilibria, pure and mixed, depending on which kinds of strategies players can have. Distributed computing is a field of computer science that studies how multiple computers should interact in order to work as one distributed system. In distributed models, computational nodes, which could represent computers, produce outputs by communicating with its neighbors in a network. Locally verifiable labeling (LVL) is a type of problem where, to each node, it has be assigned a label from a set of possible labels, while satisfying specific conditions. These problems can be relaxed into more general formulations where the allowed set of labels is infinite, called a fractional relaxation. Nash equilibria and locally verifiable labelings are related. For any game G, there is always an LVL Pi whose solutions are equivalent to Nash equilibria of G, and vice-versa. In this thesis, a proof is provided showing that if the pure Nash equilibria of a game G are related to solutions of a locally verifiable labeling Pi, then it is not necessarily true that there is a relation between mixed Nash equilibria of G and solutions of the fractional relaxation of Pi. Furthermore, it explores examples of the usefulness of linking the two areas of research described above: studying both a game and its equivalent LVL enables a broader understanding surrounding these two objects. This work introduces a new tool and shows how it can be used. This tool can produce new results in both game theory and distributed computing and help understand existing results in a different way.Description
Supervisor
Suomela, JukkaThesis advisor
Santos, FranciscoKeywords
game theory, distributed computing, Nash equilibrium, locally verifiable labeling, volunteer's dilemma, maximal independent set
