Ο φοιτητής του προγράμματος Μηνάς Μάριος Σωτηρίου θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Almost Envy-Free allocations in multigraphs
την Τρίτη 4 Φεβρουαρίου 2025 και ώρα 14:00, μέσω τηλεμετάδοσης (https://teams.live.com/meet/9383929610808?p=Oh7Hc21OtouxOb5H6F).
Σύνοψη Διπλωματικής:
This thesis studies the problem of "fairly" dividing goods in several agents. The study of the problem started in the late 40's for divisible goods with the "cake cutting" prob- lem. There are multiple notions of fairness when referring to the field of Fair Division. One notion is envy-free allocations, where nobody envies what is allocated to any other agent. Envy-freeness has been extensively studied in settings with divisible resources. This thesis focuses on settings with indivisible resources, where envy-freeness cannot be guaranteed. Instead, our focus revolves around a fairness criterion approximating envy-free allocations: that is envy-free up to any good (EFX) allocations, i.e., no agent envies any proper subset of the goods given to any other agent. The existence or not of EFX allocations is a major open problem in Fair Division, and there are only positive results for special cases. Christodoulou et al. 2023 introduced a setting with a restriction on the agents' valuations according to a graph structure: the vertices correspond to agents and the edges to goods, and each vertex/agent has zero marginal value (or in other words, they are indifferent) for the edges/goods that are not adjacent to them. The existence of EFX allocations has been shown for simple graphs when agents have general monotone valuations by Christodoulou et al. 2023 , and for multigraphs for restricted additive valuations by Kaviani et al. 2024. In this thesis, we push the state-of-the-art further, and show that the EFX allocations always exists in multigraphs and for general monotone valuations if any of the follow- ing three conditions hold: either (a) the multigraph is bipartite, or (b) each agent has at most n/4 − 1 neighbors, where n is the total number of agents, or (c) the shortest cycle with non-parallel edges has length at least 6.
Η Επιτροπή:
Ευάγγελος Μάρκακης (Συνεπιβλέπων),
Τμήμα Πληροφορικής, Ο.Π.Α.
Άρης Παγουρτζής,
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Ε.Μ.Π.
Αλκμήνη Σγουρίτσα (Συνεπιβλέπουσα),
Τμήμα Πληροφορικής, Ο.Π.Α.
Γιώργος Χριστοδούλου,
Τμήμα Πληροφορικής, Α.Π.Θ.