Sketching stochastic valuation functions

Milan Vojnović, Yiliu Wang

We consider the problem of sketching set valuation functions, defined as the expectation of a valuation function applied to independent random item values. For valuation functions…