Mind the Revenue Gap: On the Performance of Approximation Mechanisms Under Budget Constraints

We consider a buyer-seller interaction where the revenue-maximizer seller has one object to allocate and the buyer has private valuation and private budget. The presence of private budgets is one among the several triggers of complexity in mechanism design models. Che and Gale [8] show that the optimal mechanism for this setting may require a continuum of menu entries. We focus on a restricted class of simple mechanisms, consisting of those whose associated menus have a small number of entries. We show that for distributions supported on \([1,\overline{v}] \times [1 ,\overline{w}]\) , an arbitrarily high fraction of the optimal revenue can be obtained using a simple mechanism with poly-logarithmic menu size. This result applies even if the valuation and budget are arbitrarily correlated. However, if the distribution has unbounded support, then any selling mechanism that contains a fixed number of menu entries cannot guarantee any positive fraction of the optimal revenue. In fact, we are able to strengthen this negative result and show that, for some family of finite distributions, any mechanism that contains an asymptotically sub-linear number of menu entries (in the size of the finite support) cannot guarantee a positive fraction of the optimal revenue.