q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

Bangachev, Kiril; Weinberg, S. Matthew

doi:10.4230/LIPIcs.ICALP.2025.18

$q$ -Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

Kiril Bangachev

EECS Department, MIT, Cambridge, MA, USA S. Matthew Weinberg

Department of Computer Science, Princeton University, NJ, USA

Abstract

For a set $M$ of $m$ elements, we define a decreasing chain of classes of normalized monotone-increasing valuation functions from $2^{M}$ to $\mathbb{R}_{\geq 0}$ , parameterized by an integer $q\in[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 ( $q$ -partitioning valuations are “nearly” $(q-1)$ -partitioning in a precise sense, Theorem 6), interpretable (the definition arises by analyzing the core of a cost-sharing game, à la the Bondareva-Shapley Theorem for fractionally subadditive valuations, Section 3.1), and non-trivial (the class of $q$ -partitioning valuations is distinct for all $q$ , Proposition 3).

For domains where provable separations exist between subadditive and fractionally subadditive, we interpolate the stronger guarantees achievable for fractionally subadditive valuations to all $q\in\{2,\ldots,m\}$ . Two highlights are the following:

i)

An $\Omega\left(\frac{\log\log q}{\log\log m}\right)$ -competitive posted price mechanism for $q$ -partitioning valuations. Note that this matches asymptotically the state-of-the-art for both subadditive ( $q=2$ ) [22], and fractionally subadditive ( $q=m$ ) [32].
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: $\mathbb{E}[v(S)]\leq(1+1/\log q)\text{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 [25].

Keywords and phrases:

Subadditive Functions, Fractionally Subadditive Functions, Posted Price Mechanisms, Concentration Inequalities

Category:

Track A: Algorithms, Complexity and Games

Funding:

S. Matthew Weinberg: Supported by NSF CCF-1955205. During Professor Weinberg’s development of this paper, he participated as an expert witness on behalf of the State of Texas in ongoing litigation against Google (the “Google Litigation”).

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algorithmic mechanism design ; Mathematics of computing

\rightarrow

Probability and statistics ; Theory of computation

\rightarrow

Computational pricing and auctions

Related Version:

Full Version: https://arxiv.org/pdf/2304.01451 [5]

Acknowledgements:

We are thankful to Jan Vondrak for a helpful discussion which led to the inequalities based on Talagrand’s method of control by q points. We are also thankful to the anonymous reviewers for helpful remarks on the exposition.

DOI:

10.4230/LIPIcs.ICALP.2025.18

Event:

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Editors:

Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

1.1 Motivation

Functions of the form $f:2^{M}\longrightarrow\mathbb{R}$ are a fundamental object of study in the fields of Algorithmic Game Theory and Combinatorial Optimization. For example, when $M$ is a set of items in an auction, $f(S)$ could indicate the value that an agent obtains from receiving the bundle $S$ (see more about combinatorial auctions in [44, Chapter 11]). When $M$ is a set of agents, $f(S)$ could indicate the cost that agents $S$ need to pay in order to purchase a given service together (see more about cost sharing in [44, Chapter 15]).

As set functions¹¹1We will use the terms set function and valuation interchangeably in the rest of the paper. This convention is motivated by the setting of combinatorial auctions in which $f(S)$ indicates the “value” of the subset of items $S .$ are motivated by real world processes – auctions, cost sharing, and job scheduling among others – the mathematical study of such functions usually assumes that they satisfy certain natural properties. Throughout the paper, we assume that all valuations satisfy the following two simple technical properties: they are monotone ( $f(S)\leq f(T)$ whenever $S\subseteq T$ ) and normalized ( $f(\emptyset)=0$ ). Economic considerations give rise to more complex conditions on set functions. For example, frequently imposed is the condition of diminishing marginal values, also known as submodularity. Another condition motivated by economics is complement-freeness in the values that an agent obtains from bundles of items, which is also known as subadditivity. Finally, one could be interested in the existence of prices which incentivize cooperation among agents when purchasing a given service; this turns out to be equivalent to the fractionally subadditive property (see Section 3.1).²²2In this paper, the terms “submodularity”, “fractional subadditivity”, and “subadditivity” imply monotonicity and normalization.

In this paper, we focus our attention on fractionally subadditive and subadditive set functions. Trivially, fractionally subadditive functions are a smaller class strictly contained in the class of subadditive functions. Something stronger turns out to be true – Bhawalkar and Roughgarden show the existence of subadditive functions which are very far from being fractionally subadditive in a precise quantitative sense [6]. This difference between fractionally subadditive and subadditive valuations is not purely theoretical and has important implications. For example, in the context of combinatorial auctions, there exists a posted price mechanism that gives a $(1/2)$ -approximation to the optimal welfare when all players have fractionally subadditive valuations [32], but the best known approximation ratio for subadditive valuations is $\Omega(\frac{1}{\log\log m}),$ where $m$ is the number of items [22] (moreover, the [32] framework providing a $(1/2)$ -approximation for XOS provably cannot beat $O(\log m)$ for subadditive, and the [22] framework provably cannot beat $O(\log\log m)$ ). A recent breakthrough [13] established a constant-factor prophet inequality for subadditive valuations, but it is not achieved via a posted-price mechanism. Similarly, in the context of concentration inequalities, a fractionally subadditive valuation $v$ has $\mathbf{E}[v]$ -subgaussian lower tails (see [52, Corollary 3.2]), but such a strong dimension-free concentration provably does not hold for subadditive valuations (see [52, Section 4]).

What if a set function is “somewhere in between being subadditive and being fractionally subadditive”? On the one hand, as it is not fractionally subadditive, one cannot use the strong guarantees of fractional subadditivity (such as in posted price mechanisms or subgaussian concentration) when analyzing it. On the other hand, as the set function could be significantly more structured than an arbitrary subadditive function, it is perhaps inefficient to simply use the much weaker properties guaranteed by subadditivity (especially, those that provably cannot be improved for all subadditive functions). Our goal in this paper is to fill this gap by providing intermediate results for functions “in between being subadditive and being fractionally subadditive” in instances where a separation between the (known) guarantees for subadditive and XOS functions exists. This is a novel direction which complements the growing literature on demonstrating a separation between the guarantees for subadditive and XOS functions ([52, 6, 20] and others).

Explicitly, we define a chain of function classes that starts with fractionally subadditive set functions and expands to subadditive set functions. Our goal is to understand how the behaviour of these function classes changes along the chain. We focus on several setups in which subadditive and fractionally subadditive valuations have received significant attention in the literature, and in which provable separations already exist between subadditive and fractionally subadditive valuations. That is, we focus on domains in which strong claims known for fractionally subadditive valuations provably do not hold for all subadditive valuations, and we seek to interpolate these results along our hierarchy.

1.2 Results Part I: Defining $𝒒$ -partitioning valuations

Our chain of classes is parametrized by a positive integer parameter $q$ ranging between $q=|M|$ (which corresponds to the fractionally subadditive case) and $q=2$ (which corresponds to the subadditive case). The number $q$ corresponds to the complexity of fractional covers under which the valuation function is non-diminishing. We call the respective classes $q$ -partitioning and the resulting interpolation the partitioning interpolation. We give a formal definition in Definition 2. We then establish that the partitioning interpolation satisfies several desirable properties:

$\blacksquare$

Interpretability: In Section 3.1, we present an economic interpretation of $q$ -partitioning via the core of a cost-sharing game à la the Bondareva-Shapley theorem which characterizes fractionally subadditive valuations [7, 49] – See also [44, Theorem 15.6]. In slightly more detail, say there is a service that can be acquired by set $S$ of players if they together pay $c(S)$ . One can then ask, for any subset $T\subseteq[m]$ whether or not there exist non-negative prices $\{p_{i}\}_{i\in T}$ such that: a) $\sum_{i\in T}p_{i}=c(T)$ (service is purchased for $T$ ) and b) for all $S\subseteq T$ , $\sum_{i\in S}p_{i}\leq c(S)$ (no set $S\subseteq T$ wishes to deviate and purchase the service just for themselves). The Bondareva-Shapley theorem, applied to monotone normalizd cost functions, states that such prices exist for all $T$ if and only if $c(\cdot)$ is fractionally subadditive.

Consider instead modifying the game so that players are grouped into $q$ fully-cooperative cities (that is, cities will always act as a coherent unit, and will act in the best interest of the entire city). One can then ask, for any subset $T\subseteq[m]$ and any partitioning of $T$ into $q$ cities $T_{1},\ldots,T_{q}$ , do there exist non-negative prices $\{p_{i}\}_{i\in[q]}$ such that: a) $\sum_{i\in[q]}p_{i}=c(T)$ (service is purchased for $T$ ) and b) for all $S\subseteq[q]$ , $\sum_{i\in S}p_{i}\leq c(\cup_{i\in S}T_{i})$ (no set $S$ of cities wishes to deviate and purchase the service just for themselves). Proposition 10 establishes that such prices exist for all $T$ and all partitionings of $T$ into at most $q$ cities if and only if $c(\cdot)$ is $q$ -partitioning.
$\blacksquare$

Smoothness of The Interpolation: In Theorem 6, we show that our chain of classes is smooth in the sense that every $q$ -partitioning valuation is almost $(q+1)$ -partitioning. Formally, Theorem 6 establishes that the class of $q$ -partitioning valuations is $(1-1/q)$ -close to the class of $(q+1)$ -partitioning valuations. We provide a formal definition of closeness in Definition 5, but note briefly here that it is the natural extension of closeness to XOS valuation functions from [6] extended to $q<m$ . Also, every $q$ -partitioning valuation is $(q-1)$ -partitioning. Thus, the classes are “smoothly expanding along the interpolation.”
$\blacksquare$

Existence of Classes: In Proposition 3, we show that for each $m=|M|$ and $2\leq q\leq m,$ there exist $q$ -partitioning valuations over $M$ that are not $(q+1)$ -partitioning. In other words, none of the $m-1$ classes “collapses” to a lower level.

1.3 Results Part II: Posted price mechanisms and concentration inequalities

Our main results apply the partitioning interpolation to two canonical problems where subadditive and fractionally subadditive valuations are provably “far apart.” Our main results provide analyses that smoothly degrade from fractionally subadditive to subadditve as $q$ decreases – this enables stronger guarantees for wide classes of structured subadditive functions which (provably) cannot be obtained for all subadditive functions.

Posted Price Mechanisms.

Posted price mechanisms are a core objective of study within Algorithmic Game Theory, including multi-dimensional mechanism design [11], single-dimensional mechanism design [53, 2], and the price of anarchy [32, 20]. Posted price mechanisms list a price $p_{i}$ for each item $i\in[m]$ , then visit the bidders one at a time and offer them to purchase any remaining set $S$ of items at price $\sum_{i\in S}p_{i}$ (and these items become unavailable for all future bidders). Of course, strategic players will pick the remaining set $S$ that maximizes $v_{i}(S)-\sum_{i\in S}p_{i}$ .

