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
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.