We consider the problem of optimal decision making under uncertainty but assume that the decision maker's utility function is not completely known. Instead, we consider all the utilities that meet some criteria, such as preferring certain lotteries over certain other lotteries and being risk averse, s-shaped, or prudent. This extends the notion of stochastic dominance. We then give tractable formulations for such decision making problems. We formulate them as robust utility maximization problems, as optimization problems with stochastic dominance constraints, and as robust certainty equivalent maximization problems. We use a portfolio allocation problem to illustrate our results.