Supermodular set function Created 2026-10-06 Updated 2026-11-05
A set function is supermodular whenEquivalently, is a submodular set function. On a finite ground set, this means increasing marginal increments: if and , then .
For example, has increment , which increases with the cardinality of . In a convex cooperative game, supermodularity expresses increasing gains from joining larger coalitions; the corresponding marginal allocations lie in the core of a cooperative game.
Union-intersection compression 2026-10-06
An elementary union-intersection compression of a finite multiset of subsets replaces occurrences of by . A compression is a finite sequence of these moves. The move preserves every coordinate multiplicity. On incomparable sets it increases by , so repeated compression reaches a chain under inclusion. For any submodular set function, the sum of its values cannot increase.
Weighted coverage function 2026-11-05
A weighted coverage function assigns nonnegative weights to members of a finite universe , lets each choice cover a subset , and values a selection byAn item covered twice is counted only once. If , and the weights are , then , and .
Its marginal gain of a set function is the total weight of newly covered items. As the selected set grows, fewer uncovered items remain, so the marginal gain of a set function can only decrease. This proves that a weighted coverage function is a monotone submodular set function. Nonnegative weights are essential to this argument. The construction models selecting sensors or experiments whose observations overlap.[ref]
Winner determination problem 2026-10-14
Given bidders' values for item bundles, the winner determination problem maximizes 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.