TechFest Workshop - Theory Day - Session 5

Опубликовано 11 августа 2016, 7:42

Janardhan Kulkarni - Price of Anarchy Bounds Via Duality The price of anarchy (PoA), which quantifies the degradation in the quality of outcomes in a (pure) Nash equilibrium of a game, is of fundamental importance in computational game theory. For many games, a pure NE does not exist, and hence a natural goal is to quantify the inefficiency of notions such as mixed Nash equilibrium and correlated equilibrium, which always exist for finite games. We give a new framework, based on LP and convex programming duality, for bounding the price of anarchy for (coarse) correlated equilibrium. We demonstrate applicability of this framework by giving the first PoA bounds for temporal routing and scheduling games, and alternate proofs for several classical games.