  We present a methodology to robustly estimate the competitive equilibria (CE)
of combinatorial markets under the assumption that buyers do not know their
precise valuations for bundles of goods, but instead can only provide noisy
estimates. We first show tight lower- and upper-bounds on the buyers' utility
loss, and hence the set of CE, given a uniform approximation of one market by
another. We then develop a learning framework for our setup, and present two
probably-approximately-correct algorithms for learning CE, i.e., producing
uniform approximations that preserve CE, with finite-sample guarantees. The
first is a baseline that uses Hoeffding's inequality to produce a uniform
approximation of buyers' valuations with high probability. The second leverages
a connection between the first welfare theorem of economics and uniform
approximations to adaptively prune value queries when it determines that they
are provably not part of a CE. We experiment with our algorithms and find that
the pruning algorithm achieves better estimates than the baseline with far
fewer samples.
