CS Forum: Kurt Mehlhorn "Fair Allocation of Indivisible Goods"

CS forum on tietotekniikan laitoksen järjestämä seminaarisarja - kaikille avoin ja ilmainen.
CS Forum

CS forum is a seminar series arranged at the Department of Computer Science. The talk begins at 16:00 and after the talk there will be a 30-minute social event with coffee and cake. 

For catering purposes please register by 5 June


Fair Allocation of Indivisible Goods

Kurt Mehlhorn
Max Planck Institute for Informatics, Director Emeritus


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 (AAAI 22, EC 21, EC 20, JACM 22, Sicomp 21) 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.

Kurt Mehlhorn


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,Khwarizmi International Award) 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.


Professor Parinya Chalermsook, Department of Computer Science

Tietotekniikan laitos

Tietotekniikka yhdistää kaikkia aloja. Tietotekniikan laitoksella perustutkimus yhdistyy innovatiivisiin sovelluksiin.

Read more
PML research group Department of Computer Science
  • Julkaistu:
  • Päivitetty:
URL kopioitu