https://research-explorer.ista.ac.at 2000-01-01T00:00+00:00 1 monthly https://research-explorer.ista.ac.at/record/9402 Schmid, Laura Chatterjee, Krishnendu Hilbe, Christian Nowak, Martin A. 2021 Direct and indirect reciprocity are key mechanisms for the evolution of cooperation. Direct reciprocity means that individuals use their own experience to decide whether to cooperate with another person. Indirect reciprocity means that they also consider the experiences of others. Although these two mechanisms are intertwined, they are typically studied in isolation. Here, we introduce a mathematical framework that allows us to explore both kinds of reciprocity simultaneously. We show that the well-known ‘generous tit-for-tat’ strategy of direct reciprocity has a natural analogue in indirect reciprocity, which we call ‘generous scoring’. Using an equilibrium analysis, we characterize under which conditions either of the two strategies can maintain cooperation. With simulations, we additionally explore which kind of reciprocity evolves when members of a population engage in social learning to adapt to their environment. Our results draw unexpected connections between direct and indirect reciprocity while highlighting important differences regarding their evolvability. https://research-explorer.ista.ac.at/record/9402 https://research-explorer.ista.ac.at/download/9402/14496 eng Springer Nature info:eu-repo/semantics/altIdentifier/doi/10.1038/s41562-021-01114-8 info:eu-repo/semantics/altIdentifier/issn/2397-3374 info:eu-repo/semantics/altIdentifier/wos/000650304000002 info:eu-repo/semantics/altIdentifier/pmid/33986519 info:eu-repo/grantAgreement/EC/H2020/863818 info:eu-repo/grantAgreement/EC/FP7/279307 info:eu-repo/semantics/openAccess Schmid L, Chatterjee K, Hilbe C, Nowak MA. A unified framework of direct and indirect reciprocity. <i>Nature Human Behaviour</i>. 2021;5(10):1292–1302. doi:<a href="https://doi.org/10.1038/s41562-021-01114-8">10.1038/s41562-021-01114-8</a> ddc:000 A unified framework of direct and indirect reciprocity info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_6501 https://research-explorer.ista.ac.at/record/11866 Henzinger, Monika H Krinninger, Sebastian Nanongkai, Danupon 2016 We present a deterministic (1+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation Õ(n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1/8, and (ii) the O(є−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s Õ(n1/2+є+D)-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω(n1/2/logn + D) [Das Sarma et al. STOC 2011] modulo some lower-order terms, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for approximating a network’s weighted diameter which almost matches the lower bound by Holzer et al. [PODC 2012]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic, construction of an (no(1), o(1))-hop set of size O(n1+o(1)). We combine these techniques with many distributed algorithmic techniques, some of which from problems that are not directly related to shortest paths, e.g. ruling sets [Goldberg et al. STOC 1987], source detection [Lenzen, Peleg PODC 2013], and partial distance estimation [Lenzen, Patt-Shamir PODC 2015]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation O(no(1))-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation O(no(1)logW)-pass O(n1+o(1)logW)-space streaming algorithm, when edge weights are in {1, 2, …, W}. The first result answers an open problem in [Nanongkai, STOC 2014]. The second result partially answers an open problem raised by McGregor in 2006 [<pre>sublinear.info</pre>, Problem 14]. https://research-explorer.ista.ac.at/record/11866 eng Association for Computing Machinery info:eu-repo/semantics/altIdentifier/doi/10.1145/2897518.2897638 info:eu-repo/semantics/altIdentifier/issn/0737-8017 info:eu-repo/semantics/altIdentifier/isbn/978-145034132-5 info:eu-repo/semantics/altIdentifier/arxiv/1504.07056 info:eu-repo/semantics/openAccess Henzinger M, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>. Association for Computing Machinery; 2016:489-498. doi:<a href="https://doi.org/10.1145/2897518.2897638">10.1145/2897518.2897638</a> A deterministic almost-tight distributed algorithm for approximating single-source shortest paths info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794