Of key importance to multiple of these agendas is the following basic question: to what extent can posted price mechanisms optimize welfare in Bayesian settings? Specifically, assume that each bidder $i$ ’s valuation function $v_{i}(\cdot)$ is drawn independently from a known distribution $D_{i}$ over valuations in some class $\mathcal{V}$ . The optimal expected welfare is $\mathbb{E}_{\vec{v}\leftarrow\times_{i}D_{i}}[\max_{\text{partitions }S_{1},% \ldots,S_{n}}\{\sum_{i}v_{i}(S_{i})\}]$ . When strategic players participate in a posted-price mechanism with prices $\vec{p}$ , some other partition of items is selected, guaranteeing some other expected welfare. What is the maximum $\alpha(\mathcal{V})$ such that for all $D=\times_{i}D_{i}$ supported on $\mathcal{V}$ , there exists a posted-price mechanism guaranteeing expected welfare at least an $\alpha(\mathcal{V})$ -fraction of the optimal welfare? Besides being the main question of study in works such as [32, 20, 22], resolving this question has downstream implications for revenue-maximization in multi-dimensional settings due to [10].

For the class of fractionally subadditive valuations, [32] establish a $1/2$ -approximation, which also implies a $1/\log_{2}(m)$ -approximation for subadditive valuations. However, their techniques provably cannot yield stronger guarantees for subadditive valuations [6, 20]. Recent breakthrough work of [22] designs a new framework for subadditive valuations that yields an $\Omega(1/\log_{2}\log_{2}(m))$ -approximation, but aspects of their framework also provably cannot provide stronger guarantees. In this sense, there is a strong separation between the state-of-the-art guarantees on posted price mechanisms for fractionally subadditive and subadditive valuations (and also, there is a permanent separation between what can be achieved within the aforementioned frameworks).

Main Result I.

Our first main result provides an $\Omega(\frac{\log\log q}{\log\log m})$ -competitive posted price mechanism when all distributions are supported on $q$ -partitioning valuations. This is stated in Theorem 16.
Note that this guarantee matches both the constant factor approximation in the fractionally subadditive case (setting $q=m$ ) and the $\Omega(\frac{1}{\log\log m})$ factor in the subadditive case (setting $q=2$ ) and interpolates between the two approximation factors when $q$ is in between. In particular, note that this matches the state-of-the-art in both extremes, and matches the best guarantees achievable by the [22] approach in both extremes.

Concentration Inequalities.

Consider a function $f$ , and a set $S$ selected by randomly including each item $i$ independently (not necessarily with the same probability). It is often of interest to provide upper tail bounds on the distribution of $f(S)$ compared to $\mathbf{E}[f(S)]$ . McDiarmid’s inequality is one such example when $f$ is $1$ -Lipschitz.³³3 $f(\cdot)$ is $1$ -Lipschitz if $|f(S)-f(S\cup\{i\})|\leq 1$ for all $S, i$ . When $f(\cdot)$ is subadditive or fractionally subadditive, even stronger upper tail bounds are possible [52].

For example, if $f$ is both $1$ -Lipschitz and subadditive, Schechtman’s inequality implies that the probability that $f(S)$ exceeds twice its median plus $x$ decays exponentially in $x$ [48].⁴⁴4Schechtman’s inequality is more general than this, but this is one common implication. See (2) for the general statement. Importantly, Schechtman’s inequality provably cannot “kick in” arbitrarily close to the median for all subadditive functions [52].

Main Result II.

Theorem 20 improves Schechtman’s inequality across the partitioning interpolation. In particular, our improvement implies that for all $1$ -Lipschitz and $q$ -partitioning $f$ , the probability that $f(S)$ exceeds $1+O(1/\log_{2}q)$ times its median plus $x$ decays exponentially in $x$ . This is stated in Theorem 20 . In particular, Theorem 20 makes use of a new isoperimetric inequality – Theorem 21 – that may be of independent interest.⁵⁵5Note that this result, and that of [48] applies in a more general setting where there is a collection of independent random variables $X_{1},\ldots,X_{m}$ , that parameterize a function $f_{\vec{X}}:2^{[m]}\rightarrow\mathbb{R}$ , which is subadditive for all $\vec{X}$ . Like [52], we provide proofs in the canonical setting referenced in the text for simplicity of exposition.

Similarly, if $f$ is both $1$ -Lipschitz and fractionally subadditive, [52] establishes that $f$ is self-bounding. [8] establish “Chernoff-Bernstein-like” concentration inequalities on self-bounding functions, which in particular imply that $f(S)$ has $\mathbf{E}[f(S))]$ -subgaussian lower tails and slightly weaker upper tails.⁶⁶6A random variable $X$ is $\sigma^{2}$ -subgaussian if the following inequality holds. The log-moment generating function defined by $\psi_{X}(\lambda):=\log\mathbf{E}[\exp(\lambda(X-\mathbf{E}[X]))]$ exists for all real numbers $\lambda$ and, furthermore, satisfies $\psi_{X}(\lambda)\leq\frac{\lambda^{2}\sigma^{2}}{2}.$ It is well known that if $X$ is $\sigma^{2}$ -subgaussian, then $\mathbf{P}[X\geq\mathbf{E}[X]+t]\leq\exp(-\frac{t^{2}\sigma^{2}}{2})$ and $\mathbf{P}[X\leq\mathbf{E}[X]-t]\leq\exp(-\frac{t^{2}\sigma^{2}}{2}).$ We again note that this strong guarantee provably does not hold for all subadditive functions [52] – there is provably a separation between how well subadditive and fractionally subadditive concentrate. Therefore, the purpose of our results is to interpolate the stronger guarantees achievable for fractionally subadditive valuations along our hierarchy.

Main Result III.

Theorem 19 extends this across the partitioning interpolation. Specifically, our result establishes that for all $1$ -Lipschitz and $q$ -partitioning $f$ , $f(S)$ is $(\lceil m/q\rceil,0)$ -self bounding, which implies by [43, 9] that $f(S)$ has a $\lceil m/q\rceil\cdot\mathbf{E}[f(S)]$ -subgaussian lower tail and a slightly worse Bernstein-like upper tail.
It is worth noting that [48], based on Talagrand’s method of control by $q$ points, is the state-of-the-art for concentration of subadditive functions, while [52], based on the method of self-bounding functions [8, 43, 9], is state-of-the-art for fractionally subadditive functions. Our main results extend both across the partitioning interpolation, but neither of the two approaches yields “tight” results at both ends – our extension of [48] gives sharper results for small $q$ , and our extension of [52] gives sharper results for larger $q$ . This is to be expected, as the two methods are genuinely distinct.

1.4 Related Work and Connection to Subadditive MPH- $𝒌$

Hierarchies of Valuation Functions.

Prior to our work, there has been significant interest in exploring the space of valuation functions with parameterized complementarities [1, 28, 30, 31, 33, 34, 24]. That is, the simplest level of the hierarchy is (fractionally) subadditive valuations, the second level of the hierarchy already contains functions that are not subadditive, and the final level of the hierarchy contains all monotone functions. These works are distinct from ours in that they explore the space between (fractionally) subadditive valuations and arbitrary monotone valuations, whereas our work explores the space between fractionally subadditive and subadditive valuations.

To the best of our knowledge, the only prior work exploring the space between fractionally subadditive and subadditive valuations is [25]. Their main results concern the communication complexity of two-player combinatorial auctions for subadditive valuations, but they also provide improved parameterized guarantees for valuations that are subadditive and also MPH- $k$ [28]. A detailed comparison to our work is therefore merited:

$\blacksquare$

The partitioning interpolation follows from a first-principles definition (Section 3.1). On the other hand, the MPH hierarchy explores the space between fractionally subadditive and arbitrary monotone valuations, and [25] restrict attention to the portion of this space that is also subadditive.
$\blacksquare$

Our main results consider posted price mechanisms and concentration inequalities, neither of which are studied in [25]. [25] study the communication complexity of combinatorial auctions (where the gap between fractionally subadditive and subadditive is only constant), which is not studied in our work.
$\blacksquare$

We show (Proposition 14) that all $q$ -partitioning valuations are also MPH- $\lceil m/q\rceil$ . Therefore, we can conclude a $(1/2+1/\log_{2}(\lceil m/q\rceil))$ -approximation algorithm for two-player combinatorial auctions with $q$ -partitioning valuations using [25] (this is the only result of their paper concerning functions between fractionally subadditive and subadditive).
$\blacksquare$

We further show that $q$ -partitioning admits a dual definition (Definition 13, similar to the duality between XOS and fractionally subadditive). A particular feasible dual solution implies a witness that $q$ -partitioning valuations are MPH- $\lceil m/q\rceil$ . This suggests that our dual definition is perhaps “the right” modification of subadditive MPH- $k$ so that a dual definition exists.

Posted price mechanisms.

Posted price mechanisms are a core object of study within Algorithmic Game Theory. Variants of posted price mechanisms achieve state-of-the-art guarantees for wide ranges of combinatorial auctions [3, 17]. Posted price mechanisms are strongly obviously strategyproof [42, 45]. Posted price mechanisms have also been used in Bayesian settings to study the price of anarchy for welfare [32, 20, 22], revenue maximization in multi-dimensional settings [11, 40, 12, 10], and revenue maximization in single-dimensional settings [53, 2, 36, 38, 39, 37]. Most relevant to our work is the study of posted price mechanisms in Bayesian settings for welfare, where the state-of-the-art is a $(1/2)$ -approximation for fractionally subadditive valuations [32], and a $\Omega(1/\log_{2}\log_{2}(m))$ -approximation for subadditive valuations [22]. These results further imply approximation guarantees of the same asymptotics for multi-dimensional mechanism design via [10], and it is considered a major open problem whether improved guarantees are possible for subadditive valuations. Our work provide improved guarantees across the partitioning interpolation (of $\Omega(\log_{2}\log_{2}(q)/\log_{2}\log_{2}(m))$ ), which matches the state-of-the-art at both endpoints (and moreover, is provably tight at both endpoints for the approach of [22]). We also briefly note that recent work of [13] provides an $O(1)$ prophet inequality for online Bayesian combinatorial auctions, but not a posted-price mechanism, so their breakthrough is orthogonal to our work.

Concentration Inequalities.

Concentration inequalities on functions of independent random variables are a core tool across many branches of Computer Science. For example, they are widely used in Bayesian mechanism design [47, 12, 10, 41], learning theory [4, 35], and discrete optimization [26]. Vondák’s wonderful note on concentration inequalities of this form gives the state-of-the-art when $f$ is fractionally subadditive and subadditive, and mentions other applications [52]. Our results extend both the state-of-the-art for subadditive and fractionally subadditive across the partitioning interpolation. In addition, we provide a new isoperimetric inequality based on Talagrand’s method of control by $q$ points.

