If the survival function of a random variable X lies to the right of the survival function of a random variable Y, then X is said to stochastically dominate Y. Inferring stochastic dominance is particularly complicated because comparing survival functions raises four possible hypotheses: identical survival functions, dominance of X over Y, dominance of Y over X, or crossing survival functions. In this paper, we suggest four-decision tests for stochastic dominance suitable for paired samples. The tests are permutation-based and do not rely on distributional assumptions. One-sided Cramér–von Mises and Kolmogorov–Smirnov statistics are employed but the general idea may be utilized with other test statistics. The power to detect dominance and the different types of wrong decisions are investigated in an extensive simulation study. The proposed tests are applied to data from an experiment concerning the individual’s willingness to pay for a given environmental improvement.