Learning Competitive Equilibria in Noisy Combinatorial Markets

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 present two probably-approximately-correct algorithms for learning CE with finite-sample guarantees. The first is a baseline and the second leverages a connection between the first welfare theorem of economics and uniform approximations to adaptively prune value queries when it is determined that they are provably not part of a CE. Extensive experimentation shows that pruning achieves better estimates than the baseline with far fewer samples.