Approximations for Economic Efficiency and Fairness

Abstract

Efficiency and fairness are two major objectives in designing economic systems -- they provide guidelines on the desirability of economic solutions. However, perfectly efficient and fair utopian economies are often nonexistent or impractical, due to incentives, lack of information, computational hardness, etc. In this dissertation, we address this impossibility with methodology from the study of approximation algorithms. Through various cases in the field of computational economics, we demonstrate how to establish and improve the design of provably guaranteed approximations on an ideal yet impossible level of efficiency and fairness. En route, we resolve several open questions in computational social choice and mechanism design.