Dr. F.C. Kohli Centre of Excellence

Perspectives in Mathematical Sciences

January 10–February 4, 2022

Thursday, 20 January 2022, 19:00 IST

Kurt Mehlhorn, Max Planck Institut für Informatik, Saarbrücken

Title Fair Allocation of Indivisible Goods (Video Recording)

Abstract

We want to allocate a set of goods to a set of agents; think of splitting a heritage. Each agent has a valuation function over sets of goods. In the simplest case, the agents assign values to the goods and the value of a set of goods is the sum of the values of the goods in the set. We want the allocation to be fair. We introduce important notions of fairness, in particular, envy-freeness (up to any good) and Nash social welfare and discuss the existence of fair allocations and the complexity of finding or approximating one.

The talk is based on joint work with Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg, Martin Hoefer, Telikepalli Kavitha, Ruta Mehta, Pranabendu Misra, Marco Schmalhofer, Alkmini Sgouritsa, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande and Ernest van Wijland.

About the speaker

Kurt Mehlhorn is Director Emeritus of the MPI for Informatics and Senior Professor of Computer Science at Saarland University. He headed the algorithms and complexity group at the MPI for Informatics. He co-authored some 300 publications in the field, published six books, and is one of the people behind the LEDA software library. Recently, he produced a series of video lectures "Ideas and Concepts of Computer Science" (in German) for a general audience. He supervised more than 80 students, many of whom have now faculty positions. He has received several prizes (Leibniz Award, EATCS Award, Zuse Medal, ACM Paris Kanellakis Theory and Practice Award, Erasmus Medal of the Academia Europaea) for his work. He holds Honorary Doctorate Degrees from Magdeburg, Waterloo, Aarhus, Gothenburg and Patras universities and is an ACM Fellow. He is a member of the German Academy of Sciences Leopoldina, Academia Europaea, the German Academy of Science and Engineering acatech, the US Academy of Engineering, the Indian Academy of Engineering, and the US Academy of Science. From 2002 to 2008, he was vice president of the Max Planck Society. He is a co-founder of Algorithmic Solutions Software GmbH. He currently serves on the ERC Scientific Council, the Research Advisory Board of Tata Consultancy, and the advisory board of Carnegie Mellon, Qatar.