Optimization and Games for Controllable Markov Chains

<p>This book considers a class of ergodic finite controllable Markov's chains. The main idea behind the method described in this book is to develop the original discrete optimization problems (or game models) in the space of randomized formulations where the variables stand in for the distributions (mixed strategies or preferences) of the original discrete (pure) strategies in the use. The following suppositions are made: a finite state space a limited action space continuity of the probabilities and rewards associated with the actions and a necessity for accessibility. These hypotheses lead to the existence of an optimal policy. The best course of action is always stationary. It is either simple (i.e. nonrandomized stationary) or composed of two nonrandomized policies which is equivalent to randomly selecting one of two simple policies throughout each epoch by tossing a biased coin. As a bonus the optimization procedure just has to repeatedly solve the time-average dynamic programming equation making it theoretically feasible to choose the optimum course of action under the global restriction. In the ergodic cases the state distributions generated by the corresponding transition equations exponentially quickly converge to their stationary (final) values. This makes it possible to employ all widely used optimization methods (such as Gradient-like procedures Extra-proximal method Lagrange's multipliers Tikhonov's regularization) including the related numerical techniques. In the book we tackle different problems and theoretical Markov models like controllable and ergodic Markov chains multi-objective Pareto front solutions partially observable Markov chains continuous-time Markov chains Nash equilibrium and Stackelberg equilibrium Lyapunov-like function in Markov chains Best-reply strategy Bayesian incentive-compatible mechanisms Bayesian Partially Observable Markov Games bargaining solutions for Nash and Kalai-Smorodinsky formulations multi-traffic signal-control synchronization problem Rubinstein's non-cooperative bargaining solutions the transfer pricing problem as bargaining.<br></p>