Every finite recursive game has near-optimal stationary strategies that are simple monomials in the accuracy epsilon, and for fixed state count these can be computed exactly in polynomial time.
The Matrix of Maximum Out Forests of a Digraph and Its Applications
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We study the maximum out forests of a (weighted) digraph and the matrix of maximum out forests. A maximum out forest of a digraph G is a spanning subgraph of G that consists of disjoint diverging trees and has the maximum possible number of arcs. If a digraph contains any out arborescences, then maximum out forests coincide with them. We provide a new proof to the Markov chain tree theorem saying that the matrix of Ces`aro limiting probabilities of an arbitrary stationary finite Markov chain coincides with the normalized matrix of maximum out forests of the weighted digraph that corresponds to the Markov chain. We discuss the applications of the matrix of maximum out forests and its transposition, the matrix of limiting accessibilities of a digraph, to the problems of preference aggregation, measuring the vertex proximity, and uncovering the structure of a digraph.
citation-role summary
background 1
citation-polarity summary
fields
cs.GT 1years
2026 1verdicts
ACCEPT 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Existence and computation of monomial families of near-optimal strategies for recursive games
Every finite recursive game has near-optimal stationary strategies that are simple monomials in the accuracy epsilon, and for fixed state count these can be computed exactly in polynomial time.