  In the classical framework of local distributed network computing, it is
generally assumed that the entities executing distributed algorithms are
altruistic. However, in various scenarios, the value of the output produced by
an entity may have a tremendous impact on its future. This is for instance the
case of tasks such as computing maximal independent sets (MIS) in networks.
Indeed, a node belonging to the MIS may be later asked more than to a node not
in the MIS, e.g., because MIS in networks are often used as backbones to
collect, transfer, and broadcast information, which is costly. In this paper,
we revisit typical local distributed network computing tasks in the framework
of algorithmic game theory. Specifically, we focus on the construction of
solutions for locally checkable labeling (LCL) tasks, which form a large class
of distributed tasks, including MIS, coloring, maximal matching, etc., and
which have been studied for more than 20 years in distributed computing.
  Given an LCL task, the nodes are collectively aiming at computing a solution,
but, at the individual level, every node plays rationally and selfishly with
the objective of optimizing its own profit. Surprisingly, the classical
frameworks for game theory are not fully appropriate for the purpose of our
study. Moreover, we show that classical notions like Nash equilibria may yield
algorithms requiring an arbitrarily large number of rounds to converge.
Nevertheless, by extending and generalizing core results from game theory, we
establish the existence of a so-called trembling-hand perfect equilibria, a
subset of Nash equilibria that is well suited to LCL construction tasks. The
main outcome of the paper is therefore that, for essentially all distributed
tasks whose solutions are locally checkable, there exist construction
algorithms which are robust to selfishness.
