Learning Competitive Equilibria in Noisy Combinatorial Markets
Learning Competitive Equilibria in Noisy Combinatorial Markets
复制标题
DOI：
10.5555/3463952.3464120
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Enrique Areyan Viqueira;Cyrus Cousins;A. Greenwald
中科院分区：
文献类型：
--
作者：
Enrique Areyan Viqueira;Cyrus Cousins;A. Greenwald
我们提出了一种方法来鲁棒估计的竞争均衡（CE）的组合市场的假设下，买家不知道他们的精确估价捆绑的商品，而是只能提供嘈杂的估计。考虑到一个市场与另一个市场的一致逼近，我们首先给出了买家效用损失的严格下限和上限，从而给出了CE集。然后，我们为我们的设置开发了一个学习框架，并提出了两个可能近似正确的算法来学习CE，即，产生保持CE的均匀近似，具有有限样本保证。第一个是一个基线，使用Hoeffding不等式产生一个统一的近似买家的估值与高概率。第二个利用经济学的第一福利定理和统一近似之间的连接，自适应地修剪值查询时，它确定它们是可证明的CE的一部分。我们用我们的算法进行了实验，发现剪枝算法比基线用更少的样本实现了更好的估计。
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.