The Internet has emerged the single most important platform for resource sharing among parties with diverse and selfish interests and is the most interesting economics system of our time. As rapidly as new Internet systems are developed and deployed, Internet users find ways to exploit them for their own benefit in ways not intended by the designers. Prevalent undesirable examples of this phenomenon include spam in email systems, bid-sniping and shill bidding in eBay’s auction marketplace, free-loading in file-sharing networks, and click-fraud in Internet advertising. The existence of these economic bugs brings to fore the urgent problem of developing a principled approach to designing systems where exploits are not economically viable. This is the general question addressed by the research area of ‘algorithmic mechanism design’.
Techniques from algorithms are very well suited for addressing both new and traditional economic questions. In this talk I will highlight three of these: computation, reduction, and approximation. I will introduce the research area of ‘algorithmic pricing’ which looks at the question of computing a pricing (e.g., on items in a supermarket) given a known demand (e.g., the preferences of shoppers). I will reduce algorithmic mechanism design, where the demand is unknown, to algorithmic pricing. The reduction I will give is based on random sampling, it preserves approximations, and its analysis makes the connection between mechanism design and machine learning theory concrete. This approach is very generally applicable; however, in this talk I will focus on the economic objective of profit maximization.
(For economists: Motivated by the Wilson docitrine we propose a method for the design and analysis of incentive compatible mechanisms in a prior free environment. Our approach allows for general non-quasi-linear utility functions and optimization of profit or social welfare.)