Multi-Unit Combinatorial Prophet Inequalities

Shuchi Chawla, Trung Dang, Zhiyi Huang, Yifan Wang · 2025

Read Multi-Unit Combinatorial Prophet Inequalities by Shuchi Chawla, Trung Dang, Zhiyi Huang, Yifan Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-16054.txt.

Introduction

Shuchi Chawla, Trung Dang, Zhiyi Huang, and Yifan Wang study how selling many copies of each item changes prophet inequalities for online allocation, in work from twenty twenty-five. A prophet inequality bounds how well sequential pricing does against hindsight perfection. Buyers here hold flexible values over bundles.

Fixed item prices do worse in the multi unit world than in the single item one, a real gap. Letting prices move as sales proceed closes the gap in the limit. The team also builds prices set in advance that rise as stock runs low. Those prices need only a rough estimate of each item's hindsight value. Their guarantee improves strictly as supply grows.

Catalog record

CREATORShuchi Chawla, Trung Dang, Zhiyi Huang, Yifan Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE107 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-16054

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multi-Unit Combinatorial Prophet Inequalities Shuchi Chawla, Trung Dang, Zhiyi Huang, Yifan Wang Abstract We consider a combinatorial auction setting where buyers have fractionally subadditive (XOS) valuations over the items and the seller’s objective is to maximize the social welfare. A prophet inequality in this setting bounds the competitive ratio of sequential allocation (often using item pricing) against the hindsight optimum. We study the dependence of the competitive ratio on the number of copies, k k , of each item. We show that the multi-unit combinatorial setting is strictly harder than its single-item counterpart in that there is a gap between the competitive ratios achieved by static item pricings in the two settings. However, if the seller is allowed to change item prices dynamically , it becomes possible to asymptotically match the competitive ratio of a single-item static pricing. We also develop a new non-adaptive anonymous multi-unit combinatorial prophet inequality where the item prices are determined up front but increase as the item supply decreases. Setting the item prices in our prophet inequality requires minimal information about the buyers’ value distributions – merely (an estimate of) the expected social welfare accrued by each item in the hindsight optimal solution suffices. Our non-adaptive pricing achieves a competitive ratio that increases strictly as a function of the item supply k k . 1 Introduction In recent years strong connections have emerged between Bayesian mechanism design and optimal stopping problems called prophet inequalities. One surprising implication of these connections is that for many combinatorial auction settings, social welfare can be approximately maximized through a sequential pricing mechanism. Consider, for example, a book store hosting a book fair with many titles on sale. Suppose that every buyer has unit demand with different values for different books. The store’s goal is to maximize the total value buyers receive from purchasing the books. Instead of holding an auction where all buyers participate simultaneously, the store can simply place a fixed price on every item and allow buyers to purchase their favorite books at the posted prices asynchronously until supplies last. A seminal result of Feldman et al. (2014) shows that this sequential pricing mechanism obtains at worst half of the optimal expected social welfare. This type of result is called a prophet inequality. Sequential posted pricing mechanisms such as the one described above have many nice properties that make them practical. From the viewpoint of the buyers, they are easy to understand, involve no strategizing, and do not require buyers to divulge their private values. From the viewpoint of the seller, they are easy to implement and are robust to small changes in the market (e.g. the order in which buyers arrive). The question of how well they can approximate the optimal social welfare is therefore well motivated. In this paper we study posted price mechanisms in combinatorial multi-unit settings . Consider again the book fair example described above. Suppose that the seller has at least k copies of each book available for sale for some k>1 . Is it possible for the seller to price the books in a manner that obtains strictly more than half of the optimal social welfare? This question is well-understood in the single-item setting where the seller has k>1 copies of just one item to sell. Hajiaghayi et al. (2007) showed that selling the item at a fixed price until supply runs out achieves competitive ratio that increases with k as 1-O(\sqrt{\log k/k}) . Alaei (2014) showed that even better asymptotic performance ( 1-O(1/\sqrt{k}) ) can be obtained by changing prices dynamically. Most recently, Chawla et al. (2024) and Jiang et al. (2023) obtained upper and lower bounds on the performance of different kinds of posted pricing mechanisms that are tight for every value of k . In comparison, the combinatorial setting is less well understood. We focus in this paper on settings where buyers have fractionally subadditive (XOS) values over the items. For this setting, Feldman et al. (2014) showed that item pricing obtains a competitive ratio of 1/2 , and this ratio is tight for k=1 even in the single item case. For k>1 , however, it was not known prior to our work whether one could achieve a competitive ratio better that 1/2 or potentially match the performance of Alaei or Chawla et al. ’s single item pricings. Dynamic versus static pricings. The answer to this question depends on how much flexibility the seller has in setting the prices. We distinguish, in particular, between dynamic and static item pricing mechanisms. In the former, the seller can choose prices for a buyer based on the entire history of the mechanism up to that point including the identities of previously arrived buyers, their valuations, and the item supply left. In a static item pricing, in contrast, the seller sets prices on items up front, and the same prices are offered to each buyer as long as supplies last. Dynamic item pricings offer more flexibility to the seller and can therefore potentially obtain a better competitive ratio. One may further ask whether general online allocation algorithms, that do not offer the buyers a pricing at all and may not even be truthful, can obtain an even better competitive ratio. Surprisingly, in the combinatorial single-unit ( k=1 ) setting of Feldman et al. with XOS buyers, there is no gap between general online allocation and static item pricing: the latter obtains a competitive ratio of 1/2 , which is tight for online algorithms even in the setting of allocating a single item to two buyers. On the other hand, for the single item k -unit setting, Jiang et al. (2023) prove that static item pricing is strictly weaker than dynamic item pricing. 1 1 1 For the single item setting, every online allocation algorithm can be trivially seen as a dynamic pricing algorithm. We additionally consider a third kind of sequential item pricing mechanism that is stronger than static item pricing but shares many of its nice properties. In supply-based static pricing the price of each item can depend upon the amount of supply of the item left, but the same prices are offered to each buyer regardless of their identity or the timing of their arrival. For example, the seller at the book fair may price the first 10 copies of a book at a discounted price and the remaining copies at a higher amount. Observe that supply-based pricing is anonymous like static item pricing, and does not require buyers to divulge their identities or value functions to the mechanism. The role of information. A nice feature of Feldman et al. ’s 1/2 -competitive pricing is that the mechanism requires very little information about the instance to compute the prices. In particular, the price of every item is set equal to half the total welfare accrued by that item in the optimal solution. Observe that this welfare contribution of each item depends only on the values obtained by the buyers for the items they receive and not on their entire valuation function (other than its influence on the optimal allocation itself). The mechanism designer can therefore estimate these welfare contributions for a given target allocation far more easily than estimating the

Read the complete text