[{"acknowledgement":"J.S. and K.C. acknowledge support from the ERC CoG 863818 (ForM-SMArt)","oa":1,"quality_controlled":"1","publisher":"The Royal Society","year":"2023","has_accepted_license":"1","isi":1,"publication":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences","day":"29","date_created":"2023-04-02T22:01:09Z","date_published":"2023-03-29T00:00:00Z","doi":"10.1098/rspa.2022.0685","article_number":"20220685","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"citation":{"ista":"Svoboda J, Tkadlec J, Kaveh K, Chatterjee K. 2023. Coexistence times in the Moran process with environmental heterogeneity. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 479(2271), 20220685.","chicago":"Svoboda, Jakub, Josef Tkadlec, Kamran Kaveh, and Krishnendu Chatterjee. “Coexistence Times in the Moran Process with Environmental Heterogeneity.” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. The Royal Society, 2023. https://doi.org/10.1098/rspa.2022.0685.","short":"J. Svoboda, J. Tkadlec, K. Kaveh, K. Chatterjee, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 479 (2023).","ieee":"J. Svoboda, J. Tkadlec, K. Kaveh, and K. Chatterjee, “Coexistence times in the Moran process with environmental heterogeneity,” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 479, no. 2271. The Royal Society, 2023.","apa":"Svoboda, J., Tkadlec, J., Kaveh, K., & Chatterjee, K. (2023). Coexistence times in the Moran process with environmental heterogeneity. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. The Royal Society. https://doi.org/10.1098/rspa.2022.0685","ama":"Svoboda J, Tkadlec J, Kaveh K, Chatterjee K. Coexistence times in the Moran process with environmental heterogeneity. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2023;479(2271). doi:10.1098/rspa.2022.0685","mla":"Svoboda, Jakub, et al. “Coexistence Times in the Moran Process with Environmental Heterogeneity.” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 479, no. 2271, 20220685, The Royal Society, 2023, doi:10.1098/rspa.2022.0685."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","external_id":{"isi":["000957125500002"]},"author":[{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","full_name":"Svoboda, Jakub","last_name":"Svoboda"},{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","last_name":"Tkadlec"},{"last_name":"Kaveh","full_name":"Kaveh, Kamran","first_name":"Kamran"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"}],"title":"Coexistence times in the Moran process with environmental heterogeneity","abstract":[{"lang":"eng","text":"Populations evolve in spatially heterogeneous environments. While a certain trait might bring a fitness advantage in some patch of the environment, a different trait might be advantageous in another patch. Here, we study the Moran birth–death process with two types of individuals in a population stretched across two patches of size N, each patch favouring one of the two types. We show that the long-term fate of such populations crucially depends on the migration rate μ\r\n between the patches. To classify the possible fates, we use the distinction between polynomial (short) and exponential (long) timescales. We show that when μ is high then one of the two types fixates on the whole population after a number of steps that is only polynomial in N. By contrast, when μ is low then each type holds majority in the patch where it is favoured for a number of steps that is at least exponential in N. Moreover, we precisely identify the threshold migration rate μ⋆ that separates those two scenarios, thereby exactly delineating the situations that support long-term coexistence of the two types. We also discuss the case of various cycle graphs and we present computer simulations that perfectly match our analytical results."}],"oa_version":"Published Version","scopus_import":"1","intvolume":" 479","month":"03","publication_status":"published","publication_identifier":{"issn":["1364-5021"],"eissn":["1471-2946"]},"language":[{"iso":"eng"}],"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","success":1,"checksum":"13953d349fbefcb5d21ccc6b303297eb","file_id":"12796","creator":"dernst","file_size":827784,"date_updated":"2023-04-03T06:25:29Z","file_name":"2023_ProceedingsRoyalSocietyA_Svoboda.pdf","date_created":"2023-04-03T06:25:29Z"}],"license":"https://creativecommons.org/licenses/by/4.0/","ec_funded":1,"volume":479,"issue":"2271","related_material":{"link":[{"relation":"research_data","url":"https://doi.org/10.6084/m9.figshare.21261771.v1"}]},"_id":"12787","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","status":"public","date_updated":"2023-08-01T13:58:34Z","ddc":["000"],"department":[{"_id":"KrCh"}],"file_date_updated":"2023-04-03T06:25:29Z"},{"publication_status":"published","publication_identifier":{"issn":["0922-6389"],"isbn":["9781643684369"]},"language":[{"iso":"eng"}],"file":[{"creator":"dernst","date_updated":"2023-11-13T10:16:10Z","file_size":501011,"date_created":"2023-11-13T10:16:10Z","file_name":"2023_FAIA_Avni.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"14529","checksum":"1390ca38480fa4cf286b0f1a42e8c12f","success":1}],"license":"https://creativecommons.org/licenses/by-nc/4.0/","ec_funded":1,"volume":372,"abstract":[{"lang":"eng","text":"We consider bidding games, a class of two-player zero-sum graph games. The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simultaneously submit bids, and the higher bidder moves the token, where we break bidding ties in favor of Player 1. Player 1 wins the game iff the token visits a designated target vertex. We consider, for the first time, poorman discrete-bidding in which the granularity of the bids is restricted and the higher bid is paid to the bank. Previous work either did not impose granularity restrictions or considered Richman bidding (bids are paid to the opponent). While the latter mechanisms are technically more accessible, the former is more appealing from a practical standpoint. Our study focuses on threshold budgets, which is the necessary and sufficient initial budget required for Player 1 to ensure winning against a given Player 2 budget. We first show existence of thresholds. In DAGs, we show that threshold budgets can be approximated with error bounds by thresholds under continuous-bidding and that they exhibit a periodic behavior. We identify closed-form solutions in special cases. We implement and experiment with an algorithm to find threshold budgets."}],"oa_version":"Published Version","scopus_import":"1","intvolume":" 372","month":"09","date_updated":"2023-11-13T10:18:45Z","ddc":["000"],"file_date_updated":"2023-11-13T10:16:10Z","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"_id":"14518","conference":{"start_date":"2023-09-30","end_date":"2023-10-04","location":"Krakow, Poland","name":"ECAI: European Conference on Artificial Intelligence"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)"},"type":"conference","status":"public","year":"2023","has_accepted_license":"1","publication":"Frontiers in Artificial Intelligence and Applications","day":"28","page":"141-148","date_created":"2023-11-12T23:00:56Z","date_published":"2023-09-28T00:00:00Z","doi":"10.3233/FAIA230264","acknowledgement":"This research was supported in part by ISF grant no. 1679/21, ERC CoG 863818 (FoRM-SMArt) and the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie Grant Agreement No. 665385.","oa":1,"publisher":"IOS Press","quality_controlled":"1","citation":{"ista":"Avni G, Meggendorfer T, Sadhukhan S, Tkadlec J, Zikelic D. 2023. Reachability poorman discrete-bidding games. Frontiers in Artificial Intelligence and Applications. ECAI: European Conference on Artificial Intelligence vol. 372, 141–148.","chicago":"Avni, Guy, Tobias Meggendorfer, Suman Sadhukhan, Josef Tkadlec, and Dorde Zikelic. “Reachability Poorman Discrete-Bidding Games.” In Frontiers in Artificial Intelligence and Applications, 372:141–48. IOS Press, 2023. https://doi.org/10.3233/FAIA230264.","apa":"Avni, G., Meggendorfer, T., Sadhukhan, S., Tkadlec, J., & Zikelic, D. (2023). Reachability poorman discrete-bidding games. In Frontiers in Artificial Intelligence and Applications (Vol. 372, pp. 141–148). Krakow, Poland: IOS Press. https://doi.org/10.3233/FAIA230264","ama":"Avni G, Meggendorfer T, Sadhukhan S, Tkadlec J, Zikelic D. Reachability poorman discrete-bidding games. In: Frontiers in Artificial Intelligence and Applications. Vol 372. IOS Press; 2023:141-148. doi:10.3233/FAIA230264","ieee":"G. Avni, T. Meggendorfer, S. Sadhukhan, J. Tkadlec, and D. Zikelic, “Reachability poorman discrete-bidding games,” in Frontiers in Artificial Intelligence and Applications, Krakow, Poland, 2023, vol. 372, pp. 141–148.","short":"G. Avni, T. Meggendorfer, S. Sadhukhan, J. Tkadlec, D. Zikelic, in:, Frontiers in Artificial Intelligence and Applications, IOS Press, 2023, pp. 141–148.","mla":"Avni, Guy, et al. “Reachability Poorman Discrete-Bidding Games.” Frontiers in Artificial Intelligence and Applications, vol. 372, IOS Press, 2023, pp. 141–48, doi:10.3233/FAIA230264."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","external_id":{"arxiv":["2307.15218"]},"author":[{"last_name":"Avni","full_name":"Avni, Guy","orcid":"0000-0001-5588-8287","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","first_name":"Guy"},{"last_name":"Meggendorfer","orcid":"0000-0002-1712-2165","full_name":"Meggendorfer, Tobias","first_name":"Tobias","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1"},{"last_name":"Sadhukhan","full_name":"Sadhukhan, Suman","first_name":"Suman"},{"last_name":"Tkadlec","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef"},{"first_name":"Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4681-1699","full_name":"Zikelic, Dorde","last_name":"Zikelic"}],"title":"Reachability poorman discrete-bidding games","project":[{"grant_number":"665385","name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"},{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}]},{"article_number":"20230355","project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"citation":{"ieee":"J. Tkadlec, K. Kaveh, K. Chatterjee, and M. A. Nowak, “Evolutionary dynamics of mutants that modify population structure,” Journal of the Royal Society, Interface, vol. 20, no. 208. The Royal Society, 2023.","short":"J. Tkadlec, K. Kaveh, K. Chatterjee, M.A. Nowak, Journal of the Royal Society, Interface 20 (2023).","apa":"Tkadlec, J., Kaveh, K., Chatterjee, K., & Nowak, M. A. (2023). Evolutionary dynamics of mutants that modify population structure. Journal of the Royal Society, Interface. The Royal Society. https://doi.org/10.1098/rsif.2023.0355","ama":"Tkadlec J, Kaveh K, Chatterjee K, Nowak MA. Evolutionary dynamics of mutants that modify population structure. Journal of the Royal Society, Interface. 2023;20(208). doi:10.1098/rsif.2023.0355","mla":"Tkadlec, Josef, et al. “Evolutionary Dynamics of Mutants That Modify Population Structure.” Journal of the Royal Society, Interface, vol. 20, no. 208, 20230355, The Royal Society, 2023, doi:10.1098/rsif.2023.0355.","ista":"Tkadlec J, Kaveh K, Chatterjee K, Nowak MA. 2023. Evolutionary dynamics of mutants that modify population structure. Journal of the Royal Society, Interface. 20(208), 20230355.","chicago":"Tkadlec, Josef, Kamran Kaveh, Krishnendu Chatterjee, and Martin A. Nowak. “Evolutionary Dynamics of Mutants That Modify Population Structure.” Journal of the Royal Society, Interface. The Royal Society, 2023. https://doi.org/10.1098/rsif.2023.0355."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef"},{"first_name":"Kamran","full_name":"Kaveh, Kamran","last_name":"Kaveh"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"first_name":"Martin A.","last_name":"Nowak","full_name":"Nowak, Martin A."}],"article_processing_charge":"Yes (in subscription journal)","external_id":{"pmid":["38016637"]},"title":"Evolutionary dynamics of mutants that modify population structure","acknowledgement":"K.C. acknowledges support from the ERC CoG 863818(ForM-SMArt). J.T. is supported by Center for Foundations ofModern Computer Science (Charles Univ. project UNCE/SCI/004).","publisher":"The Royal Society","quality_controlled":"1","oa":1,"has_accepted_license":"1","year":"2023","day":"29","publication":"Journal of the Royal Society, Interface","doi":"10.1098/rsif.2023.0355","date_published":"2023-11-29T00:00:00Z","date_created":"2023-12-10T23:00:58Z","_id":"14657","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","date_updated":"2023-12-11T11:17:53Z","ddc":["000","570"],"file_date_updated":"2023-12-11T11:10:32Z","department":[{"_id":"KrCh"}],"abstract":[{"lang":"eng","text":"Natural selection is usually studied between mutants that differ in reproductive rate, but are subject to the same population structure. Here we explore how natural selection acts on mutants that have the same reproductive rate, but different population structures. In our framework, population structure is given by a graph that specifies where offspring can disperse. The invading mutant disperses offspring on a different graph than the resident wild-type. We find that more densely connected dispersal graphs tend to increase the invader’s fixation probability, but the exact relationship between structure and fixation probability is subtle. We present three main results. First, we prove that if both invader and resident are on complete dispersal graphs, then removing a single edge in the invader’s dispersal graph reduces its fixation probability. Second, we show that for certain island models higher invader’s connectivity increases its fixation probability, but the magnitude of the effect depends on the exact layout of the connections. Third, we show that for lattices the effect of different connectivity is comparable to that of different fitness: for large population size, the invader’s fixation probability is either constant or exponentially small, depending on whether it is more or less connected than the resident."}],"oa_version":"Published Version","pmid":1,"scopus_import":"1","month":"11","intvolume":" 20","publication_identifier":{"eissn":["1742-5662"]},"publication_status":"published","file":[{"file_name":"2023_RoyalInterface_Tkadlec.pdf","date_created":"2023-12-11T11:10:32Z","creator":"dernst","file_size":1720243,"date_updated":"2023-12-11T11:10:32Z","success":1,"file_id":"14673","checksum":"2eefab13127c7786dbd33303c482a004","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"volume":20,"issue":"208","ec_funded":1},{"date_created":"2023-04-16T22:01:08Z","date_published":"2023-01-18T00:00:00Z","doi":"10.46298/DMTCS.8383","year":"2023","has_accepted_license":"1","publication":"Discrete Mathematics and Theoretical Computer Science","day":"18","oa":1,"publisher":"EPI Sciences","quality_controlled":"1","acknowledgement":"This work was begun at the University of Waterloo and was partially supported by the Natural Sciences and Engineering Council of Canada (NSERC).\r\n","external_id":{"arxiv":["1903.06981"]},"article_processing_charge":"No","author":[{"first_name":"Ahmad","full_name":"Biniaz, Ahmad","last_name":"Biniaz"},{"first_name":"Kshitij","last_name":"Jain","full_name":"Jain, Kshitij"},{"first_name":"Anna","last_name":"Lubiw","full_name":"Lubiw, Anna"},{"full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová","first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Tillmann","full_name":"Miltzow, Tillmann","last_name":"Miltzow"},{"first_name":"Debajyoti","full_name":"Mondal, Debajyoti","last_name":"Mondal"},{"last_name":"Naredla","full_name":"Naredla, Anurag Murty","first_name":"Anurag Murty"},{"orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","last_name":"Tkadlec","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Turcotte","full_name":"Turcotte, Alexi","first_name":"Alexi"}],"title":"Token swapping on trees","citation":{"ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. 2023. Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. 24(2), 9.","chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” Discrete Mathematics and Theoretical Computer Science. EPI Sciences, 2023. https://doi.org/10.46298/DMTCS.8383.","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, Discrete Mathematics and Theoretical Computer Science 24 (2023).","ieee":"A. Biniaz et al., “Token swapping on trees,” Discrete Mathematics and Theoretical Computer Science, vol. 24, no. 2. EPI Sciences, 2023.","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (2023). Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. EPI Sciences. https://doi.org/10.46298/DMTCS.8383","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. 2023;24(2). doi:10.46298/DMTCS.8383","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” Discrete Mathematics and Theoretical Computer Science, vol. 24, no. 2, 9, EPI Sciences, 2023, doi:10.46298/DMTCS.8383."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","article_number":"9","related_material":{"record":[{"relation":"earlier_version","id":"7950","status":"public"}]},"volume":24,"issue":"2","publication_status":"published","publication_identifier":{"eissn":["1365-8050"],"issn":["1462-7264"]},"language":[{"iso":"eng"}],"file":[{"success":1,"file_id":"12844","checksum":"439102ea4f6e2aeefd7107dfb9ccf532","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2022_DMTCS_Biniaz.pdf","date_created":"2023-04-17T08:10:28Z","creator":"dernst","file_size":2072197,"date_updated":"2023-04-17T08:10:28Z"}],"scopus_import":"1","intvolume":" 24","month":"01","abstract":[{"text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.","lang":"eng"}],"oa_version":"Published Version","file_date_updated":"2023-04-17T08:10:28Z","department":[{"_id":"KrCh"},{"_id":"HeEd"},{"_id":"UlWa"}],"date_updated":"2024-01-04T12:42:09Z","ddc":["000"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","article_type":"original","status":"public","_id":"12833"},{"date_updated":"2023-02-23T13:54:21Z","ddc":["000"],"department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"file_date_updated":"2022-08-22T06:42:42Z","_id":"11938","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","publication_identifier":{"issn":["1526-1719"]},"publication_status":"published","file":[{"file_size":694538,"date_updated":"2022-08-22T06:42:42Z","creator":"dernst","file_name":"2022_JourGraphAlgorithmsApplic_Aichholzer.pdf","date_created":"2022-08-22T06:42:42Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"file_id":"11940","checksum":"dc6e255e3558faff924fd9e370886c11"}],"language":[{"iso":"eng"}],"issue":"2","related_material":{"record":[{"status":"public","id":"9296","relation":"earlier_version"}]},"volume":26,"ec_funded":1,"abstract":[{"lang":"eng","text":"A matching is compatible to two or more labeled point sets of size n with labels {1, . . . , n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled sets of n points in convex position there exists a compatible matching with ⌊√2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ). As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(log n) copies of any set of n points are necessary and sufficient for the existence of labelings of these point sets such that any compatible matching consists only of a single edge."}],"oa_version":"Published Version","scopus_import":"1","month":"06","intvolume":" 26","citation":{"chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” Journal of Graph Algorithms and Applications. Brown University, 2022. https://doi.org/10.7155/jgaa.00591.","ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and Applications. 26(2), 225–240.","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” Journal of Graph Algorithms and Applications, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:10.7155/jgaa.00591.","ieee":"O. Aichholzer et al., “On compatible matchings,” Journal of Graph Algorithms and Applications, vol. 26, no. 2. Brown University, pp. 225–240, 2022.","short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022) 225–240.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. Journal of Graph Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00591","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. Journal of Graph Algorithms and Applications. 2022;26(2):225-240. doi:10.7155/jgaa.00591"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Aichholzer, Oswin","last_name":"Aichholzer","first_name":"Oswin"},{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","last_name":"Arroyo Guevara"},{"first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová"},{"full_name":"Parada, Irene","last_name":"Parada","first_name":"Irene"},{"first_name":"Daniel","full_name":"Perz, Daniel","last_name":"Perz"},{"first_name":"Alexander","last_name":"Pilz","full_name":"Pilz, Alexander"},{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","last_name":"Tkadlec"},{"last_name":"Vogtenhuber","full_name":"Vogtenhuber, Birgit","first_name":"Birgit"}],"article_processing_charge":"No","external_id":{"arxiv":["2101.03928"]},"title":"On compatible matchings","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","name":"The Wittgenstein Prize"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"has_accepted_license":"1","year":"2022","day":"01","publication":"Journal of Graph Algorithms and Applications","page":"225-240","date_published":"2022-06-01T00:00:00Z","doi":"10.7155/jgaa.00591","date_created":"2022-08-21T22:01:56Z","acknowledgement":"A.A. funded by the Marie Sklodowska-Curie grant agreement No 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","publisher":"Brown University","quality_controlled":"1","oa":1},{"publisher":"American Physical Society","quality_controlled":"1","oa":1,"acknowledgement":"K.C. acknowledges support from ERC Start Grant No. (279307: Graph Games), ERC Consolidator Grant No. (863818: ForM-SMart), and Austrian Science Fund (FWF)\r\nGrants No. P23499-N23 and No. S11407-N23 (RiSE). This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie\r\nSkłodowska-Curie Grant Agreement No. 665385.","date_published":"2022-09-29T00:00:00Z","doi":"10.1103/physreve.106.034321","date_created":"2023-01-16T09:57:57Z","isi":1,"year":"2022","day":"29","publication":"Physical Review E","project":[{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407","name":"Game Theory"},{"name":"International IST Doctoral Program","grant_number":"665385","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"article_number":"034321","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub"},{"first_name":"Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","full_name":"Zikelic, Dorde","last_name":"Zikelic"},{"orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","last_name":"Tkadlec"}],"external_id":{"arxiv":["2210.02394"],"isi":["000870243100001"]},"article_processing_charge":"No","title":"Social balance on networks: Local minima and best-edge dynamics","citation":{"short":"K. Chatterjee, J. Svoboda, D. Zikelic, A. Pavlogiannis, J. Tkadlec, Physical Review E 106 (2022).","ieee":"K. Chatterjee, J. Svoboda, D. Zikelic, A. Pavlogiannis, and J. Tkadlec, “Social balance on networks: Local minima and best-edge dynamics,” Physical Review E, vol. 106, no. 3. American Physical Society, 2022.","apa":"Chatterjee, K., Svoboda, J., Zikelic, D., Pavlogiannis, A., & Tkadlec, J. (2022). Social balance on networks: Local minima and best-edge dynamics. Physical Review E. American Physical Society. https://doi.org/10.1103/physreve.106.034321","ama":"Chatterjee K, Svoboda J, Zikelic D, Pavlogiannis A, Tkadlec J. Social balance on networks: Local minima and best-edge dynamics. Physical Review E. 2022;106(3). doi:10.1103/physreve.106.034321","mla":"Chatterjee, Krishnendu, et al. “Social Balance on Networks: Local Minima and Best-Edge Dynamics.” Physical Review E, vol. 106, no. 3, 034321, American Physical Society, 2022, doi:10.1103/physreve.106.034321.","ista":"Chatterjee K, Svoboda J, Zikelic D, Pavlogiannis A, Tkadlec J. 2022. Social balance on networks: Local minima and best-edge dynamics. Physical Review E. 106(3), 034321.","chicago":"Chatterjee, Krishnendu, Jakub Svoboda, Dorde Zikelic, Andreas Pavlogiannis, and Josef Tkadlec. “Social Balance on Networks: Local Minima and Best-Edge Dynamics.” Physical Review E. American Physical Society, 2022. https://doi.org/10.1103/physreve.106.034321."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2210.02394"}],"month":"09","intvolume":" 106","abstract":[{"text":"Structural balance theory is an established framework for studying social relationships of friendship and enmity. These relationships are modeled by a signed network whose energy potential measures the level of imbalance, while stochastic dynamics drives the network toward a state of minimum energy that captures social balance. It is known that this energy landscape has local minima that can trap socially aware dynamics, preventing it from reaching balance. Here we first study the robustness and attractor properties of these local minima. We show that a stochastic process can reach them from an abundance of initial states and that some local minima cannot be escaped by mild perturbations of the network. Motivated by these anomalies, we introduce best-edge dynamics (BED), a new plausible stochastic process. We prove that BED always reaches balance and that it does so fast in various interesting settings.","lang":"eng"}],"oa_version":"Preprint","issue":"3","volume":106,"ec_funded":1,"publication_identifier":{"issn":["2470-0045"],"eissn":["2470-0053"]},"publication_status":"published","language":[{"iso":"eng"}],"article_type":"original","type":"journal_article","status":"public","_id":"12257","department":[{"_id":"KrCh"}],"date_updated":"2023-08-04T09:50:44Z"},{"project":[{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"The Wittgenstein Prize","grant_number":"Z00342"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Game Theory","grant_number":"S11407"}],"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","citation":{"mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” 15th International Conference on Algorithms and Computation, vol. 12635, Springer Nature, 2021, pp. 221–33, doi:10.1007/978-3-030-68211-8_18.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In 15th International Conference on Algorithms and Computation (Vol. 12635, pp. 221–233). Yangon, Myanmar: Springer Nature. https://doi.org/10.1007/978-3-030-68211-8_18","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. In: 15th International Conference on Algorithms and Computation. Vol 12635. Springer Nature; 2021:221-233. doi:10.1007/978-3-030-68211-8_18","ieee":"O. Aichholzer et al., “On compatible matchings,” in 15th International Conference on Algorithms and Computation, Yangon, Myanmar, 2021, vol. 12635, pp. 221–233.","short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and Computation, Springer Nature, 2021, pp. 221–233.","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” In 15th International Conference on Algorithms and Computation, 12635:221–33. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-68211-8_18.","ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol. 12635, 221–233."},"title":"On compatible matchings","author":[{"full_name":"Aichholzer, Oswin","last_name":"Aichholzer","first_name":"Oswin"},{"orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","last_name":"Arroyo Guevara","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M"},{"full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana"},{"last_name":"Parada","full_name":"Parada, Irene","first_name":"Irene"},{"first_name":"Daniel","last_name":"Perz","full_name":"Perz, Daniel"},{"first_name":"Alexander","full_name":"Pilz, Alexander","last_name":"Pilz"},{"full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","last_name":"Tkadlec","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Vogtenhuber","full_name":"Vogtenhuber, Birgit","first_name":"Birgit"}],"article_processing_charge":"No","external_id":{"arxiv":["2101.03928"]},"acknowledgement":"A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","publisher":"Springer Nature","quality_controlled":"1","oa":1,"day":"16","publication":"15th International Conference on Algorithms and Computation","year":"2021","date_published":"2021-02-16T00:00:00Z","doi":"10.1007/978-3-030-68211-8_18","date_created":"2021-03-28T22:01:41Z","page":"221-233","_id":"9296","status":"public","type":"conference","conference":{"location":"Yangon, Myanmar","end_date":"2021-03-02","start_date":"2021-02-28","name":"WALCOM: Algorithms and Computation"},"date_updated":"2023-02-21T16:33:44Z","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"oa_version":"Preprint","abstract":[{"text":" matching is compatible to two or more labeled point sets of size n with labels {1,…,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(logn) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.","lang":"eng"}],"month":"02","intvolume":" 12635","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/2101.03928","open_access":"1"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["03029743"],"isbn":["9783030682101"],"eissn":["16113349"]},"publication_status":"published","volume":12635,"related_material":{"record":[{"id":"11938","status":"public","relation":"later_version"}]},"ec_funded":1},{"abstract":[{"lang":"eng","text":"Selection and random drift determine the probability that novel mutations fixate in a population. Population structure is known to affect the dynamics of the evolutionary process. Amplifiers of selection are population structures that increase the fixation probability of beneficial mutants compared to well-mixed populations. Over the past 15 years, extensive research has produced remarkable structures called strong amplifiers which guarantee that every beneficial mutation fixates with high probability. But strong amplification has come at the cost of considerably delaying the fixation event, which can slow down the overall rate of evolution. However, the precise relationship between fixation probability and time has remained elusive. Here we characterize the slowdown effect of strong amplification. First, we prove that all strong amplifiers must delay the fixation event at least to some extent. Second, we construct strong amplifiers that delay the fixation event only marginally as compared to the well-mixed populations. Our results thus establish a tight relationship between fixation probability and time: Strong amplification always comes at a cost of a slowdown, but more than a marginal slowdown is not needed."}],"oa_version":"Published Version","pmid":1,"scopus_import":"1","intvolume":" 12","month":"06","publication_status":"published","publication_identifier":{"eissn":["20411723"]},"language":[{"iso":"eng"}],"file":[{"file_size":628992,"date_updated":"2021-07-19T13:02:20Z","creator":"cziletti","file_name":"2021_NatCoom_Tkadlec.pdf","date_created":"2021-07-19T13:02:20Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"checksum":"5767418926a7f7fb76151de29473dae0","file_id":"9692"}],"ec_funded":1,"issue":"1","volume":12,"_id":"9640","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","status":"public","date_updated":"2023-08-10T14:05:09Z","ddc":["510"],"department":[{"_id":"KrCh"}],"file_date_updated":"2021-07-19T13:02:20Z","acknowledgement":"K.C. acknowledges support from ERC Start grant no. (279307: Graph Games), ERC Consolidator grant no. (863818: ForM-SMart), Austrian Science Fund (FWF) grant no. P23499-N23 and S11407-N23 (RiSE). M.A.N. acknowledges support from Office of Naval Research grant N00014-16-1-2914 and from the John Templeton Foundation.","oa":1,"publisher":"Springer Nature","quality_controlled":"1","year":"2021","isi":1,"has_accepted_license":"1","publication":"Nature Communications","day":"29","date_created":"2021-07-11T22:01:15Z","date_published":"2021-06-29T00:00:00Z","doi":"10.1038/s41467-021-24271-w","article_number":"4009","project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"citation":{"ista":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. 2021. Fast and strong amplifiers of natural selection. Nature Communications. 12(1), 4009.","chicago":"Tkadlec, Josef, Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin A. Nowak. “Fast and Strong Amplifiers of Natural Selection.” Nature Communications. Springer Nature, 2021. https://doi.org/10.1038/s41467-021-24271-w.","apa":"Tkadlec, J., Pavlogiannis, A., Chatterjee, K., & Nowak, M. A. (2021). Fast and strong amplifiers of natural selection. Nature Communications. Springer Nature. https://doi.org/10.1038/s41467-021-24271-w","ama":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Fast and strong amplifiers of natural selection. Nature Communications. 2021;12(1). doi:10.1038/s41467-021-24271-w","ieee":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, and M. A. Nowak, “Fast and strong amplifiers of natural selection,” Nature Communications, vol. 12, no. 1. Springer Nature, 2021.","short":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, Nature Communications 12 (2021).","mla":"Tkadlec, Josef, et al. “Fast and Strong Amplifiers of Natural Selection.” Nature Communications, vol. 12, no. 1, 4009, Springer Nature, 2021, doi:10.1038/s41467-021-24271-w."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","external_id":{"pmid":["34188036"],"isi":["000671752100003"]},"author":[{"orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","last_name":"Tkadlec","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Nowak, Martin A.","last_name":"Nowak","first_name":"Martin A."}],"title":"Fast and strong amplifiers of natural selection"},{"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"date_updated":"2023-09-05T12:40:00Z","article_type":"original","type":"journal_article","conference":{"location":"New York, NY, United States","end_date":"2020-02-12","start_date":"2020-02-07","name":"AAAI: Conference on Artificial Intelligence"},"status":"public","_id":"9197","issue":"02","volume":34,"publication_identifier":{"isbn":["9781577358350"],"eissn":["2374-3468"],"issn":["2159-5399"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","month":"04","intvolume":" 34","abstract":[{"lang":"eng","text":"In this paper we introduce and study all-pay bidding games, a class of two player, zero-sum games on graphs. The game proceeds as follows. We place a token on some vertex in the graph and assign budgets to the two players. Each turn, each player submits a sealed legal bid (non-negative and below their remaining budget), which is deducted from their budget and the highest bidder moves the token onto an adjacent vertex. The game ends once a sink is reached, and Player 1 pays Player 2 the outcome that is associated with the sink. The players attempt to maximize their expected outcome. Our games model settings where effort (of no inherent value) needs to be invested in an ongoing and stateful manner. On the negative side, we show that even in simple games on DAGs, optimal strategies may require a distribution over bids with infinite support. A central quantity in bidding games is the ratio of the players budgets. On the positive side, we show a simple FPTAS for DAGs, that, for each budget ratio, outputs an approximation for the optimal strategy for that ratio. We also implement it, show that it performs well, and suggests interesting properties of these games. Then, given an outcome c, we show an algorithm for finding the necessary and sufficient initial ratio for guaranteeing outcome c with probability 1 and a strategy ensuring such. Finally, while the general case has not previously been studied, solving the specific game in which Player 1 wins iff he wins the first two auctions, has been long stated as an open question, which we solve."}],"oa_version":"Preprint","author":[{"first_name":"Guy","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5588-8287","full_name":"Avni, Guy","last_name":"Avni"},{"full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus"},{"orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","last_name":"Tkadlec","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef"}],"external_id":{"arxiv":["1911.08360"]},"article_processing_charge":"No","title":"All-pay bidding games on graphs","citation":{"short":"G. Avni, R. Ibsen-Jensen, J. Tkadlec, Proceedings of the AAAI Conference on Artificial Intelligence 34 (2020) 1798–1805.","ieee":"G. Avni, R. Ibsen-Jensen, and J. Tkadlec, “All-pay bidding games on graphs,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 02. Association for the Advancement of Artificial Intelligence, pp. 1798–1805, 2020.","ama":"Avni G, Ibsen-Jensen R, Tkadlec J. All-pay bidding games on graphs. Proceedings of the AAAI Conference on Artificial Intelligence. 2020;34(02):1798-1805. doi:10.1609/aaai.v34i02.5546","apa":"Avni, G., Ibsen-Jensen, R., & Tkadlec, J. (2020). All-pay bidding games on graphs. Proceedings of the AAAI Conference on Artificial Intelligence. New York, NY, United States: Association for the Advancement of Artificial Intelligence. https://doi.org/10.1609/aaai.v34i02.5546","mla":"Avni, Guy, et al. “All-Pay Bidding Games on Graphs.” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 02, Association for the Advancement of Artificial Intelligence, 2020, pp. 1798–805, doi:10.1609/aaai.v34i02.5546.","ista":"Avni G, Ibsen-Jensen R, Tkadlec J. 2020. All-pay bidding games on graphs. Proceedings of the AAAI Conference on Artificial Intelligence. 34(02), 1798–1805.","chicago":"Avni, Guy, Rasmus Ibsen-Jensen, and Josef Tkadlec. “All-Pay Bidding Games on Graphs.” Proceedings of the AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence, 2020. https://doi.org/10.1609/aaai.v34i02.5546."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"grant_number":"S11402-N23","name":"Rigorous Systems Engineering","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"Z211","name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425"},{"name":"Formal Methods meets Algorithmic Game Theory","grant_number":"M02369","call_identifier":"FWF","_id":"264B3912-B435-11E9-9278-68D0E5697425"}],"page":"1798-1805","doi":"10.1609/aaai.v34i02.5546","date_published":"2020-04-03T00:00:00Z","date_created":"2021-02-25T09:05:18Z","year":"2020","day":"03","publication":"Proceedings of the AAAI Conference on Artificial Intelligence","publisher":"Association for the Advancement of Artificial Intelligence","quality_controlled":"1","acknowledgement":"This research was supported by the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE/SHiNE), Z211-N23 (Wittgenstein Award), and M 2369-N33 (Meitner fellowship)."},{"oa_version":"Published Version","abstract":[{"text":"The fixation probability of a single mutant invading a population of residents is among the most widely-studied quantities in evolutionary dynamics. Amplifiers of natural selection are population structures that increase the fixation probability of advantageous mutants, compared to well-mixed populations. Extensive studies have shown that many amplifiers exist for the Birth-death Moran process, some of them substantially increasing the fixation probability or even guaranteeing fixation in the limit of large population size. On the other hand, no amplifiers are known for the death-Birth Moran process, and computer-assisted exhaustive searches have failed to discover amplification. In this work we resolve this disparity, by showing that any amplification under death-Birth updating is necessarily bounded and transient. Our boundedness result states that even if a population structure does amplify selection, the resulting fixation probability is close to that of the well-mixed population. Our transience result states that for any population structure there exists a threshold r⋆ such that the population structure ceases to amplify selection if the mutant fitness advantage r is larger than r⋆. Finally, we also extend the above results to δ-death-Birth updating, which is a combination of Birth-death and death-Birth updating. On the positive side, we identify population structures that maintain amplification for a wide range of values r and δ. These results demonstrate that amplification of natural selection depends on the specific mechanisms of the evolutionary process.","lang":"eng"}],"month":"01","intvolume":" 16","scopus_import":"1","file":[{"date_updated":"2020-07-14T12:47:53Z","file_size":1817531,"creator":"dernst","date_created":"2020-02-03T07:32:42Z","file_name":"2020_PlosCompBio_Tkadlec.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"7441","checksum":"ce32ee2d2f53aed832f78bbd47e882df"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["15537358"]},"publication_status":"published","volume":16,"related_material":{"record":[{"id":"7196","status":"public","relation":"part_of_dissertation"}]},"ec_funded":1,"_id":"7212","status":"public","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["000"],"date_updated":"2023-10-17T12:29:47Z","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:47:53Z","publisher":"Public Library of Science","quality_controlled":"1","oa":1,"day":"17","publication":"PLoS computational biology","has_accepted_license":"1","isi":1,"year":"2020","doi":"10.1371/journal.pcbi.1007494","date_published":"2020-01-17T00:00:00Z","date_created":"2019-12-23T13:45:11Z","article_number":"e1007494","project":[{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S11407","name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Tkadlec, Josef, et al. “Limits on Amplifiers of Natural Selection under Death-Birth Updating.” PLoS Computational Biology, vol. 16, e1007494, Public Library of Science, 2020, doi:10.1371/journal.pcbi.1007494.","ieee":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, and M. A. Nowak, “Limits on amplifiers of natural selection under death-Birth updating,” PLoS computational biology, vol. 16. Public Library of Science, 2020.","short":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, PLoS Computational Biology 16 (2020).","apa":"Tkadlec, J., Pavlogiannis, A., Chatterjee, K., & Nowak, M. A. (2020). Limits on amplifiers of natural selection under death-Birth updating. PLoS Computational Biology. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1007494","ama":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Limits on amplifiers of natural selection under death-Birth updating. PLoS computational biology. 2020;16. doi:10.1371/journal.pcbi.1007494","chicago":"Tkadlec, Josef, Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin A. Nowak. “Limits on Amplifiers of Natural Selection under Death-Birth Updating.” PLoS Computational Biology. Public Library of Science, 2020. https://doi.org/10.1371/journal.pcbi.1007494.","ista":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. 2020. Limits on amplifiers of natural selection under death-Birth updating. PLoS computational biology. 16, e1007494."},"title":"Limits on amplifiers of natural selection under death-Birth updating","author":[{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","last_name":"Tkadlec"},{"last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin A.","full_name":"Nowak, Martin A.","last_name":"Nowak"}],"article_processing_charge":"No","external_id":{"isi":["000510916500025"],"arxiv":["1906.02785"]}},{"_id":"7196","status":"public","type":"dissertation","ddc":["519"],"date_updated":"2023-10-17T12:29:46Z","supervisor":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"}],"department":[{"_id":"KrCh"},{"_id":"GradSch"}],"file_date_updated":"2020-07-14T12:47:52Z","oa_version":"Published Version","abstract":[{"lang":"eng","text":"In this thesis we study certain mathematical aspects of evolution. The two primary forces that drive an evolutionary process are mutation and selection. Mutation generates new variants in a population. Selection chooses among the variants depending on the reproductive rates of individuals. Evolutionary processes are intrinsically random – a new mutation that is initially present in the population at low frequency can go extinct, even if it confers a reproductive advantage. The overall rate of evolution is largely determined by two quantities: the probability that an invading advantageous mutation spreads through the population (called fixation probability) and the time until it does so (called fixation time). Both those quantities crucially depend not only on the strength of the invading mutation but also on the population structure. In this thesis, we aim to understand how the underlying population structure affects the overall rate of evolution. Specifically, we study population structures that increase the fixation probability of advantageous mutants (called amplifiers of selection). Broadly speaking, our results are of three different types: We present various strong amplifiers, we identify regimes under which only limited amplification is feasible, and we propose population structures that provide different tradeoffs between high fixation probability and short fixation time."}],"month":"01","alternative_title":["ISTA Thesis"],"language":[{"iso":"eng"}],"file":[{"creator":"jtkadlec","date_updated":"2020-07-14T12:47:52Z","file_size":21100497,"date_created":"2020-01-12T11:49:49Z","file_name":"thesis.zip","access_level":"closed","relation":"source_file","content_type":"application/zip","file_id":"7255","checksum":"451f8e64b0eb26bf297644ac72bfcbe9"},{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"d8c44cbc4f939c49a8efc9d4b8bb3985","file_id":"7367","creator":"dernst","file_size":11670983,"date_updated":"2020-07-14T12:47:52Z","file_name":"2020_Tkadlec_Thesis.pdf","date_created":"2020-01-28T07:32:42Z"}],"degree_awarded":"PhD","publication_status":"published","publication_identifier":{"eissn":["2663-337X"]},"related_material":{"record":[{"id":"7210","status":"public","relation":"dissertation_contains"},{"relation":"dissertation_contains","status":"public","id":"5751"},{"relation":"dissertation_contains","id":"7212","status":"public"}]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Tkadlec J. 2020. A role of graphs in evolutionary processes. Institute of Science and Technology Austria.","chicago":"Tkadlec, Josef. “A Role of Graphs in Evolutionary Processes.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7196.","ieee":"J. Tkadlec, “A role of graphs in evolutionary processes,” Institute of Science and Technology Austria, 2020.","short":"J. Tkadlec, A Role of Graphs in Evolutionary Processes, Institute of Science and Technology Austria, 2020.","apa":"Tkadlec, J. (2020). A role of graphs in evolutionary processes. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7196","ama":"Tkadlec J. A role of graphs in evolutionary processes. 2020. doi:10.15479/AT:ISTA:7196","mla":"Tkadlec, Josef. A Role of Graphs in Evolutionary Processes. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7196."},"title":"A role of graphs in evolutionary processes","article_processing_charge":"No","author":[{"full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","last_name":"Tkadlec","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef"}],"oa":1,"publisher":"Institute of Science and Technology Austria","day":"12","year":"2020","has_accepted_license":"1","date_created":"2019-12-20T12:26:36Z","doi":"10.15479/AT:ISTA:7196","date_published":"2020-01-12T00:00:00Z","page":"144"},{"_id":"9814","type":"research_data_reference","status":"public","date_updated":"2023-10-18T06:36:00Z","citation":{"ista":"Ibsen-Jensen R, Tkadlec J, Chatterjee K, Nowak M. 2020. Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners, Royal Society, 10.6084/m9.figshare.5973013.v1.","chicago":"Ibsen-Jensen, Rasmus, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. “Data and Mathematica Notebooks for Plotting Figures from Language Learning with Communication between Learners from Language Acquisition with Communication between Learners.” Royal Society, 2020. https://doi.org/10.6084/m9.figshare.5973013.v1.","ieee":"R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, and M. Nowak, “Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners.” Royal Society, 2020.","short":"R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, M. Nowak, (2020).","apa":"Ibsen-Jensen, R., Tkadlec, J., Chatterjee, K., & Nowak, M. (2020). Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners. Royal Society. https://doi.org/10.6084/m9.figshare.5973013.v1","ama":"Ibsen-Jensen R, Tkadlec J, Chatterjee K, Nowak M. Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners. 2020. doi:10.6084/m9.figshare.5973013.v1","mla":"Ibsen-Jensen, Rasmus, et al. Data and Mathematica Notebooks for Plotting Figures from Language Learning with Communication between Learners from Language Acquisition with Communication between Learners. Royal Society, 2020, doi:10.6084/m9.figshare.5973013.v1."},"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","article_processing_charge":"No","author":[{"last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"title":"Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners","department":[{"_id":"KrCh"}],"abstract":[{"lang":"eng","text":"Data and mathematica notebooks for plotting figures from Language learning with communication between learners"}],"oa_version":"Published Version","main_file_link":[{"url":"https://doi.org/10.6084/m9.figshare.5973013.v1","open_access":"1"}],"oa":1,"publisher":"Royal Society","month":"10","year":"2020","day":"15","date_created":"2021-08-06T13:09:57Z","related_material":{"record":[{"id":"198","status":"public","relation":"used_in_publication"}]},"doi":"10.6084/m9.figshare.5973013.v1","date_published":"2020-10-15T00:00:00Z"},{"department":[{"_id":"KrCh"},{"_id":"UlWa"}],"title":"Disjoint tree-compatible plane perfect matchings","author":[{"last_name":"Aichholzer","full_name":"Aichholzer, Oswin","first_name":"Oswin"},{"last_name":"Obmann","full_name":"Obmann, Julia","first_name":"Julia"},{"first_name":"Pavel","id":"B593B804-1035-11EA-B4F1-947645A5BB83","last_name":"Patak","full_name":"Patak, Pavel"},{"first_name":"Daniel","full_name":"Perz, Daniel","last_name":"Perz"},{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Aichholzer, Oswin, et al. “Disjoint Tree-Compatible Plane Perfect Matchings.” 36th European Workshop on Computational Geometry, 56, 2020.","short":"O. Aichholzer, J. Obmann, P. Patak, D. Perz, J. Tkadlec, in:, 36th European Workshop on Computational Geometry, 2020.","ieee":"O. Aichholzer, J. Obmann, P. Patak, D. Perz, and J. Tkadlec, “Disjoint tree-compatible plane perfect matchings,” in 36th European Workshop on Computational Geometry, Würzburg, Germany, Virtual, 2020.","ama":"Aichholzer O, Obmann J, Patak P, Perz D, Tkadlec J. Disjoint tree-compatible plane perfect matchings. In: 36th European Workshop on Computational Geometry. ; 2020.","apa":"Aichholzer, O., Obmann, J., Patak, P., Perz, D., & Tkadlec, J. (2020). Disjoint tree-compatible plane perfect matchings. In 36th European Workshop on Computational Geometry. Würzburg, Germany, Virtual.","chicago":"Aichholzer, Oswin, Julia Obmann, Pavel Patak, Daniel Perz, and Josef Tkadlec. “Disjoint Tree-Compatible Plane Perfect Matchings.” In 36th European Workshop on Computational Geometry, 2020.","ista":"Aichholzer O, Obmann J, Patak P, Perz D, Tkadlec J. 2020. Disjoint tree-compatible plane perfect matchings. 36th European Workshop on Computational Geometry. EuroCG: European Workshop on Computational Geometry, 56."},"date_updated":"2024-03-05T09:00:07Z","status":"public","type":"conference","conference":{"end_date":"2020-03-18","location":"Würzburg, Germany, Virtual","start_date":"2020-03-16","name":"EuroCG: European Workshop on Computational Geometry"},"article_number":"56","_id":"15082","date_published":"2020-04-01T00:00:00Z","date_created":"2024-03-05T08:57:17Z","day":"01","language":[{"iso":"eng"}],"publication":"36th European Workshop on Computational Geometry","publication_status":"published","year":"2020","month":"04","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_56.pdf"}],"oa":1,"oa_version":"Published Version","acknowledgement":"Research on this work was initiated at the 6th Austrian-Japanese-Mexican-Spanish Workshop on Discrete Geometry and continued during the 16th European Geometric Graph-Week, both held near Strobl, Austria. We are grateful to the participants for the inspiring atmosphere. We especially thank Alexander Pilz for bringing this class of problems to our attention and Birgit Vogtenhuber for inspiring discussions. D.P. is partially supported by the FWF grant I 3340-N35 (Collaborative DACH project Arrangements and Drawings). The research stay of P.P. at IST Austria is funded by the project CZ.02.2.69/0.0/0.0/17_050/0008466 Improvement of internationalization in the field of research and development at Charles University, through the support of quality projects MSCA-IF. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.","abstract":[{"text":"Two plane drawings of geometric graphs on the same set of points are called disjoint compatible if their union is plane and they do not have an edge in common. For a given set S of 2n points two plane drawings of perfect matchings M1 and M2 (which do not need to be disjoint nor compatible) are disjoint tree-compatible if there exists a plane drawing of a spanning tree T on S which is disjoint compatible to both M1 and M2.\r\nWe show that the graph of all disjoint tree-compatible perfect geometric matchings on 2n points in convex position is connected if and only if 2n ≥ 10. Moreover, in that case the diameter\r\nof this graph is either 4 or 5, independent of n.","lang":"eng"}]},{"related_material":{"record":[{"status":"public","id":"7196","relation":"part_of_dissertation"}]},"volume":2,"ec_funded":1,"file":[{"creator":"dernst","file_size":1670274,"date_updated":"2020-07-14T12:47:53Z","file_name":"2019_CommBio_Tkadlec.pdf","date_created":"2019-12-23T13:39:30Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"7211","checksum":"d1a69bfe73767e4246f0a38e4e1554dd"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2399-3642"]},"publication_status":"published","month":"04","intvolume":" 2","scopus_import":"1","oa_version":"Published Version","pmid":1,"abstract":[{"lang":"eng","text":"The rate of biological evolution depends on the fixation probability and on the fixation time of new mutants. Intensive research has focused on identifying population structures that augment the fixation probability of advantageous mutants. But these amplifiers of natural selection typically increase fixation time. Here we study population structures that achieve a tradeoff between fixation probability and time. First, we show that no amplifiers can have an asymptotically lower absorption time than the well-mixed population. Then we design population structures that substantially augment the fixation probability with just a minor increase in fixation time. Finally, we show that those structures enable higher effective rate of evolution than the well-mixed population provided that the rate of generating advantageous mutants is relatively low. Our work sheds light on how population structure affects the rate of evolution. Moreover, our structures could be useful for lab-based, medical, or industrial applications of evolutionary optimization."}],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:47:53Z","ddc":["000"],"date_updated":"2023-09-07T13:19:22Z","status":"public","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"7210","date_published":"2019-04-23T00:00:00Z","doi":"10.1038/s42003-019-0373-y","date_created":"2019-12-23T13:36:50Z","day":"23","publication":"Communications Biology","isi":1,"has_accepted_license":"1","year":"2019","publisher":"Springer Nature","quality_controlled":"1","oa":1,"title":"Population structure determines the tradeoff between fixation probability and fixation time","author":[{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","last_name":"Tkadlec"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin A.","last_name":"Nowak","full_name":"Nowak, Martin A."}],"external_id":{"isi":["000465425700006"],"pmid":["31044163"]},"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. 2019. Population structure determines the tradeoff between fixation probability and fixation time. Communications Biology. 2, 138.","chicago":"Tkadlec, Josef, Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin A. Nowak. “Population Structure Determines the Tradeoff between Fixation Probability and Fixation Time.” Communications Biology. Springer Nature, 2019. https://doi.org/10.1038/s42003-019-0373-y.","short":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, Communications Biology 2 (2019).","ieee":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, and M. A. Nowak, “Population structure determines the tradeoff between fixation probability and fixation time,” Communications Biology, vol. 2. Springer Nature, 2019.","ama":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Population structure determines the tradeoff between fixation probability and fixation time. Communications Biology. 2019;2. doi:10.1038/s42003-019-0373-y","apa":"Tkadlec, J., Pavlogiannis, A., Chatterjee, K., & Nowak, M. A. (2019). Population structure determines the tradeoff between fixation probability and fixation time. Communications Biology. Springer Nature. https://doi.org/10.1038/s42003-019-0373-y","mla":"Tkadlec, Josef, et al. “Population Structure Determines the Tradeoff between Fixation Probability and Fixation Time.” Communications Biology, vol. 2, 138, Springer Nature, 2019, doi:10.1038/s42003-019-0373-y."},"project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"article_number":"138"},{"month":"03","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1903.06981"}],"oa":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results:\r\n1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan.\r\n2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2.\r\n3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved."}],"date_created":"2020-06-08T12:25:25Z","related_material":{"record":[{"status":"public","id":"7944","relation":"dissertation_contains"},{"relation":"later_version","status":"public","id":"12833"}]},"date_published":"2019-03-16T00:00:00Z","language":[{"iso":"eng"}],"publication":"arXiv","day":"16","publication_status":"submitted","year":"2019","status":"public","type":"preprint","article_number":"1903.06981","_id":"7950","title":"Token swapping on trees","department":[{"_id":"HeEd"},{"_id":"UlWa"},{"_id":"KrCh"}],"article_processing_charge":"No","external_id":{"arxiv":["1903.06981"]},"author":[{"full_name":"Biniaz, Ahmad","last_name":"Biniaz","first_name":"Ahmad"},{"last_name":"Jain","full_name":"Jain, Kshitij","first_name":"Kshitij"},{"last_name":"Lubiw","full_name":"Lubiw, Anna","first_name":"Anna"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","last_name":"Masárová"},{"last_name":"Miltzow","full_name":"Miltzow, Tillmann","first_name":"Tillmann"},{"last_name":"Mondal","full_name":"Mondal, Debajyoti","first_name":"Debajyoti"},{"first_name":"Anurag Murty","full_name":"Naredla, Anurag Murty","last_name":"Naredla"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef"},{"last_name":"Turcotte","full_name":"Turcotte, Alexi","first_name":"Alexi"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” ArXiv, n.d.","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. Token swapping on trees. arXiv, 1903.06981.","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” ArXiv, 1903.06981.","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. arXiv.","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (n.d.). Token swapping on trees. arXiv.","ieee":"A. Biniaz et al., “Token swapping on trees,” arXiv. .","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, ArXiv (n.d.)."},"date_updated":"2024-01-04T12:42:08Z"},{"_id":"198","status":"public","article_type":"original","type":"journal_article","ddc":["000"],"date_updated":"2023-10-18T06:36:00Z","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:45:22Z","oa_version":"Submitted Version","pmid":1,"abstract":[{"text":"We consider a class of students learning a language from a teacher. The situation can be interpreted as a group of child learners receiving input from the linguistic environment. The teacher provides sample sentences. The students try to learn the grammar from the teacher. In addition to just listening to the teacher, the students can also communicate with each other. The students hold hypotheses about the grammar and change them if they receive counter evidence. The process stops when all students have converged to the correct grammar. We study how the time to convergence depends on the structure of the classroom by introducing and evaluating various complexity measures. We find that structured communication between students, although potentially introducing confusion, can greatly reduce some of the complexity measures. Our theory can also be interpreted as applying to the scientific process, where nature is the teacher and the scientists are the students.","lang":"eng"}],"intvolume":" 15","month":"03","scopus_import":"1","language":[{"iso":"eng"}],"file":[{"file_name":"2018_RS_IbsenJensen.pdf","date_created":"2019-02-12T07:54:37Z","creator":"dernst","file_size":219837,"date_updated":"2020-07-14T12:45:22Z","checksum":"444e1a9d98eb0e780671be82b13025f3","file_id":"5955","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"publication_status":"published","publication_identifier":{"eissn":["1742-5662"]},"ec_funded":1,"related_material":{"link":[{"url":"https://dx.doi.org/10.6084/m9.figshare.c.4028971","relation":"supplementary_material"}],"record":[{"status":"public","id":"9814","relation":"research_data"}]},"issue":"140","volume":15,"article_number":"20180073","project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Ibsen-Jensen R, Tkadlec J, Chatterjee K, Nowak M. 2018. Language acquisition with communication between learners. Journal of the Royal Society Interface. 15(140), 20180073.","chicago":"Ibsen-Jensen, Rasmus, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. “Language Acquisition with Communication between Learners.” Journal of the Royal Society Interface. The Royal Society, 2018. https://doi.org/10.1098/rsif.2018.0073.","apa":"Ibsen-Jensen, R., Tkadlec, J., Chatterjee, K., & Nowak, M. (2018). Language acquisition with communication between learners. Journal of the Royal Society Interface. The Royal Society. https://doi.org/10.1098/rsif.2018.0073","ama":"Ibsen-Jensen R, Tkadlec J, Chatterjee K, Nowak M. Language acquisition with communication between learners. Journal of the Royal Society Interface. 2018;15(140). doi:10.1098/rsif.2018.0073","short":"R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, M. Nowak, Journal of the Royal Society Interface 15 (2018).","ieee":"R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, and M. Nowak, “Language acquisition with communication between learners,” Journal of the Royal Society Interface, vol. 15, no. 140. The Royal Society, 2018.","mla":"Ibsen-Jensen, Rasmus, et al. “Language Acquisition with Communication between Learners.” Journal of the Royal Society Interface, vol. 15, no. 140, 20180073, The Royal Society, 2018, doi:10.1098/rsif.2018.0073."},"title":"Language acquisition with communication between learners","article_processing_charge":"No","external_id":{"pmid":["29593089"],"isi":["000428576200023"]},"author":[{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen"},{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"}],"publist_id":"7715","oa":1,"publisher":"The Royal Society","quality_controlled":"1","publication":"Journal of the Royal Society Interface","day":"01","year":"2018","isi":1,"has_accepted_license":"1","date_created":"2018-12-11T11:45:09Z","date_published":"2018-03-01T00:00:00Z","doi":"10.1098/rsif.2018.0073"},{"publisher":"Springer Nature","quality_controlled":"1","oa":1,"date_published":"2018-06-14T00:00:00Z","doi":"10.1038/s42003-018-0078-7","date_created":"2018-12-18T13:22:58Z","day":"14","publication":"Communications Biology","isi":1,"has_accepted_license":"1","year":"2018","project":[{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"}],"article_number":"71","title":"Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory","author":[{"full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"},{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Martin A.","last_name":"Nowak","full_name":"Nowak, Martin A."}],"external_id":{"isi":["000461126500071"]},"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin A. Nowak. “Construction of Arbitrarily Strong Amplifiers of Natural Selection Using Evolutionary Graph Theory.” Communications Biology. Springer Nature, 2018. https://doi.org/10.1038/s42003-018-0078-7.","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak MA. 2018. Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory. Communications Biology. 1(1), 71.","mla":"Pavlogiannis, Andreas, et al. “Construction of Arbitrarily Strong Amplifiers of Natural Selection Using Evolutionary Graph Theory.” Communications Biology, vol. 1, no. 1, 71, Springer Nature, 2018, doi:10.1038/s42003-018-0078-7.","ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. A. Nowak, “Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory,” Communications Biology, vol. 1, no. 1. Springer Nature, 2018.","short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M.A. Nowak, Communications Biology 1 (2018).","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak, M. A. (2018). Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory. Communications Biology. Springer Nature. https://doi.org/10.1038/s42003-018-0078-7","ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak MA. Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory. Communications Biology. 2018;1(1). doi:10.1038/s42003-018-0078-7"},"month":"06","intvolume":" 1","scopus_import":"1","oa_version":"Published Version","abstract":[{"lang":"eng","text":"Because of the intrinsic randomness of the evolutionary process, a mutant with a fitness advantage has some chance to be selected but no certainty. Any experiment that searches for advantageous mutants will lose many of them due to random drift. It is therefore of great interest to find population structures that improve the odds of advantageous mutants. Such structures are called amplifiers of natural selection: they increase the probability that advantageous mutants are selected. Arbitrarily strong amplifiers guarantee the selection of advantageous mutants, even for very small fitness advantage. Despite intensive research over the past decade, arbitrarily strong amplifiers have remained rare. Here we show how to construct a large variety of them. Our amplifiers are so simple that they could be useful in biotechnology, when optimizing biological molecules, or as a diagnostic tool, when searching for faster dividing cells or viruses. They could also occur in natural population structures."}],"volume":1,"related_material":{"record":[{"relation":"part_of_dissertation","id":"7196","status":"public"},{"relation":"popular_science","id":"5559","status":"public"}]},"issue":"1","ec_funded":1,"file":[{"creator":"dernst","date_updated":"2020-07-14T12:47:10Z","file_size":1804194,"date_created":"2018-12-18T13:37:04Z","file_name":"2018_CommBiology_Pavlogiannis.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"5752","checksum":"a9db825fa3b64a51ff3de035ec973b3e"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2399-3642"]},"publication_status":"published","status":"public","pubrep_id":"1045","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"5751","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:47:10Z","ddc":["004","519","576"],"date_updated":"2024-02-21T13:48:42Z"},{"title":"Indirect reciprocity with private, noisy, and incomplete information","article_processing_charge":"No","external_id":{"isi":["000451351000063"],"pmid":["30429320"]},"author":[{"orcid":"0000-0001-5116-955X","full_name":"Hilbe, Christian","last_name":"Hilbe","first_name":"Christian","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Schmid","orcid":"0000-0002-6978-7329","full_name":"Schmid, Laura","first_name":"Laura","id":"38B437DE-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684"},{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Hilbe, Christian, Laura Schmid, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. “Indirect Reciprocity with Private, Noisy, and Incomplete Information.” PNAS. National Academy of Sciences, 2018. https://doi.org/10.1073/pnas.1810565115.","ista":"Hilbe C, Schmid L, Tkadlec J, Chatterjee K, Nowak M. 2018. Indirect reciprocity with private, noisy, and incomplete information. PNAS. 115(48), 12241–12246.","mla":"Hilbe, Christian, et al. “Indirect Reciprocity with Private, Noisy, and Incomplete Information.” PNAS, vol. 115, no. 48, National Academy of Sciences, 2018, pp. 12241–46, doi:10.1073/pnas.1810565115.","apa":"Hilbe, C., Schmid, L., Tkadlec, J., Chatterjee, K., & Nowak, M. (2018). Indirect reciprocity with private, noisy, and incomplete information. PNAS. National Academy of Sciences. https://doi.org/10.1073/pnas.1810565115","ama":"Hilbe C, Schmid L, Tkadlec J, Chatterjee K, Nowak M. Indirect reciprocity with private, noisy, and incomplete information. PNAS. 2018;115(48):12241-12246. doi:10.1073/pnas.1810565115","ieee":"C. Hilbe, L. Schmid, J. Tkadlec, K. Chatterjee, and M. Nowak, “Indirect reciprocity with private, noisy, and incomplete information,” PNAS, vol. 115, no. 48. National Academy of Sciences, pp. 12241–12246, 2018.","short":"C. Hilbe, L. Schmid, J. Tkadlec, K. Chatterjee, M. Nowak, PNAS 115 (2018) 12241–12246."},"project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"date_created":"2018-12-11T11:44:05Z","doi":"10.1073/pnas.1810565115","date_published":"2018-11-27T00:00:00Z","page":"12241-12246","publication":"PNAS","day":"27","year":"2018","isi":1,"oa":1,"quality_controlled":"1","publisher":"National Academy of Sciences","department":[{"_id":"KrCh"}],"date_updated":"2024-03-27T23:30:44Z","status":"public","type":"journal_article","_id":"2","ec_funded":1,"issue":"48","volume":115,"related_material":{"record":[{"relation":"dissertation_contains","id":"10293","status":"public"}],"link":[{"url":"https://ist.ac.at/en/news/no-cooperation-without-open-communication/","relation":"press_release","description":"News on IST Homepage"}]},"language":[{"iso":"eng"}],"publication_status":"published","intvolume":" 115","month":"11","main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pubmed/30429320"}],"scopus_import":"1","oa_version":"Submitted Version","pmid":1,"abstract":[{"text":"Indirect reciprocity explores how humans act when their reputation is at stake, and which social norms they use to assess the actions of others. A crucial question in indirect reciprocity is which social norms can maintain stable cooperation in a society. Past research has highlighted eight such norms, called “leading-eight” strategies. This past research, however, is based on the assumption that all relevant information about other population members is publicly available and that everyone agrees on who is good or bad. Instead, here we explore the reputation dynamics when information is private and noisy. We show that under these conditions, most leading-eight strategies fail to evolve. Those leading-eight strategies that do evolve are unable to sustain full cooperation.Indirect reciprocity is a mechanism for cooperation based on shared moral systems and individual reputations. It assumes that members of a community routinely observe and assess each other and that they use this information to decide who is good or bad, and who deserves cooperation. When information is transmitted publicly, such that all community members agree on each other’s reputation, previous research has highlighted eight crucial moral systems. These “leading-eight” strategies can maintain cooperation and resist invasion by defectors. However, in real populations individuals often hold their own private views of others. Once two individuals disagree about their opinion of some third party, they may also see its subsequent actions in a different light. Their opinions may further diverge over time. Herein, we explore indirect reciprocity when information transmission is private and noisy. We find that in the presence of perception errors, most leading-eight strategies cease to be stable. Even if a leading-eight strategy evolves, cooperation rates may drop considerably when errors are common. Our research highlights the role of reliable information and synchronized reputations to maintain stable moral systems.","lang":"eng"}]},{"citation":{"ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2017. Amplification on undirected population structures: Comets beat stars. Scientific Reports. 7(1), 82.","chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. “Amplification on Undirected Population Structures: Comets Beat Stars.” Scientific Reports. Nature Publishing Group, 2017. https://doi.org/10.1038/s41598-017-00107-w.","ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, “Amplification on undirected population structures: Comets beat stars,” Scientific Reports, vol. 7, no. 1. Nature Publishing Group, 2017.","short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Scientific Reports 7 (2017).","ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Amplification on undirected population structures: Comets beat stars. Scientific Reports. 2017;7(1). doi:10.1038/s41598-017-00107-w","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak, M. (2017). Amplification on undirected population structures: Comets beat stars. Scientific Reports. Nature Publishing Group. https://doi.org/10.1038/s41598-017-00107-w","mla":"Pavlogiannis, Andreas, et al. “Amplification on Undirected Population Structures: Comets Beat Stars.” Scientific Reports, vol. 7, no. 1, 82, Nature Publishing Group, 2017, doi:10.1038/s41598-017-00107-w."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","author":[{"full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"},{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"publist_id":"7307","title":"Amplification on undirected population structures: Comets beat stars","article_number":"82","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Game Theory","grant_number":"S11407"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"}],"year":"2017","has_accepted_license":"1","publication":"Scientific Reports","day":"06","date_created":"2018-12-11T11:46:53Z","doi":"10.1038/s41598-017-00107-w","date_published":"2017-03-06T00:00:00Z","oa":1,"publisher":"Nature Publishing Group","quality_controlled":"1","date_updated":"2023-02-23T12:26:57Z","ddc":["004"],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:36Z","_id":"512","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","pubrep_id":"938","status":"public","publication_status":"published","publication_identifier":{"issn":["20452322"]},"language":[{"iso":"eng"}],"file":[{"file_size":1536783,"date_updated":"2020-07-14T12:46:36Z","creator":"system","file_name":"IST-2018-938-v1+1_2017_Pavlogiannis_Amplification_on.pdf","date_created":"2018-12-12T10:18:35Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"7d05cbdd914e194a019c0f91fb64e9a8","file_id":"5357"}],"ec_funded":1,"volume":7,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5449"}]},"issue":"1","abstract":[{"lang":"eng","text":"The fixation probability is the probability that a new mutant introduced in a homogeneous population eventually takes over the entire population. The fixation probability is a fundamental quantity of natural selection, and known to depend on the population structure. Amplifiers of natural selection are population structures which increase the fixation probability of advantageous mutants, as compared to the baseline case of well-mixed populations. In this work we focus on symmetric population structures represented as undirected graphs. In the regime of undirected graphs, the strongest amplifier known has been the Star graph, and the existence of undirected graphs with stronger amplification properties has remained open for over a decade. In this work we present the Comet and Comet-swarm families of undirected graphs. We show that for a range of fitness values of the mutants, the Comet and Cometswarm graphs have fixation probability strictly larger than the fixation probability of the Star graph, for fixed population size and at the limit of large populations, respectively. "}],"oa_version":"Published Version","scopus_import":1,"intvolume":" 7","month":"03"},{"oa":1,"publisher":"Institute of Science and Technology Austria","month":"01","abstract":[{"text":"Strong amplifiers of natural selection","lang":"eng"}],"oa_version":"Published Version","ec_funded":1,"date_created":"2018-12-12T12:31:32Z","date_published":"2017-01-02T00:00:00Z","doi":"10.15479/AT:ISTA:51","related_material":{"record":[{"status":"public","id":"5452","relation":"research_paper"},{"status":"public","id":"5751","relation":"research_paper"}]},"year":"2017","datarep_id":"51","has_accepted_license":"1","file":[{"checksum":"b427dd46a30096a1911b245640c47af8","file_id":"5644","content_type":"video/mp4","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T13:05:18Z","file_name":"IST-2017-51-v1+2_illustration.mp4","date_updated":"2020-07-14T12:47:02Z","file_size":32987015,"creator":"system"}],"day":"02","type":"research_data","keyword":["natural selection"],"project":[{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"status":"public","_id":"5559","article_processing_charge":"No","author":[{"last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef","last_name":"Tkadlec","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684"},{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Nowak , Martin","last_name":"Nowak ","first_name":"Martin"}],"title":"Strong amplifiers of natural selection","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:47:02Z","date_updated":"2024-02-21T13:48:42Z","citation":{"chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak . “Strong Amplifiers of Natural Selection.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:51.","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2017. Strong amplifiers of natural selection, Institute of Science and Technology Austria, 10.15479/AT:ISTA:51.","mla":"Pavlogiannis, Andreas, et al. Strong Amplifiers of Natural Selection. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:51.","ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak , “Strong amplifiers of natural selection.” Institute of Science and Technology Austria, 2017.","short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak , (2017).","ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Strong amplifiers of natural selection. 2017. doi:10.15479/AT:ISTA:51","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak , M. (2017). Strong amplifiers of natural selection. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:51"},"ddc":["519"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"}]