Extending Results to Unit-Demand Buyers

This week has been primarily spent trying to extend [1]'s results from buyers with additive valuations to buyers with unit-demand valuations. In the case of additive valuations, a buyer's valuation for a group of items is simply the sum of their valuations for each individual item. Another popular model is unit-demand valuations, where a buyer's valuation for a group of items is equal to maximum value item in the group. Essentially, in this setting, the buyer only really cares about receiving one item from the store.

In Briest et al. [2], they show that item pricing achieves within a \(log(n)\) factor of optimal revenue buy-many mechanism when buyers have unit-demand valuations. In their framework, if a buyer has a valuation vector \(v\) and receives an allocation vector of \(q\) (where \(||q||_1 \leq 1\)) at a price \(p\), their (expected) utility of buying one menu item (hence called a lottery ticket) is \(<v,q>\) - \(p\). The expected ultilty of buying a multi-set of lottery tickets is more complicated to express compared to the additive case.

Our work this week has been spent understanding what is the correct definition in the unit-demand case for the expected utility of purchasing a multi-set of lottery tickets. Our hope is that we will be able to reuse much of the machinery of [1].

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.