Show simple item record

dc.contributor.author
Collet, Simon
dc.contributor.author
Fraigniaud, Pierre
dc.contributor.author
Penna, Paolo
dc.date.accessioned
2020-07-13T10:00:15Z
dc.date.available
2017-06-12T16:12:48Z
dc.date.available
2020-05-15T12:15:10Z
dc.date.available
2020-07-13T10:00:15Z
dc.date.issued
2016-07-13
dc.identifier.uri
http://hdl.handle.net/20.500.11850/122789
dc.description.abstract
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.
en_US
dc.language.iso
en
en_US
dc.publisher
Cornell University
en_US
dc.title
Local Distributed Algorithms for Selfish Agents
en_US
dc.type
Working Paper
ethz.journal.title
arXiv
ethz.pages.start
1607.03677
en_US
ethz.size
29 p.
en_US
ethz.identifier.arxiv
1607.03677
ethz.publication.place
Ithaca, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter / Widmayer, Peter
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter / Widmayer, Peter
ethz.date.deposited
2017-06-12T16:15:52Z
ethz.source
ECIT
ethz.identifier.importid
imp593654e17ff1765692
ethz.ecitpid
pub:185119
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2017-07-18T12:26:52Z
ethz.rosetta.lastUpdated
2021-02-15T15:26:16Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Local%20Distributed%20Algorithms%20for%20Selfish%20Agents&rft.jtitle=arXiv&rft.date=2016-07-13&rft.spage=1607.03677&rft.au=Collet,%20Simon&Fraigniaud,%20Pierre&Penna,%20Paolo&rft.genre=preprint&
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record