Sketching valuation functions

Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, Tim Roughgarden

TL;DR

This paper explores how to efficiently represent complex valuation functions (used in settings like combinatorial auctions) using "sketches" – smaller, approximate versions. The authors show that subadditive functions can be sketched with a certain approximation ratio using "demand queries," a more powerful query type than standard value queries. They also establish fundamental limits on how well these functions can be sketched, connecting sketching to learning theory.

What Problem Does This Paper Address?

In scenarios like combinatorial auctions, where multiple buyers bid on bundles of items, understanding each buyer's valuation for different item combinations is crucial. These valuations can be complex, often represented as "set functions" that map any subset of items to a value. Communicating or storing these full functions can be computationally expensive, as there are $2^n$ possible subsets for $n$ items. The paper addresses the problem of "sketching" these valuation functions: finding a much smaller representation (a sketch) that approximates the original function's values within a certain ratio. This is important for efficient communication, storage, and potentially for learning these valuations. The authors focus on specific classes of set functions, particularly subadditive and submodular functions, which have economic interpretations.

Methods

The paper introduces and utilizes several key techniques:

  • Sketching Definition: A function $f'$ is an $\alpha$-sketch of $f$ if $f(S) \le f'(S) \le \alpha f(S)$ for all sets $S$, and $f'$ can be represented with a polynomial number of bits.
  • Demand Queries: A more powerful query mechanism than standard value queries. A demand query on a function $f$ with a price vector $p$ returns a set $S$ that maximizes $f(S) - \sum_{j \in S} p_j$.
  • Ellipsoidal Approximation: Building on prior work for submodular functions, the authors use ellipsoids to approximate the polytope defined by the valuation function. This is a geometric approach to finding approximations.
  • Universal Sequences: A novel concept introduced to characterize subadditive functions, which helps in constructing approximations.
  • Probabilistic Method: Used in proving lower bounds, particularly for constructing specific functions that are hard to sketch.
  • Connection to Learning: The paper establishes a link between the ability to sketch a class of valuations and the ability to learn them in the PMAC (Probably Mostly Approximately Correct) model.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Demand Queries are Key for Subadditive Functions: The paper demonstrates that while subadditive functions are "harder" than submodular ones, they can be efficiently sketched using demand queries, suggesting that the richer query model is essential for achieving good approximations.
  • Fundamental Limits Exist: The paper establishes tight lower bounds, showing that for certain classes of functions (like XOS), no sketch can achieve an approximation ratio better than $\Omega(\sqrt{n})$ without an exponential number of queries. This highlights the inherent difficulty of sketching these functions.
  • Sketching Implies Learnability: A significant theoretical contribution is showing that if a class of valuation functions admits an $\alpha$-sketch, then it can be $\alpha$-approximately learned. This provides a powerful framework for understanding learnability in terms of sketching capabilities.
  • Coverage Functions are "Easy" to Sketch: Coverage functions, a subclass of submodular functions, admit arbitrarily good sketches, meaning they can be approximated very closely with a small representation.

Key Results

  • Subadditive Functions: For every subadditive function, an $\tilde{O}(\sqrt{n})$-sketch can be found using a polynomial number of demand queries.
  • Lower Bounds for Subadditive Functions:
    • There exist subadditive (specifically XOS) functions that do not admit an $o(\sqrt{n})$-sketch.
  • Every deterministic algorithm using only value queries cannot guarantee a sketching ratio better than $n^{1-\epsilon}$ for any $\epsilon > 0$.
  • Coverage Functions: Admit arbitrarily good $(1+\epsilon)$-sketches.
  • XOS Functions: Require an exponential number of value queries for an $n^{1/2-\epsilon}$-sketch.
  • Sketching and Learning: If a class of valuations admits an $\alpha$-sketch, it can be $\alpha$-approximately learned (PMAC learning).

Limitations and Future Work

  • Computational Efficiency of Sketching: While the paper shows the existence of $\tilde{O}(\sqrt{n})$-sketches for subadditive functions using demand queries, it acknowledges that this is not computationally efficient in general. The focus is on information-theoretic bounds and query complexity.
  • Open Questions: The paper poses open questions, such as whether coverage functions can be sketched using only value or demand queries, and whether better than $\tilde{O}(\log n)$-supporting prices can be achieved for XOS functions using demand queries.
  • Information-Theoretic Bounds: The connection between sketching and learning provides information-theoretic bounds, but the paper explicitly states that these do not imply the existence of computationally efficient learning algorithms in general.
  • General Subadditive Functions: While the paper provides a $\tilde{O}(\sqrt{n})$-sketch for subadditive functions, it also highlights that for certain specific subadditive functions, no submodular function can provide a better than $n^{1/2}$-approximation.

Summary updated

Abstract

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