84 KAM Mathematical Colloquium

Vijay V. Vazirani

Georgia Institute of Technology

NEW (PRACTICAL) COMPLEMENTARY PIVOT ALGORITHMS FOR MARKET EQUILIBRIA

---

středa 5. června 2013 v 11:00, posluchárna S3, třetí patro
KAM MFF UK
Malostranské nám. 25
118 00 Praha 1

---

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
 

---

O přednášejícím

Vijay V. Vazirani studoval informatiku na MIT, Kalifornské universitě v Berkeley a 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 šíří vpodstatě v cele 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í dobe v centru jeho pozornosti a je také námětem jeho pražského kolokvia.




 

---