Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

Abstract

Subadditive and fractionally subadditive valuations are among the most well-studied classes of set functions in algorithmic game theory and discrete optimization. Not only is the fractionally subadditive class strictly contained in the subadditive class, but there also exist subadditive valuations which are very far from being fractionally subadditive in a very precise quantitative sense, as demonstrated by Bhawalkar and Roughgarden in [BR11]. This difference between fractional subadditivity and subadditivity is not only theoretical. It has important implications, for example, in the design of posted price mechanisms and in the concentration properties of the respective set functions. As the gap between fractionally subadditive set functions and subadditive set functions is large, there might be valuations which are "in between" those classes. While we cannot directly use the strong properties implied by fractional subadditivity for such functions "in between", it might also be inefficient to use the weaker properties implied by subadditivity instead. This motivates us to undertake the first systematic study of the space between fractionally subadditive and subadditive set functions. We define a chain of classes parametrized by an integer q ranging from q = 2 (corresponding to the subadditive case) to q = m, where m is the size of the ground set (corresponding to the fractionally subadditive case). For a fixed q, we call the respective class of valuations over [m] = {1, 2, . . . , m} q-partitioning. Our "interpolation" between fractional subadditivity and subadditivity satisfies three desirable properties: smoothness (as described in Theorem 3.2.1), interpretability (as described in Section 4), and existence of classes (as described in Proposition 2.1.3). The highlights of the current paper are two. On the more applied side, we design an Ω( log log q log log m )-competitive posted price mechanism for q-partitioning players. This matches asymptotically the state-of-the-art results in both the subadditive case and the fractionally subadditive case. On the more theoretical side, we establish upper tail bounds of the following form. Let v be a q-partitioning set function over [m] and S ⊆ [m] be a random set in which elements appear independently. Then, for any a, k > 0 and suitable δ (depending on q), we can bound P[v(S) ≥ (1 + δ)a + k] ≤ (1 + δ) −kP[v(S) ≤ a] −(1+δ) . The larger the value of q is, the smaller the value of δ can be and, thus, the more "fine-grained" the inequality is. To prove this result, we develop a new isoperimetric inequality using Talagrand’s method of ªcontrol by q points,º which might be of independent interest. We also discuss other probabilistic inequalities and game-theoretic applications of q-partitioning valuations.