Αυτή την Παρασκευή θα μας μιλήσει η Ευτυχία Βακαλιού, πρόσφατη απόφοιτη του τμήματός μας, για τα αποτελέσματα της πτυχιακής της εργασίας.
Η εκλαικευμένη εκδοχή του προβλήματος που μελέτησε είναι πώς να μοιράσετε μια τούρτα με δίκαιο τρόπο. Επομένως αν θέλει κανείς να φέρει γλυκά, τούρτες, κτλ, θα προσπαθήσουμε να εφαρμόσουμε τον αλγόριθμο πάνω τους!
Στην αίθουσα Α36, στις 17:00.
Ακολουθεί τίτλος και abstract
Speaker: Eftychia Vakaliou
Title: An Improved Envy-Free Cake Cutting Protocol for Four Agents
We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents, so that every agent finds her piece at least as valuable as every other agent's piece. The problem has an interesting history. Although the case of three agents is solvable with less than 15 queries, for four agents no bounded procedure was known until the recent breakthroughs of
Aziz and Mackenzie (2016). The main drawback of these new algorithms, however, is that they are quite complicated and with a very high query complexity. With four agents, the number of queries required is close to 600. In this work we provide an improved, simpler algorithm for four agents, which reduces the current complexity by a factor of 3.4. Our algorithm builds on the approach of
Aziz and Mackenzie by incorporating new insights and simplifying several steps.
The algorithm starts with an envy-free partial allocation and a leftover residue. It repeatedly reduces the residue and updates the allocation until certain structural properties are satisfied. These properties allow us to quickly produce a complete allocation without introducing any envy.
Overall, this results in an algorithm with lower complexity, which we believe is more intuitive and easier to grasp.
This is joint work with G. Amanatidis, G. Christodoulou, J. Fearnley, E. Markakis, A. Psomas