论文标题
价格（可能）是正确的：从样品中学习市场平衡
The Price is (Probably) Right: Learning Market Equilibria from Samples
论文作者
论文摘要
市场中的均衡计算通常会考虑已知玩家估值功能的设置。我们考虑玩家估值未知的设置；使用PAC学习理论框架，我们分析了一些类别的常见估值功能，并提供了输出直接PAC平衡分配的算法，而不是基于尝试学习估值功能的估计。由于存在琐碎的PAC市场成果，而最差的效率损失是无限的，因此我们降低了算法的效率。尽管一般分布下的效率损失相当高，但我们表明，在某些情况下（例如单位需求估值），可以找到具有更好实用程序的PAC市场平衡。
Equilibrium computation in markets usually considers settings where player valuation functions are known. We consider the setting where player valuations are unknown; using a PAC learning-theoretic framework, we analyze some classes of common valuation functions, and provide algorithms which output direct PAC equilibrium allocations, not estimates based on attempting to learn valuation functions. Since there exist trivial PAC market outcomes with an unbounded worst-case efficiency loss, we lower-bound the efficiency of our algorithms. While the efficiency loss under general distributions is rather high, we show that in some cases (e.g., unit-demand valuations), it is possible to find a PAC market equilibrium with significantly better utility.
