 Winner determination problem

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.