Complexity Constrained Walrasian Equilibria: Welfare Loss and Market Structure


Walrasian market clearing requires solving a large-scale optimization (or, potentially, fixed-point) problem. Algorithms for the auctioneer to solve these problems may be bounded by the curse-of-dimensionality - known in computer science as infeasibility - or, with some luck and structure, polynomial algorithms in number of agents and/or the number of signals. Moreover, high information content of idiosyncratic states could exhaust the limited (information-theoretic) bandwidth or computational resources of the auctioneer. The core questions in applying computational bounds to equilibrium are: (1) if there are a huge number of agents, do limitations on the computability and/or bandwidth in calculating the equilibrium lead to misallocation?; and (2) do these constraints change the optimal market structure?.

Work in Progress