The paper examines the theoretical foundations of the hold-up problem. At a first stage, one agent decides on the level of a relationship-specific investment. There is no contract, so at a second stage the agent must bargain with a trading partner over the surplus that the investment has generated. We show that the conventional underinvestment result hinges crucially both on the assumed bargaining game and on the choice of equilibrium concept. In particular, we prove the following two results. (i) If bargaining proceeds according to the Nash demand game, any investment level is subgame perfect, but only efficient outcomes are stochastically stable. (ii) If bargaining proceeds according to the ultimatum game (with the trading partner as proposer), only the minimal investment level is subgame perfect, but any investment level is stochastically stable.