Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Scienze dell'Informazione - DSI
via Salaria 113, III piano
Aula Seminari

Abstract: Tools from game theory have become fashionable and quite successful in tackling interesting combinatorial optimization and distributed computing problems. On the other hand, importing CS techniques into classical microeconomic research themes such as auction theory and mechanism design has exposed real-life impracticability of some economic theory findings, and has opened some interesting new research questions in algorithm analysis and design. In this talk, I will illustrate this interplay between algorithmic and mechanism design issues on the example of "combinatorial auctions". Combinatorial auctions are mechanisms that allow for a simultaneous sale of multiple items and allow "all-or-nothing" bids on combinations of these items. In particular, I will show how some of the issues in combinatorial auction design have been succesfully addressed by applying results from combinatorial optimization, complexity theory and data structures. Finally, I will discuss how some outstanding issues translate to well-defined problems that the computer science community has not studied yet, but ought to be able to tackle.