{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:3463197"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:3463197","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Almost Envy-Free allocations in multigraphs.","abstract":"Η διπλωματική μελετά το πρόβλημα της «δίκαιης» κατανομής αγαθών σε πράκτορες. Η μελέτη του προβλήματος ξεκίνησε στα τέλη της δεκαετίας του 1940 για αγαθά που μπορούν να διαχωριστούν με το πρόβλημα «cake cutting». Υπάρχουν πολλές έννοιες δίκαιου διαμοιρασμού αγαθών όταν αναφερόμαστε στον τομέα της Δίκαιης Κατανομής (Fair Division). Μία έννοια είναι οι κατανομές χωρίς φθόνο (envy-free allocations), όπου κανείς δεν ζηλεύει ό,τι έχει κατανεμηθεί σε οποιονδήποτε άλλο πράκτορα. Η απουσία φθόνου έχει μελετηθεί εκτενώς σε περιβάλλοντα με πόρους που μπορούν να διαχωριστούν. Η διπλωματική επικεντρώνεται σε διαμοιρασμούς αγαθών που δεν μπορούν να διαχωριστούν, όπου η απουσία φθόνου δεν μπορεί να εγγυηθεί. Αντίθετα, εστιάζουμε γύρω από ένα κριτήριο δικαιοσύνης που προσεγγίζει τις κατανομές χωρίς φθόνο: τους διαμοιρασμούς envy-free up to any good (EFX), δηλαδή, κανένας πράκτορας δεν ζηλεύει κανένα γνήσιο υποσύνολο των αγαθών που δίνονται σε οποιονδήποτε άλλο πράκτορα. Η ύπαρξη ή μη των διαμοιρασμών EFX αποτελεί ένα σημαντικό ανοικτό πρόβλημα στη Δίκαιη Κατανομή, και υπάρχουν μόνο θετικά αποτελέσματα για ειδικές συνθήκες. Οι Christodoulou et al. 2023 εισήγαγαν μία συνθήκη με περιορισμό στις αποτιμήσεις των πρακτόρων σύμφωνα με μια δομή γραφήματος: οι κορυφές αντιστοιχούν σε πράκτορες και οι ακμές σε αγαθά, και κάθε κορυφή/πράκτορας έχει μηδενική αξία (ή αλλιώς είναι αδιάφορος) για τις ακμές/αγαθά που δεν είναι γειτονικές με αυτήν. Η ύπαρξη των κατανομών EFX έχει αποδειχθεί για γραφήματα όταν οι πράκτορες έχουν γενικές μονότονες αποτιμήσεις από τους Christodoulou et al. 2023 και για πολυγραφήματα για περιορισμένες προσθετικές αποτιμήσεις από τους Kaviani et al. 2024. Στην παρούσα διατριβή, δείχνουμε ότι οι κατανομές EFX υπάρχουν πάντα σε πολυγραφήματα και για γενικές μονότονες αποτιμήσεις αν ισχύει τουλάχιστον μία από τις παρακάτω τρεις συνθήκες: είτε (α) το πολυγράφημα είναι διμερές, είτε (β) κάθε πράκτορας έχει το πολύ ⌈ n 4 ⌉ − 1 γείτονες, όπου n είναι ο συνολικός αριθμός των πρακτόρων, είτε (γ) ο συντομότερος κύκλος με μη παράλληλες ακμές έχει μήκος τουλάχιστον 6.","abstract_html":"Η διπλωματική μελετά το πρόβλημα της «δίκαιης» κατανομής αγαθών σε πράκτορες. Η μελέτη του προβλήματος ξεκίνησε στα τέλη της δεκαετίας του 1940 για αγαθά που μπορούν να διαχωριστούν με το πρόβλημα «cake cutting». Υπάρχουν πολλές έννοιες δίκαιου διαμοιρασμού αγαθών όταν αναφερόμαστε στον τομέα της Δίκαιης Κατανομής (Fair Division). Μία έννοια είναι οι κατανομές χωρίς φθόνο (envy-free allocations), όπου κανείς δεν ζηλεύει ό,τι έχει κατανεμηθεί σε οποιονδήποτε άλλο πράκτορα. Η απουσία φθόνου έχει μελετηθεί εκτενώς σε περιβάλλοντα με πόρους που μπορούν να διαχωριστούν. Η διπλωματική επικεντρώνεται σε διαμοιρασμούς αγαθών που δεν μπορούν να διαχωριστούν, όπου η απουσία φθόνου δεν μπορεί να εγγυηθεί. Αντίθετα, εστιάζουμε γύρω από ένα κριτήριο δικαιοσύνης που προσεγγίζει τις κατανομές χωρίς φθόνο: τους διαμοιρασμούς envy-free up to any good (EFX), δηλαδή, κανένας πράκτορας δεν ζηλεύει κανένα γνήσιο υποσύνολο των αγαθών που δίνονται σε οποιονδήποτε άλλο πράκτορα. Η ύπαρξη ή μη των διαμοιρασμών EFX αποτελεί ένα σημαντικό ανοικτό πρόβλημα στη Δίκαιη Κατανομή, και υπάρχουν μόνο θετικά αποτελέσματα για ειδικές συνθήκες. Οι Christodoulou et al. 2023 εισήγαγαν μία συνθήκη με περιορισμό στις αποτιμήσεις των πρακτόρων σύμφωνα με μια δομή γραφήματος: οι κορυφές αντιστοιχούν σε πράκτορες και οι ακμές σε αγαθά, και κάθε κορυφή/πράκτορας έχει μηδενική αξία (ή αλλιώς είναι αδιάφορος) για τις ακμές/αγαθά που δεν είναι γειτονικές με αυτήν. Η ύπαρξη των κατανομών EFX έχει αποδειχθεί για γραφήματα όταν οι πράκτορες έχουν γενικές μονότονες αποτιμήσεις από τους Christodoulou et al. 2023 και για πολυγραφήματα για περιορισμένες προσθετικές αποτιμήσεις από τους Kaviani et al. 2024. Στην παρούσα διατριβή, δείχνουμε ότι οι κατανομές EFX υπάρχουν πάντα σε πολυγραφήματα και για γενικές μονότονες αποτιμήσεις αν ισχύει τουλάχιστον μία από τις παρακάτω τρεις συνθήκες: είτε (α) το πολυγράφημα είναι διμερές, είτε (β) κάθε πράκτορας έχει το πολύ ⌈ n 4 ⌉ − 1 γείτονες, όπου n είναι ο συνολικός αριθμός των πρακτόρων, είτε (γ) ο συντομότερος κύκλος με μη παράλληλες ακμές έχει μήκος τουλάχιστον 6.","abstract_has_math":false,"creators":["Σωτηρίου Μηνάς-Μάριος","Sotiriou Minas-Marios"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025","date_published":"2025","updated_at":"2026-11-19T06:31:54Z","subjects":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:3463197"],"render_values":[{"text":"uoadl:3463197","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3463197","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3463197","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A3463197","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Σωτηρίου Μηνάς-Μάριος","Sotiriou Minas-Marios"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Τεχνολογία – Πληροφορική","Technology - Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:3463197","https://pergamos.lib.uoa.gr/uoa/dl/object/3463197"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η διπλωματική μελετά το πρόβλημα της «δίκαιης» κατανομής αγαθών σε πράκτορες. Η μελέτη του προβλήματος ξεκίνησε στα τέλη της δεκαετίας του 1940 για αγαθά που μπορούν να διαχωριστούν με το πρόβλημα «cake cutting». Υπάρχουν πολλές έννοιες δίκαιου διαμοιρασμού αγαθών όταν αναφερόμαστε στον τομέα της Δίκαιης Κατανομής (Fair Division). Μία έννοια είναι οι κατανομές χωρίς φθόνο (envy-free allocations), όπου κανείς δεν ζηλεύει ό,τι έχει κατανεμηθεί σε οποιονδήποτε άλλο πράκτορα. Η απουσία φθόνου έχει μελετηθεί εκτενώς σε περιβάλλοντα με πόρους που μπορούν να διαχωριστούν. Η διπλωματική επικεντρώνεται σε διαμοιρασμούς αγαθών που δεν μπορούν να διαχωριστούν, όπου η απουσία φθόνου δεν μπορεί να εγγυηθεί. Αντίθετα, εστιάζουμε γύρω από ένα κριτήριο δικαιοσύνης που προσεγγίζει τις κατανομές χωρίς φθόνο: τους διαμοιρασμούς envy-free up to any good (EFX), δηλαδή, κανένας πράκτορας δεν ζηλεύει κανένα γνήσιο υποσύνολο των αγαθών που δίνονται σε οποιονδήποτε άλλο πράκτορα. Η ύπαρξη ή μη των διαμοιρασμών EFX αποτελεί ένα σημαντικό ανοικτό πρόβλημα στη Δίκαιη Κατανομή, και υπάρχουν μόνο θετικά αποτελέσματα για ειδικές συνθήκες. Οι Christodoulou et al. 2023 εισήγαγαν μία συνθήκη με περιορισμό στις αποτιμήσεις των πρακτόρων σύμφωνα με μια δομή γραφήματος: οι κορυφές αντιστοιχούν σε πράκτορες και οι ακμές σε αγαθά, και κάθε κορυφή/πράκτορας έχει μηδενική αξία (ή αλλιώς είναι αδιάφορος) για τις ακμές/αγαθά που δεν είναι γειτονικές με αυτήν. Η ύπαρξη των κατανομών EFX έχει αποδειχθεί για γραφήματα όταν οι πράκτορες έχουν γενικές μονότονες αποτιμήσεις από τους Christodoulou et al. 2023 και για πολυγραφήματα για περιορισμένες προσθετικές αποτιμήσεις από τους Kaviani et al. 2024. Στην παρούσα διατριβή, δείχνουμε ότι οι κατανομές EFX υπάρχουν πάντα σε πολυγραφήματα και για γενικές μονότονες αποτιμήσεις αν ισχύει τουλάχιστον μία από τις παρακάτω τρεις συνθήκες: είτε (α) το πολυγράφημα είναι διμερές, είτε (β) κάθε πράκτορας έχει το πολύ ⌈ n 4 ⌉ − 1 γείτονες, όπου n είναι ο συνολικός αριθμός των πρακτόρων, είτε (γ) ο συντομότερος κύκλος με μη παράλληλες ακμές έχει μήκος τουλάχιστον 6.","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 Ka- viani 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."]},{"key":"dc:title","label":"Title","values":["Almost Envy-Free allocations in multigraphs."]}]}],"canonical_facts":{"dc:creator":["Σωτηρίου Μηνάς-Μάριος","Sotiriou Minas-Marios"],"dc:date":["2025"],"dc:description":["Η διπλωματική μελετά το πρόβλημα της «δίκαιης» κατανομής αγαθών σε πράκτορες. Η μελέτη του προβλήματος ξεκίνησε στα τέλη της δεκαετίας του 1940 για αγαθά που μπορούν να διαχωριστούν με το πρόβλημα «cake cutting». Υπάρχουν πολλές έννοιες δίκαιου διαμοιρασμού αγαθών όταν αναφερόμαστε στον τομέα της Δίκαιης Κατανομής (Fair Division). Μία έννοια είναι οι κατανομές χωρίς φθόνο (envy-free allocations), όπου κανείς δεν ζηλεύει ό,τι έχει κατανεμηθεί σε οποιονδήποτε άλλο πράκτορα. Η απουσία φθόνου έχει μελετηθεί εκτενώς σε περιβάλλοντα με πόρους που μπορούν να διαχωριστούν. Η διπλωματική επικεντρώνεται σε διαμοιρασμούς αγαθών που δεν μπορούν να διαχωριστούν, όπου η απουσία φθόνου δεν μπορεί να εγγυηθεί. Αντίθετα, εστιάζουμε γύρω από ένα κριτήριο δικαιοσύνης που προσεγγίζει τις κατανομές χωρίς φθόνο: τους διαμοιρασμούς envy-free up to any good (EFX), δηλαδή, κανένας πράκτορας δεν ζηλεύει κανένα γνήσιο υποσύνολο των αγαθών που δίνονται σε οποιονδήποτε άλλο πράκτορα. Η ύπαρξη ή μη των διαμοιρασμών EFX αποτελεί ένα σημαντικό ανοικτό πρόβλημα στη Δίκαιη Κατανομή, και υπάρχουν μόνο θετικά αποτελέσματα για ειδικές συνθήκες. Οι Christodoulou et al. 2023 εισήγαγαν μία συνθήκη με περιορισμό στις αποτιμήσεις των πρακτόρων σύμφωνα με μια δομή γραφήματος: οι κορυφές αντιστοιχούν σε πράκτορες και οι ακμές σε αγαθά, και κάθε κορυφή/πράκτορας έχει μηδενική αξία (ή αλλιώς είναι αδιάφορος) για τις ακμές/αγαθά που δεν είναι γειτονικές με αυτήν. Η ύπαρξη των κατανομών EFX έχει αποδειχθεί για γραφήματα όταν οι πράκτορες έχουν γενικές μονότονες αποτιμήσεις από τους Christodoulou et al. 2023 και για πολυγραφήματα για περιορισμένες προσθετικές αποτιμήσεις από τους Kaviani et al. 2024. Στην παρούσα διατριβή, δείχνουμε ότι οι κατανομές EFX υπάρχουν πάντα σε πολυγραφήματα και για γενικές μονότονες αποτιμήσεις αν ισχύει τουλάχιστον μία από τις παρακάτω τρεις συνθήκες: είτε (α) το πολυγράφημα είναι διμερές, είτε (β) κάθε πράκτορας έχει το πολύ ⌈ n 4 ⌉ − 1 γείτονες, όπου n είναι ο συνολικός αριθμός των πρακτόρων, είτε (γ) ο συντομότερος κύκλος με μη παράλληλες ακμές έχει μήκος τουλάχιστον 6.","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 Ka- viani 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."],"dc:identifier":["uoadl:3463197","https://pergamos.lib.uoa.gr/uoa/dl/object/3463197"],"dc:language":["English"],"dc:subject":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"dc:title":["Almost Envy-Free allocations in multigraphs."],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T06:31:54Z"}