1.5 Summary and Roadmap

Section 2 immediately follows with formal definitions. Section 3 defines the partitioning interpolation, and provides several basic properties (including an interpretation via cost-sharing, and a dual formulation). Section 4 overviews our first main result: an $\Omega(\frac{\log\log q}{\log\log m})$ -approximate posted-price mechanism for $q$ -partitioning valuations. Section 5 overviews our main results on concentration inequalities. Section 6 concludes. Recall that the purpose of our results in Section 4 and Section 5 are to consider domains where provable separations already exist between subadditive and fractionally subadditive valuation functions, and to extend the stronger guarantees achievable for fractionally subadditive valuations along our hierarchy. The full version contains all omitted proofs [5].

2 Preliminaries

Throughout the entire paper, we assume that valuations $f:2^{M}\longrightarrow\mathbb{R}^{+}$ are normalized, meaning that $f(\emptyset)=0,$ and increasing monotone, meaning that $f(S)\leq f(T)$ whenever $S\subseteq T.$

Standard Valuation Classes.

A valuation function $f$ is subadditive (also known as complement free and denoted CF) if for all $S, T$ , $f(S\cup T)\leq f(S)+f(T)$ . $f$ is XOS if there exists a collection $\mathcal{A}$ of non-negative additive functions⁷⁷7A valuation function $v$ is non-negative additive if for all $S$ , $v(S)=\sum_{i\in S}v(\{i\}),$ where $v(\{i\})\geq 0$ holds for all $i .$ such that for all $S$ , $f(S)=\max_{v\in\mathcal{A}}\{v(S)\}$ . $f$ is fractionally subadditive if for any $S$ and any fractional cover $\alpha(\cdot)$ such that for all $j\in S$ $\sum_{T\ni j}\alpha(T)\geq 1$ and $\alpha(T)\geq 0$ for all $T,$ it holds that $f(S)\leq\sum_{T}\alpha(T)f(T)$ . It is well-known that $f$ is XOS if and only if it is fractionally subadditive via LP duality [27].

PH- $𝒌,$ MPH- $𝒌,$ and Subadditive MPH- $𝒌$ valuations.

Maximum over PositiveHypergraph- $k$ valuations, in short MPH- $k$ , were introduced in [28]. Since then, they have been studied in various different contexts such as communication complexity of combinatorial auctions [25] and posted price mechanisms [32]. One motivation behind MPH- $k$ valuations is to construct a hierarchy of valuation classes (starting with XOS) by replacing additive valuations with a richer class of valuations parameterized by $k$ . Specifically:

Definition 1.

A valuation $v:2^{[m]}\longrightarrow\mathbb{R}_{\geq 0}$ is:

1.

PH- $𝒌$ if there exist non-negative weights $w(E)$ for subsets $E\subseteq[m],|E|\leq k$ , such that for all $S\subseteq[m]$ : $\displaystyle v(S)=\sum_{T\subseteq S\;:\;|T|\leq k}w(T).$
2.

MPH- $𝒌$ if there exists a set of PH- $k$ valuations $\mathcal{A}$ such that $\displaystyle v(S)=\max_{a\in\mathcal{A}}a(S)$ for all $S\subseteq[m].$
3.

Subadditive MPH- $𝒌$ (CFMPH- $𝒌$ ) if $v$ is simultaneously subadditive and MPH- $k .$

Note that PH- $1$ valuations are exactly the class of additive valuations, so the class of MPH- $1$ valuations is exactly the class of XOS valuations. Note also that PH- $2$ valuations need not be subadditive (and therefore, MPH- $2$ valuations need not be subadditive either). MPH- $m$ contains all monotone valuation functions, and all subadditive functions are MPH- $m/2$ [25]. We establish a connection between $q$ -partitioning valuations and valuations that are MPH- $\lceil m/q\rceil$ and subadditive in Proposition 14.

3 The Partitioning Interpolation

Here, we present our main definition. We give its more intuitive “primal form” as the main definition, and establish a “dual form” in Section 3.2.

Definition 2.

Let $q\in[2,m]$ be an integer. A valuation $v:2^{[m]}\longrightarrow\mathbb{R}_{\geq 0}$ satisfies the $q$ -partitioning property if for any $S\subseteq[m]$ and any partition $(S_{1},S_{2},\ldots,S_{q})$ of $S$ into $q$ (possibly empty) disjoint parts, and any fractional covering $\alpha$ of $[q]$ (that is, any non-negative $\alpha(\cdot)$ such that for all $j\in[q],\sum_{T\ni j}\alpha(T)\geq 1$ ):

v(S)\leq\sum_{T\subseteq[q]}\alpha(T)\cdot v\left(\cup_{j\in T}S_{j}\right).

We refer to the class of $q$ -partitioning valuations over $[m]$ as $\mathcal{Q}(q,[m])$ .

The intuition behind our definition is that $q$ captures the complexity of non-negative fractional covers under which the value of $v(\cdot)$ is non-diminishing. Subadditive valuations are only non-diminishing under very simple covers (covering $S\cup T$ by $S$ and $T$ ), while XOS valuations are non-diminishing under arbitrarily complex fractional covers. The parameter $q$ captures the desired complexity in between. We now establish a few basic properties of $q$ -partitioning valuations.

We begin with the following nearly-trivial observations: First, for any fixed $q$ and $m$ , the class $\mathcal{Q}(q,[m])$ is closed under conic combinations.⁸⁸8That is, $\mathcal{Q}(q,[m])$ is closed under linear combinations with non-negative coefficients. This has implications for oblivious rounding of linear relaxations [29]. Furthermore, for any fixed $q$ and $m$ , the class $\mathcal{Q}(q,[m])$ is closed under taking pointwise suprema, which means that one can use the “lower envelope technique” when approximating functions by $q$ -partitioning functions [28, Section 3.1].

Now, we establish the three promised properties from Section 1. We begin by confirming that indeed the partitioning interpolation interpolates between fractionally subadditive and subadditive valuations.

Proposition 3.

For all $m$ , the following relations between classes of $q$ -Partitioning valuations hold: $\text{XOS}([m])=\mathcal{Q}(m,[m])\subsetneq\mathcal{Q}(m-1,[m])\subsetneq% \cdots\cdots\subsetneq\mathcal{Q}(2,[m])=\text{CF}([m]).$

We provide a complete proof of Proposition 3 in the full version. It is reasonably straight-forward to see that $\text{XOS}([m])=\mathcal{Q}(m,[m])$ , and that $\mathcal{Q}(2,[m])=\text{CF}([m])$ . It is also straightforward to see the inclusions in the chain (any partition with $q$ parts is also a partition with $q+1$ by adding an empty partition). We show that each inclusion is strict via the following proposition, whose complete proof appears in the full version [5].

Proposition 4.

Consider a valuation $v$ over $[m]$ such that $v(S)=1$ whenever $1\leq|S|\leq m-1$ and $v(\emptyset)=0$ . The largest value $v([m])$ for which $v$ is $q$ -partitioning is $\frac{q}{q-1}.$

We now show that $\mathcal{Q}(q,[m])$ is close to $\mathcal{Q}(q+1,[m])$ in a precise sense. Note that Definition 5 applied to $q=m$ is exactly the notion of closeness used in [6].

Definition 5.

Suppose that $0<\gamma\leq 1.$ A class of valuations $\mathcal{G}$ over $[m]$ is $\gamma$ -close to the class $\mathcal{Q}(q,[m])$ if for any $g\in\mathcal{G},$ any $S\subseteq[m],$ any partition $(S_{1},S_{2},\ldots,S_{q})$ of $S$ into $q$ parts, and any fractional cover $\alpha$ of $[q],$ it is the case that

\sum_{{T}\subseteq[q]}\alpha({T})g(\bigcup_{i\in{T}}S_{i})\geq\gamma g(S).

We will see a further interpretation of Definition 5 in Proposition 11. For now, we simply present the following “smoothness” claim.

Theorem 6.

$\mathcal{Q}(q,[m])$ is $\frac{q-1}{q}$ -close to $\mathcal{Q}(q+1,[m])$ .

The proof of Theorem 6 appears in tehfull version [5]. Finally, we provide our first-principles definition of $q$ -partitioning via a cost-sharing game. This aspect is more involved, so we overview the setup in Section 3.1.

3.1 Interpretation in Cost Sharing

3.1.1 Recap: characterizing XOS via cost-sharing

Consider a set $[m]$ of players who are interested in receiving some service. There is a cost for this service described by a monotone increasing normalized cost function $c:2^{[m]}\longrightarrow\mathbb{R}.$ Here, $c(S)$ is the cost that players $S$ need to pay together so that each of them receives the service. A natural question to ask is: When is it the case that one can allocate the cost of the service between the community such that no subset of players $T\subseteq[m]$ is better off by forming a coalition and receiving the service on their own? Formally, this question asks whether the ${\mathsf{core}}$ of the game is nonempty. The ${\mathsf{core}}$ is the set of all non-negative cost-allocation vectors $\mathbf{p}=(p_{1},p_{2},\ldots,p_{m})$ that satisfy $\sum_{i\in S}p_{i}\leq c(S)\;\forall S\subseteq[m],$ and $\sum_{i\in[m]}p_{i}=c([m])$ [44, Definition 15.3]. We’ll refer to the game parameterized by cost function $c(\cdot)$ restricted to players in $S$ as $\textsc{Game}(c,S)$ . This question is answered by the Bondareva-Shapley Theorem (see [44, Theorem 15.6]). Applied to monotone normalized cost functions $c$ , it states:

Theorem 7 ([7, 49]).

The ${\mathsf{core}}$ $\textsc{Game}(c,[m])$ is non-empty if and only if for any non-negative fractional cover $\alpha$ of $[m]$ it is the case that $\sum_{S\subseteq[m]}\alpha(S)c(S)\geq c([m]).$

An immediate generalization of this theorem, which appears in [27, Section 1.1], is:

Theorem 8.

The ${\mathsf{core}}$ of $\textsc{Game}(c,S)$ is non-empty for all $S$ if and only if $c$ is fractionally subadditive.

An interpretation of the above statement is the following. No matter what subset $S\subseteq[m]$ of players are interested in the service, we can always design a cost allocation vector (which vector can depend on $S$ ) such that all players in $S$ are better off by purchasing the service together rather than deviating and forming coalitions. Since finding cores might be impossible (unless $c$ is fractionally subadditive), the following relaxation of a ${\mathsf{core}}$ appears in coalitional game theory literature. A non-negative vector $\mathbf{p}$ is in the $\gamma\text{-}\mathsf{core}$ of the game if and only if it satisfies $\sum_{i\in S}p_{i}\leq c(S)\;\forall S\subseteq[m],$ and $\gamma c([m])\leq\sum_{i\in[m]}p_{i}\leq c([m])$ [44, Definition 15.7]. Again, one has equivalent statements to Theorems 8 and 7 using a $\gamma\text{-}\mathsf{core}.$ We only state the analogous statement for Theorem 8:

