Linear Program Representations of Bayesian Mechanisms

Hu Fu, Computer Science IAM Seminar
February 22, 2021 3:00 pm Zoom

In the 1990s, Border proposed  succinct representations of Bayesian auctions in terms of interim allocation rules, describing each agent’s allocation in expectation over the other agents’ types; this contrasts with ex post allocations, which prescribe each agent’s allocation given the other agents’ types.  Border gave necessary and sufficient conditions for feasible interim allocations.  In the past decade, fast algorithms have been developed that optimize over these exponentially many constraints and realize any feasible interim allocation rule by ex post allocations.  These algorithms enable computationally efficient searches for optimal Bayesian mechanisms that go far beyond classical results.  

In this talk, I will describe this development, and give, for single item auctions, a polynomial-sized extended representation of Border’s constraints.  The latter makes it practical (as well as computationally feasible) to optimize over Bayesian mechanisms for a single item. 

RSVP here.  (No need to RSVP if you already receive IAM seminar announcements by email.)