Generalized second price auction is optimal for discrete types

- The Generalized Second Price Auction is commonly used by search engines.
- The Generalized Second Price Auction is shown to be optimal for the sale of a good.
- The result is based on linear programming duality and submodular minimization.

We prove that a variant of the second price auction for the sale of a single good through a Bayesian incentive compatible mechanism that maximizes expected revenue of the seller is optimal when the type space is discrete. Moreover, we show that this variant is related to the widely used generalized second price auction mechanism in keyword-auctions for advertising, thus providing a theoretical justification for a practical tool.