Industrial Engineering Seminar Series - Tınaz Ekim

Title: The Nobel Prize in Economic Sciences 2012 and Matching Theory

Abstract: The Nobel Prize in Economic Sciences 2012 was awarded jointly to A. E. Roth and L. S. Shapley “for the theory of stable allocations and the practice of market design.” The reason why it was awarded to A. E. Roth and L. S. Shapley is two-fold: their extremely valuable efforts in applying scientific findings to very important real life problems such as kidney exchange and student placement problems, and their contribution to the theory of stable matchings. In this talk, we will first present some basic notions about stable matchings such as the Gale-Shapley Algorithm, and then discuss about some variations. Two important applications, namely student placement and kidney exchange problems, will be given special consideration. The main focus of the talk will be the role of graph theory in the study of stable matchings. In particular, the links between stable matchings and the problem of finding an inclusion-wise maximal matching of minimum size will be explored. As a natural consequence of this link, the field of graph classes which became increasingly important, will be presented. The approach of using graph classes to solve hard problems in networks will be illustrated with examples from matching theory.

Short Bio: Tınaz Ekim is an Associate Professor in the Department of Industrial Engineering at Bogaziçi University. She completed her MS degree at the Université Paris Dauphine in the Computer Science and Mathematics Department. She obtained her PhD in 2006 in Operations Research from Ecole Polytechnique Fédérale de Lausanne (EPFL). Her research focuses on Structural and Algorithmic Graph Theory, Combinatorial Optimization and Complexity Theory. She was the director of three bilateral research grants with France and Slovenia, director of two national TÜBİTAK grants and four BAP grants. She is also the recipient of the Young Scientist Award 2016 (GEBİP) given by the Turkish Academy of Sciences. She was a Fulbright Visiting Scholar during the academic year 2017-2018 at the University of Oregon. More information available at http://www.ie.boun.edu.tr/~tinaz