Abstract:
Two players gamble a game on a finite set $X$. For each $x\in X$, a subset $\Gamma_x\subseteq X$ and a number $\varepsilon(x)$ equal to 1 or to $-1$ are defined. Player I may move from a point $x\in\{x\colon\varepsilon(x)=1\}$ to any point $y\in\Gamma_x$; this move takes a time $t(xy)$ and gives him a payoff $g(xy)$ payed by player II. The same situation exists if to replace player I by player II and points $x\in\{x\colon\varepsilon(x)=1\}$ by $x\in\{x\colon\varepsilon(x)=-1\}$. Player I tries to maximize the average income per unit time
$$
\varphi(x_0)=\varlimsup_{n\to\infty}\frac{\sum_{k=1}^n\varepsilon(x_{k-1})g(x_{k-1}x_k)}{\sum_{k=1}^nt(x+{k-1}x_k)}
$$
Along with this game the finite game is considered which terminates when the players get to a point for the second time. The income of the 1st player is defined as the average payoff per cycle. The existence of optimal stationary policies is proved. These policies coincide with stationary ones in the infinite game. It enables to construct optimal policies by the usual linear programming method for finite games.
Fulltext:
PDF file (522 kB)