Complexity of Verification of Nondeterministic Probabilistic
Multiagent Systems

M. K. Valiev and M. I. Dekhtyar

Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, Moscow, Russia

Tver State University, Tver, Russia

e-mail: valiev@keldysh.ru, Michael.Dekhtyar@tversu.ru

Received October 18, 2010

Abstract—Probabilistic systems of interacting nondeterministic intelligent agents are considered. The
states of agents in such systems are probabilistic databases (of facts), and their actions are controlled by
probabilistic logical programs. Besides, communication channels between agents are also probabilistic.
It is shown how such systems can be transformed in poynomial time to equivalent finite Markov decision
processes. This makes it possible to translate the known results on the verification of the dynamic prop-
erties of the finite Markov processes to the probabilistic multiagent systems of the considered type.

Keywords: probabilistic multiagent systems, Markov chains and decision processes, temporal logics,
verification of dynamic properties.

DOI: 10.3103/S0146411611070169

Pleiades Publishing home page | journal home page | top

If you have any problems with this server, contact webmaster.