The Price is (Probably) Right: Learning Market Equilibria from Samples
This work is significant for market designers and economists who need to find fair and efficient allocations in markets where individual preferences are not explicitly known.
This paper addresses the problem of computing market equilibria when player valuation functions are unknown, a common scenario in real-world markets. It introduces algorithms that directly output PAC equilibrium allocations without first learning valuation functions, and provides lower bounds on the efficiency of these algorithms. For unit-demand valuations, the algorithms achieve significantly better utility compared to general distributions.
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.