= Winner determination problem
= WDP
{c}
{synonym}
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.
Back to article page
