We study negotiations over multiple goods or dimensions when the maximum potential surplus that can be reached is known but the bundle of goods or decisions that realizes that surplus involves two-sided incomplete information. We use theory and controlled laboratory experiments to show that in such settings efficient trade is possible despite substantial asymmetric information. Moreover, we show that achieving efficient outcomes depends on having sufficiently rich negotiation protocols. By contrast, if agents negotiate over every good separately, then all equilibria are inefficient. We extend the theory and experiments to instances in which the surplus is either approximately known or unknown.