q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations
share
For a set M of m elements, we define a decreasing chain of classes of normalized monotone-increasing valuation functions from 2^M to ℝ_≥ 0, parameterized by an integer q ∈ [2,m]. For a given q, we refer to the class as q-partitioning. A valuation function is subadditive if and only if it is 2-partitioning, and fractionally subadditive if and only if it is m-partitioning. Thus, our chain establishes an interpolation between subadditive and fractionally subadditive valuations. We show that this interpolation is smooth, interpretable , and non-trivial. We interpolate prior results that separate subadditive and fractionally subadditive for all q ∈{2,…, m}. Two highlights are the following:(i) An Ω(loglog q/loglog m)-competitive posted price mechanism for q-partitioning valuations. Note that this matches asymptotically the state-of-the-art for both subadditive (q=2) [DKL20], and fractionally subadditive (q=m) [FGL15]. (ii)Two upper-tail concentration inequalities on 1-Lipschitz, q-partitioning valuations over independent items. One extends the state-of-the-art for q=m to q<m, the other improves the state-of-the-art for q=2 for q > 2. Our concentration inequalities imply several corollaries that interpolate between subadditive and fractionally subadditive, for example: 𝔼[v(S)]≤ (1 + 1/log q)Median[v(S)] + O(log q). To prove this, we develop a new isoperimetric inequality using Talagrand's method of control by q points, which may be of independent interest. We also discuss other probabilistic inequalities and game-theoretic applications of q-partitioning valuations, and connections to subadditive MPH-k valuations [EFNTW19].
READ FULL TEXT