---
_id: '14657'
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.'
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).
article_number: '20230355'
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Kamran
full_name: Kaveh, Kamran
last_name: Kaveh
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin A.
full_name: Nowak, Martin A.
last_name: Nowak
citation:
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
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
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.
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.
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.
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.
short: J. Tkadlec, K. Kaveh, K. Chatterjee, M.A. Nowak, Journal of the Royal Society,
Interface 20 (2023).
date_created: 2023-12-10T23:00:58Z
date_published: 2023-11-29T00:00:00Z
date_updated: 2023-12-11T11:17:53Z
day: '29'
ddc:
- '000'
- '570'
department:
- _id: KrCh
doi: 10.1098/rsif.2023.0355
ec_funded: 1
external_id:
pmid:
- '38016637'
file:
- access_level: open_access
checksum: 2eefab13127c7786dbd33303c482a004
content_type: application/pdf
creator: dernst
date_created: 2023-12-11T11:10:32Z
date_updated: 2023-12-11T11:10:32Z
file_id: '14673'
file_name: 2023_RoyalInterface_Tkadlec.pdf
file_size: 1720243
relation: main_file
success: 1
file_date_updated: 2023-12-11T11:10:32Z
has_accepted_license: '1'
intvolume: ' 20'
issue: '208'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
pmid: 1
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Journal of the Royal Society, Interface
publication_identifier:
eissn:
- 1742-5662
publication_status: published
publisher: The Royal Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Evolutionary dynamics of mutants that modify population structure
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 20
year: '2023'
...
---
_id: '13258'
abstract:
- lang: eng
text: Many human interactions feature the characteristics of social dilemmas where
individual actions have consequences for the group and the environment. The feedback
between behavior and environment can be studied with the framework of stochastic
games. In stochastic games, the state of the environment can change, depending
on the choices made by group members. Past work suggests that such feedback can
reinforce cooperative behaviors. In particular, cooperation can evolve in stochastic
games even if it is infeasible in each separate repeated game. In stochastic games,
participants have an interest in conditioning their strategies on the state of
the environment. Yet in many applications, precise information about the state
could be scarce. Here, we study how the availability of information (or lack thereof)
shapes evolution of cooperation. Already for simple examples of two state games
we find surprising effects. In some cases, cooperation is only possible if there
is precise information about the state of the environment. In other cases, cooperation
is most abundant when there is no information about the state of the environment.
We systematically analyze all stochastic games of a given complexity class, to
determine when receiving information about the environment is better, neutral,
or worse for evolution of cooperation.
acknowledgement: 'This work was supported by the European Research Council CoG 863818
(ForM-SMArt) (to K.C.), the European Research Council Starting Grant 850529: E-DIRECT
(to C.H.), the European Union’s Horizon 2020 research and innovation program under
the Marie Sklodowska-Curie Grant Agreement #754411 and the French Agence Nationale
de la Recherche (under the Investissement d’Avenir programme, ANR-17-EURE-0010)
(to M.K.).'
article_number: '4153'
article_processing_charge: Yes
article_type: original
author:
- first_name: Maria
full_name: Kleshnina, Maria
id: 4E21749C-F248-11E8-B48F-1D18A9856A87
last_name: Kleshnina
- first_name: Christian
full_name: Hilbe, Christian
id: 2FDF8F3C-F248-11E8-B48F-1D18A9856A87
last_name: Hilbe
orcid: 0000-0001-5116-955X
- first_name: Stepan
full_name: Simsa, Stepan
id: 409d615c-2f95-11ee-b934-90a352102c1e
last_name: Simsa
orcid: 0000-0001-6687-1210
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin A.
full_name: Nowak, Martin A.
last_name: Nowak
citation:
ama: Kleshnina M, Hilbe C, Simsa S, Chatterjee K, Nowak MA. The effect of environmental
information on evolution of cooperation in stochastic games. Nature Communications.
2023;14. doi:10.1038/s41467-023-39625-9
apa: Kleshnina, M., Hilbe, C., Simsa, S., Chatterjee, K., & Nowak, M. A. (2023).
The effect of environmental information on evolution of cooperation in stochastic
games. Nature Communications. Springer Nature. https://doi.org/10.1038/s41467-023-39625-9
chicago: Kleshnina, Maria, Christian Hilbe, Stepan Simsa, Krishnendu Chatterjee,
and Martin A. Nowak. “The Effect of Environmental Information on Evolution of
Cooperation in Stochastic Games.” Nature Communications. Springer Nature,
2023. https://doi.org/10.1038/s41467-023-39625-9.
ieee: M. Kleshnina, C. Hilbe, S. Simsa, K. Chatterjee, and M. A. Nowak, “The effect
of environmental information on evolution of cooperation in stochastic games,”
Nature Communications, vol. 14. Springer Nature, 2023.
ista: Kleshnina M, Hilbe C, Simsa S, Chatterjee K, Nowak MA. 2023. The effect of
environmental information on evolution of cooperation in stochastic games. Nature
Communications. 14, 4153.
mla: Kleshnina, Maria, et al. “The Effect of Environmental Information on Evolution
of Cooperation in Stochastic Games.” Nature Communications, vol. 14, 4153,
Springer Nature, 2023, doi:10.1038/s41467-023-39625-9.
short: M. Kleshnina, C. Hilbe, S. Simsa, K. Chatterjee, M.A. Nowak, Nature Communications
14 (2023).
date_created: 2023-07-23T22:01:11Z
date_published: 2023-07-12T00:00:00Z
date_updated: 2023-12-13T11:42:38Z
day: '12'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1038/s41467-023-39625-9
ec_funded: 1
external_id:
isi:
- '001029450400031'
pmid:
- '37438341'
file:
- access_level: open_access
checksum: 5aceefdfe76686267b93ae4fe81899f1
content_type: application/pdf
creator: dernst
date_created: 2023-07-31T11:32:36Z
date_updated: 2023-07-31T11:32:36Z
file_id: '13337'
file_name: 2023_NatureComm_Kleshnina.pdf
file_size: 1601682
relation: main_file
success: 1
file_date_updated: 2023-07-31T11:32:36Z
has_accepted_license: '1'
intvolume: ' 14'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
pmid: 1
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Nature Communications
publication_identifier:
eissn:
- 2041-1723
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '13336'
relation: research_data
status: public
scopus_import: '1'
status: public
title: The effect of environmental information on evolution of cooperation in stochastic
games
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14
year: '2023'
...
---
_id: '13336'
article_processing_charge: No
author:
- first_name: Maria
full_name: Kleshnina, Maria
id: 4E21749C-F248-11E8-B48F-1D18A9856A87
last_name: Kleshnina
citation:
ama: 'Kleshnina M. kleshnina/stochgames_info: The effect of environmental information
on evolution of cooperation in stochastic games. 2023. doi:10.5281/ZENODO.8059564'
apa: 'Kleshnina, M. (2023). kleshnina/stochgames_info: The effect of environmental
information on evolution of cooperation in stochastic games. Zenodo. https://doi.org/10.5281/ZENODO.8059564'
chicago: 'Kleshnina, Maria. “Kleshnina/Stochgames_info: The Effect of Environmental
Information on Evolution of Cooperation in Stochastic Games.” Zenodo, 2023. https://doi.org/10.5281/ZENODO.8059564.'
ieee: 'M. Kleshnina, “kleshnina/stochgames_info: The effect of environmental information
on evolution of cooperation in stochastic games.” Zenodo, 2023.'
ista: 'Kleshnina M. 2023. kleshnina/stochgames_info: The effect of environmental
information on evolution of cooperation in stochastic games, Zenodo, 10.5281/ZENODO.8059564.'
mla: 'Kleshnina, Maria. Kleshnina/Stochgames_info: The Effect of Environmental
Information on Evolution of Cooperation in Stochastic Games. Zenodo, 2023,
doi:10.5281/ZENODO.8059564.'
short: M. Kleshnina, (2023).
date_created: 2023-07-31T11:30:46Z
date_published: 2023-06-20T00:00:00Z
date_updated: 2023-12-13T11:42:37Z
day: '20'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.5281/ZENODO.8059564
main_file_link:
- open_access: '1'
url: https://doi.org/10.5281/zenodo.8059564
month: '06'
oa: 1
oa_version: Published Version
publisher: Zenodo
related_material:
record:
- id: '13258'
relation: used_in_publication
status: public
status: public
title: 'kleshnina/stochgames_info: The effect of environmental information on evolution
of cooperation in stochastic games'
type: research_data_reference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '13967'
abstract:
- lang: eng
text: 'A classic solution technique for Markov decision processes (MDP) and stochastic
games (SG) is value iteration (VI). Due to its good practical performance, this
approximative approach is typically preferred over exact techniques, even though
no practical bounds on the imprecision of the result could be given until recently.
As a consequence, even the most used model checkers could return arbitrarily wrong
results. Over the past decade, different works derived stopping criteria, indicating
when the precision reaches the desired level, for various settings, in particular
MDP with reachability, total reward, and mean payoff, and SG with reachability.In
this paper, we provide the first stopping criteria for VI on SG with total reward
and mean payoff, yielding the first anytime algorithms in these settings. To this
end, we provide the solution in two flavours: First through a reduction to the
MDP case and second directly on SG. The former is simpler and automatically utilizes
any advances on MDP. The latter allows for more local computations, heading towards
better practical efficiency.Our solution unifies the previously mentioned approaches
for MDP and SG and their underlying ideas. To achieve this, we isolate objective-specific
subroutines as well as identify objective-independent concepts. These structural
concepts, while surprisingly simple, form the very essence of the unified solution.'
acknowledgement: This research was funded in part by DFG projects 383882557 “SUV”
and 427755713 “GOPro”.
article_processing_charge: No
author:
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
- first_name: Maximilian
full_name: Weininger, Maximilian
id: 02ab0197-cc70-11ed-ab61-918e71f56881
last_name: Weininger
citation:
ama: 'Kretinsky J, Meggendorfer T, Weininger M. Stopping criteria for value iteration
on stochastic games with quantitative objectives. In: 38th Annual ACM/IEEE
Symposium on Logic in Computer Science. Vol 2023. Institute of Electrical
and Electronics Engineers; 2023. doi:10.1109/LICS56636.2023.10175771'
apa: 'Kretinsky, J., Meggendorfer, T., & Weininger, M. (2023). Stopping criteria
for value iteration on stochastic games with quantitative objectives. In 38th
Annual ACM/IEEE Symposium on Logic in Computer Science (Vol. 2023). Boston,
MA, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/LICS56636.2023.10175771'
chicago: Kretinsky, Jan, Tobias Meggendorfer, and Maximilian Weininger. “Stopping
Criteria for Value Iteration on Stochastic Games with Quantitative Objectives.”
In 38th Annual ACM/IEEE Symposium on Logic in Computer Science, Vol. 2023.
Institute of Electrical and Electronics Engineers, 2023. https://doi.org/10.1109/LICS56636.2023.10175771.
ieee: J. Kretinsky, T. Meggendorfer, and M. Weininger, “Stopping criteria for value
iteration on stochastic games with quantitative objectives,” in 38th Annual
ACM/IEEE Symposium on Logic in Computer Science, Boston, MA, United States,
2023, vol. 2023.
ista: 'Kretinsky J, Meggendorfer T, Weininger M. 2023. Stopping criteria for value
iteration on stochastic games with quantitative objectives. 38th Annual ACM/IEEE
Symposium on Logic in Computer Science. LICS: Symposium on Logic in Computer Science
vol. 2023.'
mla: Kretinsky, Jan, et al. “Stopping Criteria for Value Iteration on Stochastic
Games with Quantitative Objectives.” 38th Annual ACM/IEEE Symposium on Logic
in Computer Science, vol. 2023, Institute of Electrical and Electronics Engineers,
2023, doi:10.1109/LICS56636.2023.10175771.
short: J. Kretinsky, T. Meggendorfer, M. Weininger, in:, 38th Annual ACM/IEEE Symposium
on Logic in Computer Science, Institute of Electrical and Electronics Engineers,
2023.
conference:
end_date: 2023-06-29
location: Boston, MA, United States
name: 'LICS: Symposium on Logic in Computer Science'
start_date: 2023-06-26
date_created: 2023-08-06T22:01:10Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-12-13T12:06:10Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/LICS56636.2023.10175771
external_id:
arxiv:
- '2304.09930'
isi:
- '001036707700042'
intvolume: ' 2023'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2304.09930
month: '07'
oa: 1
oa_version: Preprint
publication: 38th Annual ACM/IEEE Symposium on Logic in Computer Science
publication_identifier:
isbn:
- '9798350335873'
issn:
- 1043-6871
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Stopping criteria for value iteration on stochastic games with quantitative
objectives
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2023
year: '2023'
...
---
_id: '12833'
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: 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.'
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"
article_number: '9'
article_processing_charge: No
article_type: original
author:
- first_name: Ahmad
full_name: Biniaz, Ahmad
last_name: Biniaz
- first_name: Kshitij
full_name: Jain, Kshitij
last_name: Jain
- first_name: Anna
full_name: Lubiw, Anna
last_name: Lubiw
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Tillmann
full_name: Miltzow, Tillmann
last_name: Miltzow
- first_name: Debajyoti
full_name: Mondal, Debajyoti
last_name: Mondal
- first_name: Anurag Murty
full_name: Naredla, Anurag Murty
last_name: Naredla
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Alexi
full_name: Turcotte, Alexi
last_name: Turcotte
citation:
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
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
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.
ieee: A. Biniaz et al., “Token swapping on trees,” Discrete Mathematics
and Theoretical Computer Science, vol. 24, no. 2. EPI Sciences, 2023.
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.
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.
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).
date_created: 2023-04-16T22:01:08Z
date_published: 2023-01-18T00:00:00Z
date_updated: 2024-01-04T12:42:09Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
- _id: HeEd
- _id: UlWa
doi: 10.46298/DMTCS.8383
external_id:
arxiv:
- '1903.06981'
file:
- access_level: open_access
checksum: 439102ea4f6e2aeefd7107dfb9ccf532
content_type: application/pdf
creator: dernst
date_created: 2023-04-17T08:10:28Z
date_updated: 2023-04-17T08:10:28Z
file_id: '12844'
file_name: 2022_DMTCS_Biniaz.pdf
file_size: 2072197
relation: main_file
success: 1
file_date_updated: 2023-04-17T08:10:28Z
has_accepted_license: '1'
intvolume: ' 24'
issue: '2'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
publication: Discrete Mathematics and Theoretical Computer Science
publication_identifier:
eissn:
- 1365-8050
issn:
- 1462-7264
publication_status: published
publisher: EPI Sciences
quality_controlled: '1'
related_material:
record:
- id: '7950'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Token swapping on trees
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2023'
...