Abstract
Computing market equilibria is an important practical problem for marketdesign (e.g. fair division, item allocation). However, computing equilibriarequires large amounts of information (e.g. all valuations for all buyers forall items) and compute power. We consider ameliorating these issues by applyinga method used for solving complex games: constructing a coarsened abstractionof a given market, solving for the equilibrium in the abstraction, and liftingthe prices and allocations back to the original market. We show how to boundimportant quantities such as regret, envy, Nash social welfare, Paretooptimality, and maximin share when the abstracted prices and allocations areused in place of the real equilibrium. We then study two abstraction methods ofinterest for practitioners: 1) filling in unknown valuations using techniquesfrom matrix completion, 2) reducing the problem size by aggregating groups ofbuyers/items into smaller numbers of representative buyers/items and solvingfor equilibrium in this coarsened market. We find that in real dataallocations/prices that are relatively close to equilibria can be computed fromeven very coarse abstractions.