Analysis of Prophet Inequalities for Subadditive Combinatorial Auctions

Abstract

In this paper, we attempt to effectively design a posted price mechanism that achieves an O(1) prophet inequality for general subadditive valuations. Precisely, we consider static, anonymous, and item prices which yields a very simple sequential auction model with a price menu. We present current state of the art mechanisms in [PDTKL17] (balanced pricing) and [KL20] which provide an O(log m) and an O(log log m) prophet inequality respectively. Regarding improving their current guarantees to o(log m) and o(log log m) respectively, we show impossibility results.

Moreover, in this paper, we consider a relaxation coined as bundled pricing where we no longer enforce item pricing in hopes of a better approximation guarantee. One such example of bundled prices was seen in Combinatorial Walrasian Equilibria from [FGL13] which achieve a 2-approximation in complete information. Unfortunately, this result does not extend to the Bayesian setting as we show by proving that the above bundled pricing rule is not balanced. Next, we consider the existence of balanced bundled prices that achieve constant factor approximations. In fact, we prove impossibility results regarding guarantees of the form o(log m) when m ≤ n using a reduction technique to balanced item prices. For the other case, we show existence of appropriate balanced bundled prices for general m and n = 1. We conclude with a conjecture regarding the relationship between the number of agents and the complexity of the valuation class for which there exist appropriate balanced bundled prices.