Average-energy games View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-03

AUTHORS

Patricia Bouyer, Nicolas Markey, Mickael Randour, Kim G. Larsen, Simon Laursen

ABSTRACT

Two-player quantitative zero-sum games provide a natural framework to synthesize controllers with performance guarantees for reactive systems within an uncontrollable environment. Classical settings include mean-payoff games, where the objective is to optimize the long-run average gain per action, and energy games, where the system has to avoid running out of energy. We study average-energy games, where the goal is to optimize the long-run average of the accumulated energy. We show that this objective arises naturally in several applications, and that it yields interesting connections with previous concepts in the literature. We prove that deciding the winner in such games is in NP∩coNP and at least as hard as solving mean-payoff games, and we establish that memoryless strategies suffice to win. We also consider the case where the system has to minimize the average-energy while maintaining the accumulated energy within predefined bounds at all times: this corresponds to operating with a finite-capacity storage for energy. We give results for one-player and two-player games, and establish complexity bounds and memory requirements. More... »

PAGES

91-127

References to SciGraph publications

  • 2013. Synthesis from LTL Specifications with Mean-Payoff Objectives in TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS
  • 2005. Games Where You Can Play Optimally Without Any Memory in CONCUR 2005 – CONCURRENCY THEORY
  • 2014. Minimizing Running Costs in Consumption Systems in COMPUTER AIDED VERIFICATION
  • 2013. Optimal Bounds for Multiweighted and Parametrised Energy Games in THEORIES OF PROGRAMMING AND FORMAL METHODS
  • 2014-06. Strategy synthesis for multi-dimensional quantitative objectives in ACTA INFORMATICA
  • 2008. Infinite Runs in Weighted Timed Automata with Energy Constraints in FORMAL MODELING AND ANALYSIS OF TIMED SYSTEMS
  • 2010. Energy Parity Games in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2009. Games through Nested Fixpoints in COMPUTER AIDED VERIFICATION
  • 2013. Automated Synthesis of Reliable and Efficient Systems Through Game Theory: A Case Study in PROCEEDINGS OF THE EUROPEAN CONFERENCE ON COMPLEX SYSTEMS 2012
  • 2009. Automatic Synthesis of Robust and Optimal Controllers – An Industrial Case Study in HYBRID SYSTEMS: COMPUTATION AND CONTROL
  • 1979-06. Positional strategies for mean payoff games in INTERNATIONAL JOURNAL OF GAME THEORY
  • 2006. Half-Positional Determinacy of Infinite Games in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2009. Better Quality in Synthesis through Quantitative Objectives in COMPUTER AIDED VERIFICATION
  • 1987-06. The bad match; a total reward stochastic game in OR SPECTRUM
  • 2005. Intruder Deduction for AC-Like Equational Theories with Homomorphisms in TERM REWRITING AND APPLICATIONS
  • 2011-04. Faster algorithms for mean-payoff games in FORMAL METHODS IN SYSTEM DESIGN
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00236-016-0274-1

    DOI

    http://dx.doi.org/10.1007/s00236-016-0274-1

    DIMENSIONS

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


    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/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Laboratoire Sp\u00e9cification et V\u00e9rification", 
              "id": "https://www.grid.ac/institutes/grid.464035.0", 
              "name": [
                "LSV, CNRS and ENS Cachan, Avenue du Pr\u00e9sident Wilson, 61, 94230, Cachan, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bouyer", 
            "givenName": "Patricia", 
            "id": "sg:person.014467443251.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014467443251.73"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Laboratoire Sp\u00e9cification et V\u00e9rification", 
              "id": "https://www.grid.ac/institutes/grid.464035.0", 
              "name": [
                "LSV, CNRS and ENS Cachan, Avenue du Pr\u00e9sident Wilson, 61, 94230, Cachan, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Markey", 
            "givenName": "Nicolas", 
            "id": "sg:person.07601744130.31", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07601744130.31"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Universit\u00e9 Libre de Bruxelles", 
              "id": "https://www.grid.ac/institutes/grid.4989.c", 
              "name": [
                "Computer Science Department, Universit\u00e9 libre de Bruxelles (ULB), Avenue Franklin Roosevelt, 50, 1050, Brussels, Belgium"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Randour", 
            "givenName": "Mickael", 
            "id": "sg:person.016525130237.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016525130237.39"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Aalborg University", 
              "id": "https://www.grid.ac/institutes/grid.5117.2", 
              "name": [
                "Aalborg University, Fredrik Bajers Vej 5, 9100, Aalborg, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Larsen", 
            "givenName": "Kim G.", 
            "id": "sg:person.012135303667.82", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012135303667.82"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Aalborg University", 
              "id": "https://www.grid.ac/institutes/grid.5117.2", 
              "name": [
                "Aalborg University, Fredrik Bajers Vej 5, 9100, Aalborg, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Laursen", 
            "givenName": "Simon", 
            "id": "sg:person.015014012371.97", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015014012371.97"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/2461328.2461370", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003894342"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14162-1_50", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007068745", 
              "https://doi.org/10.1007/978-3-642-14162-1_50"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14162-1_50", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007068745", 
              "https://doi.org/10.1007/978-3-642-14162-1_50"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ic.2015.03.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010847376"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ic.2015.03.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010847376"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-36742-7_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011243039", 
              "https://doi.org/10.1007/978-3-642-36742-7_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02658-4_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011390017", 
              "https://doi.org/10.1007/978-3-642-02658-4_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02658-4_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011390017", 
              "https://doi.org/10.1007/978-3-642-02658-4_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ic.2015.03.010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013377026"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-08867-9_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014016250", 
              "https://doi.org/10.1007/978-3-319-08867-9_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0020-0190(98)00150-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014580512"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2012.07.038", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017993333"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00236-013-0182-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018480690", 
              "https://doi.org/10.1007/s00236-013-0182-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01768705", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021856463", 
              "https://doi.org/10.1007/bf01768705"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01768705", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021856463", 
              "https://doi.org/10.1007/bf01768705"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10703-010-0105-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027686195", 
              "https://doi.org/10.1007/s10703-010-0105-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02658-4_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034421154", 
              "https://doi.org/10.1007/978-3-642-02658-4_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02658-4_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034421154", 
              "https://doi.org/10.1007/978-3-642-02658-4_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-00602-9_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036660750", 
              "https://doi.org/10.1007/978-3-642-00602-9_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-00602-9_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036660750", 
              "https://doi.org/10.1007/978-3-642-00602-9_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11787006_29", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037550490", 
              "https://doi.org/10.1007/11787006_29"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11787006_29", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037550490", 
              "https://doi.org/10.1007/11787006_29"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01732644", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038261869", 
              "https://doi.org/10.1007/bf01732644"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(78)90011-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040432621"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11539452_33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040847100", 
              "https://doi.org/10.1007/11539452_33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11539452_33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040847100", 
              "https://doi.org/10.1007/11539452_33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11539452_33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040847100", 
              "https://doi.org/10.1007/11539452_33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(95)00188-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041478813"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-32033-3_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043619867", 
              "https://doi.org/10.1007/978-3-540-32033-3_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-32033-3_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043619867", 
              "https://doi.org/10.1007/978-3-540-32033-3_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-00395-5_90", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044793646", 
              "https://doi.org/10.1007/978-3-319-00395-5_90"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(03)00427-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044823399"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(03)00427-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044823399"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-85778-5_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046321257", 
              "https://doi.org/10.1007/978-3-540-85778-5_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-39698-4_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047231693", 
              "https://doi.org/10.1007/978-3-642-39698-4_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2168/lmcs-4(3:12)2008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069150951"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4204/eptcs.146.11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072354997"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4204/eptcs.193.1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072355556"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4204/eptcs.227.1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072355958"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/lics.2012.30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095598064"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-03", 
        "datePublishedReg": "2018-03-01", 
        "description": "Two-player quantitative zero-sum games provide a natural framework to synthesize controllers with performance guarantees for reactive systems within an uncontrollable environment. Classical settings include mean-payoff games, where the objective is to optimize the long-run average gain per action, and energy games, where the system has to avoid running out of energy. We study average-energy games, where the goal is to optimize the long-run average of the accumulated energy. We show that this objective arises naturally in several applications, and that it yields interesting connections with previous concepts in the literature. We prove that deciding the winner in such games is in NP\u2229coNP and at least as hard as solving mean-payoff games, and we establish that memoryless strategies suffice to win. We also consider the case where the system has to minimize the average-energy while maintaining the accumulated energy within predefined bounds at all times: this corresponds to operating with a finite-capacity storage for energy. We give results for one-player and two-player games, and establish complexity bounds and memory requirements.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00236-016-0274-1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3793837", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1133515", 
            "issn": [
              "0001-5903", 
              "1432-0525"
            ], 
            "name": "Acta Informatica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "55"
          }
        ], 
        "name": "Average-energy games", 
        "pagination": "91-127", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "be87ebc9d4178a5df4042a05bd7f37f22c9e42bec44b481c203b8508f3c27b9b"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00236-016-0274-1"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1039997237"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00236-016-0274-1", 
          "https://app.dimensions.ai/details/publication/pub.1039997237"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T12:37", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70037_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00236-016-0274-1"
      }
    ]
     

    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/s00236-016-0274-1'

    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/s00236-016-0274-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00236-016-0274-1'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00236-016-0274-1'


     

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

    200 TRIPLES      21 PREDICATES      56 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00236-016-0274-1 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 schema:author N75895604aa3940a6a54d970e3d6acc79
    4 schema:citation sg:pub.10.1007/11539452_33
    5 sg:pub.10.1007/11787006_29
    6 sg:pub.10.1007/978-3-319-00395-5_90
    7 sg:pub.10.1007/978-3-319-08867-9_30
    8 sg:pub.10.1007/978-3-540-32033-3_23
    9 sg:pub.10.1007/978-3-540-85778-5_4
    10 sg:pub.10.1007/978-3-642-00602-9_7
    11 sg:pub.10.1007/978-3-642-02658-4_14
    12 sg:pub.10.1007/978-3-642-02658-4_24
    13 sg:pub.10.1007/978-3-642-14162-1_50
    14 sg:pub.10.1007/978-3-642-36742-7_12
    15 sg:pub.10.1007/978-3-642-39698-4_15
    16 sg:pub.10.1007/bf01732644
    17 sg:pub.10.1007/bf01768705
    18 sg:pub.10.1007/s00236-013-0182-6
    19 sg:pub.10.1007/s10703-010-0105-x
    20 https://doi.org/10.1016/0012-365x(78)90011-0
    21 https://doi.org/10.1016/0304-3975(95)00188-3
    22 https://doi.org/10.1016/j.ic.2015.03.001
    23 https://doi.org/10.1016/j.ic.2015.03.010
    24 https://doi.org/10.1016/j.tcs.2012.07.038
    25 https://doi.org/10.1016/s0020-0190(98)00150-1
    26 https://doi.org/10.1016/s0304-3975(03)00427-4
    27 https://doi.org/10.1109/lics.2012.30
    28 https://doi.org/10.1145/2461328.2461370
    29 https://doi.org/10.2168/lmcs-4(3:12)2008
    30 https://doi.org/10.4204/eptcs.146.11
    31 https://doi.org/10.4204/eptcs.193.1
    32 https://doi.org/10.4204/eptcs.227.1
    33 schema:datePublished 2018-03
    34 schema:datePublishedReg 2018-03-01
    35 schema:description Two-player quantitative zero-sum games provide a natural framework to synthesize controllers with performance guarantees for reactive systems within an uncontrollable environment. Classical settings include mean-payoff games, where the objective is to optimize the long-run average gain per action, and energy games, where the system has to avoid running out of energy. We study average-energy games, where the goal is to optimize the long-run average of the accumulated energy. We show that this objective arises naturally in several applications, and that it yields interesting connections with previous concepts in the literature. We prove that deciding the winner in such games is in NP∩coNP and at least as hard as solving mean-payoff games, and we establish that memoryless strategies suffice to win. We also consider the case where the system has to minimize the average-energy while maintaining the accumulated energy within predefined bounds at all times: this corresponds to operating with a finite-capacity storage for energy. We give results for one-player and two-player games, and establish complexity bounds and memory requirements.
    36 schema:genre research_article
    37 schema:inLanguage en
    38 schema:isAccessibleForFree false
    39 schema:isPartOf N0245f5aa6ee94e1e8b259e58642cec3a
    40 Nc0b030328d2c435aa80f3d2fa9f81e14
    41 sg:journal.1133515
    42 schema:name Average-energy games
    43 schema:pagination 91-127
    44 schema:productId N6d4a011c8f264a3fb2f73cb94ba68e8b
    45 Nd1d9cd822542486aa1bfb2ee6259807f
    46 Nf9e692560404435797e62d5ea10bda8c
    47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039997237
    48 https://doi.org/10.1007/s00236-016-0274-1
    49 schema:sdDatePublished 2019-04-11T12:37
    50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    51 schema:sdPublisher N1440d351637349c0b9af9f2a0066c726
    52 schema:url https://link.springer.com/10.1007%2Fs00236-016-0274-1
    53 sgo:license sg:explorer/license/
    54 sgo:sdDataset articles
    55 rdf:type schema:ScholarlyArticle
    56 N0245f5aa6ee94e1e8b259e58642cec3a schema:volumeNumber 55
    57 rdf:type schema:PublicationVolume
    58 N1440d351637349c0b9af9f2a0066c726 schema:name Springer Nature - SN SciGraph project
    59 rdf:type schema:Organization
    60 N1e604ac5f0fd4f49b0c470b151ac1e34 rdf:first sg:person.07601744130.31
    61 rdf:rest Nfe134aa6494a42ee82cf5119529b2d25
    62 N6d4a011c8f264a3fb2f73cb94ba68e8b schema:name dimensions_id
    63 schema:value pub.1039997237
    64 rdf:type schema:PropertyValue
    65 N75895604aa3940a6a54d970e3d6acc79 rdf:first sg:person.014467443251.73
    66 rdf:rest N1e604ac5f0fd4f49b0c470b151ac1e34
    67 Nab62a809f9f54a6383f94cfbce8e59b0 rdf:first sg:person.012135303667.82
    68 rdf:rest Ncb35aef2ec27485ab87674f07b76f4e4
    69 Nc0b030328d2c435aa80f3d2fa9f81e14 schema:issueNumber 2
    70 rdf:type schema:PublicationIssue
    71 Ncb35aef2ec27485ab87674f07b76f4e4 rdf:first sg:person.015014012371.97
    72 rdf:rest rdf:nil
    73 Nd1d9cd822542486aa1bfb2ee6259807f schema:name doi
    74 schema:value 10.1007/s00236-016-0274-1
    75 rdf:type schema:PropertyValue
    76 Nf9e692560404435797e62d5ea10bda8c schema:name readcube_id
    77 schema:value be87ebc9d4178a5df4042a05bd7f37f22c9e42bec44b481c203b8508f3c27b9b
    78 rdf:type schema:PropertyValue
    79 Nfe134aa6494a42ee82cf5119529b2d25 rdf:first sg:person.016525130237.39
    80 rdf:rest Nab62a809f9f54a6383f94cfbce8e59b0
    81 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Mathematical Sciences
    83 rdf:type schema:DefinedTerm
    84 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Applied Mathematics
    86 rdf:type schema:DefinedTerm
    87 sg:grant.3793837 http://pending.schema.org/fundedItem sg:pub.10.1007/s00236-016-0274-1
    88 rdf:type schema:MonetaryGrant
    89 sg:journal.1133515 schema:issn 0001-5903
    90 1432-0525
    91 schema:name Acta Informatica
    92 rdf:type schema:Periodical
    93 sg:person.012135303667.82 schema:affiliation https://www.grid.ac/institutes/grid.5117.2
    94 schema:familyName Larsen
    95 schema:givenName Kim G.
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012135303667.82
    97 rdf:type schema:Person
    98 sg:person.014467443251.73 schema:affiliation https://www.grid.ac/institutes/grid.464035.0
    99 schema:familyName Bouyer
    100 schema:givenName Patricia
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014467443251.73
    102 rdf:type schema:Person
    103 sg:person.015014012371.97 schema:affiliation https://www.grid.ac/institutes/grid.5117.2
    104 schema:familyName Laursen
    105 schema:givenName Simon
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015014012371.97
    107 rdf:type schema:Person
    108 sg:person.016525130237.39 schema:affiliation https://www.grid.ac/institutes/grid.4989.c
    109 schema:familyName Randour
    110 schema:givenName Mickael
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016525130237.39
    112 rdf:type schema:Person
    113 sg:person.07601744130.31 schema:affiliation https://www.grid.ac/institutes/grid.464035.0
    114 schema:familyName Markey
    115 schema:givenName Nicolas
    116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07601744130.31
    117 rdf:type schema:Person
    118 sg:pub.10.1007/11539452_33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040847100
    119 https://doi.org/10.1007/11539452_33
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/11787006_29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037550490
    122 https://doi.org/10.1007/11787006_29
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-3-319-00395-5_90 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044793646
    125 https://doi.org/10.1007/978-3-319-00395-5_90
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/978-3-319-08867-9_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014016250
    128 https://doi.org/10.1007/978-3-319-08867-9_30
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/978-3-540-32033-3_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043619867
    131 https://doi.org/10.1007/978-3-540-32033-3_23
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/978-3-540-85778-5_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046321257
    134 https://doi.org/10.1007/978-3-540-85778-5_4
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/978-3-642-00602-9_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036660750
    137 https://doi.org/10.1007/978-3-642-00602-9_7
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/978-3-642-02658-4_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034421154
    140 https://doi.org/10.1007/978-3-642-02658-4_14
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/978-3-642-02658-4_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011390017
    143 https://doi.org/10.1007/978-3-642-02658-4_24
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/978-3-642-14162-1_50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007068745
    146 https://doi.org/10.1007/978-3-642-14162-1_50
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/978-3-642-36742-7_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011243039
    149 https://doi.org/10.1007/978-3-642-36742-7_12
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/978-3-642-39698-4_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047231693
    152 https://doi.org/10.1007/978-3-642-39698-4_15
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1007/bf01732644 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038261869
    155 https://doi.org/10.1007/bf01732644
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1007/bf01768705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021856463
    158 https://doi.org/10.1007/bf01768705
    159 rdf:type schema:CreativeWork
    160 sg:pub.10.1007/s00236-013-0182-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018480690
    161 https://doi.org/10.1007/s00236-013-0182-6
    162 rdf:type schema:CreativeWork
    163 sg:pub.10.1007/s10703-010-0105-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1027686195
    164 https://doi.org/10.1007/s10703-010-0105-x
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1016/0012-365x(78)90011-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040432621
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1016/0304-3975(95)00188-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041478813
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1016/j.ic.2015.03.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010847376
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1016/j.ic.2015.03.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013377026
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1016/j.tcs.2012.07.038 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017993333
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1016/s0020-0190(98)00150-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014580512
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1016/s0304-3975(03)00427-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044823399
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1109/lics.2012.30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095598064
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1145/2461328.2461370 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003894342
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.2168/lmcs-4(3:12)2008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069150951
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.4204/eptcs.146.11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072354997
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.4204/eptcs.193.1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072355556
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.4204/eptcs.227.1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072355958
    191 rdf:type schema:CreativeWork
    192 https://www.grid.ac/institutes/grid.464035.0 schema:alternateName Laboratoire Spécification et Vérification
    193 schema:name LSV, CNRS and ENS Cachan, Avenue du Président Wilson, 61, 94230, Cachan, France
    194 rdf:type schema:Organization
    195 https://www.grid.ac/institutes/grid.4989.c schema:alternateName Université Libre de Bruxelles
    196 schema:name Computer Science Department, Université libre de Bruxelles (ULB), Avenue Franklin Roosevelt, 50, 1050, Brussels, Belgium
    197 rdf:type schema:Organization
    198 https://www.grid.ac/institutes/grid.5117.2 schema:alternateName Aalborg University
    199 schema:name Aalborg University, Fredrik Bajers Vej 5, 9100, Aalborg, Denmark
    200 rdf:type schema:Organization
     




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


    ...