Locally Verifiable Labelings and Nash Equilibria

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Computer Science
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
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.
Suomela, Jukka
Thesis advisor
Santos, Francisco
game theory, distributed computing, Nash equilibrium, locally verifiable labeling, volunteer's dilemma, maximal independent set
Other note