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