Timezone: »

 
Spotlight
The Adaptive Complexity of Maximizing a Gross Substitutes Valuation
Ron Kupfer · Sharon Qian · Eric Balkanski · Yaron Singer

Tue Dec 08 07:00 AM -- 07:10 AM (PST) @ Orals & Spotlights: Learning Theory
in Orals & Spotlights Track 11: Learning Theory »

In this paper, we study the adaptive complexity of maximizing a monotone gross substitutes function under a cardinality constraint. Our main result is an algorithm that achieves a 1-epsilon approximation in O(log n) adaptive rounds for any constant epsilon > 0, which is an exponential speedup in parallel running time compared to previously studied algorithms for gross substitutes functions. We show that the algorithmic results are tight in the sense that there is no algorithm that obtains a constant factor approximation in o(log n) rounds. Both the upper and lower bounds are under the assumption that queries are only on feasible sets (i.e., of size at most k). We also show that under a stronger model, where non-feasible queries are allowed, there is no non-adaptive algorithm that obtains an approximation better than 1/2 + epsilon. Both lower bounds extend to the class of OXS functions. Additionally, we conduct experiments on synthetic and real data sets to demonstrate the near-optimal performance and efficiency of the algorithm in practice.

Author Information

Ron Kupfer (The Hebrew University of Jerusalem)
Sharon Qian (Harvard)
Eric Balkanski (Harvard)
Yaron Singer (Harvard University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors