On Stochastic Games with Multiple Objectives View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Taolue Chen , Vojtěch Forejt , Marta Kwiatkowska , Aistis Simaitis , Clemens Wiltsche

ABSTRACT

We study two-player stochastic games, where the goal of one player is to satisfy a formula given as a positive boolean combination of expected total reward objectives and the behaviour of the second player is adversarial. Such games are important for modelling, synthesis and verification of open systems with stochastic behaviour. We show that finding a winning strategy is PSPACE-hard in general and undecidable for deterministic strategies. We also prove that optimal strategies, if they exists, may require infinite memory and randomisation. However, when restricted to disjunctions of objectives only, memoryless deterministic strategies suffice, and the problem of deciding whether a winning strategy exists is NP-complete. We also present algorithms to approximate the Pareto sets of achievable objectives for the class of stopping games. More... »

PAGES

266-277

Book

TITLE

Mathematical Foundations of Computer Science 2013

ISBN

978-3-642-40312-5
978-3-642-40313-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-40313-2_25

DOI

http://dx.doi.org/10.1007/978-3-642-40313-2_25

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1050804192


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, United Kingdom", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, United Kingdom"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Taolue", 
        "id": "sg:person.014034042506.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014034042506.15"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, United Kingdom", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, United Kingdom"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Forejt", 
        "givenName": "Vojt\u011bch", 
        "id": "sg:person.012103627631.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012103627631.41"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, United Kingdom", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, United Kingdom"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kwiatkowska", 
        "givenName": "Marta", 
        "id": "sg:person.011375012273.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011375012273.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, United Kingdom", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, United Kingdom"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Simaitis", 
        "givenName": "Aistis", 
        "id": "sg:person.010605171167.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010605171167.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, United Kingdom", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, United Kingdom"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wiltsche", 
        "givenName": "Clemens", 
        "id": "sg:person.013041737446.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013041737446.42"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We study two-player stochastic games, where the goal of one player is to satisfy a formula given as a positive boolean combination of expected total reward objectives and the behaviour of the second player is adversarial. Such games are important for modelling, synthesis and verification of open systems with stochastic behaviour. We show that finding a winning strategy is PSPACE-hard in general and undecidable for deterministic strategies. We also prove that optimal strategies, if they exists, may require infinite memory and randomisation. However, when restricted to disjunctions of objectives only, memoryless deterministic strategies suffice, and the problem of deciding whether a winning strategy exists is NP-complete. We also present algorithms to approximate the Pareto sets of achievable objectives for the class of stopping games.", 
    "editor": [
      {
        "familyName": "Chatterjee", 
        "givenName": "Krishnendu", 
        "type": "Person"
      }, 
      {
        "familyName": "Sgall", 
        "givenName": "Jir\u00ed", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-40313-2_25", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-40312-5", 
        "978-3-642-40313-2"
      ], 
      "name": "Mathematical Foundations of Computer Science 2013", 
      "type": "Book"
    }, 
    "keywords": [
      "stochastic games", 
      "two-player stochastic games", 
      "deterministic strategies", 
      "Pareto set", 
      "stochastic behavior", 
      "multiple objectives", 
      "positive boolean combinations", 
      "infinite memory", 
      "reward objective", 
      "optimal strategy", 
      "second player", 
      "Boolean combinations", 
      "such games", 
      "open system", 
      "game", 
      "algorithm", 
      "problem", 
      "modelling", 
      "class", 
      "formula", 
      "set", 
      "NP", 
      "objective", 
      "system", 
      "strategies", 
      "behavior", 
      "verification", 
      "players", 
      "goal", 
      "disjunction", 
      "combination", 
      "achievable objectives", 
      "memory", 
      "randomisation", 
      "synthesis", 
      "total reward objectives", 
      "disjunctions of objectives", 
      "memoryless deterministic strategies"
    ], 
    "name": "On Stochastic Games with Multiple Objectives", 
    "pagination": "266-277", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050804192"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-40313-2_25"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-40313-2_25", 
      "https://app.dimensions.ai/details/publication/pub.1050804192"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:03", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_285.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-40313-2_25"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40313-2_25'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40313-2_25'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40313-2_25'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40313-2_25'


 

This table displays all metadata directly associated to this object as RDF triples.

