Randomization
and Simplification in Dynamic Decision Making
Ehud
Kalai and Eilon Solan
Journal
of Economic Theory, to appear.
Randomization adds beneficial
flexibility to the construction of optimal simple plans in dynamic environments.
A decision maker, restricted to the use
of simple plans, may find a stochastic plan that
strictly outperforms all deterministic ones.
This is true even in non interactive deterministic environments where the
decision maker’s choices have no influence on his signals nor on
the future evolution of the system.
We describe a natural decomposition of simple plans into two components:
an action selection rule and a behavior
modification rule.
In non interactive environments optimal
simple plans do not require randomization in the action selection rule.
Only randomization in the behavior
modification rule may be necessary.