{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T17:27:03Z","timestamp":1790530023605,"version":"4.1.0"},"publisher-location":"Cham","reference-count":44,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030451899","type":"print"},{"value":"9783030451905","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-45190-5_19","type":"book-chapter","created":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T09:03:02Z","timestamp":1587114182000},"page":"346-364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Simple Strategies in Multi-Objective MDPs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2254-0596","authenticated-orcid":false,"given":"Florent","family":"Delgrange","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6143-1926","authenticated-orcid":false,"given":"Joost-Pieter","family":"Katoen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2843-5511","authenticated-orcid":false,"given":"Tim","family":"Quatmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mickael","family":"Randour","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","unstructured":"Baier, C., Daum, M., Dubslaff, C., Klein, J., Kl\u00fcppelholz, S.: Energy-utility quantiles. In: NASA Formal Methods, NFM. pp. 285\u2013299 (2014). https:\/\/doi.org\/10.1007\/978-3-319-06200-6_24","DOI":"10.1007\/978-3-319-06200-6_24"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Baier, C., Dubslaff, C., Kl\u00fcppelholz, S.: Trade-off analysis meets probabilistic model checking. In: CSL-LICS. pp. 1:1\u20131:10. ACM (2014)","DOI":"10.1145\/2603088.2603089"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Baier, C., Hermanns, H., Katoen, J.: The 10, 000 facets of MDP model checking. In: Computing and Software Science, LNCS, vol. 10000, pp. 420\u2013451. Springer (2019)","DOI":"10.1007\/978-3-319-91908-9_21"},{"key":"19_CR4","unstructured":"Baier, C., Katoen, J.P.: Principles of model checking. MIT Press (2008)"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Baier, C., Klein, J., Leuschner, L., Parker, D., Wunderlich, S.: Ensuring the reliability of your model checker: Interval iteration for Markov decision processes. In: CAV (1). LNCS, vol. 10426, pp. 160\u2013180. Springer (2017)","DOI":"10.1007\/978-3-319-63387-9_8"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Barrett, L., Narayanan, S.: Learning all optimal policies with multiple criteria. In: (ICML). pp. 41\u201347 (2008)","DOI":"10.1145\/1390156.1390162"},{"key":"19_CR7","doi-asserted-by":"publisher","unstructured":"Benini, L., Bogliolo, A., Paleologo, G.A., De Micheli, G.: Policy optimization for dynamic power management. Trans. Comp.-Aided Des. Integ. Cir. Sys. 18(6), 813\u2013833 (2006). https:\/\/doi.org\/10.1109\/43.766730","DOI":"10.1109\/43.766730"},{"key":"19_CR8","unstructured":"Berthon, R., Randour, M., Raskin, J.: Threshold constraints with guarantees for parity objectives in Markov decision processes. In: ICALP. LIPIcs, vol. 80, pp. 121:1\u2013121:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Bouyer, P., Gonz\u00e1lez, M., Markey, N., Randour, M.: Multi-weighted Markov decision processes with reachability objectives. In: GandALF. EPTCS, vol.\u00a0277, pp. 250\u2013264 (2018)","DOI":"10.4204\/EPTCS.277.18"},{"issue":"1","key":"19_CR10","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1145\/322234.322242","volume":"28","author":"JL Bruno","year":"1981","unstructured":"Bruno, J.L., Downey, P.J., Frederickson, G.N.: Sequencing tasks with exponential service times to minimize the expected flow time or makespan. J. ACM 28(1), 100\u2013113 (1981). https:\/\/doi.org\/10.1145\/322234.322242","journal-title":"J. ACM"},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2016.10.011","volume":"254","author":"V Bruy\u00e8re","year":"2017","unstructured":"Bruy\u00e8re, V., Filiot, E., Randour, M., Raskin, J.: Meet your expectations with guarantees: Beyond worst-case synthesis in quantitative games. Inf. Comput. 254, 259\u2013295 (2017)","journal-title":"Inf. Comput."},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., de Alfaro, L., Henzinger, T.A.: Trading memory for randomness. In: QEST. pp. 206\u2013217. IEEE Computer Society (2004)","DOI":"10.21236\/ADA458138"},{"key":"19_CR13","unstructured":"Chatterjee, K., Kret\u00ednsk\u00e1, Z., Kret\u00ednsk\u00fd, J.: Unifying two views on multiple mean-payoff objectives in markov decision processes. LMCS 13(2) (2017)"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Majumdar, R., Henzinger, T.A.: Markov decision processes with multiple objectives. In: STACS. LNCS, vol.\u00a03884, pp. 325\u2013336. Springer (2006)","DOI":"10.1007\/11672142_26"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Chen, T., Kwiatkowska, M.Z., Parker, D., Simaitis, A.: Verifying team formation protocols with probabilistic model checking. In: CLIMA. pp. 190\u2013207 (2011)","DOI":"10.1007\/978-3-642-22359-4_14"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Dehnert, C., Junges, S., Katoen, J.P., Volk, M.: A Storm is coming: A modern probabilistic model checker. In: CAV. LNCS, vol. 10427. Springer (2017)","DOI":"10.1007\/978-3-319-63390-9_31"},{"key":"19_CR17","unstructured":"Delgrange, F., Katoen, J.P., Quatmann, T., Randour, M.: Simple strategies in multi-objective MDPs (technical report). CoRR abs\/\/1910.11024 (2019), http:\/\/arxiv.org\/abs\/1910.11024"},{"key":"19_CR18","doi-asserted-by":"publisher","DOI":"10.6084\/m9.figshare.11569485","author":"F Delgrange","year":"2020","unstructured":"Delgrange, F., Katoen, J.P., Quatmann, T., Randour, M.: Evaluated artifact for this paper. figshare (2020). https:\/\/doi.org\/10.6084\/m9.figshare.11569485","journal-title":"Evaluated artifact for this paper. figshare"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"von Essen, C., Giannakopoulou, D.: Probabilistic verification and synthesis of the next generation airborne collision avoidance system. STTT 18(2), 227\u2013243 (2016)","DOI":"10.1007\/s10009-015-0388-8"},{"key":"19_CR20","doi-asserted-by":"publisher","unstructured":"Etessami, K., Kwiatkowska, M.Z., Vardi, M.Y., Yannakakis, M.: Multi-objective model checking of Markov decision processes. Logical Methods in Computer Science 4(4) (2008). https:\/\/doi.org\/10.2168\/LMCS-4(4:8)2008","DOI":"10.2168\/LMCS-4(4:8)2008"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"Feng, L., Wiltsche, C., Humphrey, L.R., Topcu, U.: Controller synthesis for autonomous systems interacting with human operators. In: ICCPS. pp. 70\u201379. ACM (2015)","DOI":"10.1145\/2735960.2735973"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Forejt, V., Kwiatkowska, M.Z., Norman, G., Parker, D.: Automated verification techniques for probabilistic systems. In: SFM. LNCS, vol.\u00a06659, pp.53\u2013113. Springer (2011)","DOI":"10.1007\/978-3-642-21455-4_3"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Forejt, V., Kwiatkowska, M.Z., Norman, G., Parker, D., Qu, H.: Quantitative multi-objective verification for probabilistic systems. In: TACAS. LNCS, vol.\u00a06605, pp. 112\u2013127. Springer (2011)","DOI":"10.1007\/978-3-642-19835-9_11"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Forejt, V., Kwiatkowska, M.Z., Parker, D.: Pareto curves for probabilistic model checking. In: ATVA. LNCS, vol. 7561, pp. 317\u2013332. Springer (2012)","DOI":"10.1007\/978-3-642-33386-6_25"},{"key":"19_CR25","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1979)"},{"key":"19_CR26","unstructured":"Gleixner, A., Bastubbe, M., Eifler, L., Gally, T., Gamrath, G., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., L\u00fcbbecke, M.E., Maher, S.J., Miltenberger, M., M\u00fcller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schl\u00f6sser, F., Schubert, C., Serrano, F., Shinano, Y., Viernickel, J.M., Walter, M., Wegscheider, F., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 6.0. Technical report, Optimization Online (July 2018), http:\/\/www.optimization-online.org\/DB_HTML\/2018\/07\/6692.html"},{"key":"19_CR27","unstructured":"Gurobi Optimization, L.: Gurobi optimizer reference manual (2019), http:\/\/www.gurobi.com"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"Hartmanns, A., Junges, S., Katoen, J., Quatmann, T.: Multi-cost bounded reachability in MDP. In: TACAS (2). LNCS, vol. 10806, pp. 320\u2013339. Springer (2018)","DOI":"10.1007\/978-3-319-89963-3_19"},{"key":"19_CR29","unstructured":"Junges, S., Jansen, N., Wimmer, R., Quatmann, T., Winterer, L., Katoen, J., Becker, B.: Finite-state controllers of POMDPs using parameter synthesis. In: UAI. pp. 519\u2013529. AUAI Press (2018)"},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"Kwiatkowska, M., Norman, G., Parker, D.: PRISM 4.0: Verification of probabilistic real-time systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) Proc. 23rd International Conference on Computer Aided Verification (CAV\u201911). LNCS, vol.\u00a06806, pp. 585\u2013591. Springer (2011)","DOI":"10.1007\/978-3-642-22110-1_47"},{"key":"19_CR31","doi-asserted-by":"publisher","unstructured":"Kwiatkowska, M.Z., Norman, G., Parker, D.: The PRISM benchmark suite. In: QEST. pp. 203\u2013204 (2012). https:\/\/doi.org\/10.1109\/QEST.2012.14","DOI":"10.1109\/QEST.2012.14"},{"key":"19_CR32","doi-asserted-by":"crossref","unstructured":"Lacerda, B., Parker, D., Hawes, N.: Multi-objective policy generation for mobile robots under probabilistic time-bounded guarantees. In: ICAPS. pp. 504\u2013512. AAAI Press (2017)","DOI":"10.1609\/icaps.v27i1.13865"},{"key":"19_CR33","first-page":"3253","volume":"13","author":"DJ Lizotte","year":"2012","unstructured":"Lizotte, D.J., Bowling, M., Murphy, S.A.: Linear fitted-Q iteration with multiple reward functions. J. Mach. Learn. Res. 13, 3253\u20133295 (2012)","journal-title":"J. Mach. Learn. Res."},{"key":"19_CR34","unstructured":"Perny, P., Weng, P.: On finding compromise solutions in multiobjective Markov decision processes. In: ECAI. FAIA, vol. 215, pp. 969\u2013970. IOS Press (2010)"},{"key":"19_CR35","doi-asserted-by":"crossref","unstructured":"Pia, A.D., Dey, S.S., Molinaro, M.: Mixed-integer quadratic programming is in NP. Math. Program. 162(1-2), 225\u2013240 (2017)","DOI":"10.1007\/s10107-016-1036-0"},{"key":"19_CR36","doi-asserted-by":"crossref","unstructured":"Puterman, M.L.: Markov Decision Processes. John Wiley and Sons (1994)","DOI":"10.1002\/9780470316887"},{"key":"19_CR37","doi-asserted-by":"crossref","unstructured":"Qiu, Q., Wu, Q., Pedram, M.: Stochastic modeling of a power-managed system: Construction and optimization. In: ISLPED. pp. 194\u2013199. ACM (1999)","DOI":"10.1145\/313817.313923"},{"key":"19_CR38","doi-asserted-by":"crossref","unstructured":"Quatmann, T., Junges, S., Katoen, J.: Markov automata with multiple objectives. In: CAV (1). LNCS, vol. 10426, pp. 140\u2013159. Springer (2017)","DOI":"10.1007\/978-3-319-63387-9_7"},{"key":"19_CR39","doi-asserted-by":"crossref","unstructured":"Randour, M., Raskin, J., Sankur, O.: Variations on the stochastic shortest path problem. In: VMCAI. Lecture Notes in Computer Science, vol.\u00a08931, pp.1\u201318. Springer (2015)","DOI":"10.1007\/978-3-662-46081-8_1"},{"key":"19_CR40","doi-asserted-by":"crossref","unstructured":"Randour, M., Raskin, J., Sankur, O.: Percentile queries in multi-dimensional Markov decision processes. FMSD 50(2-3), 207\u2013248 (2017)","DOI":"10.1007\/s10703-016-0262-7"},{"key":"19_CR41","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1613\/jair.3987","volume":"48","author":"DM Roijers","year":"2013","unstructured":"Roijers, D.M., Vamplew, P., Whiteson, S., Dazeley, R.: A survey of multi-objective sequential decision-making. JAIR 48, 67\u2013113 (2013)","journal-title":"JAIR"},{"key":"19_CR42","doi-asserted-by":"crossref","unstructured":"Scheftelowitsch, D., Buchholz, P., Hashemi, V., Hermanns, H.: Multi-objective approaches to Markov decision processes with uncertain transition parameters. In: VALUETOOLS. pp. 44\u201351. ACM (2017)","DOI":"10.1145\/3150928.3150945"},{"issue":"6","key":"19_CR43","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1287\/mnsc.37.6.667","volume":"37","author":"M Srinivasan","year":"1991","unstructured":"Srinivasan, M.: Nondeterministic polling systems. Management Science 37(6), 667\u2013681 (1991). https:\/\/doi.org\/10.1287\/mnsc.37.6.667","journal-title":"Management Science"},{"key":"19_CR44","doi-asserted-by":"publisher","unstructured":"Wiering, M.A., de Jong, E.D.: Computing optimal stationary policies for multi-objective Markov decision processes. In: ADPRL. pp. 158\u2013165 (2007). https:\/\/doi.org\/10.1109\/ADPRL.2007.368183","DOI":"10.1109\/ADPRL.2007.368183"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-45190-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T15:39:19Z","timestamp":1666366759000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45190-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030451899","9783030451905"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45190-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TACAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dublin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ireland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 April 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 April 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2020\/tacas","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"155","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"14","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference could not take place due to the COVID-19 pandemic. There was an online event on July 2, 2020.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}