Abstract

This talk focuses on Fisher markets, a special case of general equilibrium theory that achieves efficient and fair allocations for divisible goods. A new class of utility functions, called constrained piecewise linear concave (PLC) utility functions, will be introduced. This general class captures many well-studied special cases, including markets with PLC utilities, markets with satiation, and matching markets. For the special case of PLC utilities, although the problem is PPAD-hard, Devanur and Kannan(FOCS 2008) gave a polynomial-time algorithm when the number of goods is constant. 

Our main result is a fixed parameter approximation scheme for computing an approximate equilibrium,where the parameters are the number of agents and the approximation accuracy. This is a joint work with Jugal Garg and László Végh.

Time

2023-06-18  11:00 - 11:30   

Speaker

Yixin Tao, ITCS@SUFE

Room

Guangdong Hotel