We model decentralized team formation as a game in which players make offers to potential teams whose members then either accept or reject the offers. The games induce no-delay subgame perfect equilibria with unique outcomes that are individually rational and match soulmates. We provide sufficient conditions for equilibria to implement core coalition structures, and show that when each player can make a sufficiently large number of proposals, outcomes are Pareto optimal. We then design a mechanism to implement equilibrium of this game and provide sufficient conditions to ensure that truthful reporting of preferences is a strong ex post Nash equilibrium. Moreover, we show empirically that players rarely have an incentive to misreport preferences more generally. Furthermore, for the problem with cardinal preferences, we show empirically that the resulting mechanism results in significantly higher social welfare than serial dictatorship, and the outcomes are highly equitable.