Computing Optimal Auctions

This past week has been spent on trying to answer the following question: in the case of the additive buyer, does there exist a set of valuation classes and a distribution over these classes such that there is the strict gap in the revenue of the optimal buy-\(n\) and buy-\((n+1)\) incentive-compatible mechanism. Recall, that for a mechanism to be buy-\(k\) incentive-compatible, it means that it is always in a buyer's utility maximizing interest to purchase a single menu option compared to any multi-set of menu options of size at most \(k\). Under this definition, we already know that the revenue of the optimal buy-\(n\) incentive-compatible mechanism for a given set of valuation classes and distribution is at least as much as the optimal buy-\((n+1)\) incentive-compatible mechanism (see [1]). The question is whether we can come up with an general input for which there is a strict separation.

I was able to code the linear program found in [2] which computes the optimal buy-1 incentive-compatible mechanism. We wanted to come up with an example input for \(n=2\) with these previously described properties. This required us to compute the optimal buy-2 incentive-compatible mechanism and optimal buy-3 incentive compatible-mechanism. Unfortunately, once we jump to the buy-2 case, we no longer have linear constraints. Rather, we have introduced some quadratic constraints due to the lottery function. Again, unfortunately, I was able to prove we cannot encode the quadratic constraints as a positive semi-definite (PSD) matrix. This means that our program is not convex. Luckily, Gurobi, a optimization solver, is able to handle non-convex quadratic constraints. Using this library, I was able to create a program to find the optimal buy-2 incentive-compatible menu for a given input. I was then able to check to see if this menu was also buy-3 incentive-compatible. By finding a small example, we hope that it could be suggestive of a way to formulate a general input to achieve a strict separation.

After trying many, many inputs, I was finally able to find an input which leads to a optimal mechanism which is buy-2 incentive-compatible but not buy-3 incentive compatible. While this does not necessarily mean that there is a revenue drop off between the two classes for the input (since I am not able to actually compute the optimal buy-3 incentive-compatible menu for the input due to cubic constraints), it is still a useful example to play with. We are currently trying to generalize it so we can get it to work with \(n\) items. Beyond this development, George and I have also begun to type up our results in Latex.

References

[1] Assadi, Sepehr, and Ariel Schvartzman. "Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling." arXiv preprint arXiv:2205.14312 (2022).
[2] Briest, Patrick, Shuchi Chawla, Robert Kleinberg, and S. Matthew Weinberg. "Pricing lotteries." Journal of Economic Theory 156 (2015): 144-174.