Mechanism Design, Machine Learning, and Pricing Problems

Consider a seller with multiple digital goods or services for sale, such as movies, soft-ware, or network services, over which buyers may have complicated preferences. In order to sell these items through an incentive-compatible auction mechanism, this mechanism should have the property that each bidder is offered a set of prices that do not depend on the value of her bid. The problem of designing a revenue-maximizing auction is known in the economics literature as the optimal auction design problem [Myerson 1981]. The classical model for optimal auction design assumes a Bayesian setting in which players’ valuations (types) are drawn from some probability distribution that furthermore is known to the mechanism designer. For example, to sell a single item of fixed marginal cost, one should set the price that maximizes the profit margin per sale times the probability a random person would be willing to buy at that price. However, in complex or non-static environments, these assumptions become unrealistic. In these settings, machine learning can provide a natural approach to the design of near-optimal mechanisms without such strong assumptions or degree of prior knowledge. Specifically, notice that while a truthful auction mechanism should have the propert