Currently there is a growing literature exploring the features of optimal monetary policy in New Keynesian models under both commitment and discretion. This literature usually solves for the optimal allocations that are consistent with a rational expectations market equiibrium, but it does not study how the policy can be implemented given the available policy instruments. Recently, however, King and Wolman (2004) have shown that a time-consistent policy cannot be implemented through the control of nominal money balances. In particular, they find that equilibria are not unique under a money stock regime. We find that their conclusion of non-uniqueness of Markov-perfect equilibria is sensitive to the instrument of choice. Surprisingly, if, instead, the monetary authority chooses the nominal interest rate, there exists a unique Markov-perfect equilibrium. We then investigate under what conditions a time-consistent planner can implement the optimal allocation by simply announcing his policy rule in a decentralized setting.