In this paper, we study ex post strategy-proofness (ESP), a natural notion of strategy- proofness in settings with interdependent values. ESP requires that, for every agent, truthful reporting is always optimal regardless of the strategies and types of other agents. For environments with transfers, ESP implementability is characterized by a generalized cyclical monotonicity condition. Alternatively, implementability can be characterized by an optimality condition related to an induced matching problem between types and alternatives. In an important class of environments where types satisfy a generalized “one-dimensionality” property, implementability is equivalent to a simple monotonicity condition where “higher” types receive “higher” alternatives. Using this finding, we show that for a single object auction, more allocation rules are implementable if either the type space is less dense or the extent of preference interdependence is less severe. For environments without transfers, nontrivial implementation is possible only when preferences exhibit sufficient independence. In the context of binary and ternary voting models, we illustrate how this condition significantly constrains the scope of implementation.