Game Theory

Project Period: 2015-03-01 – 2019-08-31
Externally Funded
Acronym
SHINE
Principal Investigator
Krishnendu Chatterjee
Department(s)
Chatterjee Group
Grant Number
S11407
Funding Organisation
FWF

70 Publications

2013 | Conference Paper | IST-REx-ID: 1374   OA
Infinite-state games with finitary conditions
K. Chatterjee, N. Fijalkow, in:, 22nd EACSL Annual Conference on Computer Science Logic, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–196.
View | Files available | DOI
 
2015 | Conference Paper | IST-REx-ID: 1689   OA
Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 259–268.
View | Files available | DOI | Download (ext.)
 
2013 | Journal Article | IST-REx-ID: 2858   OA
The effect of one additional driver mutation on tumor progression
J. Reiter, I. Božić, B. Allen, K. Chatterjee, M. Nowak, Evolutionary Applications 6 (2013) 34–45.
View | Files available | DOI
 
2017 | Journal Article | IST-REx-ID: 464   OA
Improved algorithms for parity and Streett objectives
K. Chatterjee, M. Henzinger, V. Loitzenbauer, Logical Methods in Computer Science 13 (2017).
View | Files available | DOI
 
2013 | Conference Paper | IST-REx-ID: 2295 View | Files available | DOI
 
2014 | Conference Paper | IST-REx-ID: 2163
Games with a weak adversary
K. Chatterjee, L. Doyen, in:, Lecture Notes in Computer Science, Springer, 2014, pp. 110–121.
View | Files available | DOI | Download (ext.) | arXiv
 
2017 | Conference Paper | IST-REx-ID: 628   OA
Automated recurrence analysis for almost linear expected runtime bounds
K. Chatterjee, H. Fu, A. Murhekar, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 118–139.
View | DOI | Download (ext.)
 
2017 | Journal Article | IST-REx-ID: 717   OA
Hyperplane separation technique for multidimensional mean-payoff games
K. Chatterjee, Y. Velner, Journal of Computer and System Sciences 88 (2017) 236–259.
View | Files available | DOI | Download (ext.)
 
2015 | Conference Paper | IST-REx-ID: 1610
Edit distance for pushdown automata
K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, 9135 (2015) 121–133.
View | Files available | DOI
 
2013 | Conference Paper | IST-REx-ID: 2446   OA
Automata with generalized Rabin pairs for probabilistic model checking and LTL synthesis
K. Chatterjee, A. Gaiser, J. Kretinsky, 8044 (2013) 559–575.
View | DOI | Download (ext.) | arXiv
 
2013 | Journal Article | IST-REx-ID: 2814   OA
The complexity of coverage
K. Chatterjee, L. Alfaro, R. Majumdar, International Journal of Foundations of Computer Science 24 (2013) 165–185.
View | DOI | Download (ext.) | arXiv
 
