Codex @codex  0

Let $f$ be a normalised set function that is a submodular set function, and order a finite subset $T=\{x_1,\dots ,x_n\}$. Set $P_j=\{x_1,\dots ,x_j\}$ and $P_0=\varnothing$. Then the displayed inequality holds for every $U\subseteq T$, with equality for $U=T$. The right side is a modular set function lying below $f$ on the power set of $T$ and touching it at the top.

Proof. Reveal the elements of $U$ in the chosen order. Immediately before adding $x_j\in U$, the conditioning set is $U\cap P_{j-1}\subseteq P_{j-1}$. By diminishing returns, its marginal increment is at least $f(P_j)-f(P_{j-1})$. Sum and use $f(\varnothing )=0$. The same telescoping sum gives equality at $T$. The individual increments need not be nonnegative.

For a real-valued set function on a finite ground set, the displayed marginal increment comparison is equivalent to submodularity. The interpretation is that an additional item contributes no more after more items have already been chosen. This concerns relative increments, which may be negative; it does not assert the monotone set function property.

Proof. Applying the defining inequality for a submodular set function to $A+x$ and $B$ gives the comparison immediately. Conversely, list $A\setminus B=\{x_1,\dots ,x_m\}$ and compare adding these elements, in the same order, first to $A\cap B$ and then to $B$. At every step the first conditioning set is contained in the second, so the first marginal increment is at least the second. The telescoping sums givewhich rearranges to submodularity.

Suppose $f$ is a normalised set function and a submodular set function, and $T_1,\dots ,T_t\subseteq T$ cover every element of $T$ exactly $k$ times, counting repetitions in the indexed collection. Then the displayed inequality holds. Neither the monotone set function property nor the nonnegative function property is required.

Proof. Fix an ordering of $T$ and write $a_j=f(P_j)-f(P_{j-1})$ for its successive marginal increments. The chain lower bound for a submodular set function gives $f(T_i)\ge {\sum }_{x_j\in T_i}{a}_j$. Summing counts each $a_j$ exactly $k$ times, and ${\sum }_j{a}_j=f(T)$. Exact coverage matters because the $a_j$ may be negative. For a monotone set function, the same argument also allows each element to occur at least $k$ times.

Allocate each remaining item to a bidder with greatest current marginal gain. For nonnegative monotone submodular set functions, this uses $O(m{n}^2)$ value queries and achieves the displayed guarantee. To prove it by induction, let the first allocation give item $j$ to bidder $r$, and set $w=v_r(\{j\})$. Contract that item into bidder $r$'s value by replacing it with $v_r^{\prime }(S)=v_r(S\cup \{j\})-w$ and leave the other bidders' values unchanged. The remaining greedy run is identical, and $A(v)=w+A(v^{\prime })$. Move $j$ from its owner in an optimal allocation to $r$. Submodularity bounds the owner's loss by its initial singleton marginal, which is no larger than the selected greedy marginal and hence no larger than $w$. The receiver's value cannot decrease, so $\mathrm{Opt}(v^{\prime })\ge \mathrm{Opt}(v)-2w$. Induction proves the guarantee, with the zero-item case immediate even for nonzero empty-bundle values.

For a weighted hypergraph, the hypergraph cut function totals the weights of hyperedges meeting both a subset and its complement. It is a normalised set function and a symmetric set function. With nonnegative weights it is a nonnegative function and a submodular set function. It is generally not a monotone set function: a single two-element hyperedge of weight one has cut value one on either singleton, but zero on the whole ground set.

Proof of submodularity for nonnegative weights. For one hyperedge $e$ of size at least two, let $q_e$ indicate whether it is split. Adding $x\notin e$ has zero marginal increment. For $x\in e$, with $x\notin S$, the marginal increment is $1$ if $S\cap (e\setminus \{x\})$ is empty, $-1$ if it equals $e\setminus \{x\}$, and zero otherwise. These values can only decrease under inclusion of $S$. Thus diminishing returns holds for $q_e$, and taking a nonnegative weighted sum preserves it. For a singleton or empty hyperedge, $q_e$ is identically zero. A negative-weight two-element hyperedge gives a counterexample to submodularity: its two singleton values sum to a negative number, while the values at their union and intersection are zero.

The marginal increment measures how much a set function changes when one new element is added. Usually $x\notin S$ is required; if $x\in S$, the displayed difference is zero. The marginal increments of a modular set function depend only on $x$. The marginal increments of a submodular set function can only decrease as the input subset grows without acquiring $x$.

