Analytical models of government formation typically assume low-dimensional real policy spaces. Behaviorally, however, politicians negotiate to form governments in high-dimensional discrete issue spaces. We model these negotiations, leveraging the fact that different politicians typically attach different importance to the same issue, allowing gains from trade to be realized when they negotiate agreed positions on a large package of issues. The set of issues in this agreed package is endogenous; politicians need not agree on every issue before they go into government together, “tabling” issues on which they agree to disagree. We exercise our model computationally, calibrating it using 91 real-world government formation settings, and mapping out the relative probability of Condorcet winning cabinets in different settings. This probability measures how hard it is for negotiators to find Condorcet winning cabinets in a giant high- dimensional state space. We test this claim empirically with a statistical model of the duration of bargaining after an election.