On the Complexity of Market Equilibria and Revenue Maximization

This thesis consists of two parts. In the first part, we concentrate on the computation of Market Equilibria and settle the long-standing open problem regarding the computation of an approximate Arrow-Debreu market equilibrium in markets with CES utilities. We prove that the problem is PPAD-complete when the Constant Elasticity of Substitution parameter $\rho$ is any constant less than -1. Building on this result, we introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory, and prove that it is PPAD-hard to compute an approximate Arrow-Debreu market equilibrium in markets with linear and non-monotone utilities. In the second part, we study Revenue Maximization. We begin by resolving the complexity of the revenue-optimal Bayesian Unit-demand Item Pricing problem when the buyer's values for the items are independent. We show that the problem can be solved in polynomial time for distributions of support size 2; but its decision version is NP-complete for distributions of support size 3. Next, we study the optimal mechanism design problem for a single unit-demand buyer with item values drawn from independent distributions. We show that, for distributions of support-size 2 and the same high value, Item Pricing can achieve the same revenue as any menu of lotteries. On the other hand, we provide simple examples where randomization improves revenue. Finally, we show that unless the polynomial-time hierarchy collapses, namely P^{NP}=P^{#P}, there is no universal efficient randomized algorithm that implements an optimal mechanism even when distributions have support size 3