Abstract:
The article specifies the top estimate of complexity of potential transformations algorithm for solving cyclic games on graphs. This estimate is close to the lower estimate. The authors obtained the data on optimal deviation to solving cyclic games with temporary function on the oriented graphs. The finiteness of the algorithm results in high level of complexity. The article contains the analysis of exponential estimate of algorithm's iterations.
Keywords:full data cyclic games, positional games, stationary Nash equilibrium, guaranteed time complexity, algorithm of potential transformations.
Fulltext:
PDF file (329 kB)