## Discounting the Future in Systems Theory

*Luca de Alfaro,
Thomas A. Henzinger,
and Rupak Majumdar*

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.

*Proceedings of the
30th International Colloquium on Automata, Languages, and Programming*
(ICALP),
Lecture Notes in Computer Science 2719,
Springer, 2003, pp. 1022-1037.

Download inofficial, sometimes updated
PostScript /
PDF document.
© 2003 Springer.