If $A$ is a stochastic matrix, then $A$ is entry-wise nonnegative and $Ae = e$, i.e., $(1,e)$ is a right eigenpair for $A$.
Is it true that there exists a vector $b$ such that
$$(A - I)x \geq b$$
has no solutions in $x$? If so, is there a simple proof?
Motivation: I've been trying to construct an answer to another question using linear programming duality (as the OP implies he is interested in). If my reasoning is correct, this is the only step I need to complete the argument. I feel like this should be an easy question to answer, but I've been working on it for a while with no success.
Your inequality $(A-I)x \ge b$ has no solutions in $x$ as soon as $b>0$. Indeed, any potential solution would have to satisfy $A x \ge x + b$ and, since rows of $A$ are nonnegative and sum to one, each element of vector $Ax$ is a convex combination of the components of $x$, which must be less than $x_{max}$, the largest component of $x$. On the other hand, at least one element of $x+b$ is greater than $x_{max}$, which proves the impossibility.
By the way, applying Farkas' Lemma to this impossible system shows that the following always admits solutions in y $$y^T (A-I) = 0, y \ge 0 \text{ and } y^T b > 0$$ which expresses the fact that $A$ necessarily admits a nonnegative left eigenvector with eigenvalue $1$ (the last inequality ensures that $y$ is nonzero).