84. matematické kolokvium KAM - prof. Vijay V. Vazirani (Georgia Institute of Technology): New (practical) complementary pivot algorithms for market equilibria

Abstract

Complementary pivot algorithms, in the style of the simplex algorithm, tend to work well in practice despite having an exponential worst case behavior - a case in point being the classic Lemke-Howson algorithm (1964) for 2-player Nash equilibrium. This algorithm also gives a direct proof of membership of the problem in the class PPAD and yields deep structural insights, such as oddness of the number of equilibria.

Our first result accomplishes all of the above for the problem of finding an equilibrium for an Arrow-Debreu market under separable, piecewise linear concave utilities. Our second result extends this to markets with production.

Based on the following paper, and a recent joint work with Jugal Garg and Ruta Mehta: http://www.cc.gatech.edu/~vazirani/SPLC.pdf

Prof. Vazirani přednese ve čtvrtek 6. 6. od 10: 30 v posluchárně S6, 2. patro, druhou - speciálněji zaměřenou - přednášku

MATCHING - A NEW PROOF FOR AN ANCIENT ALGORITHM

Abstract
For all practical purposes, the Micali-Vazirani algorithm, discovered in 1980, is still the most efficient known maximum matching algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication). However, this has remained a "black box" result for the last 32 years. We hope to change this with the help of a recent paper giving a simpler proof and exposition of the algorithm: http://arxiv.org/abs/1210.4594

In the interest of covering all the ideas, we will assume that the audience is familiar with basic notions such as augmenting paths and bipartite matching algorithm.

CV

Vijay V. Vazirani studoval informatiku na MIT, Kalifornské universitě v Berkeley and na Harvardské universitě (kde jeho školiteli byli M. Blum and M. Rabin). Získal též prestižní President Young Investigator Award. Posléze byl zaměstnán na předních institucích v USA a v Indii (IBM, Cornell, Caltech, AT&T Murray Hill, MSRI Berkeley). Od roku 1995 je řádným profesorem na Fakultě Informatiky v Georgia Institute of Technology. Jeho vědecká práce se vyznačuje nebývalou šírí vpodstatě v celé informatice včetně sociálních aspektů disciplíny. V této souvislosti byl například opakovaně hostem laboratoře SISL (Social and Information Sciences Laboratory) na CalTechu.

Vijay je autorem více než 100 článků z teorie algoritmů (včetně známých algoritmů pro párování), teorie složitosti, přibližných algoritmů a mnoha prací věnovaných algoritmům pro trh a tržní rovnováhu (tzv. market equilibria) a algoritmické teorii her. Je autorem několika knih včetně populárních Approximation Algorithms (Springer 2001). Vazirani je editorem 3 mezinárodních časopisů a autorem několika patentů. Dostal několik mezinárodních ocenění, jmenujme např. Googgenheim Fellowship a rovněž byl v roce 2005 zvolen ACM Fellow. Prof Vazirani je znám jako výborný přednášející. Ekonomicky motivovaná informatika je v poslední době v centru jeho pozornosti a je také námětem jeho pražského kolokvia.