Separating the Revenue-Optimal Buy-\(k\) and Buy-(\(k+1\)) Auction

This week a great deal of progress was made on finding an example which observes a revenue gap between the optimal buy-\(k\) and buy-\((k+1)\) incentive compatible menu. Specifically, I was able to construct a new, nicer example compared to last week's which witnesses a gap between the revenue of its optimal buy-2 and buy-3 incentive-compatible menu. To verify this gap, I was able to use the program from last week to compute the optimal buy-2 incentive compatible revenue for this distribution. Then, I was also able to write a new program to compute the optimal buy-3 incentive-compatible mechanism for a distribution by encoding the cubic constraints using quadratic and linear terms. By introducing some new variables and constraints, Gurobi (the solver) is able to solve for the optimal menu in this case.

There are several nice properties in this new example. Specifically, there appears be a very simple way of computing the optimal buy-\(k\) incentive-compatible menu for arbitrary \(k\). Further, it appears that this example should yield a strict gap in revenue between the optimal buy-\(k\) and buy-\((k+1)\) incentive-compatible mechanism, which would be an exciting research development. My current main challenge is proving that my way of generating the revenue-optimal menu is indeed revenue-optimal (i.e. there doesn't exist some other menu which achieves greater revenue).

I've spent quite a bit of time thinking about how to show this and I've made some progress on showing how to transform any revenue-optimal solution into a specific form without losing revenue or incentive-compatiblilty, but more work is needed. This will be my main focus for the rest of the coming week.