Cyclical games with prohibitions |
| |
Authors: | Alexander V. Karzanov Vasilij N. Lebedev |
| |
Affiliation: | (1) Institute for Systems Studies, 9 Prospect 60 Let Oktyabrya, 117312 Moscow, Russia;(2) Institute of Physics and Technology, Moscow, Russia |
| |
Abstract: | We consider a certain combinatorial game on a digraph for two cases of the price function. For one case the game in question extends the cyclical game studied in Ehrenfeucht and Mycielski (1979) and Gurvitch, Karzanov and Khachiyan (1988) which, in its turn, is a generalization of the well-known problem of finding a minimum mean cycle in an edge-weighted digraph. We prove the existence of optimal uniform stationary strategies for both cases and give algorithms to find such strategies.This work was partially supported by Chaire municipale , Mairie de Grenoble. |
| |
Keywords: | Digraph cyclical game stationary strategy mean cycle |
本文献已被 SpringerLink 等数据库收录! |
|