Computing Equilibrium Prices in Exchange Economies with Tax Distortions

We consider the computation of equilibrium prices in market settings where purchases of goods are subject to taxation. While this scenario is a standard one in applied computational work, so far it has not been an object of study in theoretical computer science. Taxes introduce significant distortions: equilibria are no longer Pareto optimal, sufficient conditions for uniqueness do not continue to guarantee it, existence itself must be revisited. We analyze the effects of these distortions on scenarios which, in the absence of taxes, admit polynomial time algorithms. In spite of the loss of certain structural properties (including uniqueness), we are able to obtain polynomial time algorithms or approximation schemes in several instances where the model without taxes admitted them.