The following is too large for a comment and definitely not an answer.

Fix $n \in \mathbb{N}$ and let $\cal{P}$ be the set of stochastic $n \times n$-matrices with $\text{diag}(P) = 0$. Let further $$\mathcal{E} := \left\{\pi \in \mathbb{R}^n \colon \pi_i \geq 0, \sum \pi_i = 1, \exists P \in \mathcal{P} \text{ with } \pi \cdot P = \pi\right\},$$ each $\pi$ being a row vector. Then both $\mathcal{P}$ and $\mathcal{E}$ are compact convex subsets of $\mathbb{R}^{n \times n}$ resp. $\mathbb{R}^n$ and not empty if $n \geq 2$ and for $n = 2$ we have $\mathcal{E} = \{(0.5,0.5\}$. The problem is that $(1,0,\ldots,0), \ldots, (0,0,\ldots,1) \not\in \mathcal{E}$.

But for large $n$ it seems (I have no proof) it seems that almost any random stochastic $\pi$ is in $\mathcal{E}$. For this case your original problem is equivalent to "Find a $P \in \mathcal{P}$ with $\pi \cdot P = \pi$". Here the explicit construction of a homogeneous Markov chain with transition probability matrix $P$ (appropriately chosen) may be helpful to get a "feeling" for the solution. Of course this is impossible to formalize.

It seems to me that for $n$ large using numerical methods may be too heavy for this sort of problem. Edit (I've just seen the answer of Israel) A reformulation as a linear programm with criterion $$\sum P_{ii} = \min!$$ and variables $P_{ij}$ is possible.

The following is too large for a comment and definitely not an answer.

Fix $n \in \mathbb{N}$ and let $\cal{P}$ be the set of stochastic $n \times n$-matrices with $\text{diag}(P) = 0$. Let further $$\mathcal{E} := \left\{\pi \in \mathbb{R}^n \colon \pi_i \geq 0, \sum \pi_i = 1, \exists P \in \mathcal{P} \text{ with } \pi \cdot P = \pi\right\},$$ each $\pi$ being a row vector. Then both $\mathcal{P}$ and $\mathcal{E}$ are compact convex subsets of $\mathbb{R}^{n \times n}$ resp. $\mathbb{R}^n$ and not empty if $n \geq 2$ and for $n = 2$ we have $\mathcal{E} = \{(0.5,0.5\}$. The problem is that $(1,0,\ldots,0), \ldots, (0,0,\ldots,1) \not\in \mathcal{E}$.

But for large $n$ it seems (I have no proof) it seems that almost any random stochastic $\pi$ is in $\mathcal{E}$. For this case your original problem is equivalent to "Find a $P \in \mathcal{P}$ with $\pi \cdot P = \pi$". Here the explicit construction of a homogeneous Markov chain with transition probability matrix $P$ (appropriately chosen) may be helpful to get a "feeling" for the solution. Of course this is impossible to formalize.

It seems to me that for $n$ large using numerical methods may be too heavy for this sort of problem. Edit (I've just seen the answer of Robert Israel) A reformulation as a linear programm with criterion $$\sum P_{ii} = \min!$$ and variables $P_{ij}$ is possible.

The following is too large for a comment and definitely not an answer.

Fix $n \in \mathbb{N}$ and let $\cal{P}$ be the set of stochastic $n \times n$-matrices with $\text{diag}(P) = 0$. Let further $$\mathcal{E} := \left\{\pi \in \mathbb{R}^n \colon \pi_i \geq 0, \sum \pi_i = 1, \exists P \in \mathcal{P} \text{ with } \pi \cdot P = \pi\right\},$$ each $\pi$ being a row vector. Then both $\mathcal{P}$ and $\mathcal{E}$ are compact convex subsets of $\mathbb{R}^{n \times n}$ resp. $\mathbb{R}^n$ and not empty if $n \geq 2$ and for $n = 2$ we have $\mathcal{E} = \{(0.5,0.5\}$. The problem is that $(1,0,\ldots,0), \ldots, (0,0,\ldots,1) \not\in \mathcal{E}$.

But for large $n$ it seems (I have no proof) it seems that almost any random stochastic $\pi$ is in $\mathcal{E}$. For this case your original problem is equivalent to "Find a $P \in \mathcal{P}$ with $\pi \cdot P = \pi$". Here the explicit construction of a homogeneous Markov chain with transition probability matrix $P$ (appropriately chosen) may be helpful to get a "feeling" for the solution. Of course this is impossible to formalize.

It seems to me that for $n$ large using numerical methods may be too heavy for this sort of problem. Unfortunately a reformulation as a linear programm with criterion $$\sum \pi_i = \min!$$ and variables $\pi_i$ and $P_{ij}$ seems not possible due to the term $\pi \cdot \mathcal{P} $.

The following is too large for a comment and definitely not an answer.

Fix $n \in \mathbb{N}$ and let $\cal{P}$ be the set of stochastic $n \times n$-matrices with $\text{diag}(P) = 0$. Let further $$\mathcal{E} := \left\{\pi \in \mathbb{R}^n \colon \pi_i \geq 0, \sum \pi_i = 1, \exists P \in \mathcal{P} \text{ with } \pi \cdot P = \pi\right\},$$ each $\pi$ being a row vector. Then both $\mathcal{P}$ and $\mathcal{E}$ are compact convex subsets of $\mathbb{R}^{n \times n}$ resp. $\mathbb{R}^n$ and not empty if $n \geq 2$ and for $n = 2$ we have $\mathcal{E} = \{(0.5,0.5\}$. The problem is that $(1,0,\ldots,0), \ldots, (0,0,\ldots,1) \not\in \mathcal{E}$.

But for large $n$ it seems (I have no proof) it seems that almost any random stochastic $\pi$ is in $\mathcal{E}$. For this case your original problem is equivalent to "Find a $P \in \mathcal{P}$ with $\pi \cdot P = \pi$". Here the explicit construction of a homogeneous Markov chain with transition probability matrix $P$ (appropriately chosen) may be helpful to get a "feeling" for the solution. Of course this is impossible to formalize.

It seems to me that for $n$ large using numerical methods may be too heavy for this sort of problem. Edit (I've just seen the answer of Israel) A reformulation as a linear programm with criterion $$\sum P_{ii} = \min!$$ and variables $P_{ij}$ is possible.