Given the marginal distribution information of the underlying asset price at two future times $T_1$ and $T_2$, we consider the problem of determining a model-free upper bound on the price of a class of American options that must be exercised at either $T_1$ or $T_2$. The model uncertainty consistent with the given marginal information is described as the martingale optimal transport problem. We show that any option exercise scheme associated with any market model that jointly maximizes the expected option payoff must be nonrandomized if the American option payoff satisfies a suitable convexity condition and the model-free price upper bound and its relaxed version coincide. The latter condition is desired to be removed under appropriate conditions on the cost and marginals.