Abstract:
In a remarkable paper \cite{Vohra} (and a more detailed research monograph \cite{vohra2}) using linear programming duality and submodular optimization tools, Vohra established the discrete type space analogs of the celebrated optimal auction design results of Myerson \cite{myerson} for the sale of a single good through a Bayesian incentive compatible mechanism that maximizes expected revenue of the seller. According to \cite{Vohra}, a possible implementation of the optimal mechanism is a second price auction with reserve. We show that this statement calls for an adjustment. More precisely, the discrete nature of the type space requires a modification of the second price with reserve auction structure. The result of the modification, a discrete second price auction, is related to the generalized second price auction mechanism widely used in keyword auctions for online advertising, thus providing a theoretical justification for a practical tool. We also establish that a second price auction with reserve is optimal in the limit in a discrete type setting when we quantize the types, i.e., we allow only types that are multiples of a given value. Thus, our observation gives a simple generalization of an earlier result of Harris and Raviv \cite{hr}.