131 TRIPLES      23 PREDICATES      64 URIs      57 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-40313-2_25 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N4d05ec04fb73436e80a7bcf8e1f33511
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We study two-player stochastic games, where the goal of one player is to satisfy a formula given as a positive boolean combination of expected total reward objectives and the behaviour of the second player is adversarial. Such games are important for modelling, synthesis and verification of open systems with stochastic behaviour. We show that finding a winning strategy is PSPACE-hard in general and undecidable for deterministic strategies. We also prove that optimal strategies, if they exists, may require infinite memory and randomisation. However, when restricted to disjunctions of objectives only, memoryless deterministic strategies suffice, and the problem of deciding whether a winning strategy exists is NP-complete. We also present algorithms to approximate the Pareto sets of achievable objectives for the class of stopping games.
7 schema:editor Ndee0b740d7504cce8c9d5dbaaf30990c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N2b41d45a01ef4254a6a7a7a3fc968f8e
12 schema:keywords Boolean combinations
13 NP
14 Pareto set
15 achievable objectives
16 algorithm
17 behavior
18 class
19 combination
20 deterministic strategies
21 disjunction
22 disjunctions of objectives
23 formula
24 game
25 goal
26 infinite memory
27 memory
28 memoryless deterministic strategies
29 modelling
30 multiple objectives
31 objective
32 open system
33 optimal strategy
34 players
35 positive boolean combinations
36 problem
37 randomisation
38 reward objective
39 second player
40 set
41 stochastic behavior
42 stochastic games
43 strategies
44 such games
45 synthesis
46 system
47 total reward objectives
48 two-player stochastic games
49 verification
50 schema:name On Stochastic Games with Multiple Objectives
51 schema:pagination 266-277
52 schema:productId Nc64c8f10a2f14eddb6398606e050035c
53 Ncf0421047cf74986ae8ee6774af86888
54 schema:publisher N230dded4518d4b17bd6ecadbd64b416f
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050804192
56 https://doi.org/10.1007/978-3-642-40313-2_25
57 schema:sdDatePublished 2021-12-01T20:03
58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
59 schema:sdPublisher N0c60728bb4bd4602a2ba29b9c6a3b1b4
60 schema:url https://doi.org/10.1007/978-3-642-40313-2_25
61 sgo:license sg:explorer/license/
62 sgo:sdDataset chapters
63 rdf:type schema:Chapter
64 N0c60728bb4bd4602a2ba29b9c6a3b1b4 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 N230dded4518d4b17bd6ecadbd64b416f schema:name Springer Nature
67 rdf:type schema:Organisation
68 N2b41d45a01ef4254a6a7a7a3fc968f8e schema:isbn 978-3-642-40312-5
69 978-3-642-40313-2
70 schema:name Mathematical Foundations of Computer Science 2013
71 rdf:type schema:Book
72 N4d05ec04fb73436e80a7bcf8e1f33511 rdf:first sg:person.014034042506.15
73 rdf:rest Ndb0c02dc32564a76abf57f4ba89427ec
74 N5b63ff28ab1340958ee48319b2c2f12b rdf:first sg:person.013041737446.42
75 rdf:rest rdf:nil
76 N629724815b93452aa7f2dba887f4e8f8 rdf:first sg:person.010605171167.62
77 rdf:rest N5b63ff28ab1340958ee48319b2c2f12b
78 N76656c330e9a46e18257dca73c594045 schema:familyName Chatterjee
79 schema:givenName Krishnendu
80 rdf:type schema:Person
81 N9e3d37eebec745248e13f8c0efa561b5 schema:familyName Sgall
82 schema:givenName Jirí
83 rdf:type schema:Person
84 Nb088cf03b6c6405f93526509462fe60f rdf:first N9e3d37eebec745248e13f8c0efa561b5
85 rdf:rest rdf:nil
86 Nc4fac680a18d4503be5f46f638c558de rdf:first sg:person.011375012273.39
87 rdf:rest N629724815b93452aa7f2dba887f4e8f8
88 Nc64c8f10a2f14eddb6398606e050035c schema:name dimensions_id
89 schema:value pub.1050804192
90 rdf:type schema:PropertyValue
91 Ncf0421047cf74986ae8ee6774af86888 schema:name doi
92 schema:value 10.1007/978-3-642-40313-2_25
93 rdf:type schema:PropertyValue
94 Ndb0c02dc32564a76abf57f4ba89427ec rdf:first sg:person.012103627631.41
95 rdf:rest Nc4fac680a18d4503be5f46f638c558de
96 Ndee0b740d7504cce8c9d5dbaaf30990c rdf:first N76656c330e9a46e18257dca73c594045
97 rdf:rest Nb088cf03b6c6405f93526509462fe60f
98 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
99 schema:name Mathematical Sciences
100 rdf:type schema:DefinedTerm
101 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
102 schema:name Statistics
103 rdf:type schema:DefinedTerm
104 sg:person.010605171167.62 schema:affiliation grid-institutes:grid.4991.5
105 schema:familyName Simaitis
106 schema:givenName Aistis
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010605171167.62
108 rdf:type schema:Person
109 sg:person.011375012273.39 schema:affiliation grid-institutes:grid.4991.5
110 schema:familyName Kwiatkowska
111 schema:givenName Marta
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011375012273.39
113 rdf:type schema:Person
114 sg:person.012103627631.41 schema:affiliation grid-institutes:grid.4991.5
115 schema:familyName Forejt
116 schema:givenName Vojtěch
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012103627631.41
118 rdf:type schema:Person
119 sg:person.013041737446.42 schema:affiliation grid-institutes:grid.4991.5
120 schema:familyName Wiltsche
121 schema:givenName Clemens
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013041737446.42
123 rdf:type schema:Person
124 sg:person.014034042506.15 schema:affiliation grid-institutes:grid.4991.5
125 schema:familyName Chen
126 schema:givenName Taolue
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014034042506.15
128 rdf:type schema:Person
129 grid-institutes:grid.4991.5 schema:alternateName Department of Computer Science, University of Oxford, United Kingdom
130 schema:name Department of Computer Science, University of Oxford, United Kingdom
131 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...