Equilibria of Games in Networks for Local Tasks

Simon Collet 1 Pierre Fraigniaud 1, 2 Paolo Penna 1
2 GANG - Networks, Graphs and Algorithms
IRIF - Institut de Recherche en Informatique Fondamentale, Inria de Paris
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.
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-01964761
Contributor : Pierre Fraigniaud <>
Submitted on : Sunday, December 23, 2018 - 3:16:02 PM
Last modification on : Wednesday, October 2, 2019 - 5:29:08 PM
Long-term archiving on: Sunday, March 24, 2019 - 1:21:16 PM

File

paper16.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Simon Collet, Pierre Fraigniaud, Paolo Penna. Equilibria of Games in Networks for Local Tasks. OPODIS 2018 - 22nd International Conference on Principles of Distributed Systems, Dec 2018, Hong-Kong, China. ⟨10.4230/LIPIcs.OPODIS.2018.0⟩. ⟨hal-01964761⟩

Share

Metrics

Record views

121

Files downloads

62