Faculty Recruiting Support CICS

Learning Market Equilibria from Samples

21 Apr
Wednesday, 04/21/2021 12:15pm to 1:15pm
Virtual via Zoom
Theory Seminar
Speaker: Vignesh Viswanathan

Abstract: Equilibrium computation in markets usually considers settings where player valuation functions are known. In this talk, I will explore the setting where player valuations are unknown; using a Probably Approximately Correct (PAC) learning-theoretic framework, I will analyze some classes of common valuation functions, and present 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, I will also lower-bound the efficiency of our algorithms.

Original Paper: The Price is (Probably) Right: Learning Market Equilibria from Samples

Join the Zoom meeting

The CICS Theory Seminar is online, free and open to the public. If you are interested in giving a talk, please email Professor Immerman or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.