Progress in the Unit-Demand Direction

This past week we made quite a bit of progress on extending [1]'s constructions for the unit-demand valuations. Specifically, we managed to reformulate the lottery function from [1] to work for unit demand valuations. As part of this effort, I generated the following (unwieldy and not nice) unit-demand version of function:

\(Lot_1(\Delta) = 1 - \Pi_{i = 1}^m(1-x_{i,1})\)
\(Lot_j(\Delta) = \left(1- \sum_{i = 1}^{j-1}Lot(\Delta)_i\right) \cdot \sum_{k = 1}^m \left((-1)^{k-1} \cdot \sum_{I \subseteq [m], |I| = k} \Pi_{l \in I} \left(\frac{x_{l,j}}{ 1 - \sum_{a < l} x_{l,a}}\right)\right)\)

As it turns out, there exists a much simpler form of this same function. With this simpler defintion in hand, George and I managed to show that the gap between the revenue of the optimal buy-\(n\) mechanism and bundling is finite. The more specific bound currently illudes us due to technical intricacy related to whether all the buyer types have the same total order over the valuations of the items.

Besides this progress, I have also created a python program to automatically calculate several of the functions which are relevant to our bounds. In the coming week, I hope to use this program to help us discover bad instances which witness a large gap between the revenue of optimal and simple mechanisms.

References

[1] Assadi, Sepehr, and Ariel Schvartzman. "Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling." arXiv preprint arXiv:2205.14312 (2022).