Introduction to Buy-k Mechanisms

Since Myerson's seminal 1981 paper [1], the field of Auction Design has witnessed a plethora of research activity. During the summer of 2022, we seek to add to this trend by investigating and developing the theory of buy-\(k\) mechanisms in Auction Design. Our work will build from the foundation laid by the recent paper by Assadi and Schvartzman [2], which defines the notion of buy-\(k\) mechanisms (a generalization of buy-many mechanisms).

Our Setting

Our work revolves around a setting in which there is a single seller and buyer. Let's call the seller Alice and the buyer Bob. Suppose, Alice has two items to sell: oranges and apples. She would like to construct a menu for her store in such a way as to maximize her expected revenue when Bob walks into her store. Alice's menu can consist of different options, where each option yields an allocation to Bob (for example an apple or orange or both) in exchange for a price. Meanwhile, Bob has a private valuation for the apple and orange (and the combination of both of them). If Alice knew these valuations, then she could easily construct a revenue maximizing menu. However, she does not know this private information. Rather, she knows the (possibly correlated) distributions \(D_{apples},D_{oranges}\) from which Bob samples inorder to realize his valuations for the items.

Under this setting, it has been shown that Alice can devise a menu and pricing scheme which leads to unbounded revenue compared to any "simple" menu scheme. This scheme relies on utilizing random allocations with super-additive prices. For example, Alice may charge 5 dollars for an apple and 5 dollars for an orange when each item is bought separately but when they are bought together she may charge 11 dollars. Since Bob is only allowed to interact with Alice once (buy-one mechanism), it may be in Bob's utility-maximizing interest to purchase this overpriced combination of items.

To circumvent these unintuitive properties, the notion of buy-many mechanisms were introduced. Under the buy-many mechanism model, Bob is allowed to interact with Alice as many times as he wishes. This effectively prevents Alice from charging super-additive prices since Bob can achieve the same allocation by simply interacting with Alice mulitple times and purchasing the items separately. Chawla et al. [3] has shown under the buy-many mechanism model that item pricing, a "simple" mechanism, can achieve within a factor \(O(log(n))\) of the optimal revenue mechanism, where \(n\) is the number of items and assuming arbitrarily correlated distributions.

In recent work, Assadi and Schvartzman [2] generalize the concept of buy-many mechanisms to buy-\(k\) mechanisms inorder to help understand the gap between buy-one mechanisms (unbounded revenue gap) and buy-many mechanisms (\(O(log(n))\) revenue gap). As part of their paper, they prove that when \(k=n\) bundling, another simple mechanism, achieves within a \(O(n^3)\) fraction of the revenue of the optimal buy-\(n\). They also show that that when \(k = \Theta(n^{1/2-\epsilon})\), the revenue gap between the optimal buy-\(k\) mechanism and bundling may be exponential.

Our Goals

Our goal this summer will be to expand on the work laid out in [2]. There are several potential directions of interest. The primary direction would be to understand how the gap between optimal revenue mechanism and bundling changes as we interpolate \(k\) between \(\Theta(n^{1/2-\epsilon})\) (exponential revenue gap) and \(n\) (polynomial revenue gap). Additionally, in the paper, they also only consider the case where buyer's exhibit additive valuations. Another popular notion is called unit-demand, where a buyer's demand for a group of items is equal to their maximum valuation for any single item in the group. We will attempt to extend their results to hold in the unit-demand case. Finally, we would also like to investigate whether revenue continuity holds under buy-\(k\) mechanisms.

References

[1] Myerson, Roger B. "Optimal auction design." Mathematics of operations research 6.1 (1981): 58-73.
[2] Assadi, Sepehr, and Ariel Schvartzman. "Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling." arXiv preprint arXiv:2205.14312 (2022).
[3] Chawla, Shuchi, Yifeng Teng, and Christos Tzamos. "Buy-many mechanisms are not much better than item pricing." Games and Economic Behavior 134 (2022): 104-116.