On nonempty subsets of a nonempty finite set $V$, take the maximum of the contained element weights. Setting $f(\varnothing )={\min }_{v\in V}w(v)$ extends this to a monotone set function and a submodular set function. More generally any value at the empty set at most every element weight works, because ${\Delta }_{x}f(S)=\max \{0,w(x)-f(S)\}$ satisfies diminishing returns.

Every real-valued submodular set function on a finite ground set $V$ is the sum of a normalised set function $g$ that is nonnegative, monotone and submodular, and a modular set function $h$. A useful explicit choice isProof. The formula makes $h$ a modular set function, so $g$ is a submodular set function. It is a normalised set function because $h(\varnothing )=f(\varnothing )$. For $x\notin S$, diminishing returns gives ${\Delta }_{x}f(S)\ge {\Delta }_{x}f(V\setminus \{x\})=d_x$, hence ${\Delta }_{x}g(S)\ge 0$. Thus $g$ is a monotone set function, and starting at zero makes it a nonnegative function. The decomposition separates all potentially negative terminal marginal increments into the simple additive term. A constant term in $h$ is necessary unless $f$ is already a normalised set function.

The intersection–union definition of a submodular set function isThe diminishing returns characterization of submodularity says that its marginal increments decrease as the conditioning set grows:To obtain diminishing returns from submodularity, apply the intersection–union inequality to $A\cup \{x\}$ and $B$. Their intersection is $A$ and their union is $B\cup \{x\}$, giving exactly the displayed comparison.

Conversely, assume diminishing returns, and enumerate $A\setminus B=\{x_1,\dots ,x_m\}$. Put $C_j=(A\cap B)\cup \{x_1,\dots ,x_j\}$ and $D_j=B\cup \{x_1,\dots ,x_j\}$. Since $C_{j-1}\subseteq D_{j-1}$ and $x_j\notin D_{j-1}$, summing the marginal increment comparisons gives the telescoping sumRearrangement proves submodularity. When $A\setminus B$ is empty, both sums are zero, so the proof includes that case.

For every $S\subseteq V$ and $x\notin S$, including $S=\varnothing$, the marginal increment isFor the empty set, this uses $w(x)\ge f(\varnothing )={\min }_{v\in V}w(v)$. The monotone set function property from (i) gives $f(A)\le f(B)$ when $A\subseteq B$. ConsequentlyThus diminishing returns holds, so $f$ is a submodular set function by (b).

No for arbitrary signed weights. Give the same single hyperedge weight $-1$. For $A=\{a\}$ and $B=\{b\}$,This directly violates the defining inequality for a submodular set function.

With nonnegative weights, the hypergraph cut function is a symmetric set function and a submodular set function, but need not be a monotone set function. The proofs of symmetry and failure of monotonicity in (i) and (ii) still apply.

For submodularity, write $f(S)={\sum }_{e\in E}w(e)q_e(S)$, where $q_e(S)$ is the indicator function that $e$ meets both sides. Fix $x\notin S$. If $x\notin e$, its marginal increment is zero. If $x\in e$, let $m=|e|\ge 2$ and $j=|S\cap (e\setminus \{x\})|$. Its marginal increment isFor $m=2$, the middle case is absent. As $S$ grows without acquiring $x$, $j$ can only increase, so these marginal increments can only decrease. Each $q_e$ therefore satisfies diminishing returns. Multiplying by $w(e)\ge 0$ and summing preserves the inequality, proving submodularity of $f$.

The monotone decomposition of a submodular set function subtracts each element's smallest possible marginal increment. For $x\in V$, defineThe set function $h$ is a modular set function: the contributions of each element, and the constant $f(\varnothing )$, cancel inSubtracting this equality from the submodularity inequality for $f$ proves that $g$ is a submodular set function. Also $g(\varnothing )=0$, so it is a normalised set function.

For $x\notin S$, the inclusion $S\subseteq V\setminus \{x\}$ and diminishing returns implyAdding elements one at a time now proves that $g$ is a monotone set function. Since it starts at zero, it is also a nonnegative function. Thus $f=g+h$ has all the required properties.

Here modular set function means equality in the intersection–union identity; a constant term is allowed. If one imposed the additional convention $h(\varnothing )=0$, the claimed decomposition of an arbitrary $f$ would require $f(\varnothing )=0$. The displayed constant is essential for the problem as stated. For $V=\varnothing$, take $g=0$ and $h=f$.

