We conduct a laboratory experiment to study a decentralized market where goods are differentiated and evaluations are private. We implement different semi-structured bargaining protocols based on deferred acceptance, and we compare their performance to the benchmark scenario of a sealed-bid auction. We show that bargaining dramatically improves efficiency, mainly to the benefit of players rather than the silent auctioneer. A protocol of unconstrained simultaneous bargaining performs best, doubling the proportion of deals relative to the benchmark. This is because participants seek to reveal information through a gradual bidding-up strategy that favors bargaining environments. Aggregate efficiency nonetheless suffers from the fact that buyers bargain harder than sellers, and that some players over-bargain to appropriate a larger share of the unknown surplus.