Citation
Luca de Alfaro, Tom Henzinger, Rupak Majumdar. "Discounting the Future in Systems Theory". Proc. of the 30th International Colloquium on Automata, Languages, and Programming (ICALP), 2003.

Abstract
Discounting the future means that the value, today, of a unit payoff is 1 if the payoff occurs today, a if it occurs tomorrow, a 2 if it occurs the day after tomorrow, and so on, for some real-valued discount factor 0 < a < 1. Discounting (or inflation) is a key paradigm in economics and has been studied in Markov decision processes as well as game theory. We submit that discounting also has a natural place in systems engineering: for nonterminating systems, a potential bug in the far-away future is less troubling than a potential bug today. We therefore develop a systems theory with discounting. Our theory includes several basic elements: discounted versions of system properties that correspond to the omega-regular properties, fixpoint-based algorithms for checking discounted properties, and a quantitative notion of bisimilarity for capturing the difference between two states with respect to discounted properties. We present the theory in a general form that applies to probabilistic systems as well as multicomponent systems (games), but it readily specializes to classical transition systems. We show that discounting, besides its natural practical appeal, has also several mathematical benefits. First, the resulting theory is robust, in that small perturbations of a system can cause only small changes in the properties of the system. Second, the theory is computational, in that the values of discounted properties, as well as the discounted bisimilarity distance between states, can be computed to any desired degree of precision.

Electronic downloads

• http://dx.doi.org/10.1007/3-540-45061-0_79

• HTML

  Luca de Alfaro, Tom Henzinger, Rupak Majumdar. <a
  href="http://chess.eecs.berkeley.edu/pubs/732.html"
  >Discounting the Future in Systems Theory</a>,
  Proc.  of the 30th International Colloquium on Automata,
  Languages, and Programming (ICALP), 2003.

• Plain text

  Luca de Alfaro, Tom Henzinger, Rupak Majumdar.
  "Discounting the Future in Systems Theory". Proc. 
  of the 30th International Colloquium on Automata, Languages,
  and Programming (ICALP), 2003.

• BibTeX

  @inproceedings{deAlfaroHenzingerMajumdar03_DiscountingFutureInSystemsTheory,
      author = {Luca de Alfaro and Tom Henzinger and Rupak Majumdar},
      title = {Discounting the Future in Systems Theory},
      booktitle = {Proc.  of the 30th International Colloquium on
                Automata, Languages, and Programming (ICALP)},
      year = {2003},
      abstract = { Discounting the future means that the value,
                today, of a unit payoff is 1 if the payoff occurs
                today, a if it occurs tomorrow, a 2 if it occurs
                the day after tomorrow, and so on, for some
                real-valued discount factor 0 < a < 1. Discounting
                (or inflation) is a key paradigm in economics and
                has been studied in Markov decision processes as
                well as game theory. We submit that discounting
                also has a natural place in systems engineering:
                for nonterminating systems, a potential bug in the
                far-away future is less troubling than a potential
                bug today. We therefore develop a systems theory
                with discounting. Our theory includes several
                basic elements: discounted versions of system
                properties that correspond to the omega-regular
                properties, fixpoint-based algorithms for checking
                discounted properties, and a quantitative notion
                of bisimilarity for capturing the difference
                between two states with respect to discounted
                properties. We present the theory in a general
                form that applies to probabilistic systems as well
                as multicomponent systems (games), but it readily
                specializes to classical transition systems. We
                show that discounting, besides its natural
                practical appeal, has also several mathematical
                benefits. First, the resulting theory is robust,
                in that small perturbations of a system can cause
                only small changes in the properties of the
                system. Second, the theory is computational, in
                that the values of discounted properties, as well
                as the discounted bisimilarity distance between
                states, can be computed to any desired degree of
                precision.},
      URL = {http://chess.eecs.berkeley.edu/pubs/732.html}
  }
  

Posted by Christopher Brooks on 4 Nov 2010.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.