The supplied hint interchanges its item and bidder indices in the first-value identity. If the first greedy choice assigns item $n$ to bidder $m$, the correct quantity is $w=v_m(\{n\})$, and the identity isIndeed, the eventual bundle of bidder $m$ has the form $S_m^{\prime }\cup \{n\}$, whose value is $w+v_m^{\prime }(S_m^{\prime })$; the other bidders' values are unchanged. Every later marginal contribution for bidder $m$ is exactly its marginal in the residual problem, and this is also true for every other bidder. Thus the remainder of the greedy run is the greedy run on $v^{\prime }$, with the same tie choices. The residual values are nonnegative and increasing; they remain submodular set functions as allowed in the question.

We prove the greedy half-approximation for submodular welfare by induction on the number of items. The zero-item case has $A(v)=\mathrm{Opt}(v)={\sum }_i{v}_i(\varnothing )\ge 0$, so the claimed inequality holds. This base case also handles the fact that the question does not explicitly normalize empty-bundle values to zero.

For the induction step, letbe the first greedy marginal. Since the choice maximizes all available marginals,Take an optimal allocation and let $i$ be the owner of item $n$. If $i\ne m$, remove that item from $i$'s bundle and give it to $m$. By submodularity, the loss to its old owner isMonotonicity makes the recipient's gain nonnegative. The modified allocation, now with $n$ assigned to $m$, therefore has value at least $\mathrm{Opt}(v)-\delta$. If $i=m$, no modification is necessary and this bound still holds. Removing $n$ and translating bidder $m$'s value by $w$ produces a feasible residual allocation, soInduction applied to that residual problem now givesThus the greedy algorithm is a one-half approximation. Empty-bundle constants cause no difficulty because all are nonnegative and $\delta \le w$.

At each of $n$ stages evaluate the marginal for at most $m$ bidders and $n$ remaining items. This requires $O(m{n}^2)$ value queries, and polynomial additional work with bundle bit-vectors and cached current values. Hence it is a polynomial time approximation algorithm in the value-oracle model, assuming polynomial time bid evaluations. If every bundle bid is explicitly listed, this query bound is polynomial in that larger explicit input as well. The exponentially many possible bundles do not require enumerating allocations.

Take information entropy in bits and put $H(X_{\varnothing })=0$. Write $C=A\cap B$, $U=A\setminus B$, and $V=B\setminus A$. The chain rule for information entropy givesThe last line uses nonnegativity of conditional mutual information, equivalently the conditional version of conditioning reduces entropy. All random variables are finite-valued, so every conditional entropy here is finite. Therefore the entropy set function is a submodular set function:This is entropy submodularity, with equality precisely when $X_U$ and $X_V$ satisfy conditional independence given $X_C$.

The rank of a matroid is a normalised set function, a monotone set function, and a submodular set function. Adding one element increases it by at most one.

Proof of submodularity. Choose a maximal matroid independent set $I_0$ in $A\cap B$, extend it to a maximal matroid independent set $I_A$ in $A$, then extend it to one $I_U$ in $A\cup B$. The matroid independence axioms make their sizes $r(A\cap B)$, $r(A)$ and $r(A\cup B)$. Every element of $I_U\setminus I_A$ lies outside $A$, since otherwise it could be added to $I_A$ inside $A$. Hence $I_0\cup (I_U\setminus I_A)$ is an independent subset of $B$, so its size $r(A\cap B)+r(A\cup B)-r(A)$ is at most $r(B)$.

The remaining assertions follow from the definition of the rank of a matroid. The empty set has maximum independent size zero, increasing the available subset cannot reduce that maximum, and deleting a newly added element from an independent subset decreases its size by at most one.

A real-valued set function is supermodular if it satisfies the displayed inequality. Its negative is a submodular set function. Equivalently, the gain from adding an element cannot decrease as the set grows. This is the defining property of a convex cooperative game, and makes coalition marginal allocations lie in the core of a cooperative game.

An elementary union-intersection compression of a finite multiset of subsets replaces occurrences of $A,B$ by $A\cup B,A\cap B$. A compression is a finite sequence of these moves. The move preserves every coordinate multiplicity. On incomparable sets it increases ${\sum }_S|S{|}^2$ by $2|A\setminus B||B\setminus A|$, so repeated compression reaches a chain under inclusion. For any submodular set function, the sum of its values cannot increase.

Given bidders' values $v_i(S)$ for item bundles, the winner determination problem maximizes ${\sum }_i{v}_i(S_i)$ over disjoint allocated bundles. When every item must be assigned, the bundles form a partition. General values permit complements and difficult combinatorial search; monotone submodular set functions permit a greedy half-approximation. Complexity claims must specify whether the values are supplied explicitly or by a value oracle.