Theorem 9.

The $\gamma\text{-}\mathsf{core}$ of $\textsc{Game}(c,S)$ is non-empty for all $S$ if and only if $c$ is $\gamma$ -close to XOS.

3.1.2 $𝒒$ -partitioning via cost-sharing

Consider instead a partition of players into $q$ (possibly empty) cities $S_{1},\ldots,S_{q}$ . We think of each city as a fully-cooperative entity that takes a single action.⁹⁹9Perhaps the city has an elected official that acts on behalf of the city’s welfare, or perhaps the city’s members have built enough trust that they can perfectly profit-share any gains the city gets. The question of interest is whether ${\mathsf{citycore}}(S_{1},S_{2},\ldots,S_{q})$ of the game is non-empty. ${\mathsf{citycore}}(S_{1},S_{2},\ldots,S_{q})$ is the set of non-negative cost-allocation vectors $\mathbf{p}=(p_{1},p_{2},\ldots,p_{q})$ that satisfy $\sum_{i\in T}p_{i}\leq c(\bigcup_{i\in T}S_{i})$ for all $T\subseteq[q],$ and $\sum_{i\in[q]}p_{i}=c(\bigcup_{i\in[q]}S_{i}).$ Note that a vector in the ${\mathsf{citycore}}$ will incentivize cooperation as each subset of cities needs to pay at least as much if they choose to form a coalition. We parallel the theorems in the previous section with the following propositions. We’ll refer to the above game as $\textsc{Game}(c,S,S_{1},\ldots,S_{q})$ when the normalized monotone cost function is $c$ , players in $S$ are participating, and they are partitioned into cities $S_{1},\ldots,S_{q}$ .

Proposition 10.

The ${\mathsf{citycore}}$ of $\textsc{Game}(c,S,S_{1},\ldots,S_{q})$ is non-empty for all $S,S_{1},\ldots,S_{q}$ if and only if $c$ is $q$ -partitioning.

Again, the interpretation is simple. No matter which people are interested in the service and how they are distributed between cities, we can design a cost allocation vector such that all cities are better off by purchasing the service together rather than forming coalitions. Finally, one can also relax the concept of a ${\mathsf{citycore}}$ to a $\gamma\text{-}\mathsf{citycore}$ as follows. This is the set of non-negative cost-allocation vectors $\mathbf{p}=(p_{1},p_{2},\ldots,p_{q})$ that satisfy $\sum_{i\in T}p_{i}\leq c(\bigcup_{i\in T}S_{i})\;\forall T\subseteq[q],$ and $\gamma c(\bigcup_{i\in[q]}S_{i})\leq\sum_{i\in[q]}p_{i}\leq c(\bigcup_{i\in[q]% }S_{i}).$ We can then also conclude:

Proposition 11.

The $\gamma\text{-}\mathsf{citycore}$ of $\textsc{Game}(c,S,S_{1},\ldots,S_{q})$ is non-empty for all $S,S_{1},\ldots,S_{q}$ if and only if $c$ is $\gamma$ -close to $q$ -partitioning.

3.2 The Dual Definition and Relation to MPH Hierarchy

Finally, we provide a dual view of the $q$ -partitioning property (as in XOS vs. fractionally subadditive), and relate $q$ -partitioning to valuations that are MPH- $\lceil m/q\rceil$ . First, we observe that the $q$ -partitioning property can be reinterpreted as a claim about a linear program, opening the possibility of a dual definition.

Observation 12.

A valuation function $f$ is $q$ -partitioning if and only if for all $S$ and all partitions $(S_{1},\ldots,S_{q})$ of $S$ into $q$ (possibly empty) disjoint parts, the value of the following LP is $v(S)$ :¹⁰¹⁰10Below, the variables are $\alpha(T)$ for all $T\subseteq[q]$ .

\begin{split}\min&\sum_{{T}\subseteq[q]}v(\bigcup_{i\in T}S_{i})\cdot\alpha(T)% ,\text{ s.t.}\\ &\sum_{T\ni j}\alpha(T)\geq 1\;\;\;\forall j\in[q],\\ &\alpha(T)\geq 0\;\;\;\forall T\subseteq[q].\end{split}

(1)

The proof of Observation 12 is fairly immediate by observing that feasible solutions to the LP are exactly fractional covers, and that the objective function is exactly the bound on $v(S)$ implied by that fractional cover. We now state a “dual” definition of $q$ -partitioning valuations. The equivalence with Definition 2 is a simple application of linear programming, which we present in the full version [5].

Definition 13.

Let $2\leq q\leq m$ be integers. A valuation $v:2^{[m]}\longrightarrow\mathbb{R}_{\geq 0}$ satisfies the dual $q$ -partitioning property if for any $S\subseteq[m]$ and any partition $(S_{1},S_{2},\ldots,S_{q})$ of $S$ into $q$ disjoint parts, the following linear program has value at least $v(S):$

\begin{split}\max&\sum_{j\in[q]}p_{j},\text{ s.t.}\\ &\sum_{j\in T}p_{j}\leq v(\bigcup_{j\in T}S_{j})\;\;\;\forall T\subseteq[q],\\ &p_{j}\geq 0\;\;\;\forall j\in[q].\end{split}

(Dual Definition)

This dual definition allows us to establish the useful relationship between the partitioning and MPH hierarchies given in Proposition 14.

Proposition 14.

A valuation over $[m]$ satisfying the $q$ -partitioning property is MPH- $\lceil\frac{m}{q}\rceil$ and subadditive.

Proof.

To prove this statement, for each $S\subseteq[m],$ we will create a clause $w^{S}$ containing hyperedges of size at most $\lceil\frac{m}{q}\rceil,$ which takes value $v(S)$ at $S$ and for any $T\neq S,$ $w^{S}(T)\leq v(S).$ This will be clearly enough as we can take the maximum over clauses $w^{S}.$ Take an arbitrary set $S$ and partition it into $q$ subsets $S_{1},S_{2},\ldots,S_{q}$ of almost equal size such that each subset has at most $\lceil\frac{m}{q}\rceil$ elements. We will construct a clause of the form

w^{S}=(S_{1}:p_{1},\;S_{2}:p_{2},\;\ldots,\;S_{q}:p_{q}),

where $p_{i}$ is the weight of set $S_{i}$ for each $i .$ Note that the weights $p_{1},p_{2},\ldots,p_{q}$ must satisfy

\begin{split}&\sum_{i}p_{i}=v(S),\\ &\sum_{i\in I}p_{i}\leq v(\bigcup_{i\in I}S_{i})\;\forall I\subseteq[q],\\ &p_{i}\geq 0\;\forall i\in[q].\end{split}

The existence of such weights is guaranteed by Definition 13, which completes the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 15.

It should be noted that the converse statement does not hold true if $q\not\in\{2,m\}$ . Let $k=\lceil\frac{m}{q}\rceil.$ The valuation $v(S):=\max\left(\binom{|S|}{k},\frac{1}{2}\binom{m}{k}\right)$ over $[m]$ is MPH- $k$ and subadditive. However, it is simple to show that it is not $q$ -partitioning. Split $[m]$ into $q$ sets of almost equal size $S_{1},S_{2},\ldots,S_{q}$ and consider the fractional cover $\alpha$ over $[q]$ assigning weight $\frac{1}{q-1}$ to all subsets of $[q]$ of size $q-1.$ A simple calculation shows that $v$ and $\alpha$ do not satisfy the $q$ -partitioning property.

4 Main Result I: Posted Price Mechanisms

We consider the setup of [32]. Namely, there are $n$ buyers interested in a set of items $[m].$ The buyers’ valuations come from a product distribution $\mathcal{D}=\mathcal{D}_{1}\times\mathcal{D}_{2}\cdots\times\mathcal{D}_{n}$ , known to the seller. The optimal expected welfare is then $\textsc{OPT}(\mathcal{D}):=\mathbb{E}_{\vec{v}\leftarrow\mathcal{D}}[\max_{% \text{Partitions }S_{1},\ldots,S_{n}}\{\sum_{i=1}^{n}v_{i}(S_{i})\}]$ . The goal of the seller is to fix prices $p_{1},\ldots,p_{m}$ so that the following procedure guarantees welfare at least $c\cdot\textsc{OPT}$ in expectation:

$\blacksquare$

Let $A$ denote the set of available items. Initially $A=[m]$ .
$\blacksquare$

Visit the buyers one at a time in adversarial order. When visiting buyer $i$ , they will purchase the set $S_{i}:=\arg\max_{S\subseteq A}\{v_{i}(S)-\sum_{i\in S}p_{i}\}$ , and update $A:=A\setminus S_{i}$ .

Theorem 16.

When all agents have $q$ -partitioning valuations, there exists a $\Omega(\frac{\log\log q}{\log\log m})$ -competitive posted price mechanism.¹¹¹¹11Unless explicitly indicated, logarithms have base 2 throughout the rest of this section.

Note that this result matches asymptotically the best known competitive ratios for XOS (when $q=m,$ a constant ratio mechanism was proven in [32]) and CF valuations (when $q=2,$ a $\Omega(\frac{1}{\log\log m})$ -competitive posted price mechanism was proven in [22]) and interpolates smoothly when $q$ is in between.

Like [22], we first give a proof in the case when each $\mathcal{D}_{i}$ is a point-mass, as this captures the key ideas. A complete proof in the general case appears in the full version [5].

Our proof will follow the same framework as [22]. To this end, let $p\in[0,1]$ be a real number. Denote by $\Delta(p)$ the set of distributions over $2^{[m]}$ such that $\mathbf{P}_{S\leftarrow\lambda}[i\in S]\leq p$ holds for all $\lambda\in\Delta(p)$ and all $i\in[m]$ . The framework of [22] establishes the following:

Lemma 17 ([22, Eq. (6)]).

A class of monotone valuations $\mathcal{G}$ over $[m]$ is given. If for any $v\in\mathcal{G},$ there exists a real number $p\in[0,1]$ (possibly depending on $v$ ), such that

\max_{\lambda\in\Delta(p)}\min_{\mu\in\Delta(p)}\mathbf{E}_{S\leftarrow\lambda% ,T\leftarrow\mu}[v(S\backslash T)]\geq\alpha\times v([m]),

there exists an $\alpha$ -competitive posted price mechanism when all players have valuations in $\mathcal{G}.$

