L'attività di ricerca si riferisce al periodo 2005-2007.
Il concetto di equilibrio riveste un ruolo centrale nella teoria economica e nella teoria dei giochi. Il problema del calcolo di equilibri in giochi e mercati è un problema fondamentale in Informatica, per il suo legame con importanti problemi matematici (teoremi del punto fisso, zeri di polinomi) e per la vastità delle applicazioni.
E' stato dato un contributo sostanziale all'avanzamento delle conoscenze sull'argomento in diverse direzioni. Innanzitutto si è contribuito all'estensione delle famiglie di problemi per cui l'equilibrio è calcolabile in tempo polinomiale, arrivando all'inclusione di classi di problemi di grande interesse applicativo (mercati con funzioni di utilità con "elasticità della sostituzione"costante) [1]. Inoltre è stata determinata una corrispondenza uno a uno tra giochi a due persone in forma normale e alcune famiglie di mercati, corrispondenza che consente di dimostrare che per tali mercati non e' possibile introdurre algoritmi efficienti, modulo la veridicità di alcune congetture classiche in complessità computazionale [2].
Riferimenti:
[1] Market Equilibrium via the Excess Demand Function (B. Codenotti, B. McCune and K. Varadarajan). Proceedings of STOC 2005.
[2] Leontief Economies Encode Nonzero Sum Two-Player Games (B. Codenotti, A. Saberi, K. Varadarajan, Y. Ye). Electronic Colloquium on Computational Complexity, Report TR05-055. Proceedings of SODA 2006.
Focus