License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.6
URN: urn:nbn:de:0030-drops-100668
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10066/
Collet, Simon ;
Fraigniaud, Pierre ;
Penna, Paolo
Equilibria of Games in Networks for Local Tasks
Abstract
Distributed tasks such as constructing a maximal independent set (MIS) in a network, or properly coloring the nodes or the edges of a network with reasonably few colors, are known to admit efficient distributed randomized algorithms. Those algorithms essentially proceed according to some simple generic rules, by letting each node choosing a temptative value at random, and checking whether this choice is consistent with the choices of the nodes in its vicinity. If this is the case, then the node outputs the chosen value, else it repeats the same process. Although such algorithms are, with high probability, running in a polylogarithmic number of rounds, they are not robust against actions performed by rational but selfish nodes. Indeed, such nodes may prefer specific individual outputs over others, e.g., because the formers suit better with some individual constraints. For instance, a node may prefer not being placed in a MIS as it is not willing to serve as a relay node. Similarly, a node may prefer not being assigned some radio frequencies (i.e., colors) as these frequencies would interfere with other devices running at that node. In this paper, we show that the probability distribution governing the choices of the output values in the generic algorithm can be tuned such that no nodes will rationally deviate from this distribution. More formally, and more generally, we prove that the large class of so-called LCL tasks, including MIS and coloring, admit simple "Luby's style" algorithms where the probability distribution governing the individual choices of the output values forms a Nash equilibrium. In fact, we establish the existence of a stronger form of equilibria, called symmetric trembling-hand perfect equilibria for those games.
BibTeX - Entry
@InProceedings{collet_et_al:LIPIcs:2018:10066,
author = {Simon Collet and Pierre Fraigniaud and Paolo Penna},
title = {{Equilibria of Games in Networks for Local Tasks}},
booktitle = {22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
pages = {6:1--6:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-098-9},
ISSN = {1868-8969},
year = {2018},
volume = {125},
editor = {Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10066},
URN = {urn:nbn:de:0030-drops-100668},
doi = {10.4230/LIPIcs.OPODIS.2018.6},
annote = {Keywords: Local distributed computing, Locally checkable labelings}
}
|
Keywords: |
|
Local distributed computing, Locally checkable labelings |
|
Collection: |
|
22nd International Conference on Principles of Distributed Systems (OPODIS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
15.01.2019 |
