A Graph Theoretic Approach to Markets for Indivisible Goods

Many important markets, such as the housing market, involve goods that are both indivisible and of budgetary significance. We introduce new graph theoretic techniques ideally suited to analyzing such markets. In this paper and its companion (Caplin and Leahy [2010]), we use these techniques to fully characterize the comparative static properties of these markets and to identify algorithms for computing equilibria.