[22] then show that when $\mathcal{G}$ is the class of all subadditive functions, such a $p$ exists for $\alpha=\Theta(\frac{1}{\log\log m})$ , but no better. In the rest of this section, we will show that when $\mathcal{G}$ is the set of $q$ -partitioning valuations, the conditions of Lemma 17 hold with $\alpha=\Omega\left(\frac{\log\log q}{\log\log m}\right)$ . It is clear that (the deterministic case of) Theorem 16 follows immediately from Lemma 17 and Proposition 18. It is worth noting that, while we leverage Lemma 17 exactly as in [22], the proof of Proposition 18 for general $q$ is quite novel in comparison to the $q=2$ (subadditive).

Proposition 18.

Let $v\in\mathcal{Q}(q,[m])$ . Then there exists a real number $p\in[0,1]$ such that:

\max_{\lambda\in\Delta(p)}\min_{\mu\in\Delta(p)}\mathbf{E}_{S\leftarrow\lambda% ,T\leftarrow\mu}[v(S\backslash T)]\geq\Omega\left(\frac{\log\log q}{\log\log m% }\right)\times v([m]).

Proof.

Denote

g(p)=\max_{\lambda\in\Delta(p)}\min_{\mu\in\Delta(p)}\mathbf{E}_{S\leftarrow% \lambda,T\leftarrow\mu}[v(S\backslash T)],\quad\quad f(p)=\max_{\lambda\in% \Delta(p)}\mathbf{E}_{S\leftarrow\lambda}[v(S)],

and let $\lambda^{p}$ be a maximizing distribution in $\arg\max_{\lambda\in\Delta(p)}\mathbf{E}_{S\leftarrow\lambda}[v(S)].$
Without loss of generality, assume that $q$ is a perfect power of 2, i.e. $q=2^{r}$ (we can always decrease $q$ to a power of $2$ without changing the asymptotics of $\Omega(\frac{\log\log q}{\log\log m})$ ). Now, fix some $p\in\left(0,\frac{1}{16}\right].$ We will show that $g(p)\geq\frac{1}{8}\left(f(p)-f(p^{\frac{r}{2}})\right).$ The first step is the obvious bound

g(p)\geq\min_{\mu\in\Delta(p)}\mathbf{E}_{S\leftarrow\lambda^{p},T\leftarrow% \mu}[v(S\backslash T)],

which follows from the fact that we can choose $\lambda=\lambda^{p}.$ Now, we bound $\mathbf{E}_{S\leftarrow\lambda^{p},T\leftarrow\mu}[v(S\backslash T)].$ Fix a distribution $\mu.$ Let $S$ be drawn according to $\lambda^{p}$ and $T_{1},T_{2},\ldots,T_{r}$ be $r$ independent sets drawn according to $\mu.$ Then,

\mathbf{E}[v(S\backslash T)]=\mathbf{E}\left[\sum_{i=1}^{r}\frac{1}{r}v(S% \backslash T_{i})\right].

Now, we will use the $q$ -partitioning property. Note that the sets $T_{1},T_{2}\ldots,T_{r}$ define a partitioning of $S$ into $2^{r}=q$ subsets. That is, for any $\vec{v}\in\{0,1\}^{r},$ we can define

S_{\vec{v}}=\{j\in S:\;j\in T_{i}\text{ for }v_{i}=1\text{ and }j\not\in T_{i}% \text{ for }v_{i}=0\}.

(Partitioning with

r

sets)

According to this partitioning, define $A_{0},A_{1},A_{2},\ldots,A_{r}$ as follows:

A_{t}=\{j\in S\;:\;j\text{ belongs to exactly }t\text{ of the sets }T_{i}\}=% \bigcup_{\vec{v}\;:\;1^{T}\vec{v}=t}S_{\vec{v}}.

Then, by the $q$ -partitioning property, we know that

\frac{8}{r}\left(v(S\backslash T_{1})+v(S\backslash T_{2})+\cdots+v(S% \backslash T_{r})\right)+v(\bigcup_{j\geq\frac{7r}{8}}A_{j})\geq v(S).

Indeed, that is the case for the following reason. If $\vec{v}$ is such that $1^{T}\vec{v}<\frac{7r}{8},$ then $S_{\vec{v}}$ belongs to at least $r-1^{T}\vec{v}\geq\frac{r}{8}$ of the sets $S\backslash T_{i},$ so it is “fractionally covered” by the term $\frac{8}{r}\left(v(S\backslash T_{1})+v(S\backslash T_{2})+\cdots+v(S% \backslash T_{r})\right).$ If, on the other hand, $\vec{v}$ is such that $1^{T}\vec{v}\geq\frac{7r}{8},$ then it is fractionally covered by the term $v(\bigcup_{j\geq\frac{7r}{8}}A_{j}).$
Now, let $A=\bigcup_{j\geq\frac{7r}{8}}A_{j}.$ We claim that each element $j\in[m]$ belongs to $A$ with probability at most $p^{r/2}$ (over the randomness in drawing $S\leftarrow\lambda^{p}$ and $T_{1},\ldots,T_{r}\leftarrow\mu$ , then defining $A$ as above). To prove this, we will use the classical Chernoff bound as follows. Let $Y_{i}$ be the indicator that $j\in T_{i}.$ Then, $\mathbf{P}[Y_{i}=1]\leq p,$ so $\mathbf{E}[\sum_{i=1}^{r}Y_{i}]\leq rp.$ On the other hand, $j$ is in $A$ if and only if $\sum_{i=1}^{r}Y_{i}\geq\frac{7}{8}r.$ Now, let $\delta=\frac{7}{8p}-1$ and let $\mu=rp.$ Then, by Chernoff bound,

	$\displaystyle\mathbf{P}\left[\sum_{i=1}^{r}Y_{i}\geq\frac{7}{8}r\right]$	$\displaystyle\leq\mathbf{P}\left[\sum_{i=1}^{r}Y_{i}\geq\mu(1+\delta)\right]% \leq\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu}$
		$\displaystyle\leq\left(\frac{e^{1+\delta}}{(1+\delta)^{1+\delta}}\right)^{rp}=% \left(\frac{8ep}{7}\right)^{\frac{7r}{8}}\leq p^{\frac{r}{2}},$

where the last inequality follows since $p\leq\frac{1}{16}.$ All of this together shows that

g(p)\geq\min_{\mu\in\Delta(p)}\mathbf{E}_{S\leftarrow\lambda^{p},T\leftarrow% \mu}[v(S\backslash T)]\geq

\frac{1}{r}\sum_{i=1}^{r}\mathbf{E}[v(S\backslash T_{i})]\geq\frac{1}{8}% \mathbf{E}[v(S)]-\frac{1}{8}\mathbf{E}[v(A)]\geq\frac{1}{8}f(p)-\frac{1}{8}f(p% ^{\frac{r}{2}}),

where the last inequality holds as each element appears in $A$ with probability at most $p^{r/2}.$ Using the same telescoping trick as in [22], we can reach the conclusion. The details are in the full version [5]. $\hfill\blacktriangleleft$

5 Main Result II: Concentration Inequalities

In this section, we present our concentration inequalities for the partitioning interpolation. We begin by overviewing our results and their context in further detail, highlighting some proofs. We provide complete proofs in the subsequent section and the full version [5]. .

[52] establishes that when $v$ is XOS, the random variable $v(S)$ has $\mathbf{E}[v(S)]$ -subgaussian lower tails. The proof follows by establishing that $1$ -Lipschitz XOS functions of independent random variables are self bounding, and applying a concentration inequality of [8]. We begin by showing that $1$ -Lipschitz $q$ -partitioning functions are $(\lceil m/q\rceil,0)$ -self bounding, and applying a concentration inequality of [43, 9] to yield the following:

Theorem 19.

Any 1-Lipschitz $q$ -partitioning valuation $v$ over $[m]$ satisfies the following inequalities

\mathbf{P}\left[v(S)\geq\mathbf{E}[v(S)]+t\right]\leq\exp\left(-\frac{1}{2}% \times\frac{t^{2}}{\lceil\frac{m}{q}\rceil\mathbf{E}[v(S)]+\frac{3\lceil\frac{% m}{q}\rceil-1}{6}t}\right)\;\text{ for }t\geq 0,

\mathbf{P}[v(S)\leq\mathbf{E}[v(S)]-t]\leq\exp\left(-\frac{1}{2}\times\frac{t^% {2}}{\lceil\frac{m}{q}\rceil\mathbf{E}[v(S)]}\right)\;\text{ for }\mathbf{E}[Z% ]\geq t\geq 0.

We prove Theorem 19 in the full version [5]. Theorem 19 matches [52] at $q=m$ , and provides non-trivial tail bounds for $q=\omega(1)$ . One should note, however, the the above inequality is useless when $q$ is constant, as it only implies $O(m\mathbf{E}[v(S)])$ -subgaussian behaviour, but it is well known that any 1-Lipschitz set function is $m$ -subgaussian via McDiarmid’s inequality. Our next inequality considers an alternate approach, based on state-of-the-art concentration inequalities for subadditve functions. [48] proves¹²¹²12Schechtman actually considers the non-normalized case and proves that $\mathbf{P}[v(S)\geq(q+1)a+k]\leq q^{-k}\mathbf{P}[v(S)\leq a]^{-q},$ but reducing the factor from $q+1$ to $q$ in the normalized case is a trivial modification of the proof. It follows, in particular, from our Theorem 20. that whenever $v$ is normalized 1-Lipschitz subadditive, the following inequality holds for any real numbers $a>0,k>0,$ and integer $q\geq 2,$

\mathbf{P}[v(S)\geq qa+k]\leq q^{-k}\mathbf{P}[v(S)\leq a]^{-q}.

(2)

In particular, setting $a=\mathbf{Med}[v(S)],q=2$ , and integrating over $k=0$ to $\infty$ allows one to conclude the bound $\mathbf{E}[v(S)]\leq 2\mathbf{Med}[v(S)]+O(1)$ , which has proven useful, for example in [47]. While this inequality establishes a very rapid exponential decay, the decay only begins at $2a$ as we need $q\geq 2$ .¹³¹³13Recall that this is necessary, and not just an artifact of the proof – an example is given in [52]. What if we seek an upper tail bound of the form $\mathbf{P}[v(S)\geq 1.1a+k]$ or, even more strongly, something of the form $\mathbf{P}[v(S)\geq(1+{o_{m}(1)})a+k]$ ? Our next inequality accomplishes this:

Theorem 20.

Suppose that $v\in\mathcal{Q}(q,[m])$ , and $S\subseteq[m]$ is a random set in which each element appears independently. Then the following inequality holds for any $a\geq 0,k\geq 0,$ and integers $1\leq s<r\leq\log_{2}q.$

\mathbf{P}\left[v(S)\geq\frac{r}{s}a+k\right]\leq\left(\frac{r}{s}\right)^{-k}% \mathbf{P}[v(S)\leq a]^{-\frac{r}{s}}.

