---
_id: '8671'
abstract:
- lang: eng
text: 'We study relations between evidence theory and S-approximation spaces. Both
theories have their roots in the analysis of Dempsterchr(''39'')s multivalued
mappings and lower and upper probabilities, and have close relations to rough
sets. We show that an S-approximation space, satisfying a monotonicity condition,
can induce a natural belief structure which is a fundamental block in evidence
theory. We also demonstrate that one can induce a natural belief structure on
one set, given a belief structure on another set, if the two sets are related
by a partial monotone S-approximation space. '
acknowledgement: We are very grateful to the anonymous reviewer for detailed comments
and suggestions that significantly improved the presentation of this paper. The
research was partially supported by a DOC fellowship of the Austrian Academy of
Sciences.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: A.
full_name: Shakiba, A.
last_name: Shakiba
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: M.R.
full_name: Hooshmandasl, M.R.
last_name: Hooshmandasl
- first_name: M.
full_name: Alambardar Meybodi, M.
last_name: Alambardar Meybodi
citation:
ama: Shakiba A, Goharshady AK, Hooshmandasl MR, Alambardar Meybodi M. A note on
belief structures and s-approximation spaces. Iranian Journal of Mathematical
Sciences and Informatics. 2020;15(2):117-128. doi:10.29252/ijmsi.15.2.117
apa: Shakiba, A., Goharshady, A. K., Hooshmandasl, M. R., & Alambardar Meybodi,
M. (2020). A note on belief structures and s-approximation spaces. Iranian
Journal of Mathematical Sciences and Informatics. Iranian Academic Center
for Education, Culture and Research. https://doi.org/10.29252/ijmsi.15.2.117
chicago: Shakiba, A., Amir Kafshdar Goharshady, M.R. Hooshmandasl, and M. Alambardar
Meybodi. “A Note on Belief Structures and S-Approximation Spaces.” Iranian
Journal of Mathematical Sciences and Informatics. Iranian Academic Center
for Education, Culture and Research, 2020. https://doi.org/10.29252/ijmsi.15.2.117.
ieee: A. Shakiba, A. K. Goharshady, M. R. Hooshmandasl, and M. Alambardar Meybodi,
“A note on belief structures and s-approximation spaces,” Iranian Journal of
Mathematical Sciences and Informatics, vol. 15, no. 2. Iranian Academic Center
for Education, Culture and Research, pp. 117–128, 2020.
ista: Shakiba A, Goharshady AK, Hooshmandasl MR, Alambardar Meybodi M. 2020. A note
on belief structures and s-approximation spaces. Iranian Journal of Mathematical
Sciences and Informatics. 15(2), 117–128.
mla: Shakiba, A., et al. “A Note on Belief Structures and S-Approximation Spaces.”
Iranian Journal of Mathematical Sciences and Informatics, vol. 15, no.
2, Iranian Academic Center for Education, Culture and Research, 2020, pp. 117–28,
doi:10.29252/ijmsi.15.2.117.
short: A. Shakiba, A.K. Goharshady, M.R. Hooshmandasl, M. Alambardar Meybodi, Iranian
Journal of Mathematical Sciences and Informatics 15 (2020) 117–128.
date_created: 2020-10-18T22:01:36Z
date_published: 2020-10-01T00:00:00Z
date_updated: 2025-04-15T07:55:04Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.29252/ijmsi.15.2.117
external_id:
arxiv:
- '1805.10672'
file:
- access_level: open_access
checksum: f299661a6d51cda6d255a76be696f48d
content_type: application/pdf
creator: dernst
date_created: 2020-10-19T11:14:20Z
date_updated: 2020-10-19T11:14:20Z
file_id: '8676'
file_name: 2020_ijmsi_Shakiba_accepted.pdf
file_size: 261688
relation: main_file
success: 1
file_date_updated: 2020-10-19T11:14:20Z
has_accepted_license: '1'
intvolume: ' 15'
issue: '2'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 117-128
project:
- _id: 267066CE-B435-11E9-9278-68D0E5697425
name: Quantitative Analysis of Probabilistic Systems with a focus on Crypto-Currencies
publication: Iranian Journal of Mathematical Sciences and Informatics
publication_identifier:
eissn:
- 2008-9473
issn:
- 1735-4463
publication_status: published
publisher: Iranian Academic Center for Education, Culture and Research
quality_controlled: '1'
scopus_import: '1'
status: public
title: A note on belief structures and s-approximation spaces
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2020'
...
---
_id: '8767'
abstract:
- lang: eng
text: Resources are rarely distributed uniformly within a population. Heterogeneity
in the concentration of a drug, the quality of breeding sites, or wealth can all
affect evolutionary dynamics. In this study, we represent a collection of properties
affecting the fitness at a given location using a color. A green node is rich
in resources while a red node is poorer. More colors can represent a broader spectrum
of resource qualities. For a population evolving according to the birth-death
Moran model, the first question we address is which structures, identified by
graph connectivity and graph coloring, are evolutionarily equivalent. We prove
that all properly two-colored, undirected, regular graphs are evolutionarily equivalent
(where “properly colored” means that no two neighbors have the same color). We
then compare the effects of background heterogeneity on properly two-colored graphs
to those with alternative schemes in which the colors are permuted. Finally, we
discuss dynamic coloring as a model for spatiotemporal resource fluctuations,
and we illustrate that random dynamic colorings often diminish the effects of
background heterogeneity relative to a proper two-coloring.
acknowledgement: 'We thank Igor Erovenko for many helpful comments on an earlier version
of this paper. : Army Research Laboratory (grant W911NF-18-2-0265) (M.A.N.); the
Bill & Melinda Gates Foundation (grant OPP1148627) (M.A.N.); the NVIDIA Corporation
(A.M.). The funders had no role in study design, data collection and analysis, decision
to publish, or preparation of the manuscript.'
article_number: e1008402
article_processing_charge: No
article_type: original
author:
- first_name: Kamran
full_name: Kaveh, Kamran
last_name: Kaveh
- first_name: Alex
full_name: McAvoy, Alex
last_name: McAvoy
- 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: Kaveh K, McAvoy A, Chatterjee K, Nowak MA. The Moran process on 2-chromatic
graphs. PLOS Computational Biology. 2020;16(11). doi:10.1371/journal.pcbi.1008402
apa: Kaveh, K., McAvoy, A., Chatterjee, K., & Nowak, M. A. (2020). The Moran
process on 2-chromatic graphs. PLOS Computational Biology. Public Library
of Science. https://doi.org/10.1371/journal.pcbi.1008402
chicago: Kaveh, Kamran, Alex McAvoy, Krishnendu Chatterjee, and Martin A. Nowak.
“The Moran Process on 2-Chromatic Graphs.” PLOS Computational Biology.
Public Library of Science, 2020. https://doi.org/10.1371/journal.pcbi.1008402.
ieee: K. Kaveh, A. McAvoy, K. Chatterjee, and M. A. Nowak, “The Moran process on
2-chromatic graphs,” PLOS Computational Biology, vol. 16, no. 11. Public
Library of Science, 2020.
ista: Kaveh K, McAvoy A, Chatterjee K, Nowak MA. 2020. The Moran process on 2-chromatic
graphs. PLOS Computational Biology. 16(11), e1008402.
mla: Kaveh, Kamran, et al. “The Moran Process on 2-Chromatic Graphs.” PLOS Computational
Biology, vol. 16, no. 11, e1008402, Public Library of Science, 2020, doi:10.1371/journal.pcbi.1008402.
short: K. Kaveh, A. McAvoy, K. Chatterjee, M.A. Nowak, PLOS Computational Biology
16 (2020).
date_created: 2020-11-18T07:20:23Z
date_published: 2020-11-05T00:00:00Z
date_updated: 2025-06-12T07:02:01Z
day: '05'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1371/journal.pcbi.1008402
external_id:
isi:
- '000591317200004'
pmid:
- '33151935'
file:
- access_level: open_access
checksum: 555456dd0e47bcf9e0994bcb95577e88
content_type: application/pdf
creator: dernst
date_created: 2020-11-18T07:26:10Z
date_updated: 2020-11-18T07:26:10Z
file_id: '8768'
file_name: 2020_PlosCompBio_Kaveh.pdf
file_size: 2498594
relation: main_file
success: 1
file_date_updated: 2020-11-18T07:26:10Z
has_accepted_license: '1'
intvolume: ' 16'
isi: 1
issue: '11'
keyword:
- Ecology
- Modelling and Simulation
- Computational Theory and Mathematics
- Genetics
- Ecology
- Evolution
- Behavior and Systematics
- Molecular Biology
- Cellular and Molecular Neuroscience
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '11'
oa: 1
oa_version: Published Version
pmid: 1
publication: PLOS Computational Biology
publication_identifier:
eissn:
- 1553-7358
issn:
- 1553-734X
publication_status: published
publisher: Public Library of Science
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Moran process on 2-chromatic graphs
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: 16
year: '2020'
...
---
_id: '8788'
abstract:
- lang: eng
text: 'We consider a real-time setting where an environment releases sequences of
firm-deadline tasks, and an online scheduler chooses on-the-fly the ones to execute
on a single processor so as to maximize cumulated utility. The competitive ratio
is a well-known performance measure for the scheduler: it gives the worst-case
ratio, among all possible choices for the environment, of the cumulated utility
of the online scheduler versus an offline scheduler that knows these choices in
advance. Traditionally, competitive analysis is performed by hand, while automated
techniques are rare and only handle static environments with independent tasks.
We present a quantitative-verification framework for precedence-aware competitive
analysis, where task releases may depend on preceding scheduling choices, i.e.,
the environment can respond to scheduling decisions dynamically . We consider
two general classes of precedences: 1) follower precedences force the release
of a dependent task upon the completion of a set of precursor tasks, while and
2) pairing precedences modify the characteristics of a dependent task provided
the completion of a set of precursor tasks. Precedences make competitive analysis
challenging, as the online and offline schedulers operate on diverging sequences.
We make a formal presentation of our framework, and use a GPU-based implementation
to analyze ten well-known schedulers on precedence-based application examples
taken from the existing literature: 1) a handshake protocol (HP); 2) network packet-switching;
3) query scheduling (QS); and 4) a sporadic-interrupt setting. Our experimental
results show that precedences and task parameters can vary drastically the best
scheduler. Our framework thus supports application designers in choosing the best
scheduler among a given set automatically.'
acknowledgement: 'This work was supported by the Austrian Science Foundation (FWF)
under the NFN RiSE/SHiNE under Grant S11405 and Grant S11407. This article was presented
in the International Conference on Embedded Software 2020 and appears as part of
the ESWEEK-TCAD special issue. '
article_processing_charge: No
article_type: original
author:
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Nico
full_name: Schaumberger, Nico
last_name: Schaumberger
- first_name: Ulrich
full_name: Schmid, Ulrich
last_name: Schmid
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Pavlogiannis A, Schaumberger N, Schmid U, Chatterjee K. Precedence-aware automated
competitive analysis of real-time scheduling. IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems. 2020;39(11):3981-3992. doi:10.1109/TCAD.2020.3012803
apa: Pavlogiannis, A., Schaumberger, N., Schmid, U., & Chatterjee, K. (2020).
Precedence-aware automated competitive analysis of real-time scheduling. IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems.
IEEE. https://doi.org/10.1109/TCAD.2020.3012803
chicago: Pavlogiannis, Andreas, Nico Schaumberger, Ulrich Schmid, and Krishnendu
Chatterjee. “Precedence-Aware Automated Competitive Analysis of Real-Time Scheduling.”
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.
IEEE, 2020. https://doi.org/10.1109/TCAD.2020.3012803.
ieee: A. Pavlogiannis, N. Schaumberger, U. Schmid, and K. Chatterjee, “Precedence-aware
automated competitive analysis of real-time scheduling,” IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no.
11. IEEE, pp. 3981–3992, 2020.
ista: Pavlogiannis A, Schaumberger N, Schmid U, Chatterjee K. 2020. Precedence-aware
automated competitive analysis of real-time scheduling. IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems. 39(11), 3981–3992.
mla: Pavlogiannis, Andreas, et al. “Precedence-Aware Automated Competitive Analysis
of Real-Time Scheduling.” IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, vol. 39, no. 11, IEEE, 2020, pp. 3981–92, doi:10.1109/TCAD.2020.3012803.
short: A. Pavlogiannis, N. Schaumberger, U. Schmid, K. Chatterjee, IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems 39 (2020) 3981–3992.
date_created: 2020-11-22T23:01:24Z
date_published: 2020-11-01T00:00:00Z
date_updated: 2026-04-02T14:37:50Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/TCAD.2020.3012803
external_id:
isi:
- '000587712700069'
intvolume: ' 39'
isi: 1
issue: '11'
language:
- iso: eng
month: '11'
oa_version: None
page: 3981-3992
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: IEEE Transactions on Computer-Aided Design of Integrated Circuits and
Systems
publication_identifier:
eissn:
- 1937-4151
issn:
- 0278-0070
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Precedence-aware automated competitive analysis of real-time scheduling
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 39
year: '2020'
...
---
_id: '8789'
abstract:
- lang: eng
text: Cooperation is a ubiquitous and beneficial behavioural trait despite being
prone to exploitation by free-riders. Hence, cooperative populations are prone
to invasions by selfish individuals. However, a population consisting of only
free-riders typically does not survive. Thus, cooperators and free-riders often
coexist in some proportion. An evolutionary version of a Snowdrift Game proved
its efficiency in analysing this phenomenon. However, what if the system has already
reached its stable state but was perturbed due to a change in environmental conditions?
Then, individuals may have to re-learn their effective strategies. To address
this, we consider behavioural mistakes in strategic choice execution, which we
refer to as incompetence. Parametrising the propensity to make such mistakes allows
for a mathematical description of learning. We compare strategies based on their
relative strategic advantage relying on both fitness and learning factors. When
strategies are learned at distinct rates, allowing learning according to a prescribed
order is optimal. Interestingly, the strategy with the lowest strategic advantage
should be learnt first if we are to optimise fitness over the learning path. Then,
the differences between strategies are balanced out in order to minimise the effect
of behavioural uncertainty.
acknowledgement: "This work was supported by the European Union’s Horizon 2020 research
and innovation program under the Marie Sklodowska-Curie Grant Agreement #754411,
the Australian Research Council Discovery Grants DP160101236 and DP150100618, and
the European Research Council Consolidator Grant 863818 (FoRM-SMArt).\r\nAuthors
would like to thank Patrick McKinlay for his work on the preliminary results for
this paper."
article_number: '1945'
article_processing_charge: No
article_type: original
author:
- first_name: Maria
full_name: Kleshnina, Maria
id: 4E21749C-F248-11E8-B48F-1D18A9856A87
last_name: Kleshnina
orcid: 0000-0002-5518-8317
- first_name: Sabrina
full_name: Streipert, Sabrina
last_name: Streipert
- first_name: Jerzy
full_name: Filar, Jerzy
last_name: Filar
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Kleshnina M, Streipert S, Filar J, Chatterjee K. Prioritised learning in snowdrift-type
games. Mathematics. 2020;8(11). doi:10.3390/math8111945
apa: Kleshnina, M., Streipert, S., Filar, J., & Chatterjee, K. (2020). Prioritised
learning in snowdrift-type games. Mathematics. MDPI. https://doi.org/10.3390/math8111945
chicago: Kleshnina, Maria, Sabrina Streipert, Jerzy Filar, and Krishnendu Chatterjee.
“Prioritised Learning in Snowdrift-Type Games.” Mathematics. MDPI, 2020.
https://doi.org/10.3390/math8111945.
ieee: M. Kleshnina, S. Streipert, J. Filar, and K. Chatterjee, “Prioritised learning
in snowdrift-type games,” Mathematics, vol. 8, no. 11. MDPI, 2020.
ista: Kleshnina M, Streipert S, Filar J, Chatterjee K. 2020. Prioritised learning
in snowdrift-type games. Mathematics. 8(11), 1945.
mla: Kleshnina, Maria, et al. “Prioritised Learning in Snowdrift-Type Games.” Mathematics,
vol. 8, no. 11, 1945, MDPI, 2020, doi:10.3390/math8111945.
short: M. Kleshnina, S. Streipert, J. Filar, K. Chatterjee, Mathematics 8 (2020).
corr_author: '1'
date_created: 2020-11-22T23:01:24Z
date_published: 2020-11-04T00:00:00Z
date_updated: 2026-04-07T08:37:03Z
day: '04'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.3390/math8111945
ec_funded: 1
external_id:
isi:
- '000593962100001'
file:
- access_level: open_access
checksum: 61cfcc3b35760656ce7a9385a4ace5d2
content_type: application/pdf
creator: dernst
date_created: 2020-11-23T13:06:30Z
date_updated: 2020-11-23T13:06:30Z
file_id: '8797'
file_name: 2020_Mathematics_Kleshnina.pdf
file_size: 565191
relation: main_file
success: 1
file_date_updated: 2020-11-23T13:06:30Z
has_accepted_license: '1'
intvolume: ' 8'
isi: 1
issue: '11'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Mathematics
publication_identifier:
eissn:
- 2227-7390
publication_status: published
publisher: MDPI
quality_controlled: '1'
scopus_import: '1'
status: public
title: Prioritised learning in snowdrift-type 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: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 8
year: '2020'
...
---
OA_place: repository
OA_type: green
_id: '9197'
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.
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).
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
citation:
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'
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.
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.
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.
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.
short: G. Avni, R. Ibsen-Jensen, J. Tkadlec, Proceedings of the AAAI Conference
on Artificial Intelligence 34 (2020) 1798–1805.
conference:
end_date: 2020-02-12
location: New York, NY, United States
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2020-02-07
date_created: 2021-02-25T09:05:18Z
date_published: 2020-04-03T00:00:00Z
date_updated: 2025-07-03T11:44:58Z
day: '03'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1609/aaai.v34i02.5546
external_id:
arxiv:
- '1911.08360'
intvolume: ' 34'
issue: '02'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1911.08360
month: '04'
oa: 1
oa_version: Preprint
page: 1798-1805
project:
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 264B3912-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02369
name: Formal Methods meets Algorithmic Game Theory
publication: Proceedings of the AAAI Conference on Artificial Intelligence
publication_identifier:
eissn:
- 2374-3468
isbn:
- '9781577358350'
issn:
- 2159-5399
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: All-pay bidding games on graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2020'
...
---
OA_place: publisher
OA_type: hybrid
_id: '9814'
abstract:
- lang: eng
text: Data and mathematica notebooks for plotting figures from Language learning
with communication between learners
article_processing_charge: No
author:
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
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
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
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.
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.
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.
short: R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, M. Nowak, (2020).
date_created: 2021-08-06T13:09:57Z
date_published: 2020-10-15T00:00:00Z
date_updated: 2025-04-15T08:12:20Z
day: '15'
department:
- _id: KrCh
doi: 10.6084/m9.figshare.5973013.v1
main_file_link:
- open_access: '1'
url: https://doi.org/10.6084/m9.figshare.5973013.v1
month: '10'
oa: 1
oa_version: Published Version
publisher: Royal Society
related_material:
record:
- id: '198'
relation: used_in_publication
status: public
status: public
title: Data and mathematica notebooks for plotting figures from language learning
with communication between learners from language acquisition with communication
between learners
type: research_data_reference
user_id: 0043cee0-e5fc-11ee-9736-f83bc23afbf0
year: '2020'
...
---
OA_place: publisher
_id: '7196'
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.'
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
citation:
ama: Tkadlec J. A role of graphs in evolutionary processes. 2020. doi:10.15479/AT:ISTA:7196
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
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.
ista: Tkadlec J. 2020. A role of graphs in evolutionary processes. Institute of
Science and Technology Austria.
mla: Tkadlec, Josef. A Role of Graphs in Evolutionary Processes. Institute
of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7196.
short: J. Tkadlec, A Role of Graphs in Evolutionary Processes, Institute of Science
and Technology Austria, 2020.
corr_author: '1'
date_created: 2019-12-20T12:26:36Z
date_published: 2020-01-12T00:00:00Z
date_updated: 2026-04-16T08:32:37Z
day: '12'
ddc:
- '519'
degree_awarded: PhD
department:
- _id: KrCh
- _id: GradSch
doi: 10.15479/AT:ISTA:7196
file:
- access_level: closed
checksum: 451f8e64b0eb26bf297644ac72bfcbe9
content_type: application/zip
creator: jtkadlec
date_created: 2020-01-12T11:49:49Z
date_updated: 2020-07-14T12:47:52Z
file_id: '7255'
file_name: thesis.zip
file_size: 21100497
relation: source_file
- access_level: open_access
checksum: d8c44cbc4f939c49a8efc9d4b8bb3985
content_type: application/pdf
creator: dernst
date_created: 2020-01-28T07:32:42Z
date_updated: 2020-07-14T12:47:52Z
file_id: '7367'
file_name: 2020_Tkadlec_Thesis.pdf
file_size: 11670983
relation: main_file
file_date_updated: 2020-07-14T12:47:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '144'
publication_identifier:
eissn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '5751'
relation: dissertation_contains
status: public
- id: '7210'
relation: dissertation_contains
status: public
- id: '7212'
relation: dissertation_contains
status: public
status: public
supervisor:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
title: A role of graphs in evolutionary processes
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2020'
...
---
_id: '7212'
abstract:
- lang: eng
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.
article_number: e1007494
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- 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, 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
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
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.
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.
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.
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.
short: J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, PLoS Computational
Biology 16 (2020).
date_created: 2019-12-23T13:45:11Z
date_published: 2020-01-17T00:00:00Z
date_updated: 2026-04-16T08:32:38Z
day: '17'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1371/journal.pcbi.1007494
ec_funded: 1
external_id:
arxiv:
- '1906.02785'
isi:
- '000510916500025'
file:
- access_level: open_access
checksum: ce32ee2d2f53aed832f78bbd47e882df
content_type: application/pdf
creator: dernst
date_created: 2020-02-03T07:32:42Z
date_updated: 2020-07-14T12:47:53Z
file_id: '7441'
file_name: 2020_PlosCompBio_Tkadlec.pdf
file_size: 1817531
relation: main_file
file_date_updated: 2020-07-14T12:47:53Z
has_accepted_license: '1'
intvolume: ' 16'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _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
grant_number: S11407
name: Game Theory
publication: PLoS computational biology
publication_identifier:
eissn:
- 1553-7358
issn:
- 1553-734X
publication_status: published
publisher: Public Library of Science
quality_controlled: '1'
related_material:
record:
- id: '7196'
relation: part_of_dissertation
status: public
scopus_import: '1'
status: public
title: Limits on amplifiers of natural selection under death-Birth updating
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: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 16
year: '2020'
...
---
_id: '7343'
abstract:
- lang: eng
text: Coinfections with multiple pathogens can result in complex within‐host dynamics
affecting virulence and transmission. While multiple infections are intensively
studied in solitary hosts, it is so far unresolved how social host interactions
interfere with pathogen competition, and if this depends on coinfection diversity.
We studied how the collective disease defences of ants – their social immunity
– influence pathogen competition in coinfections of same or different fungal pathogen
species. Social immunity reduced virulence for all pathogen combinations, but
interfered with spore production only in different‐species coinfections. Here,
it decreased overall pathogen sporulation success while increasing co‐sporulation
on individual cadavers and maintaining a higher pathogen diversity at the community
level. Mathematical modelling revealed that host sanitary care alone can modulate
competitive outcomes between pathogens, giving advantage to fast‐germinating,
thus less grooming‐sensitive ones. Host social interactions can hence modulate
infection dynamics in coinfected group members, thereby altering pathogen communities
at the host level and population level.
acknowledged_ssus:
- _id: LifeSc
acknowledgement: "We thank Bernhardt Steinwender and Jorgen Eilenberg for the fungal
strains, Xavier Espadaler, Mireia Diaz, Christiane Wanke, Lumi Viljakainen and the
Social Immunity Team at IST Austria, for help with ant collection, and Wanda Gorecka
and Gertraud Stift of the IST Austria Life Science Facility for technical support.
We are thankful to Dieter Ebert for input at all stages of the project, Roger Mundry
for statistical advice, Hinrich Schulenburg, Paul Schmid-Hempel, Yuko\r\nUlrich
and Joachim Kurtz for project discussion, Bor Kavcic for advice on growth curves,
Marcus Roper for advice on modelling work and comments on the manuscript, as well
as Marjon de Vos, Weini Huang and the Social Immunity Team for comments on the manuscript.\r\nThis
study was funded by the German Research Foundation (DFG) within the Priority Programme
1399 Host-parasite Coevolution (CR 118/3 to S.C.) and the People Programme\r\n(Marie
Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013)
under REA grant agreement no 291734 (ISTFELLOW to B.M.). "
article_processing_charge: Yes (via OA deal)
article_type: letter_note
author:
- first_name: Barbara
full_name: Milutinovic, Barbara
id: 2CDC32B8-F248-11E8-B48F-1D18A9856A87
last_name: Milutinovic
orcid: 0000-0002-8214-4758
- first_name: Miriam
full_name: Stock, Miriam
id: 42462816-F248-11E8-B48F-1D18A9856A87
last_name: Stock
- first_name: Anna V
full_name: Grasse, Anna V
id: 406F989C-F248-11E8-B48F-1D18A9856A87
last_name: Grasse
- first_name: Elisabeth
full_name: Naderlinger, Elisabeth
id: 31757262-F248-11E8-B48F-1D18A9856A87
last_name: Naderlinger
- first_name: Christian
full_name: Hilbe, Christian
id: 2FDF8F3C-F248-11E8-B48F-1D18A9856A87
last_name: Hilbe
orcid: 0000-0001-5116-955X
- first_name: Sylvia
full_name: Cremer, Sylvia
id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87
last_name: Cremer
orcid: 0000-0002-2193-3868
citation:
ama: Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. Social
immunity modulates competition between coinfecting pathogens. Ecology Letters.
2020;23(3):565-574. doi:10.1111/ele.13458
apa: Milutinovic, B., Stock, M., Grasse, A. V., Naderlinger, E., Hilbe, C., &
Cremer, S. (2020). Social immunity modulates competition between coinfecting pathogens.
Ecology Letters. Wiley. https://doi.org/10.1111/ele.13458
chicago: Milutinovic, Barbara, Miriam Stock, Anna V Grasse, Elisabeth Naderlinger,
Christian Hilbe, and Sylvia Cremer. “Social Immunity Modulates Competition between
Coinfecting Pathogens.” Ecology Letters. Wiley, 2020. https://doi.org/10.1111/ele.13458.
ieee: B. Milutinovic, M. Stock, A. V. Grasse, E. Naderlinger, C. Hilbe, and S. Cremer,
“Social immunity modulates competition between coinfecting pathogens,” Ecology
Letters, vol. 23, no. 3. Wiley, pp. 565–574, 2020.
ista: Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. 2020.
Social immunity modulates competition between coinfecting pathogens. Ecology Letters.
23(3), 565–574.
mla: Milutinovic, Barbara, et al. “Social Immunity Modulates Competition between
Coinfecting Pathogens.” Ecology Letters, vol. 23, no. 3, Wiley, 2020, pp.
565–74, doi:10.1111/ele.13458.
short: B. Milutinovic, M. Stock, A.V. Grasse, E. Naderlinger, C. Hilbe, S. Cremer,
Ecology Letters 23 (2020) 565–574.
corr_author: '1'
date_created: 2020-01-20T13:32:12Z
date_published: 2020-03-01T00:00:00Z
date_updated: 2025-06-12T07:32:35Z
day: '01'
ddc:
- '570'
department:
- _id: SyCr
- _id: KrCh
doi: 10.1111/ele.13458
ec_funded: 1
external_id:
isi:
- '000507515900001'
pmid:
- '31950595'
file:
- access_level: open_access
checksum: 0cd8be386fa219db02845b7c3991ce04
content_type: application/pdf
creator: dernst
date_created: 2020-11-19T11:27:10Z
date_updated: 2020-11-19T11:27:10Z
file_id: '8776'
file_name: 2020_EcologyLetters_Milutinovic.pdf
file_size: 561749
relation: main_file
success: 1
file_date_updated: 2020-11-19T11:27:10Z
has_accepted_license: '1'
intvolume: ' 23'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc/4.0/
month: '03'
oa: 1
oa_version: Published Version
page: 565-574
pmid: 1
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 25DAF0B2-B435-11E9-9278-68D0E5697425
grant_number: CR-118/3-1
name: Host-Parasite Coevolution
publication: Ecology Letters
publication_identifier:
eissn:
- 1461-0248
issn:
- 1461-023X
publication_status: published
publisher: Wiley
quality_controlled: '1'
related_material:
link:
- description: News on IST Homepage
relation: press_release
url: https://ist.ac.at/en/news/social-ants-shapes-disease-outcome/
record:
- id: '13060'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Social immunity modulates competition between coinfecting pathogens
tmp:
image: /images/cc_by_nc.png
legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
short: CC BY-NC (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2020'
...
---
_id: '7346'
abstract:
- lang: eng
text: 'The Price of Anarchy (PoA) is a well-established game-theoretic concept to
shed light on coordination issues arising in open distributed systems. Leaving
agents to selfishly optimize comes with the risk of ending up in sub-optimal states
(in terms of performance and/or costs), compared to a centralized system design.
However, the PoA relies on strong assumptions about agents'' rationality (e.g.,
resources and information) and interactions, whereas in many distributed systems
agents interact locally with bounded resources. They do so repeatedly over time
(in contrast to "one-shot games"), and their strategies may evolve. Using a more
realistic evolutionary game model, this paper introduces a realized evolutionary
Price of Anarchy (ePoA). The ePoA allows an exploration of equilibrium selection
in dynamic distributed systems with multiple equilibria, based on local interactions
of simple memoryless agents. Considering a fundamental game related to virus propagation
on networks, we present analytical bounds on the ePoA in basic network topologies
and for different strategy update dynamics. In particular, deriving stationary
distributions of the stochastic evolutionary process, we find that the Nash equilibria
are not always the most abundant states, and that different processes can feature
significant off-equilibrium behavior, leading to a significantly higher ePoA compared
to the PoA studied traditionally in the literature. '
alternative_title:
- LIPIcs
article_number: '21'
article_processing_charge: No
arxiv: 1
author:
- first_name: Laura
full_name: Schmid, Laura
id: 38B437DE-F248-11E8-B48F-1D18A9856A87
last_name: Schmid
orcid: 0000-0002-6978-7329
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Schmid L, Chatterjee K, Schmid S. The evolutionary price of anarchy: Locally
bounded agents in a dynamic virus game. In: Proceedings of the 23rd International
Conference on Principles of Distributed Systems. Vol 153. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.OPODIS.2019.21'
apa: 'Schmid, L., Chatterjee, K., & Schmid, S. (2020). The evolutionary price
of anarchy: Locally bounded agents in a dynamic virus game. In Proceedings
of the 23rd International Conference on Principles of Distributed Systems
(Vol. 153). Neuchâtel, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.OPODIS.2019.21'
chicago: 'Schmid, Laura, Krishnendu Chatterjee, and Stefan Schmid. “The Evolutionary
Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game.” In Proceedings
of the 23rd International Conference on Principles of Distributed Systems,
Vol. 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.OPODIS.2019.21.'
ieee: 'L. Schmid, K. Chatterjee, and S. Schmid, “The evolutionary price of anarchy:
Locally bounded agents in a dynamic virus game,” in Proceedings of the 23rd
International Conference on Principles of Distributed Systems, Neuchâtel,
Switzerland, 2020, vol. 153.'
ista: 'Schmid L, Chatterjee K, Schmid S. 2020. The evolutionary price of anarchy:
Locally bounded agents in a dynamic virus game. Proceedings of the 23rd International
Conference on Principles of Distributed Systems. OPODIS: International Conference
on Principles of Distributed Systems, LIPIcs, vol. 153, 21.'
mla: 'Schmid, Laura, et al. “The Evolutionary Price of Anarchy: Locally Bounded
Agents in a Dynamic Virus Game.” Proceedings of the 23rd International Conference
on Principles of Distributed Systems, vol. 153, 21, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2020, doi:10.4230/LIPIcs.OPODIS.2019.21.'
short: L. Schmid, K. Chatterjee, S. Schmid, in:, Proceedings of the 23rd International
Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2020.
conference:
end_date: 2019-12-19
location: Neuchâtel, Switzerland
name: 'OPODIS: International Conference on Principles of Distributed Systems'
start_date: 2019-12-17
date_created: 2020-01-21T16:00:26Z
date_published: 2020-02-10T00:00:00Z
date_updated: 2025-04-15T08:10:32Z
day: '10'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.OPODIS.2019.21
external_id:
arxiv:
- '1906.00110'
file:
- access_level: open_access
checksum: 9a91916ac2c21ab42458fcda39ef0b8d
content_type: application/pdf
creator: dernst
date_created: 2020-03-23T09:14:06Z
date_updated: 2020-07-14T12:47:56Z
file_id: '7608'
file_name: 2019_LIPIcS_Schmid.pdf
file_size: 630752
relation: main_file
file_date_updated: 2020-07-14T12:47:56Z
has_accepted_license: '1'
intvolume: ' 153'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Preprint
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: Proceedings of the 23rd International Conference on Principles of Distributed
Systems
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The evolutionary price of anarchy: Locally bounded agents in a dynamic virus
game'
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 153
year: '2020'
...
---
_id: '8728'
abstract:
- lang: eng
text: Discrete-time Markov Chains (MCs) and Markov Decision Processes (MDPs) are
two standard formalisms in system analysis. Their main associated quantitative
objectives are hitting probabilities, discounted sum, and mean payoff. Although
there are many techniques for computing these objectives in general MCs/MDPs,
they have not been thoroughly studied in terms of parameterized algorithms, particularly
when treewidth is used as the parameter. This is in sharp contrast to qualitative
objectives for MCs, MDPs and graph games, for which treewidth-based algorithms
yield significant complexity improvements. In this work, we show that treewidth
can also be used to obtain faster algorithms for the quantitative problems. For
an MC with n states and m transitions, we show that each of the classical quantitative
objectives can be computed in O((n+m)⋅t2) time, given a tree decomposition
of the MC with width t. Our results also imply a bound of O(κ⋅(n+m)⋅t2) for
each objective on MDPs, where κ is the number of strategy-iteration refinements
required for the given input and objective. Finally, we make an experimental evaluation
of our new algorithms on low-treewidth MCs and MDPs obtained from the DaCapo benchmark
suite. Our experiments show that on low-treewidth MCs and MDPs, our algorithms
outperform existing well-established methods by one or more orders of magnitude.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Ali
full_name: Asadi, Ali
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Kiarash
full_name: Mohammadi, Kiarash
last_name: Mohammadi
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: 'Asadi A, Chatterjee K, Goharshady AK, Mohammadi K, Pavlogiannis A. Faster
algorithms for quantitative analysis of MCs and MDPs with small treewidth. In:
Automated Technology for Verification and Analysis. Vol 12302. Springer
Nature; 2020:253-270. doi:10.1007/978-3-030-59152-6_14'
apa: 'Asadi, A., Chatterjee, K., Goharshady, A. K., Mohammadi, K., & Pavlogiannis,
A. (2020). Faster algorithms for quantitative analysis of MCs and MDPs with small
treewidth. In Automated Technology for Verification and Analysis (Vol.
12302, pp. 253–270). Hanoi, Vietnam: Springer Nature. https://doi.org/10.1007/978-3-030-59152-6_14'
chicago: Asadi, Ali, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Kiarash Mohammadi,
and Andreas Pavlogiannis. “Faster Algorithms for Quantitative Analysis of MCs
and MDPs with Small Treewidth.” In Automated Technology for Verification and
Analysis, 12302:253–70. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-59152-6_14.
ieee: A. Asadi, K. Chatterjee, A. K. Goharshady, K. Mohammadi, and A. Pavlogiannis,
“Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth,”
in Automated Technology for Verification and Analysis, Hanoi, Vietnam,
2020, vol. 12302, pp. 253–270.
ista: 'Asadi A, Chatterjee K, Goharshady AK, Mohammadi K, Pavlogiannis A. 2020.
Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth.
Automated Technology for Verification and Analysis. ATVA: Automated Technology
for Verification and Analysis, LNCS, vol. 12302, 253–270.'
mla: Asadi, Ali, et al. “Faster Algorithms for Quantitative Analysis of MCs and
MDPs with Small Treewidth.” Automated Technology for Verification and Analysis,
vol. 12302, Springer Nature, 2020, pp. 253–70, doi:10.1007/978-3-030-59152-6_14.
short: A. Asadi, K. Chatterjee, A.K. Goharshady, K. Mohammadi, A. Pavlogiannis,
in:, Automated Technology for Verification and Analysis, Springer Nature, 2020,
pp. 253–270.
conference:
end_date: 2020-10-23
location: Hanoi, Vietnam
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2020-10-19
date_created: 2020-11-06T07:30:05Z
date_published: 2020-10-12T00:00:00Z
date_updated: 2026-07-03T22:35:27Z
day: '12'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-030-59152-6_14
external_id:
isi:
- '000723555700014'
file:
- access_level: open_access
checksum: ae83f27e5b189d5abc2e7514f1b7e1b5
content_type: application/pdf
creator: dernst
date_created: 2020-11-06T07:41:03Z
date_updated: 2020-11-06T07:41:03Z
file_id: '8729'
file_name: 2020_LNCS_ATVA_Asadi_accepted.pdf
file_size: 726648
relation: main_file
success: 1
file_date_updated: 2020-11-06T07:41:03Z
has_accepted_license: '1'
intvolume: ' 12302'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 253-270
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 267066CE-B435-11E9-9278-68D0E5697425
name: Quantitative Analysis of Probabilistic Systems with a focus on Crypto-Currencies
publication: Automated Technology for Verification and Analysis
publication_identifier:
eisbn:
- '9783030591526'
eissn:
- 1611-3349
isbn:
- '9783030591519'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '8934'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12302
year: '2020'
...
---
_id: '8089'
abstract:
- lang: eng
text: "We consider the classical problem of invariant generation for programs with
polynomial assignments and focus on synthesizing invariants that are a conjunction
of strict polynomial inequalities. We present a sound and semi-complete method
based on positivstellensaetze, i.e. theorems in semi-algebraic geometry that characterize
positive polynomials over a semi-algebraic set.\r\n\r\nOn the theoretical side,
the worst-case complexity of our approach is subexponential, whereas the worst-case
complexity of the previous complete method (Kapur, ACA 2004) is doubly-exponential.
Even when restricted to linear invariants, the best previous complexity for complete
invariant generation is exponential (Colon et al, CAV 2003). On the practical
side, we reduce the invariant generation problem to quadratic programming (QCLP),
which is a classical optimization problem with many industrial solvers. We demonstrate
the applicability of our approach by providing experimental results on several
academic benchmarks. To the best of our knowledge, the only previous invariant
generation method that provides completeness guarantees for invariants consisting
of polynomial inequalities is (Kapur, ACA 2004), which relies on quantifier elimination
and cannot even handle toy programs such as our running example."
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Hongfei
full_name: Fu, Hongfei
id: 3AAD03D6-F248-11E8-B48F-1D18A9856A87
last_name: Fu
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Ehsan Kafshdar
full_name: Goharshady, Ehsan Kafshdar
last_name: Goharshady
citation:
ama: 'Chatterjee K, Fu H, Goharshady AK, Goharshady EK. Polynomial invariant generation
for non-deterministic recursive programs. In: Proceedings of the 41st ACM SIGPLAN
Conference on Programming Language Design and Implementation. Association
for Computing Machinery; 2020:672-687. doi:10.1145/3385412.3385969'
apa: 'Chatterjee, K., Fu, H., Goharshady, A. K., & Goharshady, E. K. (2020).
Polynomial invariant generation for non-deterministic recursive programs. In Proceedings
of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation
(pp. 672–687). London, United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3385412.3385969'
chicago: Chatterjee, Krishnendu, Hongfei Fu, Amir Kafshdar Goharshady, and Ehsan
Kafshdar Goharshady. “Polynomial Invariant Generation for Non-Deterministic Recursive
Programs.” In Proceedings of the 41st ACM SIGPLAN Conference on Programming
Language Design and Implementation, 672–87. Association for Computing Machinery,
2020. https://doi.org/10.1145/3385412.3385969.
ieee: K. Chatterjee, H. Fu, A. K. Goharshady, and E. K. Goharshady, “Polynomial
invariant generation for non-deterministic recursive programs,” in Proceedings
of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation,
London, United Kingdom, 2020, pp. 672–687.
ista: 'Chatterjee K, Fu H, Goharshady AK, Goharshady EK. 2020. Polynomial invariant
generation for non-deterministic recursive programs. Proceedings of the 41st ACM
SIGPLAN Conference on Programming Language Design and Implementation. PLDI: Programming
Language Design and Implementation, 672–687.'
mla: Chatterjee, Krishnendu, et al. “Polynomial Invariant Generation for Non-Deterministic
Recursive Programs.” Proceedings of the 41st ACM SIGPLAN Conference on Programming
Language Design and Implementation, Association for Computing Machinery, 2020,
pp. 672–87, doi:10.1145/3385412.3385969.
short: K. Chatterjee, H. Fu, A.K. Goharshady, E.K. Goharshady, in:, Proceedings
of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation,
Association for Computing Machinery, 2020, pp. 672–687.
conference:
end_date: 2020-06-20
location: London, United Kingdom
name: 'PLDI: Programming Language Design and Implementation'
start_date: 2020-06-15
date_created: 2020-07-05T22:00:45Z
date_published: 2020-06-11T00:00:00Z
date_updated: 2026-07-03T22:35:28Z
day: '11'
department:
- _id: KrCh
doi: 10.1145/3385412.3385969
external_id:
arxiv:
- '1902.04373'
isi:
- '000614622300045'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1902.04373
month: '06'
oa: 1
oa_version: Preprint
page: 672-687
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
publication: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language
Design and Implementation
publication_identifier:
isbn:
- '9781450376136'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '8934'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Polynomial invariant generation for non-deterministic recursive programs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...
---
_id: '7810'
abstract:
- lang: eng
text: "Interprocedural data-flow analyses form an expressive and useful paradigm
of numerous static analysis applications, such as live variables analysis, alias
analysis and null pointers analysis. The most widely-used framework for interprocedural
data-flow analysis is IFDS, which encompasses distributive data-flow functions
over a finite domain. On-demand data-flow analyses restrict the focus of the analysis
on specific program locations and data facts. This setting provides a natural
split between (i) an offline (or preprocessing) phase, where the program is partially
analyzed and analysis summaries are created, and (ii) an online (or query) phase,
where analysis queries arrive on demand and the summaries are used to speed up
answering queries.\r\nIn this work, we consider on-demand IFDS analyses where
the queries concern program locations of the same procedure (aka same-context
queries). We exploit the fact that flow graphs of programs have low treewidth
to develop faster algorithms that are space and time optimal for many common data-flow
analyses, in both the preprocessing and the query phase. We also use treewidth
to develop query solutions that are embarrassingly parallelizable, i.e. the total
work for answering each query is split to a number of threads such that each thread
performs only a constant amount of work. Finally, we implement a static analyzer
based on our algorithms, and perform a series of on-demand analysis experiments
on standard benchmarks. Our experimental results show a drastic speed-up of the
queries after only a lightweight preprocessing phase, which significantly outperforms
existing techniques."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: 'Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. Optimal and perfectly
parallel algorithms for on-demand data-flow analysis. In: European Symposium
on Programming. Vol 12075. Springer Nature; 2020:112-140. doi:10.1007/978-3-030-44914-8_5'
apa: 'Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Pavlogiannis, A.
(2020). Optimal and perfectly parallel algorithms for on-demand data-flow analysis.
In European Symposium on Programming (Vol. 12075, pp. 112–140). Dublin,
Ireland: Springer Nature. https://doi.org/10.1007/978-3-030-44914-8_5'
chicago: Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen,
and Andreas Pavlogiannis. “Optimal and Perfectly Parallel Algorithms for On-Demand
Data-Flow Analysis.” In European Symposium on Programming, 12075:112–40.
Springer Nature, 2020. https://doi.org/10.1007/978-3-030-44914-8_5.
ieee: K. Chatterjee, A. K. Goharshady, R. Ibsen-Jensen, and A. Pavlogiannis, “Optimal
and perfectly parallel algorithms for on-demand data-flow analysis,” in European
Symposium on Programming, Dublin, Ireland, 2020, vol. 12075, pp. 112–140.
ista: 'Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. 2020. Optimal
and perfectly parallel algorithms for on-demand data-flow analysis. European Symposium
on Programming. ESOP: Programming Languages and Systems, LNCS, vol. 12075, 112–140.'
mla: Chatterjee, Krishnendu, et al. “Optimal and Perfectly Parallel Algorithms for
On-Demand Data-Flow Analysis.” European Symposium on Programming, vol.
12075, Springer Nature, 2020, pp. 112–40, doi:10.1007/978-3-030-44914-8_5.
short: K. Chatterjee, A.K. Goharshady, R. Ibsen-Jensen, A. Pavlogiannis, in:, European
Symposium on Programming, Springer Nature, 2020, pp. 112–140.
conference:
end_date: 2020-04-30
location: Dublin, Ireland
name: 'ESOP: Programming Languages and Systems'
start_date: 2020-04-25
corr_author: '1'
date_created: 2020-05-10T22:00:50Z
date_published: 2020-04-18T00:00:00Z
date_updated: 2026-07-03T22:35:31Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-030-44914-8_5
external_id:
isi:
- '000681656800005'
file:
- access_level: open_access
checksum: 8618b80f4cf7b39a60e61a6445ad9807
content_type: application/pdf
creator: dernst
date_created: 2020-05-26T13:34:48Z
date_updated: 2020-07-14T12:48:03Z
file_id: '7895'
file_name: 2020_LNCS_Chatterjee.pdf
file_size: 651250
relation: main_file
file_date_updated: 2020-07-14T12:48:03Z
has_accepted_license: '1'
intvolume: ' 12075'
isi: 1
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 112-140
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 266EEEC0-B435-11E9-9278-68D0E5697425
name: Quantitative Game-theoretic Analysis of Blockchain Applications and Smart
Contracts
- _id: 267066CE-B435-11E9-9278-68D0E5697425
name: Quantitative Analysis of Probabilistic Systems with a focus on Crypto-Currencies
publication: European Symposium on Programming
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030449131'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '8934'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Optimal and perfectly parallel algorithms for on-demand data-flow analysis
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: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12075
year: '2020'
...
---
_id: '6918'
abstract:
- lang: eng
text: "We consider the classic problem of Network Reliability. A network is given
together with a source vertex, one or more target vertices, and probabilities
assigned to each of the edges. Each edge of the network is operable with its associated
probability and the problem is to determine the probability of having at least
one source-to-target path that is entirely composed of operable edges. This problem
is known to be NP-hard.\r\n\r\nWe provide a novel scalable algorithm to solve
the Network Reliability problem when the treewidth of the underlying network is
small. We also show our algorithm’s applicability for real-world transit networks
that have small treewidth, including the metro networks of major cities, such
as London and Tokyo. Our algorithm leverages tree decompositions to shrink the
original graph into much smaller graphs, for which reliability can be efficiently
and exactly computed using a brute force method. To the best of our knowledge,
this is the first exact algorithm for Network Reliability that can scale to handle
real-world instances of the problem."
acknowledgement: We are grateful to the anonymous reviewers for their comments, which
significantly improved the present work. The research was partially supported by
the EPSRC Early Career Fellowship EP/R023379/1, grant no. SC7-1718-01 of the London
Mathematical Society, an IBM PhD Fellowship, and a DOC Fellowship of the Austrian
Academy of Sciences (ÖAW).
article_number: '106665'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Fatemeh
full_name: Mohammadi, Fatemeh
last_name: Mohammadi
citation:
ama: Goharshady AK, Mohammadi F. An efficient algorithm for computing network reliability
in small treewidth. Reliability Engineering and System Safety. 2020;193.
doi:10.1016/j.ress.2019.106665
apa: Goharshady, A. K., & Mohammadi, F. (2020). An efficient algorithm for computing
network reliability in small treewidth. Reliability Engineering and System
Safety. Elsevier. https://doi.org/10.1016/j.ress.2019.106665
chicago: Goharshady, Amir Kafshdar, and Fatemeh Mohammadi. “An Efficient Algorithm
for Computing Network Reliability in Small Treewidth.” Reliability Engineering
and System Safety. Elsevier, 2020. https://doi.org/10.1016/j.ress.2019.106665.
ieee: A. K. Goharshady and F. Mohammadi, “An efficient algorithm for computing network
reliability in small treewidth,” Reliability Engineering and System Safety,
vol. 193. Elsevier, 2020.
ista: Goharshady AK, Mohammadi F. 2020. An efficient algorithm for computing network
reliability in small treewidth. Reliability Engineering and System Safety. 193,
106665.
mla: Goharshady, Amir Kafshdar, and Fatemeh Mohammadi. “An Efficient Algorithm for
Computing Network Reliability in Small Treewidth.” Reliability Engineering
and System Safety, vol. 193, 106665, Elsevier, 2020, doi:10.1016/j.ress.2019.106665.
short: A.K. Goharshady, F. Mohammadi, Reliability Engineering and System Safety
193 (2020).
date_created: 2019-09-29T22:00:44Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2026-07-03T22:35:31Z
day: '01'
department:
- _id: KrCh
doi: 10.1016/j.ress.2019.106665
external_id:
arxiv:
- '1712.09692'
isi:
- '000501641400050'
intvolume: ' 193'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1712.09692
month: '01'
oa: 1
oa_version: Preprint
project:
- _id: 266EEEC0-B435-11E9-9278-68D0E5697425
name: Quantitative Game-theoretic Analysis of Blockchain Applications and Smart
Contracts
publication: Reliability Engineering and System Safety
publication_identifier:
issn:
- 0951-8320
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '8934'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: An efficient algorithm for computing network reliability in small treewidth
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 193
year: '2020'
...
---
OA_place: repository
OA_type: green
_id: '5948'
abstract:
- lang: eng
text: We study the termination problem for nondeterministic probabilistic programs.
We consider the bounded termination problem that asks whether the supremum of
the expected termination time over all schedulers is bounded. First, we show that
ranking supermartingales (RSMs) are both sound and complete for proving bounded
termination over nondeterministic probabilistic programs. For nondeterministic
probabilistic programs a previous result claimed that RSMs are not complete for
bounded termination, whereas our result corrects the previous flaw and establishes
completeness with a rigorous proof. Second, we present the first sound approach
to establish lower bounds on expected termination time through RSMs.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Hongfei
full_name: Fu, Hongfei
last_name: Fu
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: 'Fu H, Chatterjee K. Termination of nondeterministic probabilistic programs.
In: International Conference on Verification, Model Checking, and Abstract
Interpretation. Vol 11388. Springer Nature; 2019:468-490. doi:10.1007/978-3-030-11245-5_22'
apa: 'Fu, H., & Chatterjee, K. (2019). Termination of nondeterministic probabilistic
programs. In International Conference on Verification, Model Checking, and
Abstract Interpretation (Vol. 11388, pp. 468–490). Cascais, Portugal: Springer
Nature. https://doi.org/10.1007/978-3-030-11245-5_22'
chicago: Fu, Hongfei, and Krishnendu Chatterjee. “Termination of Nondeterministic
Probabilistic Programs.” In International Conference on Verification, Model
Checking, and Abstract Interpretation, 11388:468–90. Springer Nature, 2019.
https://doi.org/10.1007/978-3-030-11245-5_22.
ieee: H. Fu and K. Chatterjee, “Termination of nondeterministic probabilistic programs,”
in International Conference on Verification, Model Checking, and Abstract Interpretation,
Cascais, Portugal, 2019, vol. 11388, pp. 468–490.
ista: 'Fu H, Chatterjee K. 2019. Termination of nondeterministic probabilistic programs.
International Conference on Verification, Model Checking, and Abstract Interpretation.
VMCAI: Verification, Model Checking, and Abstract Interpretation, LNCS, vol. 11388,
468–490.'
mla: Fu, Hongfei, and Krishnendu Chatterjee. “Termination of Nondeterministic Probabilistic
Programs.” International Conference on Verification, Model Checking, and Abstract
Interpretation, vol. 11388, Springer Nature, 2019, pp. 468–90, doi:10.1007/978-3-030-11245-5_22.
short: H. Fu, K. Chatterjee, in:, International Conference on Verification, Model
Checking, and Abstract Interpretation, Springer Nature, 2019, pp. 468–490.
conference:
end_date: 2019-01-15
location: Cascais, Portugal
name: 'VMCAI: Verification, Model Checking, and Abstract Interpretation'
start_date: 2019-01-13
date_created: 2019-02-10T22:59:17Z
date_published: 2019-01-11T00:00:00Z
date_updated: 2025-07-03T11:45:45Z
day: '11'
department:
- _id: KrCh
doi: 10.1007/978-3-030-11245-5_22
external_id:
arxiv:
- '1701.02944'
isi:
- '000931943000022'
intvolume: ' 11388'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1701.02944
month: '01'
oa: 1
oa_version: Preprint
page: 468-490
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: International Conference on Verification, Model Checking, and Abstract
Interpretation
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Termination of nondeterministic probabilistic programs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11388
year: '2019'
...
---
OA_place: publisher
OA_type: hybrid
_id: '10190'
abstract:
- lang: eng
text: 'The verification of concurrent programs remains an open challenge, as thread
interaction has to be accounted for, which leads to state-space explosion. Stateless
model checking battles this problem by exploring traces rather than states of
the program. As there are exponentially many traces, dynamic partial-order reduction
(DPOR) techniques are used to partition the trace space into equivalence classes,
and explore a few representatives from each class. The standard equivalence that
underlies most DPOR techniques is the happens-before equivalence, however recent
works have spawned a vivid interest towards coarser equivalences. The efficiency
of such approaches is a product of two parameters: (i) the size of the partitioning
induced by the equivalence, and (ii) the time spent by the exploration algorithm
in each class of the partitioning. In this work, we present a new equivalence,
called value-happens-before and show that it has two appealing features. First,
value-happens-before is always at least as coarse as the happens-before equivalence,
and can be even exponentially coarser. Second, the value-happens-before partitioning
is efficiently explorable when the number of threads is bounded. We present an
algorithm called value-centric DPOR (VCDPOR), which explores the underlying partitioning
using polynomial time per class. Finally, we perform an experimental evaluation
of VCDPOR on various benchmarks, and compare it against other state-of-the-art
approaches. Our results show that value-happens-before typically induces a significant
reduction in the size of the underlying partitioning, which leads to a considerable
reduction in the running time for exploring the whole partitioning.'
acknowledgement: "The authors would also like to thank anonymous referees for their
valuable comments and helpful suggestions. This work is supported by the Austrian
Science Fund (FWF) NFN grants S11407-N23 (RiSE/SHiNE) and S11402-N23 (RiSE/SHiNE),
by the Vienna Science and Technology Fund (WWTF) Project ICT15-003, and by the Austrian
Science Fund (FWF) Schrodinger grant J-4220.\r\n"
article_number: '124'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Viktor
full_name: Toman, Viktor
id: 3AF3DA7C-F248-11E8-B48F-1D18A9856A87
last_name: Toman
orcid: 0000-0001-9036-063X
citation:
ama: 'Chatterjee K, Pavlogiannis A, Toman V. Value-centric dynamic partial order
reduction. In: Proceedings of the 34th ACM International Conference on Object-Oriented
Programming, Systems, Languages, and Applications. Vol 3. ACM; 2019. doi:10.1145/3360550'
apa: 'Chatterjee, K., Pavlogiannis, A., & Toman, V. (2019). Value-centric dynamic
partial order reduction. In Proceedings of the 34th ACM International Conference
on Object-Oriented Programming, Systems, Languages, and Applications (Vol.
3). Athens, Greece: ACM. https://doi.org/10.1145/3360550'
chicago: Chatterjee, Krishnendu, Andreas Pavlogiannis, and Viktor Toman. “Value-Centric
Dynamic Partial Order Reduction.” In Proceedings of the 34th ACM International
Conference on Object-Oriented Programming, Systems, Languages, and Applications,
Vol. 3. ACM, 2019. https://doi.org/10.1145/3360550.
ieee: K. Chatterjee, A. Pavlogiannis, and V. Toman, “Value-centric dynamic partial
order reduction,” in Proceedings of the 34th ACM International Conference on
Object-Oriented Programming, Systems, Languages, and Applications, Athens,
Greece, 2019, vol. 3.
ista: 'Chatterjee K, Pavlogiannis A, Toman V. 2019. Value-centric dynamic partial
order reduction. Proceedings of the 34th ACM International Conference on Object-Oriented
Programming, Systems, Languages, and Applications. OOPSLA: Object-oriented Programming,
Systems, Languages and Applications vol. 3, 124.'
mla: Chatterjee, Krishnendu, et al. “Value-Centric Dynamic Partial Order Reduction.”
Proceedings of the 34th ACM International Conference on Object-Oriented Programming,
Systems, Languages, and Applications, vol. 3, 124, ACM, 2019, doi:10.1145/3360550.
short: K. Chatterjee, A. Pavlogiannis, V. Toman, in:, Proceedings of the 34th ACM
International Conference on Object-Oriented Programming, Systems, Languages, and
Applications, ACM, 2019.
conference:
end_date: 2019-10-25
location: Athens, Greece
name: 'OOPSLA: Object-oriented Programming, Systems, Languages and Applications'
start_date: 2019-10-23
corr_author: '1'
date_created: 2021-10-27T14:57:06Z
date_published: 2019-10-10T00:00:00Z
date_updated: 2026-04-08T07:00:31Z
day: '10'
ddc:
- '000'
department:
- _id: GradSch
- _id: KrCh
doi: 10.1145/3360550
external_id:
arxiv:
- '1909.00989'
file:
- access_level: open_access
checksum: 2149979c46964c4d117af06ccb6c0834
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T11:41:56Z
date_updated: 2021-11-12T11:41:56Z
file_id: '10278'
file_name: 2019_ACM_Chatterjee.pdf
file_size: 570829
relation: main_file
success: 1
file_date_updated: 2021-11-12T11:41:56Z
has_accepted_license: '1'
intvolume: ' 3'
keyword:
- safety
- risk
- reliability and quality
- software
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: Proceedings of the 34th ACM International Conference on Object-Oriented
Programming, Systems, Languages, and Applications
publication_identifier:
eissn:
- 2475-1421
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
record:
- id: '10199'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Value-centric dynamic partial order reduction
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3
year: '2019'
...
---
_id: '7950'
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."
article_number: '1903.06981'
article_processing_charge: No
arxiv: 1
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. arXiv. doi:10.48550/arXiv.1903.06981
apa: Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte,
A. (n.d.). Token swapping on trees. arXiv. https://doi.org/10.48550/arXiv.1903.06981
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. https://doi.org/10.48550/arXiv.1903.06981.
ieee: A. Biniaz et al., “Token swapping on trees,” arXiv. .
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,
doi:10.48550/arXiv.1903.06981.
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_created: 2020-06-08T12:25:25Z
date_published: 2019-03-16T00:00:00Z
date_updated: 2026-04-08T07:23:00Z
day: '16'
department:
- _id: HeEd
- _id: UlWa
- _id: KrCh
doi: 10.48550/arXiv.1903.06981
external_id:
arxiv:
- '1903.06981'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1903.06981
month: '03'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: draft
related_material:
record:
- id: '12833'
relation: later_version
status: public
- id: '7944'
relation: dissertation_contains
status: public
status: public
title: Token swapping on trees
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6462'
abstract:
- lang: eng
text: A controller is a device that interacts with a plant. At each time point,it
reads the plant’s state and issues commands with the goal that the plant oper-ates
optimally. Constructing optimal controllers is a fundamental and challengingproblem.
Machine learning techniques have recently been successfully applied totrain controllers,
yet they have limitations. Learned controllers are monolithic andhard to reason
about. In particular, it is difficult to add features without retraining,to guarantee
any level of performance, and to achieve acceptable performancewhen encountering
untrained scenarios. These limitations can be addressed bydeploying quantitative
run-timeshieldsthat serve as a proxy for the controller.At each time point, the
shield reads the command issued by the controller andmay choose to alter it before
passing it on to the plant. We show how optimalshields that interfere as little
as possible while guaranteeing a desired level ofcontroller performance, can be
generated systematically and automatically usingreactive synthesis. First, we abstract the plant by building a stochastic model.Second,
we consider the learned controller to be a black box. Third, we mea-surecontroller
performanceandshield interferenceby two quantitative run-timemeasures that are
formally defined using weighted automata. Then, the problemof constructing a shield
that guarantees maximal performance with minimal inter-ference is the problem
of finding an optimal strategy in a stochastic2-player game“controller versus
shield” played on the abstract state space of the plant with aquantitative objective
obtained from combining the performance and interferencemeasures. We illustrate
the effectiveness of our approach by automatically con-structing lightweight shields
for learned traffic-light controllers in various roadnetworks. The shields we
generate avoid liveness bugs, improve controller per-formance in untrained and
changing traffic situations, and add features to learnedcontrollers, such as giving
priority to emergency vehicles.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- first_name: Roderick
full_name: Bloem, Roderick
last_name: Bloem
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Bettina
full_name: Konighofer, Bettina
last_name: Konighofer
- first_name: Stefan
full_name: Pranger, Stefan
last_name: Pranger
citation:
ama: 'Avni G, Bloem R, Chatterjee K, Henzinger TA, Konighofer B, Pranger S. Run-time
optimization for learned controllers through quantitative games. In: 31st International
Conference on Computer-Aided Verification. Vol 11561. Springer; 2019:630-649.
doi:10.1007/978-3-030-25540-4_36'
apa: 'Avni, G., Bloem, R., Chatterjee, K., Henzinger, T. A., Konighofer, B., &
Pranger, S. (2019). Run-time optimization for learned controllers through quantitative
games. In 31st International Conference on Computer-Aided Verification
(Vol. 11561, pp. 630–649). New York, NY, United States: Springer. https://doi.org/10.1007/978-3-030-25540-4_36'
chicago: Avni, Guy, Roderick Bloem, Krishnendu Chatterjee, Thomas A Henzinger, Bettina
Konighofer, and Stefan Pranger. “Run-Time Optimization for Learned Controllers
through Quantitative Games.” In 31st International Conference on Computer-Aided
Verification, 11561:630–49. Springer, 2019. https://doi.org/10.1007/978-3-030-25540-4_36.
ieee: G. Avni, R. Bloem, K. Chatterjee, T. A. Henzinger, B. Konighofer, and S. Pranger,
“Run-time optimization for learned controllers through quantitative games,” in
31st International Conference on Computer-Aided Verification, New York,
NY, United States, 2019, vol. 11561, pp. 630–649.
ista: 'Avni G, Bloem R, Chatterjee K, Henzinger TA, Konighofer B, Pranger S. 2019.
Run-time optimization for learned controllers through quantitative games. 31st
International Conference on Computer-Aided Verification. CAV: Computer Aided Verification,
LNCS, vol. 11561, 630–649.'
mla: Avni, Guy, et al. “Run-Time Optimization for Learned Controllers through Quantitative
Games.” 31st International Conference on Computer-Aided Verification, vol.
11561, Springer, 2019, pp. 630–49, doi:10.1007/978-3-030-25540-4_36.
short: G. Avni, R. Bloem, K. Chatterjee, T.A. Henzinger, B. Konighofer, S. Pranger,
in:, 31st International Conference on Computer-Aided Verification, Springer, 2019,
pp. 630–649.
conference:
end_date: 2019-07-18
location: New York, NY, United States
name: 'CAV: Computer Aided Verification'
start_date: 2019-07-13
corr_author: '1'
date_created: 2019-05-16T11:22:30Z
date_published: 2019-07-12T00:00:00Z
date_updated: 2025-04-15T06:26:05Z
day: '12'
ddc:
- '000'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1007/978-3-030-25540-4_36
external_id:
isi:
- '000491468000036'
file:
- access_level: open_access
checksum: c231579f2485c6fd4df17c9443a4d80b
content_type: application/pdf
creator: dernst
date_created: 2019-08-14T09:35:24Z
date_updated: 2020-07-14T12:47:31Z
file_id: '6816'
file_name: 2019_CAV_Avni.pdf
file_size: 659766
relation: main_file
file_date_updated: 2020-07-14T12:47:31Z
has_accepted_license: '1'
intvolume: ' 11561'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 630-649
project:
- _id: 264B3912-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02369
name: Formal Methods meets Algorithmic Game Theory
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: 31st International Conference on Computer-Aided Verification
publication_identifier:
isbn:
- '9783030255398'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Run-time optimization for learned controllers through quantitative 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: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 11561
year: '2019'
...
---
_id: '6836'
abstract:
- lang: eng
text: Direct reciprocity is a powerful mechanism for the evolution of cooperation
on the basis of repeated interactions1,2,3,4. It requires that interacting individuals
are sufficiently equal, such that everyone faces similar consequences when they
cooperate or defect. Yet inequality is ubiquitous among humans5,6 and is generally
considered to undermine cooperation and welfare7,8,9,10. Most previous models
of reciprocity do not include inequality11,12,13,14,15. These models assume that
individuals are the same in all relevant aspects. Here we introduce a general
framework to study direct reciprocity among unequal individuals. Our model allows
for multiple sources of inequality. Subjects can differ in their endowments, their
productivities and in how much they benefit from public goods. We find that extreme
inequality prevents cooperation. But if subjects differ in productivity, some
endowment inequality can be necessary for cooperation to prevail. Our mathematical
predictions are supported by a behavioural experiment in which we vary the endowments
and productivities of the subjects. We observe that overall welfare is maximized
when the two sources of heterogeneity are aligned, such that more productive individuals
receive higher endowments. By contrast, when endowments and productivities are
misaligned, cooperation quickly breaks down. Our findings have implications for
policy-makers concerned with equity, efficiency and the provisioning of public
goods.
article_processing_charge: No
article_type: letter_note
author:
- first_name: Oliver P.
full_name: Hauser, Oliver P.
last_name: Hauser
- first_name: Christian
full_name: Hilbe, Christian
id: 2FDF8F3C-F248-11E8-B48F-1D18A9856A87
last_name: Hilbe
orcid: 0000-0001-5116-955X
- 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: Hauser OP, Hilbe C, Chatterjee K, Nowak MA. Social dilemmas among unequals.
Nature. 2019;572(7770):524-527. doi:10.1038/s41586-019-1488-5
apa: Hauser, O. P., Hilbe, C., Chatterjee, K., & Nowak, M. A. (2019). Social
dilemmas among unequals. Nature. Springer Nature. https://doi.org/10.1038/s41586-019-1488-5
chicago: Hauser, Oliver P., Christian Hilbe, Krishnendu Chatterjee, and Martin A.
Nowak. “Social Dilemmas among Unequals.” Nature. Springer Nature, 2019.
https://doi.org/10.1038/s41586-019-1488-5.
ieee: O. P. Hauser, C. Hilbe, K. Chatterjee, and M. A. Nowak, “Social dilemmas among
unequals,” Nature, vol. 572, no. 7770. Springer Nature, pp. 524–527, 2019.
ista: Hauser OP, Hilbe C, Chatterjee K, Nowak MA. 2019. Social dilemmas among unequals.
Nature. 572(7770), 524–527.
mla: Hauser, Oliver P., et al. “Social Dilemmas among Unequals.” Nature,
vol. 572, no. 7770, Springer Nature, 2019, pp. 524–27, doi:10.1038/s41586-019-1488-5.
short: O.P. Hauser, C. Hilbe, K. Chatterjee, M.A. Nowak, Nature 572 (2019) 524–527.
date_created: 2019-09-01T22:00:56Z
date_published: 2019-08-22T00:00:00Z
date_updated: 2025-07-10T11:53:55Z
day: '22'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1038/s41586-019-1488-5
ec_funded: 1
external_id:
isi:
- '000482219600045'
file:
- access_level: open_access
checksum: a6e0e3168bf62de624e7772cdfaeb26f
content_type: application/pdf
creator: dernst
date_created: 2020-05-14T10:00:32Z
date_updated: 2020-07-14T12:47:42Z
file_id: '7828'
file_name: 2019_Nature_Hauser.pdf
file_size: 18577756
relation: main_file
file_date_updated: 2020-07-14T12:47:42Z
has_accepted_license: '1'
intvolume: ' 572'
isi: 1
issue: '7770'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 524-527
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Nature
publication_identifier:
eissn:
- 1476-4687
issn:
- 0028-0836
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
link:
- description: News on IST Homepage
relation: press_release
url: https://ist.ac.at/en/news/too-much-inequality-impedes-support-for-public-goods-according-to-research-published-in-nature/
scopus_import: '1'
status: public
title: Social dilemmas among unequals
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 572
year: '2019'
...
---
_id: '6884'
abstract:
- lang: eng
text: 'In two-player games on graphs, the players move a token through a graph to
produce a finite or infinite path, which determines the qualitative winner or
quantitative payoff of the game. We study bidding games in which the players bid
for the right to move the token. Several bidding rules were studied previously.
In Richman bidding, in each round, the players simultaneously submit bids, and
the higher bidder moves the token and pays the other player. Poorman bidding is
similar except that the winner of the bidding pays the "bank" rather than the
other player. Taxman bidding spans the spectrum between Richman and poorman bidding.
They are parameterized by a constant tau in [0,1]: portion tau of the winning
bid is paid to the other player, and portion 1-tau to the bank. While finite-duration
(reachability) taxman games have been studied before, we present, for the first
time, results on infinite-duration taxman games. It was previously shown that
both Richman and poorman infinite-duration games with qualitative objectives reduce
to reachability games, and we show a similar result here. Our most interesting
results concern quantitative taxman games, namely mean-payoff games, where poorman
and Richman bidding differ significantly. A central quantity in these games is
the ratio between the two players'' initial budgets. While in poorman mean-payoff
games, the optimal payoff of a player depends on the initial ratio, in Richman
bidding, the payoff depends only on the structure of the game. In both games the
optimal payoffs can be found using (different) probabilistic connections with
random-turn games in which in each turn, instead of bidding, a coin is tossed
to determine which player moves. While the value with Richman bidding equals the
value of a random-turn game with an un-biased coin, with poorman bidding, the
bias in the coin is the initial ratio of the budgets. We give a complete classification
of mean-payoff taxman games that is based on a probabilistic connection: the value
of a taxman bidding game with parameter tau and initial ratio r, equals the value
of a random-turn game that uses a coin with bias F(tau, r) = (r+tau * (1-r))/(1+tau).
Thus, we show that Richman bidding is the exception; namely, for every tau <1,
the value of the game depends on the initial ratio. Our proof technique simplifies
and unifies the previous proof techniques for both Richman and poorman bidding. '
alternative_title:
- LIPIcs
article_number: '11'
article_processing_charge: No
arxiv: 1
author:
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Dorde
full_name: Zikelic, Dorde
id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
last_name: Zikelic
orcid: 0000-0002-4681-1699
citation:
ama: 'Avni G, Henzinger TA, Zikelic D. Bidding mechanisms in graph games. In: Vol
138. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.MFCS.2019.11'
apa: 'Avni, G., Henzinger, T. A., & Zikelic, D. (2019). Bidding mechanisms in
graph games (Vol. 138). Presented at the MFCS: Mathematical Foundations of Computer
Science, Aachen, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.MFCS.2019.11'
chicago: Avni, Guy, Thomas A Henzinger, and Dorde Zikelic. “Bidding Mechanisms in
Graph Games,” Vol. 138. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
https://doi.org/10.4230/LIPICS.MFCS.2019.11.
ieee: 'G. Avni, T. A. Henzinger, and D. Zikelic, “Bidding mechanisms in graph games,”
presented at the MFCS: Mathematical Foundations of Computer Science, Aachen, Germany,
2019, vol. 138.'
ista: 'Avni G, Henzinger TA, Zikelic D. 2019. Bidding mechanisms in graph games.
MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 138, 11.'
mla: Avni, Guy, et al. Bidding Mechanisms in Graph Games. Vol. 138, 11, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.MFCS.2019.11.
short: G. Avni, T.A. Henzinger, D. Zikelic, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019.
conference:
end_date: 2019-08-30
location: Aachen, Germany
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2019-08-26
corr_author: '1'
date_created: 2019-09-18T08:04:26Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2025-07-10T11:53:57Z
day: '01'
ddc:
- '004'
department:
- _id: ToHe
- _id: KrCh
doi: 10.4230/LIPICS.MFCS.2019.11
ec_funded: 1
external_id:
arxiv:
- '1905.03835'
file:
- access_level: open_access
checksum: 6346e116a4f4ed1414174d96d2c4fbd7
content_type: application/pdf
creator: kschuh
date_created: 2019-09-27T11:45:15Z
date_updated: 2020-07-14T12:47:42Z
file_id: '6913'
file_name: 2019_LIPIcs_Avni.pdf
file_size: 554457
relation: main_file
file_date_updated: 2020-07-14T12:47:42Z
has_accepted_license: '1'
intvolume: ' 138'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 264B3912-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02369
name: Formal Methods meets Algorithmic Game Theory
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Rigorous Systems Engineering
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '9239'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Bidding mechanisms in graph 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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 138
year: '2019'
...