Interactive evolutionary algorithms for multi-objective opti- mization have gained an increasing interest in recent years. As multi- objective optimization usually deals with the optimization of conflicting objectives, a decision maker is involved in the optimization process when encountering incomparable solutions. We study the impact of a decision maker from a theoretical perspective and analyze the runtime of evolu- tionary algorithms until they have produced for the first time a Pareto optimal solution with the highest preference of the decision maker. Con- sidering the linear decision maker, we show that many multi-objective optimization problems are not harder than their single-objective coun- terpart. Interestingly, this does not hold for a decision maker using the Chebeyshev utility function. Furthermore, we point out situations where evolutionary algorithms involving a linear decision maker have difficulties in producing an optimal solution even if the underlying single-objective problems are easy to be solved by simple evolutionary algorithms.