Locally Verifiable Labelings and Nash Equilibria

Thumbnail Image

Files

master_Fernandes_Batista_João_2022.pdf (915.21 KB)

URL

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.

Authors

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, Jukka

Thesis advisor

Santos, Francisco

Keywords

game theory, distributed computing, Nash equilibrium, locally verifiable labeling, volunteer's dilemma, maximal independent set

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202208285204

Collections

[dipl] Perustieteiden korkeakoulu / SCI