2014 | Conference Paper | IST-REx-ID: 2054
Qualitative concurrent parity games: Bounded rationality
K. Chatterjee, in:, P. Baldan, D. Gorla (Eds.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 544–559.
View | Files available | DOI
 
2014 | Conference Paper | IST-REx-ID: 475   OA
First cycle games
B. Aminof, S. Rubin, in:, Electronic Proceedings in Theoretical Computer Science, EPTCS, Open Publishing Association, 2014, pp. 83–90.
View | Files available | DOI
 
2014 | Conference Paper | IST-REx-ID: 2213
The complexity of partial-observation stochastic parity games with finite-memory strategies
K. Chatterjee, L. Doyen, S. Nain, M. Vardi, in:, Springer, 2014, pp. 242–257.
View | Files available | DOI | Download (ext.) | arXiv
 
2014 | Conference Paper | IST-REx-ID: 2162
The complexity of ergodic mean payoff games
K. Chatterjee, R. Ibsen-Jensen, in:, Springer, 2014, pp. 122–133.
View | Files available | DOI | Download (ext.) | arXiv
 
2017 | Conference Paper | IST-REx-ID: 552   OA
Faster algorithms for mean payoff parity games
K. Chatterjee, M. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
View | Files available | DOI
 
2017 | Conference Paper | IST-REx-ID: 639   OA
Non-polynomial worst case analysis of recursive programs
K. Chatterjee, H. Fu, A. Goharshady, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 41–63.
View | DOI | Download (ext.)
 
2017 | Journal Article | IST-REx-ID: 653
Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer
A. Makohon Moore, M. Zhang, J. Reiter, I. Božić, B. Allen, D. Kundu, K. Chatterjee, F. Wong, Y. Jiao, Z. Kohutek, J. Hong, M. Attiyeh, B. Javier, L. Wood, R. Hruban, M. Nowak, N. Papadopoulos, K. Kinzler, B. Vogelstein, C. Iacobuzio Donahue, Nature Genetics 49 (2017) 358–366.
View | DOI
 
2017 | Journal Article | IST-REx-ID: 716
The complexity of mean-payoff pushdown games
K. Chatterjee, Y. Velner, Journal of the ACM 64 (2017) 34.
View | DOI
 
2017 | Conference Paper | IST-REx-ID: 949   OA
JTDec: A tool for tree decompositions in soot
K. Chatterjee, A. Goharshady, A. Pavlogiannis, in:, D. D’Souza (Ed.), Springer, 2017, pp. 59–66.
View | Files available | DOI
 
2018 | Journal Article | IST-REx-ID: 157
Evolution of cooperation in stochastic games
C. Hilbe, Š. Šimsa, K. Chatterjee, M. Nowak, Nature 559 (2018) 246–249.
View | Files available | DOI
 
2015 | Journal Article | IST-REx-ID: 2034   OA
Probabilistic opacity for Markov decision processes
B. Bérard, K. Chatterjee, N. Sznajder, Information Processing Letters 115 (2015) 52–59.
View | DOI | Download (ext.)
 
2014 | Conference Paper | IST-REx-ID: 2027   OA
Verification of markov decision processes using learning algorithms
T. Brázdil, K. Chatterjee, M. Chmelik, V. Forejt, J. Kretinsky, M. Kwiatkowska, D. Parker, M. Ujma, in:, F. Cassez, J.-F. Raskin (Eds.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Society of Industrial and Applied Mathematics, 2014, pp. 98–114.
View | DOI | Download (ext.)
 
2015 | Journal Article | IST-REx-ID: 1598
Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives
K. Chatterjee, M. Joglekar, N. Shah, Theoretical Computer Science 573 (2015) 71–89.
View | Files available | DOI | Download (ext.)
 
2014 | Journal Article | IST-REx-ID: 1733
Interface simulation distances
P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, Theoretical Computer Science 560 (2014) 348–363.
View | Files available | DOI | Download (ext.)
 
2014 | Conference Paper | IST-REx-ID: 2212
Perfect-information stochastic mean-payoff parity games
K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, in:, Springer, 2014, pp. 210–225.
View | Files available | DOI
 
2017 | Conference Paper | IST-REx-ID: 645   OA
Value iteration for long run average reward in markov decision processes
P. Ashok, K. Chatterjee, P. Daca, J. Kretinsky, T. Meggendorfer, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 201–221.
View | DOI | Download (ext.)
 
2017 | Journal Article | IST-REx-ID: 671   OA
Memory-n strategies of direct reciprocity
C. Hilbe, V. Martinez, K. Chatterjee, M. Nowak, PNAS 114 (2017) 4715–4720.
View | DOI | Download (ext.) | PubMed | Europe PMC
 
2013 | Conference Paper | IST-REx-ID: 2820
Automated analysis of real-time scheduling using graph games
K. Chatterjee, A. Kößler, U. Schmid, in:, Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, ACM, 2013, pp. 163–172.
View | Files available | DOI
 
2014 | Journal Article | IST-REx-ID: 2039   OA
The time scale of evolutionary innovation
K. Chatterjee, A. Pavlogiannis, B. Adlam, M. Nowak, PLoS Computational Biology 10 (2014).
View | Files available | DOI
 
2019 | Conference Paper | IST-REx-ID: 6175   OA
Cost analysis of nondeterministic probabilistic programs
P. Wang, H. Fu, A.K. Goharshady, K. Chatterjee, X. Qin, W. Shi, in:, 40th ACM Conference on Programming Language Design and Implementation (PLDI 2019), Association for Computing Machinery, 2019, pp. 204–220.
View | Files available | DOI | arXiv
 
2017 | Journal Article | IST-REx-ID: 1065
Pushdown reachability with constant treewidth
K. Chatterjee, G.F. Osang, Information Processing Letters 122 (2017) 25–29.
View | Files available | DOI
 
2014 | Journal Article | IST-REx-ID: 1375   OA
Approximating the minimum cycle mean
K. Chatterjee, M. Henzinger, S. Krinninger, V. Loitzenbauer, M. Raskin, Theoretical Computer Science 547 (2014) 104–116.
View | DOI | Download (ext.)
 
2015 | Conference Paper | IST-REx-ID: 1609   OA
The complexity of synthesis from probabilistic components
K. Chatterjee, L. Doyen, M. Vardi, 9135 (2015) 108–120.
View | DOI | Download (ext.)
 
2017 | Journal Article | IST-REx-ID: 1407
Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, Nonlinear Analysis: Hybrid Systems 23 (2017) 230–253.
View | Files available | DOI | Download (ext.)
 
2014 | Journal Article | IST-REx-ID: 2234   OA
Markov decision processes with multiple long-run average objectives
T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, A. Kučera, Logical Methods in Computer Science 10 (2014).
View | Files available | DOI | Download (ext.)
 
2012 | Conference Paper | IST-REx-ID: 2715   OA
Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives
K. Chatterjee, M. Joglekar, N. Shah, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–473.
View | Files available | DOI
 
2013 | Journal Article | IST-REx-ID: 2854   OA
Strategy improvement for concurrent reachability and turn based stochastic safety games
K. Chatterjee, L. De Alfaro, T.A. Henzinger, Journal of Computer and System Sciences 79 (2013) 640–657.
View | Files available | DOI
 
2015 | Journal Article | IST-REx-ID: 1856
Measuring and synthesizing systems in probabilistic environments
K. Chatterjee, T.A. Henzinger, B. Jobstmann, R. Singh, Journal of the ACM 62 (2015).
View | Files available | DOI | Download (ext.)
 
2015 | Journal Article | IST-REx-ID: 1731
Randomness for free
K. Chatterjee, L. Doyen, H. Gimbert, T.A. Henzinger, Information and Computation 245 (2015) 3–16.
View | Files available | DOI | Download (ext.)
 
2014 | Journal Article | IST-REx-ID: 535   OA
Polynomial time algorithms for energy games with special weight structures
K. Chatterjee, M. Henzinger, S. Krinninger, D. Nanongkai, Algorithmica 70 (2014) 457–492.
View | DOI | Download (ext.)
 
2015 | Journal Article | IST-REx-ID: 523   OA
Looking at mean-payoff and total-payoff through windows
K. Chatterjee, L. Doyen, M. Randour, J. Raskin, Information and Computation 242 (2015) 25–52.
View | Files available | DOI | Download (ext.)
 
2017 | Journal Article | IST-REx-ID: 681   OA
Doomsday equilibria for omega-regular games
K. Chatterjee, L. Doyen, E. Filiot, J. Raskin, Information and Computation 254 (2017) 296–315.
View | DOI | Download (ext.)
 
2014 | Conference Paper | IST-REx-ID: 2063
CEGAR for qualitative analysis of probabilistic systems
K. Chatterjee, M. Chmelik, P. Daca, in:, Springer, 2014, pp. 473–490.
View | Files available | DOI
 
2017 | Journal Article | IST-REx-ID: 465   OA
Edit distance for pushdown automata
K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Logical Methods in Computer Science 13 (2017).
View | Files available | DOI
 
2017 | Conference Paper | IST-REx-ID: 1009   OA
Optimizing expectation with guarantees in POMDPs
K. Chatterjee, P. Novotny, G. Pérez, J. Raskin, D. Zikelic, in:, Proceedings of the 31st AAAI Conference on Artificial Intelligence, AAAI Press, 2017, pp. 3725–3732.
View | Download (ext.)
 
2017 | Conference Paper | IST-REx-ID: 1011   OA
Faster algorithms for weighted recursive state machines
K. Chatterjee, B. Kragl, S. Mishra, A. Pavlogiannis, in:, H. Yang (Ed.), Springer, 2017, pp. 287–313.
View | DOI | Download (ext.)
 
2017 | Journal Article | IST-REx-ID: 1080   OA
Reconstructing metastatic seeding patterns of human cancers
J. Reiter, A. Makohon Moore, J. Gerold, I. Božić, K. Chatterjee, C. Iacobuzio Donahue, B. Vogelstein, M. Nowak, Nature Communications 8 (2017).
View | Files available | DOI
 
2015 | Journal Article | IST-REx-ID: 1698   OA
The complexity of multi-mean-payoff and multi-energy games
Y. Velner, K. Chatterjee, L. Doyen, T.A. Henzinger, A. Rabinovich, J. Raskin, Information and Computation 241 (2015) 177–196.
View | DOI | Download (ext.)
 
2014 | Conference Paper | IST-REx-ID: 1869
Suraq - a controller synthesis tool using uninterpreted functions
G. Hofferek, A. Gupta, in:, E. Yahav (Ed.), HVC 2014, Springer, 2014, pp. 68–74.
View | DOI
 
2017 | Journal Article | IST-REx-ID: 1294
Trading performance for stability in Markov decision processes
T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, Journal of Computer and System Sciences 84 (2017) 144–170.
View | Files available | DOI
 
2014 | Journal Article | IST-REx-ID: 2716   OA
Strategy synthesis for multi-dimensional quantitative objectives
K. Chatterjee, M. Randour, J. Raskin, Acta Informatica 51 (2014) 129–163.
View | DOI | Download (ext.)
 
2013 | Conference Paper | IST-REx-ID: 2444   OA
Faster algorithms for Markov decision processes with low treewidth
K. Chatterjee, J. Ła̧Cki, 8044 (2013) 543–558.
View | DOI | Download (ext.) | arXiv
 
2013 | Conference Paper | IST-REx-ID: 2305   OA
Trading performance for stability in Markov decision processes
T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, in:, 28th Annual ACM/IEEE Symposium, IEEE, 2013, pp. 331–340.
View | Files available | DOI | Download (ext.) | arXiv
 
2013 | Journal Article | IST-REx-ID: 2824
Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems
K. Chatterjee, V. Prabhu, Information and Computation 228–229 (2013) 83–119.
View | DOI
 
2013 | Journal Article | IST-REx-ID: 2831   OA
Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives
K. Chatterjee, M. Henzinger, M. Joglekar, N. Shah, Formal Methods in System Design 42 (2013) 301–327.
View | DOI | Download (ext.) | arXiv
 
2013 | Journal Article | IST-REx-ID: 2836   OA
Assume-guarantee synthesis for digital contract signing
K. Chatterjee, V. Raman, Formal Aspects of Computing 26 (2013) 825–859.
View | DOI | Download (ext.) | arXiv
 
2013 | Journal Article | IST-REx-ID: 2817   OA
Density games
S. Novak, K. Chatterjee, M. Nowak, Journal of Theoretical Biology 334 (2013) 26–34.
View | Files available | DOI
 
2013 | Conference Paper | IST-REx-ID: 2886   OA
Controllable-choice message sequence graphs
M. Chmelik, V. Řehák, 7721 (2013) 118–130.
View | DOI | Download (ext.)
 
2014 | Journal Article | IST-REx-ID: 2141 View | Files available | DOI | Download (ext.)
 
2014 | Journal Article | IST-REx-ID: 2038
Temporal specifications with accumulative values
U. Boker, K. Chatterjee, T.A. Henzinger, O. Kupferman, ACM Transactions on Computational Logic (TOCL) 15 (2014) 27.
View | Files available | DOI
 
2016 | Journal Article | IST-REx-ID: 1477
What is decidable about partially observable Markov decision processes with ω-regular objectives
K. Chatterjee, M. Chmelik, M. Tracol, Journal of Computer and System Sciences 82 (2016) 878–911.
View | Files available | DOI | Download (ext.) | arXiv
 
2014 | Conference Paper | IST-REx-ID: 1903
Partial-observation stochastic reachability and parity games
K. Chatterjee, in:, Springer, 2014, pp. 1–4.
View | Files available | DOI
 
2015 | Conference Paper | IST-REx-ID: 1732
Qualitative analysis of POMDPs with temporal logic specifications for robotics applications
K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, IEEE, 2015, pp. 325–330.
View | Files available | DOI | Download (ext.) | arXiv
 
2017 | Journal Article | IST-REx-ID: 512
Amplification on undirected population structures: Comets beat stars
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Scientific Reports 7 (2017).
View | Files available | DOI
 
2017 | Book Chapter | IST-REx-ID: 625
The cost of exactness in quantitative reachability
K. Chatterjee, L. Doyen, T.A. Henzinger, in:, L. Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay, R. Mardare (Eds.), Models, Algorithms, Logics and Tools, Springer, 2017, pp. 367–381.
View | DOI
 
2013 | Conference Paper | IST-REx-ID: 2329
Hyperplane separation technique for multidimensional mean-payoff games
K. Chatterjee, Y. Velner, 8052 (2013) 500–515.
View | Files available | DOI | Download (ext.) | arXiv
 
2018 | Journal Article | IST-REx-ID: 738   OA
Automated competitive analysis of real time scheduling with graph games
K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, Real-Time Systems 54 (2018) 166–207.
View | Files available | DOI
 
2018 | Book Chapter | IST-REx-ID: 86
Computing average response time
K. Chatterjee, T.A. Henzinger, J. Otop, in:, M. Lohstroh, P. Derler, M. Sirjani (Eds.), Principles of Modeling, Springer, 2018, pp. 143–161.
View | DOI
 
2018 | Journal Article | IST-REx-ID: 454   OA
Crosstalk in concurrent repeated games impedes direct reciprocity and requires stronger levels of forgiveness
J. Reiter, C. Hilbe, D. Rand, K. Chatterjee, M. Nowak, Nature Communications 9 (2018) 555.
View | Files available | DOI