Sketching valuation functions

• DOI: 10.5555/2095116.2095197
• Publication Date: 2012-01-17
• Authors: Ashwinkumar Badan...; Shahar Dobzinski; Hu Fu; Robert Kleinberg; Noam Nisan; Tim Roughgarden
• Keywords: Subadditivity; Submodular set function; Sketch; Infimum and supremum; Value (mathematics)

Motivated by the problem of querying and communicating bidders' valuations in combinatorial auctions, we study how well different classes set functions can be sketched. More formally, let f a function mapping subsets some ground [n] to non-negative real numbers. We say that f' is an α-sketch if for every S, value f'(S) lies between f(S)/α f(S), specified poly(n) bits.We show subadditive there exists where α = n1/2. O(polylog(n)). Furthermore, provide algorithm finds these sketches with polynomial number demand queries. This essentially best hope since:1. exist (in fact, XOS functions) do not admit o(n1/2) sketch. (Balcan Harvey [3] previously showed belonging class substitutes O(n1/3) sketch.)2. prove deterministic accesses via queries only cannot guarantee sketching ratio better than n1−e.We also coverage functions, interesting subclass submodular arbitrarily good sketches.Finally, connection learning. valuations, admits α-sketch, then it α-approximately learned PMAC model Balcan Harvey. The bounds are information-theoretic imply existence computationally efficient learning algorithms general.