Let's say we have a transition matrix of
From \ To Alpha Beta Gamma Delta
Alpha 0 0.5 0 0.5
Beta 0.7 0 0.3 0
Gamma 0.5 0.1 0 0.4
Delta 0.4 0.2 0.4 0
which can be solved to come up with steady state transition probabilities of
Alpha: 34.9%
Beta: 24.0%
Gamma: 16.9%
Delta: 24.2%
Now, imagine Alpha, Beta, Gamma, and Delta are agents and they can alter only their own transition rows (i.e. how much they decide to link to the other agents). I'm also imagining that agents cannot link to themselves at all (hence the 0s along the diagonal). How would Delta change its row's transitions probabilities so as to maximize its own steady state probability? For example, if it unilaterally sent all of its "to" probability to Alpha, its steady state probability would increase to 25.2%, and if shifted all of its probability to Gamma, its steady state probability would increase even more to 25.8%. That's a bit interesting because Alpha has a higher probability of shifting to Delta than does Gamma, so the heuristic of "shift to the agent that links most strongly to me" doesn't always maximize one's own steady state probability.
Abstracting from this example, the general question is: Given a N X N transition matrix of N agents in which rows sum to 1, how can an agent maximize their steady state probability by adjusting only their own row's transition probabilities? Is the agent's steady state probability always maximized by assigning a transition probability of 1 to one agent, and 0 to all other agents?
Best Answer
Let $m_{ij}$ denote the expected number of steps in the Markov chain, starting from state $i$, to get to state $j$. (In particular, let $m_{ii}$ denote the expected number of steps to leave $i$ and return.)
These can also be computed with a system of equations: to find $m_{1j}, m_{2j}, \dots, m_{nj}$ all at once, the equations are $$ m_{ij} = 1 + \sum_{k \ne j} P_{ik} m_{kj} $$ for $i=1, \dots, n$. The idea is that to find $m_{ij}$, you take one step in the Markov chain, then average $m_{kj}$ over all states you could be in next, weighted by the probability of ending up in them.
A theorem about Markov chains says that if the Markov chain is irreducible, then there is a unique stationary distribution $\vec{\pi}$, and $\pi_i$ (the stationary probability of state $i$) is $\frac1{m_{ii}}$. Therefore, if state $i$ can change its transition probabilities, it maximizes $\pi_i$ by minimizing $\frac1{m_{ii}}$.
The equation we wrote down earlier for $m_{ii}$ is $$ m_{ii} = 1 + \sum_{j \ne i} P_{ij} m_{ji} $$ so to minimize $m_{ii}$, it's best for state $i$ to set $P_{ij}=1$ for the state $j$ which has the least expected time $m_{ji}$.
Let $\vec{m}$ be the vector $(m_{ji})_{i \ne j}$ of all these expected times. In terms of your transition matrix $P$, let $P'$ be the matrix with row and column $i$ removed. Then the system of equations we wrote down earlier can be summarized as $$ \vec{m} = \vec{1} + P'\vec{m} $$ or $(I - P')\vec{m} = \vec{1}$.
(Compare this with the stationary equations $\vec{\pi}(I - P) = \vec{0}$. Among other differences, the stationary vector $\vec{\pi}$ is a row vector that is left-multiplied by $I-P$, while $\vec{m}$ is a column vector we right-multiply by $I-P'$.)
In your example, we have $$ P' = \begin{bmatrix}0 & 0.5 & 0 \\ 0.7 & 0 & 0.3 \\ 0.5 & 0.1 & 0 \end{bmatrix} \qquad I-P' = \begin{bmatrix}1 & -0.5 & 0 \\ -0.7 & 1 & -0.3 \\ -0.5 & -0.1 & 1\end{bmatrix} $$ and the vector $\vec{m}$ is $(I-P')^{-1}\vec{1} \approx (2.97248, 3.94495, 2.88073)$.
This tells us that Delta should send all its probability to the state Gamma, which returns to Delta in $m_{\gamma,\delta} \approx 2.88073$ steps. This will make the expected return time to Delta $m_{\delta,\delta} \approx 3.88073$, and the stationary probability of Delta will be $\pi_{\delta} \approx \frac1{3.88073} \approx 0.257683$.