The interesting extension for $q$ -partitioning valuations via Theorem 20 is that one may take $s=\log_{2}q-1,r=\log_{2}q$ . From here, for example, one can again take $a$ to be the median of $v(S)$ , and integrate from $k=0$ to $\infty$ to conclude that $\mathbf{E}[v(S)]\leq(1+O(\frac{1}{\log q}))\mathbf{Med}[v(S)]+O(\log q).$ In the very special case of $q=m$ , we can also replace $\frac{r}{s}$ with any real $1+\delta>0$ and obtain the $\mathbf{E}[v(S)]\leq\mathbf{Med}[v(S)]+O(\sqrt{\mathbf{Med}[v(S)]})$ , which is the same extremely strong relationship implied by the $\mathbf{E}[v(S)]$ -subgaussian behaviour. We prove these simple corollaries of Theorem 20 in the full version [5] and now proceed to a proof of Theorem 20. To do so, we need to make a detour and generalize Talagrand’s method of “control by $q$ -points”.

5.1 A Probabilistic Detour: A New Isoperimetric Concentration Inequality

Suppose that we have a product probability space $\Omega=\prod_{i=1}^{N}\Omega_{i}$ with product probability measure $\mathbf{P}.$ Throughout, in order to highlight our new techniques instead of dealing with issues of measurability, we will assume that the probability spaces are discrete and are equipped with the discrete sigma algebra. These conditions are not necessary and can be significantly relaxed (see [51, Section 2.1]).

For $q+1$ points¹⁴¹⁴14In the current section, we will reserve the letter “ $q$ ” to indicate the number of points $y^{1},y^{2},\ldots,y^{q}.$ While this choice might seem unnatural given that the current paper is all about “ $q$ -Partitioning” and “ $q$ ” already has a different meaning, we have chosen to stick to Talagrand’s notation. The reason is that the probabilistic approach we use is already known as “control by $q$ points” in literature [51, Section 3]. $y^{1},y^{2},\ldots,y^{q},x$ in $\Omega,$ and an integer $1\leq s\leq q,$ we define

\begin{split}f^{s}(y^{1},y^{2},&\ldots,y^{q};x):=\\ &\Big{|}\Big{\{}i\in[N]:x_{i}\text{ appears less than $s$ times in the % multiset }\{y^{1}_{i},y^{2}_{i},\ldots,y^{q}_{i}\}\Big{\}}\Big{|}.\end{split}

(3)

Using this definition, one can extend $f^{s}$ to subsets $A_{1},A_{2},A_{3},\ldots,A_{q}$ of $\Omega$ as follows

f^{s}(A_{1},A_{2},\ldots,A_{q};x):=\inf\{f^{s}(y^{1},y^{2},\ldots,y^{q};x)\;:% \;y^{i}\in A_{i}\;\forall i\}.

When $A=A_{1},A_{2},\ldots,A_{q},$ the function $f^{s}(A_{1},A_{2},\ldots,A_{q};x)$ intuitively defines a “distance” from $x$ to $A .$ ¹⁵¹⁵15This interpretation of $f^{s}$ as a “distance” is what motivates the name “isoperimetric inequality” [51]. The definition of the function $f^{s}$ is motivated by and generalizes previous work of Talagrand [51, 50]. Our main technical result, the proof of which can be found in the full version [5], is the following. In it, $A_{1},A_{2},\ldots,A_{q}$ are fixed while $x$ is random, distributed according to $\mathbf{P},$ which is the aforementioned product distribution over $\Omega.$

Theorem 21.

Suppose that $\alpha\geq\frac{1}{s}$ is a real number and $t(\alpha,q,s)$ is the larger root of the equation $t+\alpha qt^{-\frac{1}{\alpha s}}=\alpha q+1.$ Then, $\int_{\Omega}t(\alpha,q,s)^{f^{s}(A_{1},A_{2},\ldots,A_{q};x)}d\mathbf{P}(x)% \leq\frac{1}{\prod_{i=1}^{q}\mathbf{P}[A_{i}]^{\alpha}}.$

In particular, setting $A_{1}=A_{2}=\cdots=A_{q}=A,\alpha=\frac{1}{s},t=\frac{q}{s},$ we obtain

\mathbf{P}[f^{s}(\underbrace{A,A,\ldots,A}_{q};x)\geq k]\leq\left(\frac{q}{s}% \right)^{-k}\mathbf{P}[x\in A]^{-\frac{q}{s}}.

Given Theorem 21, the proof of Theorem 20 is rather simple. It is given in the full version [5]. Here, we only mention that it again relies on (Partitioning with $r$ sets).

6 Conclusion

We introduce the partitioning interpolation to interpolate between fractionally subadditive and subadditive valuations. We provide an interpretation of the definition via a cost-sharing game (as in [7, 49] for fractionally subadditive), and also show a relation to the subadditive MPH- $k$ hierarchy via a dual definition. We apply our definition in canonical domains (posted price mechanisms and concentration inequalities) where the fractionally subadditive and subadditive valuations are already known to be provably “far apart”, and use the partitioning interpolation to interpolate between them. One technical nugget worth highlighting is Equation (Partitioning with $r$ sets), which appears in both Proposition 18 and Theorem 20.

Precise closeness of $\mathcal{Q}(q,[m])$ to $\mathcal{Q}(q^{\prime},[m])$ .

We establish that $\mathcal{Q}(q,[m])$ is $\frac{q-1}{q}$ -close to $\mathcal{Q}(q+1,[m])$ . In the full version [5], we show $q$ -partitioning valuations that are not $\left(\frac{q^{2}-1}{q^{2}}+\epsilon\right)$ -close to $\mathcal{Q}(q+1,[m])$ for any $\epsilon>0.$ It is interesting to understand what valuations in $\mathcal{Q}(q,[m])$ are furthest from $\mathcal{Q}(q+1,[m])$ (and how far they are).

Similarly, it is interesting to understand for which $\beta,$ the class $\mathcal{Q}(q,[m])$ pointwise $\beta$ -approximates $\mathcal{Q}(q+1,[m])$ .¹⁶¹⁶16See [15] for a formal definition of pointwise $\beta$ -approximation. Interestingly, a function is $\beta$ -close to XOS if and only if it is pointwise $\beta$ -approximated by XOS. But, it is not clear whether these two properties are identical for $q\neq m.$ Determining the precise relationship between the two properties is itself interesting. We note that one direction is easy. For any $q,$ being pointwise $\beta$ -approximated by $\mathcal{Q}(q,[m])$ implies being $\beta$ -close to $\mathcal{Q}(q,[m])$ . Open is whether the converse is true.

We also note that [6] resolves asymptotically the closeness of $\mathcal{Q}(2,[m])$ to $\mathcal{Q}(m,[m])$ at $\Theta(1/\log m)$ . In the full version [5], we show that simple modifications of their arguments imply that $\mathcal{Q}(2,[m])$ is $\Theta(1/\log q)$ -close to $\mathcal{Q}(q,[m])$ for any $q$ .

Constructing “hard” $𝒒$ -Partitioning valuations.

Our two main results, Theorems 16 and 20, both establish the existence of desirable properties for $q$ -partitioning valuations. However, to demonstrate tightness, one would need “hard” constructions of $q$ -partitioning valuations that are not $(q+1)$ -partitioning (recall that we have given constructions of valuation functions in $\mathcal{Q}(q,[m])\setminus\mathcal{Q}(q+1,[m])$ , but they are not “hard”). It does not appear at all straightforward to adapt constructions of “hard” valuations that are subadditive but not fractionally subadditive (e.g. [6]) to create a valuation function in $\mathcal{Q}(q,[m])\setminus\mathcal{Q}(q+1,[m])$ . Indeed, there is no previous construction of valuations that are subadditive MPH- $k$ but not subadditive MPH- $(k-1)$ (even without restricting to “hard” constructions). Constructing such functions (for which, e.g., the arguments made in Sections 4 and 5 are tight) is therefore an important open direction.

Applications in Algorithmic Game Theory.

Guarantees of posted-price mechanisms are perhaps the most notable domain within algorithmic game theory where fractionally subadditive and subadditive functions are far apart. Still, there are other settings where they are separated. For example, in best-response dynamics in combinatorial auctions, a dynamics leading to a constant fraction of the optimal welfare exists in the fractionally subadditive case, but there is a $O(\frac{\log\log m}{\log m})$ impossibility result in the subadditive case [21]. There are also constant-factor gaps between approximations achievable in polynomial communication complexity for combinatorial auctions [16, 27, 25], and for the price of anarchy of simple auctions [46]. Note that in the context of communication complexity of combinatorial auctions, Proposition 14 combined with the results for two players in [25] already imply improved communication protocols across the interpolation, but no lower bounds stronger than what can be inherited from fractionally subadditive valuations are known. Relevant is also the recent line of work on algorithmic contract theory [18, 19, 23].

Concentration Inequalities.

In the proof of Theorem 21, we have followed the approach of Talagrand in [50]. Dembo provides an alternative proof of the special case of this theorem for $s=1$ using a more systematic approach for proving isoperimetry based on information inequalities in [14]. It is interesting to understand to what extent the inequality in Theorem 21 can be recovered using the information inequalities framework in [14]. Moreover, the state-of-the-art provides two different approaches to concentration inequalities at the two extremes of the partitioning interpolation. It is important to understand the (asymptotically) optimal tail bounds across the partitioning interpolation, and it is interesting to understand whether there is a unified approach that yields (asymptotically) optimal tail bounds across a broad range of $\{2,\ldots,m\}$ .

References

