[{"page":"25 - 52","issue":"6","language":[{"iso":"eng"}],"type":"journal_article","day":"24","_id":"523","department":[{"_id":"KrCh"}],"scopus_import":1,"oa_version":"Preprint","publication":"Information and Computation","oa":1,"ec_funded":1,"date_published":"2015-03-24T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1302.4248","open_access":"1"}],"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"volume":242,"date_created":"2018-12-11T11:46:57Z","month":"03","title":"Looking at mean-payoff and total-payoff through windows","date_updated":"2020-08-11T10:10:18Z","citation":{"ista":"Chatterjee K, Doyen L, Randour M, Raskin J. 2015. Looking at mean-payoff and total-payoff through windows. Information and Computation. 242(6), 25–52.","ama":"Chatterjee K, Doyen L, Randour M, Raskin J. Looking at mean-payoff and total-payoff through windows. *Information and Computation*. 2015;242(6):25-52. doi:10.1016/j.ic.2015.03.010","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Mickael Randour, and Jean Raskin. “Looking at Mean-Payoff and Total-Payoff through Windows.” *Information and Computation* 242, no. 6 (2015): 25–52. https://doi.org/10.1016/j.ic.2015.03.010.","short":"K. Chatterjee, L. Doyen, M. Randour, J. Raskin, Information and Computation 242 (2015) 25–52.","apa":"Chatterjee, K., Doyen, L., Randour, M., & Raskin, J. (2015). Looking at mean-payoff and total-payoff through windows. *Information and Computation*, *242*(6), 25–52. https://doi.org/10.1016/j.ic.2015.03.010","mla":"Chatterjee, Krishnendu, et al. “Looking at Mean-Payoff and Total-Payoff through Windows.” *Information and Computation*, vol. 242, no. 6, Elsevier, 2015, pp. 25–52, doi:10.1016/j.ic.2015.03.010.","ieee":"K. Chatterjee, L. Doyen, M. Randour, and J. Raskin, “Looking at mean-payoff and total-payoff through windows,” *Information and Computation*, vol. 242, no. 6, pp. 25–52, 2015."},"intvolume":" 242","publisher":"Elsevier","publist_id":"7296","quality_controlled":"1","status":"public","year":"2015","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"},{"full_name":"Randour, Mickael","last_name":"Randour","first_name":"Mickael"},{"full_name":"Raskin, Jean","last_name":"Raskin","first_name":"Jean"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2279"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"text":"We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.","lang":"eng"}],"doi":"10.1016/j.ic.2015.03.010"},{"publication":"Information and Computation","oa":1,"date_published":"2015-10-11T00:00:00Z","oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1409.5306","open_access":"1"}],"type":"journal_article","language":[{"iso":"eng"}],"page":"2 - 24","issue":"6","_id":"524","department":[{"_id":"KrCh"}],"scopus_import":1,"day":"11","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen"}],"quality_controlled":"1","status":"public","year":"2015","abstract":[{"lang":"eng","text":"We consider concurrent games played by two players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question of whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time."}],"doi":"10.1016/j.ic.2015.03.009","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"id":"5403","relation":"earlier_version","status":"public"}]},"publication_status":"published","date_created":"2018-12-11T11:46:57Z","month":"10","title":"Qualitative analysis of concurrent mean payoff games","date_updated":"2020-08-11T10:10:18Z","citation":{"ista":"Chatterjee K, Ibsen-Jensen R. 2015. Qualitative analysis of concurrent mean payoff games. Information and Computation. 242(6), 2–24.","ama":"Chatterjee K, Ibsen-Jensen R. Qualitative analysis of concurrent mean payoff games. *Information and Computation*. 2015;242(6):2-24. doi:10.1016/j.ic.2015.03.009","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” *Information and Computation* 242, no. 6 (2015): 2–24. https://doi.org/10.1016/j.ic.2015.03.009.","apa":"Chatterjee, K., & Ibsen-Jensen, R. (2015). Qualitative analysis of concurrent mean payoff games. *Information and Computation*, *242*(6), 2–24. https://doi.org/10.1016/j.ic.2015.03.009","short":"K. Chatterjee, R. Ibsen-Jensen, Information and Computation 242 (2015) 2–24.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” *Information and Computation*, vol. 242, no. 6, Elsevier, 2015, pp. 2–24, doi:10.1016/j.ic.2015.03.009.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “Qualitative analysis of concurrent mean payoff games,” *Information and Computation*, vol. 242, no. 6, pp. 2–24, 2015."},"intvolume":" 242","external_id":{"arxiv":["1409.5306"]},"volume":242,"publisher":"Elsevier","publist_id":"7295"},{"has_accepted_license":"1","month":"01","type":"technical_report","language":[{"iso":"eng"}],"ddc":["004"],"date_created":"2018-12-12T11:39:17Z","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","date_updated":"2020-08-11T10:10:15Z","citation":{"mla":"Chatterjee, Krishnendu, et al. *Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes*. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v1-1.","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, *Unifying two views on multiple mean-payoff objectives in Markov decision processes*. IST Austria, 2015.","apa":"Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). *Unifying two views on multiple mean-payoff objectives in Markov decision processes*. IST Austria. https://doi.org/10.15479/AT:IST-2015-318-v1-1","short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. *Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v1-1.","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","ama":"Chatterjee K, Komarkova Z, Kretinsky J. *Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes*. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v1-1"},"file":[{"access_level":"open_access","file_size":689863,"relation":"main_file","checksum":"e4869a584567c506349abda9c8ec7db3","content_type":"application/pdf","creator":"system","date_updated":"2020-07-14T12:46:52Z","file_name":"IST-2015-318-v1+1_main.pdf","date_created":"2018-12-12T11:54:11Z","file_id":"5533"}],"page":"41","file_date_updated":"2020-07-14T12:46:52Z","_id":"5429","department":[{"_id":"KrCh"}],"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","day":"12","oa":1,"date_published":"2015-01-12T00:00:00Z","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Zuzana","last_name":"Komarkova","full_name":"Komarkova, Zuzana"},{"first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan","orcid":"0000-0002-8122-2881","last_name":"Kretinsky"}],"year":"2015","oa_version":"Published Version","status":"public","pubrep_id":"318","doi":"10.15479/AT:IST-2015-318-v1-1","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. \r\nThere have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. \r\nWe consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics.\r\nOur problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).\r\nOur main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions.\r\nFinally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"id":"5435","relation":"later_version","status":"public"},{"id":"1657","relation":"later_version","status":"public"},{"status":"public","id":"466","relation":"later_version"}]},"publication_identifier":{"issn":["2664-1690"]},"publication_status":"published"},{"file":[{"date_updated":"2020-07-14T12:46:52Z","file_name":"IST-2015-319-v1+1_long.pdf","date_created":"2018-12-12T11:53:21Z","file_id":"5482","access_level":"open_access","file_size":1089651,"checksum":"62c6ea01e342553dcafb88a070fb1ad5","relation":"main_file","creator":"system","content_type":"application/pdf"}],"page":"31","file_date_updated":"2020-07-14T12:46:52Z","month":"02","has_accepted_license":"1","type":"technical_report","language":[{"iso":"eng"}],"ddc":["000"],"date_created":"2018-12-12T11:39:17Z","citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 31p.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. *Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs*. IST Austria; 2015. doi:10.15479/AT:IST-2015-319-v1-1","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. *Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-319-v1-1.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). *Faster algorithms for quantitative verification in constant treewidth graphs*. IST Austria. https://doi.org/10.15479/AT:IST-2015-319-v1-1","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, *Faster algorithms for quantitative verification in constant treewidth graphs*. IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. *Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs*. IST Austria, 2015, doi:10.15479/AT:IST-2015-319-v1-1."},"date_updated":"2020-08-11T10:09:21Z","title":"Faster algorithms for quantitative verification in constant treewidth graphs","publisher":"IST Austria","day":"10","_id":"5430","department":[{"_id":"KrCh"}],"alternative_title":["IST Austria Technical Report"],"oa_version":"Published Version","status":"public","year":"2015","oa":1,"date_published":"2015-02-10T00:00:00Z","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen"},{"full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","id":"5437","relation":"later_version"},{"id":"1607","relation":"later_version","status":"public"}]},"publication_identifier":{"issn":["2664-1690"]},"publication_status":"published","pubrep_id":"319","abstract":[{"text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean- payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) ) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O ( n · log( | a · b · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · log( n · W )) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.","lang":"eng"}],"doi":"10.15479/AT:IST-2015-319-v1-1"},{"file_date_updated":"2020-07-14T12:46:53Z","page":"25","file":[{"date_created":"2018-12-12T11:53:31Z","file_id":"5491","date_updated":"2020-07-14T12:46:53Z","file_name":"IST-2015-322-v1+1_safetygames.pdf","content_type":"application/pdf","creator":"system","relation":"main_file","checksum":"bfb858262c30445b8e472c40069178a2","file_size":661015,"access_level":"open_access"}],"date_created":"2018-12-12T11:39:17Z","ddc":["005","519"],"language":[{"iso":"eng"}],"type":"technical_report","month":"02","has_accepted_license":"1","title":"The patience of concurrent stochastic games with safety and reachability objectives","citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic games with safety and reachability objectives, IST Austria, 25p.","ama":"Chatterjee K, Ibsen-Jensen R, Hansen K. *The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives*. IST Austria; 2015. doi:10.15479/AT:IST-2015-322-v1-1","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Kristoffer Hansen. *The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-322-v1-1.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Hansen, K. (2015). *The patience of concurrent stochastic games with safety and reachability objectives*. IST Austria. https://doi.org/10.15479/AT:IST-2015-322-v1-1","short":"K. Chatterjee, R. Ibsen-Jensen, K. Hansen, The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. *The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives*. IST Austria, 2015, doi:10.15479/AT:IST-2015-322-v1-1.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and K. Hansen, *The patience of concurrent stochastic games with safety and reachability objectives*. IST Austria, 2015."},"date_updated":"2020-07-14T23:07:59Z","publisher":"IST Austria","day":"19","_id":"5431","department":[{"_id":"KrCh"}],"alternative_title":["IST Austria Technical Report"],"oa_version":"Published Version","year":"2015","status":"public","oa":1,"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Kristoffer","full_name":"Hansen, Kristoffer","last_name":"Hansen"}],"date_published":"2015-02-19T00:00:00Z","publication_identifier":{"issn":["2664-1690"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"lang":"eng","text":"We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target set is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed.\r\n\r\n Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience is needed in general for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, then the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential."}],"doi":"10.15479/AT:IST-2015-322-v1-1","pubrep_id":"322"}]