Abstract
We study PMAC-learning of real-valued set functions with limited complementarity. We prove, to our knowledge, the first nontrivial learnability result for set functions exhibiting complementarity, generalizing Balcan and Harvey’s result for submodular functions. We prove a nearly matching information theoretical lower bound on the number of samples required, complementing our learnability result. We conduct numerical simulations to show that our algorithm is likely to perform well in practice.
Introduction
In economics and algorithmic game theory, set functions are essential tools for modeling how agents value combinations of items. Traditionally, research has focused on complement-free functions, such as submodular functions, which represent the principle of diminishing returns. These functions are mathematically well-behaved and relatively easy to learn.
However, many real-world scenarios involve complementarity—where the value of a bundle exceeds the sum of its parts (e.g., a left and right shoe). While learning arbitrary set functions is computationally intractable, many practical applications exhibit only limited complementarity. This paper bridges the gap by parameterizing the degree of complementarity and providing efficient learning algorithms.
Measuring Complementarity
The authors employ two hierarchies to quantify complementarity: the Supermodular Degree (SD) and Supermodular Width (SMW). These metrics categorize functions based on the minimum size of subsets required to generate synergistic value. By focusing on functions with a bounded degree of complementarity $d$, the learning problem becomes manageable.
The Learning Framework
The learning task is decomposed into two distinct subtasks:
- The Combinatorial Subtask: Identifying the "zeros" of the function. The authors demonstrate that for a function with complementarity degree $d$, all information regarding zero-valued sets is contained within subsets of size at most $d+1$. Algorithm 1 is proposed to track these small "zero sets."
- The Statistical Subtask: Estimating the distribution of positive values. A key theoretical contribution is a new concentration bound showing that, under product distributions, these functions cluster sharply around their median value. Algorithm 2 leverages this by using the empirical mean as a predictor.
Algorithm 3 integrates these components to learn general monotone functions with limited complementarity.
Key Results and Sample Complexity
The paper establishes that functions in the SMW-$d$ hierarchy can be $O(1/\log(\epsilon))$-approximately learned. The required sample complexity is $O(n^{d+1})$, where $n$ is the number of items. Crucially, the authors prove a nearly matching lower bound of $\Omega(n^{d+1})$, indicating that the algorithm's dependence on the complementarity degree is near-optimal.
Empirical Validation
Numerical simulations were conducted using synthetic set functions from the Maximum-over-Positive-Hypergraphs (MPH) hierarchy on a ground set of $n=1000$ items. The results confirm the theoretical prediction of concentration of measure. Even at high degrees of complementarity (e.g., $d=15$), the function values remain remarkably concentrated around the mean.
This concentration suggests that the proposed algorithm is robust and likely to perform well in practical settings, even beyond the theoretical worst-case scenarios.
Conclusion
This work provides the first nontrivial learnability results for set functions with complementarity. While the reliance on product distributions and the exponential scaling with $d$ are limitations, the results offer a significant step toward understanding complex valuation functions in real-world markets. Future research may explore more general distributions or specific structural properties that allow for even more efficient learning.
Summary updated