[1] Ittai Abraham, Moshe Babaioff, Shaddin Dughmi, and Tim Roughgarden. Combinatorial auctions with restricted complements. In Boi Faltings, Kevin Leyton-Brown, and Panos Ipeirotis, editors, Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012, pages 3–16. ACM, 2012. doi:10.1145/2229012.2229016.
[2] Saeed Alaei, Jason D. Hartline, Rad Niazadeh, Emmanouil Pountourakis, and Yang Yuan. Optimal auctions vs. anonymous pricing. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1446–1463. IEEE Computer Society, 2015. doi:10.1109/FOCS.2015.92.
[3] Sepehr Assadi, Thomas Kesselheim, and Sahil Singla. Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 653–661. SIAM, 2021. doi:10.1137/1.9781611976465.40.
[4] Maria-Florina Balcan and Nicholas J.A. Harvey. Learning submodular functions. Proceedings of The 43rd ACM Symposium on Theory of Computing, pages 793–802, 2011. doi:10.1145/1993636.1993741.
[5] Kiril Bangachev and S. Matthew Weinberg. q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations, 2023. doi:10.48550/arXiv.2304.01451.
[6] Kshipra Bhawalkar and Tim Roughgarden. Welfare guarantees for combinatorial auctions with item bidding. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 700–709, 2011. doi:10.1137/1.9781611973082.55.
[7] O.N. Bondareva. Some applications of linear programming to cooperative games. Problemy Kibernetiki, 1963.
[8] S. Boucheron, G. Lugosi, and P. Massart. A sharp concentration inequality with applications. Random Struct. Algorithms, 16:277–292, 2000. doi:10.1002/(SICI)1098-2418(200005)16:3\%3C277::AID-RSA4\%3E3.0.CO;2-1.
[9] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. On concentration of self-bounding functions. Electronic Journal of Probability, 14, 2009. doi:10.1214/EJP.v14-690.
[10] Yang Cai and Mingfei Zhao. Simple mechanisms for subadditive buyers via duality. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 170–183. ACM, 2017. doi:10.1145/3055399.3055465.
[11] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 311–320. ACM, 2010. doi:10.1145/1806689.1806733.
[12] Shuchi Chawla and J. Benjamin Miller. Mechanism design for subadditive agents via an ex ante relaxation. In Vincent Conitzer, Dirk Bergemann, and Yiling Chen, editors, Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, Maastricht, The Netherlands, July 24-28, 2016, pages 579–596. ACM, 2016. doi:10.1145/2940716.2940756.
[13] José Correa and Andrés Cristi. A constant factor prophet inequality for online combinatorial auctions. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 686–697, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585151.
[14] Amir Dembo. Information inequalities and concentration of measure. Annals of Probability, 25:927–939, 1997. URL: https://www.jstor.org/stable/2959616?seq=1.
[15] Nikhil R. Devanur, Jamie Morgenstern, Vasilis Syrgkanis, and S. Matthew Weinberg. Simple auctions with simple strategies. In Tim Roughgarden, Michal Feldman, and Michael Schwarz, editors, Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC ’15, Portland, OR, USA, June 15-19, 2015, pages 305–322. ACM, 2015. doi:10.1145/2764468.2764484.
[16] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. Mathematics of Operations Research, 35:610–618, 2005. doi:10.1145/1060590.1060681.
[17] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Truthful randomized mechanisms for combinatorial auctions. J. Comput. Syst. Sci., 78(1):15–25, 2012. doi:10.1016/j.jcss.2011.02.010.
[18] Paul Dutting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Combinatorial Contracts . In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 815–826, Los Alamitos, CA, USA, February 2022. IEEE Computer Society. doi:10.1109/FOCS52979.2021.00084.
[19] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent contracts. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1311–1324, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585193.
[20] Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput., 49(3):540–582, 2020. doi:10.1137/20M1323850.
[21] Paul Dütting and Thomas Kesselheim. Best-response dynamics in combinatorial auctions with item bidding. Games Econ. Behav., 134:428–448, 2022. doi:10.1016/j.geb.2020.09.006.
[22] Paul Dütting, Thomas Kesselheim, and Brendan Lucier. An o(log log m) prophet inequality for subadditive combinatorial auctions. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 306–317. IEEE, 2020. doi:10.1109/FOCS46700.2020.00037.
[23] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent combinatorial contracts. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1857–1891. SIAM Society for Industrial and Applied Mathematics, 2025. doi:10.1137/1.9781611978322.58.
[24] Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S. Matthew Weinberg. A simple and approximately optimal mechanism for a buyer with complements. Oper. Res., 69(1):188–206, 2021. doi:10.1287/opre.2020.2039.
[25] Tomer Ezra, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, and S. Matthew Weinberg. Settling the communication complexity of combinatorial auctions with two subadditive buyers. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 249–272. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00025.
[26] Yaron Fairstein, Ariel Kulik, and Hadas Shachnai. Modular and submodular optimization with multiple knapsack constraints via fractional grouping. 29th Annual European Symposium on Algorithms, 2021. doi:10.4230/LIPIcs.ESA.2021.41.
[27] Uriel Feige. On maximizing welfare when utility functions are subadditive. Siam Journal on Computing, pages 41–50, 2009. doi:10.1137/070680977.
[28] Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, and Vasilis Syrgkanis. A unifying hierarchy of valuations with complements and substitutes. In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pages 872–878. AAAI Press, 2015. doi:10.1609/AAAI.V29I1.9314.
[29] Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen. Oblivious rounding and the integrality gap. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2016. doi:10.4230/LIPIcs.APPROX-RANDOM.2016.8.
[30] Uriel Feige and Rani Izsak. Welfare maximization and the supermodular degree. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, January 9-12, 2013, pages 247–256. ACM, 2013. doi:10.1145/2422436.2422466.
[31] Michal Feldman, Ophir Friedler, Jamie Morgenstern, and Guy Reiner. Simple mechanisms for agents with complements. In Vincent Conitzer, Dirk Bergemann, and Yiling Chen, editors, Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, Maastricht, The Netherlands, July 24-28, 2016, pages 251–267. ACM, 2016. doi:10.1145/2940716.2940735.
[32] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2015. doi:10.1137/1.9781611973730.10.
[33] Moran Feldman and Rani Izsak. Constrained monotone function maximization and the supermodular degree. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, volume 28 of LIPIcs, pages 160–175. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2014. doi:10.4230/LIPIcs.APPROX-RANDOM.2014.160.
[34] Moran Feldman and Rani Izsak. Building a good team: Secretary problems and the supermodular degree. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1651–1670. SIAM, 2017. doi:10.1137/1.9781611974782.109.
[35] Vitaly Feldman and Jan Vondrák. Optimal bounds on approximation of submodular and xos functions by juntas. Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 227–236, 2013. doi:10.1109/ITA.2014.6804263.
[36] Yiding Feng, Jason D. Hartline, and Yingkai Li. Optimal auctions vs. anonymous pricing: Beyond linear utility. In Anna Karlin, Nicole Immorlica, and Ramesh Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 885–886. ACM, 2019. doi:10.1145/3328526.3329603.
[37] Yaonan Jin, Shunhua Jiang, Pinyan Lu, and Hengjie Zhang. Tight revenue gaps among multi-unit mechanisms. In Péter Biró, Shuchi Chawla, and Federico Echenique, editors, EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, pages 654–673. ACM, 2021. doi:10.1145/3465456.3467621.
[38] Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao. Tight approximation ratio of anonymous pricing. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 674–685. ACM, 2019. doi:10.1145/3313276.3316331.
[39] Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, and Tao Xiao. Tight revenue gaps among simple mechanisms. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 209–228. SIAM, 2019. doi:10.1137/1.9781611975482.14.
[40] Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econ. Behav., 113:97–115, 2019. doi:10.1016/j.geb.2014.11.002.
[41] Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, and S. Matthew Weinberg. Approximation schemes for a unit-demand buyer with independent items via symmetries. Proceedings of The 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, pages 220–232, 2019. doi:10.1109/FOCS.2019.00023.
[42] Shengwu Li. Obviously strategyproof mechanisms. American Economics Review, 107(11):3257–3287, 2017.
[43] Colin McDiarmid and Bruce A. Reed. Concentration for self-bounding functions and an inequality of talagrand. Random Struct. Algorithms, 29(4):549–557, 2006. doi:10.1002/rsa.20145.
[44] Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
[45] Marek Pycia and Peter Troyan. Obvious dominance and random priority. In Anna Karlin, Nicole Immorlica, and Ramesh Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, page 1. ACM, 2019. doi:10.1145/3328526.3329613.
[46] Tim Roughgarden, Vasilis Syrgkanis, and Éva Tardos. The price of anarchy in auctions. Journal of Artificial Intelligence Research, 59, 2016. doi:10.1613/jair.5272.
[47] Aviad Rubinstein and S. Matthew Weinberg. Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. ACM Transactions on Economics and Computation, 6:1–25, 2018. doi:10.1145/3105448.
[48] Gideon Schechtman. Chapter 37 - concentration, results and applications. In Handbook of the Geometry of Banach Spaces, pages 1603–1634. Elsevier Science B.V., 2003. doi:10.1016/S1874-5849(03)80044-X.
[49] L.S. Shapley. On balanced sets and cores. Naval Res. Logistics Q., 14:453–460, 1967.
[50] Michel Talagrand. New concentration inequalities in product spaces. Inventiones mathematicae, 126:505–563, 1996. doi:10.1007/s002220050108.
[51] Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications mathématiques de l’IHÉS, 81, 2001. URL: https://arxiv.org/abs/math/9406212.
[52] Jan Vondrák. A note on concentration of submodular functions. CoRR, 2010. arXiv:1005.2791.
[53] Qiqi Yan. Mechanism design via correlation gap. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 710–719. SIAM, 2011. doi:10.1137/1.9781611973082.56.

[bib.bib1] [1] Ittai Abraham, Moshe Babaioff, Shaddin Dughmi, and Tim Roughgarden. Combinatorial auctions with restricted complements. In Boi Faltings, Kevin Leyton-Brown, and Panos Ipeirotis, editors, Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012, pages 3–16. ACM, 2012. doi:10.1145/2229012.2229016.

[bib.bib2] [2] Saeed Alaei, Jason D. Hartline, Rad Niazadeh, Emmanouil Pountourakis, and Yang Yuan. Optimal auctions vs. anonymous pricing. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1446–1463. IEEE Computer Society, 2015. doi:10.1109/FOCS.2015.92.

[bib.bib3] [3] Sepehr Assadi, Thomas Kesselheim, and Sahil Singla. Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 653–661. SIAM, 2021. doi:10.1137/1.9781611976465.40.

[bib.bib4] [4] Maria-Florina Balcan and Nicholas J.A. Harvey. Learning submodular functions. Proceedings of The 43rd ACM Symposium on Theory of Computing, pages 793–802, 2011. doi:10.1145/1993636.1993741.

[bib.bib5] [5] Kiril Bangachev and S. Matthew Weinberg. q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations, 2023. doi:10.48550/arXiv.2304.01451.

[bib.bib6] [6] Kshipra Bhawalkar and Tim Roughgarden. Welfare guarantees for combinatorial auctions with item bidding. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 700–709, 2011. doi:10.1137/1.9781611973082.55.

[bib.bib7] [7] O.N. Bondareva. Some applications of linear programming to cooperative games. Problemy Kibernetiki, 1963.

[bib.bib8] [8] S. Boucheron, G. Lugosi, and P. Massart. A sharp concentration inequality with applications. Random Struct. Algorithms, 16:277–292, 2000. doi:10.1002/(SICI)1098-2418(200005)16:3\%3C277::AID-RSA4\%3E3.0.CO;2-1.

[bib.bib9] [9] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. On concentration of self-bounding functions. Electronic Journal of Probability, 14, 2009. doi:10.1214/EJP.v14-690.

[bib.bib10] [10] Yang Cai and Mingfei Zhao. Simple mechanisms for subadditive buyers via duality. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 170–183. ACM, 2017. doi:10.1145/3055399.3055465.

[bib.bib11] [11] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 311–320. ACM, 2010. doi:10.1145/1806689.1806733.

