2014
2015
2016
2017
2018
2019
2020
2022
2023
2024

The twenty-fourth meeting of the Prague computer science seminar

Milan Vlach

Envy-free divisions

Undoubtedly, one of the oldest questions faced through the history of human society is the problem of dividing a divisible object among a finite number of individuals in such a way that every individual beliefs that he or she received a fair piece.

November 24, 2016

4:00pm

Auditorium E-301, FEL CTU
Karlovo nám. 13, Praha 2
Show on the map

Lecture annotation

Undoubtedly, one of the oldest questions faced through the history of human society is the problem of dividing a divisible object among a finite number of individuals in such a way that every individual beliefs that he or she received a fair piece. After formalization of the basic notions of object divisibility and of division fairness, we mainly follow the history of mathematical and computational models dealing with proportional and envy-free divisions. We begin with recalling the results of Steinhaus, Knaster, and Banach on proportional solutions, the results of Dubins and Spanier on the existence of such solutions, and extensions of the existence results obtained by Sagara and Vlach for envy-freeness in situations that permit infinite number of individuals and nonadditive preferences. Then we present recent results of Woeginger and Sgall, Edmonds and Pruhs, and Procaccia, which show that, for a fairly general model of computation, achieving envy-freeness is provably harder than achieving proportionality, and that we now understand the case of proportionality much better than that of envy-freeness.

In particular, we know that there exist fast finite discrete proportional procedures whose number of steps can be bounded by a function that depends on the number of individuals and not on the individual preferences. On the other hand, until very recently, it was generally believed that no such a procedure exists for envy-freeness. We conclude with a brief discussion of the recent claim of Aziz and Mackenzie that such a procedure exists. The gap between known lower bounds and the upper bound of the Aziz and Mackenzie procedure is extremely wide, and we can therefore expect a lot of improvements possibly leading to a practical method, provided the result is correct.

Lecturer

Milan Vlach

Milan Vlach graduated from the Lomonosov State University in 1963. Since then he has worked at the Faculty of Mathematics and Physics at Charles University in Prague. He also taught and conducted research at a number of universities and research institutes in Europe, Japan, and the United States. In 1970’s he contributed to introducing the subjects of informatics and computer science in secondary and tertiary education by writing textbooks and establishing a department conducting teaching and research in computer science. His early research is concerned with special problems of linear optimization and production scheduling. His papers on multi-index transportations are still being referred to. Later his interests moved to optimization under uncertainty. With a support of Japanese Ministry of Education, he cofounded the Czech-Japan Seminar on Decision Making under Uncertainty and together with Prof. Ramík publishes a monograph Generalized Concavity in Fuzzy Optimization and Decision Analysis. In recent years his research is focused mainly to the theory of games and its application to problems of fair allocation of limited resources. His joint paper with Nobusumi Sagara in the International Journal of Game Theory belongs to a few papers on fair division with nonadditive preferences.

ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR

The seminar typically takes place on Thursdays at 4:15pm in lecture rooms of the Czech Technical University in Prague or the Charles University.

Its program consists of a one-hour lecture followed by a discussion. The lecture is based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures are in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Jaroslav Hlinka (Czech Academy of Sciences, Computer Science Institute), Michal Chytil, Pavel Kordík (CTU in Prague, Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), Jan Kybic (CTU in Prague, Faculty of Electrical Engineering), Michal Pěchouček (CTU in Prague, Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences, Institute of Information Theory and Automation), Tomáš Werner (CTU in Prague, Faculty of Electrical Engineering), and Filip Železný (CTU in Prague, Faculty of Electrical Engineering)

The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.

Supporters

Contact

Prague computer science seminar is suspended until further notice to prevent spread of the new coronavirus.