New directions in how computer science can inform the design of economic mechanisms and systems: Automated mechanism design, necessarily exponentially long theories, AI mediators, and fast convergence to high welfare

I will present new results in four directions in how computer science can inform the design of economic mechanisms and systems. First, I will discuss automated mechanism design, with a focus on the number of samples one needs from the prior distribution, and also how flexible a mechanism class one should optimize over given a number of samples. Second, I will show that there are cases where the characterization of an optimal mechanism—e.g., optimal multi-item sales mechanism—requires an exponentially long description and that may explain why manual mechanism design has not been able to solve the problem for over 40 years. Third, I will describe AI mediators. Perhaps surprisingly, an optimal communication equilibrium (of which mechanism design and information design are special cases) can be computed in polynomial time, and the recent breakthroughs in two-player imperfect-information game solving can be leveraged for the problem. I will also discuss how the mediator can steer the agents to a good equilibrium. Fourth, I present a family of no-regret learning dynamics (including optimistic mirror descent (OMD)) that either reaches a Nash equilibrium or yields welfare greater than the robust price of anarchy. This yields the best approximation bound for welfare maximization under polynomial-time algorithms. I also show that when full efficiency is guaranteed via smoothness, Nash equilibrium finding is tractable via OMD. Finally, in 2-player games, when OMD does not converge to a Nash equilibrium, OMD converges to coarse correlated equilibrium with an infinite rate of convergence, i.e., in strongly polynomial time.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.