[bib.bib12] [12] Shuchi Chawla and J. Benjamin Miller. Mechanism design for subadditive agents via an ex ante relaxation. In Vincent Conitzer, Dirk Bergemann, and Yiling Chen, editors, Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, Maastricht, The Netherlands, July 24-28, 2016, pages 579–596. ACM, 2016. doi:10.1145/2940716.2940756.

[bib.bib13] [13] José Correa and Andrés Cristi. A constant factor prophet inequality for online combinatorial auctions. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 686–697, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585151.

[bib.bib14] [14] Amir Dembo. Information inequalities and concentration of measure. Annals of Probability, 25:927–939, 1997. URL: https://www.jstor.org/stable/2959616?seq=1.

[bib.bib15] [15] Nikhil R. Devanur, Jamie Morgenstern, Vasilis Syrgkanis, and S. Matthew Weinberg. Simple auctions with simple strategies. In Tim Roughgarden, Michal Feldman, and Michael Schwarz, editors, Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC ’15, Portland, OR, USA, June 15-19, 2015, pages 305–322. ACM, 2015. doi:10.1145/2764468.2764484.

[bib.bib16] [16] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. Mathematics of Operations Research, 35:610–618, 2005. doi:10.1145/1060590.1060681.

[bib.bib17] [17] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Truthful randomized mechanisms for combinatorial auctions. J. Comput. Syst. Sci., 78(1):15–25, 2012. doi:10.1016/j.jcss.2011.02.010.

[bib.bib18] [18] Paul Dutting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Combinatorial Contracts . In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 815–826, Los Alamitos, CA, USA, February 2022. IEEE Computer Society. doi:10.1109/FOCS52979.2021.00084.

[bib.bib19] [19] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent contracts. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1311–1324, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585193.

[bib.bib20] [20] Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput., 49(3):540–582, 2020. doi:10.1137/20M1323850.

[bib.bib21] [21] Paul Dütting and Thomas Kesselheim. Best-response dynamics in combinatorial auctions with item bidding. Games Econ. Behav., 134:428–448, 2022. doi:10.1016/j.geb.2020.09.006.

[bib.bib22] [22] Paul Dütting, Thomas Kesselheim, and Brendan Lucier. An o(log log m) prophet inequality for subadditive combinatorial auctions. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 306–317. IEEE, 2020. doi:10.1109/FOCS46700.2020.00037.

[bib.bib23] [23] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent combinatorial contracts. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1857–1891. SIAM Society for Industrial and Applied Mathematics, 2025. doi:10.1137/1.9781611978322.58.

[bib.bib24] [24] Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S. Matthew Weinberg. A simple and approximately optimal mechanism for a buyer with complements. Oper. Res., 69(1):188–206, 2021. doi:10.1287/opre.2020.2039.

[bib.bib25] [25] Tomer Ezra, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, and S. Matthew Weinberg. Settling the communication complexity of combinatorial auctions with two subadditive buyers. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 249–272. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00025.

[bib.bib26] [26] Yaron Fairstein, Ariel Kulik, and Hadas Shachnai. Modular and submodular optimization with multiple knapsack constraints via fractional grouping. 29th Annual European Symposium on Algorithms, 2021. doi:10.4230/LIPIcs.ESA.2021.41.

[bib.bib27] [27] Uriel Feige. On maximizing welfare when utility functions are subadditive. Siam Journal on Computing, pages 41–50, 2009. doi:10.1137/070680977.

[bib.bib28] [28] Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, and Vasilis Syrgkanis. A unifying hierarchy of valuations with complements and substitutes. In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pages 872–878. AAAI Press, 2015. doi:10.1609/AAAI.V29I1.9314.

[bib.bib29] [29] Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen. Oblivious rounding and the integrality gap. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2016. doi:10.4230/LIPIcs.APPROX-RANDOM.2016.8.

[bib.bib30] [30] Uriel Feige and Rani Izsak. Welfare maximization and the supermodular degree. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, January 9-12, 2013, pages 247–256. ACM, 2013. doi:10.1145/2422436.2422466.

[bib.bib31] [31] Michal Feldman, Ophir Friedler, Jamie Morgenstern, and Guy Reiner. Simple mechanisms for agents with complements. In Vincent Conitzer, Dirk Bergemann, and Yiling Chen, editors, Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, Maastricht, The Netherlands, July 24-28, 2016, pages 251–267. ACM, 2016. doi:10.1145/2940716.2940735.

[bib.bib32] [32] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2015. doi:10.1137/1.9781611973730.10.

[bib.bib33] [33] Moran Feldman and Rani Izsak. Constrained monotone function maximization and the supermodular degree. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, volume 28 of LIPIcs, pages 160–175. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2014. doi:10.4230/LIPIcs.APPROX-RANDOM.2014.160.

[bib.bib34] [34] Moran Feldman and Rani Izsak. Building a good team: Secretary problems and the supermodular degree. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1651–1670. SIAM, 2017. doi:10.1137/1.9781611974782.109.

[bib.bib35] [35] Vitaly Feldman and Jan Vondrák. Optimal bounds on approximation of submodular and xos functions by juntas. Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 227–236, 2013. doi:10.1109/ITA.2014.6804263.

[bib.bib36] [36] Yiding Feng, Jason D. Hartline, and Yingkai Li. Optimal auctions vs. anonymous pricing: Beyond linear utility. In Anna Karlin, Nicole Immorlica, and Ramesh Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 885–886. ACM, 2019. doi:10.1145/3328526.3329603.

[bib.bib37] [37] Yaonan Jin, Shunhua Jiang, Pinyan Lu, and Hengjie Zhang. Tight revenue gaps among multi-unit mechanisms. In Péter Biró, Shuchi Chawla, and Federico Echenique, editors, EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, pages 654–673. ACM, 2021. doi:10.1145/3465456.3467621.

[bib.bib38] [38] Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao. Tight approximation ratio of anonymous pricing. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 674–685. ACM, 2019. doi:10.1145/3313276.3316331.

[bib.bib39] [39] Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, and Tao Xiao. Tight revenue gaps among simple mechanisms. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 209–228. SIAM, 2019. doi:10.1137/1.9781611975482.14.

[bib.bib40] [40] Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econ. Behav., 113:97–115, 2019. doi:10.1016/j.geb.2014.11.002.

[bib.bib41] [41] Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, and S. Matthew Weinberg. Approximation schemes for a unit-demand buyer with independent items via symmetries. Proceedings of The 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, pages 220–232, 2019. doi:10.1109/FOCS.2019.00023.

[bib.bib42] [42] Shengwu Li. Obviously strategyproof mechanisms. American Economics Review, 107(11):3257–3287, 2017.

[bib.bib43] [43] Colin McDiarmid and Bruce A. Reed. Concentration for self-bounding functions and an inequality of talagrand. Random Struct. Algorithms, 29(4):549–557, 2006. doi:10.1002/rsa.20145.

[bib.bib44] [44] Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.

[bib.bib45] [45] Marek Pycia and Peter Troyan. Obvious dominance and random priority. In Anna Karlin, Nicole Immorlica, and Ramesh Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, page 1. ACM, 2019. doi:10.1145/3328526.3329613.

[bib.bib46] [46] Tim Roughgarden, Vasilis Syrgkanis, and Éva Tardos. The price of anarchy in auctions. Journal of Artificial Intelligence Research, 59, 2016. doi:10.1613/jair.5272.

[bib.bib47] [47] Aviad Rubinstein and S. Matthew Weinberg. Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. ACM Transactions on Economics and Computation, 6:1–25, 2018. doi:10.1145/3105448.

[bib.bib48] [48] Gideon Schechtman. Chapter 37 - concentration, results and applications. In Handbook of the Geometry of Banach Spaces, pages 1603–1634. Elsevier Science B.V., 2003. doi:10.1016/S1874-5849(03)80044-X.

[bib.bib49] [49] L.S. Shapley. On balanced sets and cores. Naval Res. Logistics Q., 14:453–460, 1967.

[bib.bib50] [50] Michel Talagrand. New concentration inequalities in product spaces. Inventiones mathematicae, 126:505–563, 1996. doi:10.1007/s002220050108.

[bib.bib51] [51] Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications mathématiques de l’IHÉS, 81, 2001. URL: https://arxiv.org/abs/math/9406212.

[bib.bib52] [52] Jan Vondrák. A note on concentration of submodular functions. CoRR, 2010. arXiv:1005.2791.

[bib.bib53] [53] Qiqi Yan. Mechanism design via correlation gap. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 710–719. SIAM, 2011. doi:10.1137/1.9781611973082.56.

q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Motivation

1.2 Results Part I: Defining 𝒒-partitioning valuations

1.3 Results Part II: Posted price mechanisms and concentration inequalities

Posted Price Mechanisms.

Main Result I.

Concentration Inequalities.

Main Result II.

Main Result III.

1.4 Related Work and Connection to Subadditive MPH-𝒌

Hierarchies of Valuation Functions.

Posted price mechanisms.

Concentration Inequalities.

1.5 Summary and Roadmap

2 Preliminaries

Standard Valuation Classes.

PH-𝒌, MPH-𝒌, and Subadditive MPH-𝒌 valuations.

Definition 1.

3 The Partitioning Interpolation

Definition 2.

Proposition 3.

Proposition 4.

Definition 5.

Theorem 6.

3.1 Interpretation in Cost Sharing

3.1.1 Recap: characterizing XOS via cost-sharing

Theorem 7 ([7, 49]).

Theorem 8.

Theorem 9.

3.1.2 𝒒-partitioning via cost-sharing

Proposition 10.

Proposition 11.

3.2 The Dual Definition and Relation to MPH Hierarchy

Observation 12.

Definition 13.

Proposition 14.

Proof.

▶ Remark 15.

4 Main Result I: Posted Price Mechanisms

Theorem 16.

Lemma 17 ([22, Eq. (6)]).

Proposition 18.

Proof.

5 Main Result II: Concentration Inequalities

Theorem 19.

Theorem 20.

5.1 A Probabilistic Detour: A New Isoperimetric Concentration Inequality

Theorem 21.

6 Conclusion

Precise closeness of 𝓠⁢(𝒒,[𝒎]) to 𝓠⁢(𝒒′,[𝒎]).

Constructing “hard” 𝒒-Partitioning valuations.

Applications in Algorithmic Game Theory.

Concentration Inequalities.

References

$q$ -Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

1.2 Results Part I: Defining $𝒒$ -partitioning valuations

1.4 Related Work and Connection to Subadditive MPH- $𝒌$

PH- $𝒌,$ MPH- $𝒌,$ and Subadditive MPH- $𝒌$ valuations.

3.1.2 $𝒒$ -partitioning via cost-sharing

$\blacktriangleright$ Remark 15.

Precise closeness of $\mathcal{Q}(q,[m])$ to $\mathcal{Q}(q^{\prime},[m])$ .

Constructing “hard” $𝒒$ -Partitioning valuations.