{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:5452509"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:5452509","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Improvements in Discrete Fair Division Topics","abstract":"Η δίκαιη κατανομή αδιαίρετων αγαθών είναι ένα κεντρικό πρόβλημα των Μαθηματικών και της Θεωρητικής Πληροφορικής όπου στόχος είναι να διανεμηθούν πόροι μεταξύ οντοτήτων με τέτοιο τρόπο ώστε να πληρούνται αυστηρά τεκμηριωμένες έννοιες δικαιοσύνης. Η παρούσα εργασία μελετά προσεγγιστικές λύσεις ως προς το Maximin Share (MMS) σε συνδυασμό με άλλα κριτήρια, ενώ εστιάζει τόσο στην αλγοριθμική υλοποίηση όσο και στους στοιχειώδεις περιορισμούς της προσεγγισιμότητας. Μελετάμε κλασικές μεθοδολογίες διανομής, συμπεριλαμβανομένου των Round-Robin και Κύκλων Απαλλαγής Φθόνου και αξιολογούμε την ικανότητά τους να προσφέρουν προσεγγιστικές εγγυήσεις για αρκετά πρωτόκολλα διακαιοσύνης (EF1, EFX, MMS, PMMS). Πέρα από τον σχεδιασμό αλγορίθμων, καθιερώνουμε άνω φράγματα προσεγγισιμότητας, δείχνωντας ότι κάτω από ορισμένα κριτήρια, δεν υπάρχει αλγόριθμος που να πετυχαίνει καλυτερα αποτελέσματα από τα άνω φράγματα που παρουσιάζουμε. Αυτά τα αποτελέσματα χαρακτηρίζουν τους περιορισμούς των εννοιών δικαιοσύνης που κληρονομούνται εξαιτίας της αδιαιρετότητας των αγαθών και όχι μόνο. Τα αποτελέσματά μας συνδράμουν στην ουσιαστικότερη κατανόηση του χάσματος μεταξύ επιτευξιμότητας λόγων προσέγγισης και των θεωρητικών ορίων. Συμπερασματικά, με την παρούσα εργασία προσφέρουμε ταυτόχρονα βελτιωμένα αποτελέσματα με χρήση γνωστών μεθόδων αλλά και νέα αποτελέσματα μη προσεγγισιμότητας στον τομέα αυτό.","abstract_html":"Η δίκαιη κατανομή αδιαίρετων αγαθών είναι ένα κεντρικό πρόβλημα των Μαθηματικών και της Θεωρητικής Πληροφορικής όπου στόχος είναι να διανεμηθούν πόροι μεταξύ οντοτήτων με τέτοιο τρόπο ώστε να πληρούνται αυστηρά τεκμηριωμένες έννοιες δικαιοσύνης. Η παρούσα εργασία μελετά προσεγγιστικές λύσεις ως προς το Maximin Share (MMS) σε συνδυασμό με άλλα κριτήρια, ενώ εστιάζει τόσο στην αλγοριθμική υλοποίηση όσο και στους στοιχειώδεις περιορισμούς της προσεγγισιμότητας. Μελετάμε κλασικές μεθοδολογίες διανομής, συμπεριλαμβανομένου των Round-Robin και Κύκλων Απαλλαγής Φθόνου και αξιολογούμε την ικανότητά τους να προσφέρουν προσεγγιστικές εγγυήσεις για αρκετά πρωτόκολλα διακαιοσύνης (EF1, EFX, MMS, PMMS). Πέρα από τον σχεδιασμό αλγορίθμων, καθιερώνουμε άνω φράγματα προσεγγισιμότητας, δείχνωντας ότι κάτω από ορισμένα κριτήρια, δεν υπάρχει αλγόριθμος που να πετυχαίνει καλυτερα αποτελέσματα από τα άνω φράγματα που παρουσιάζουμε. Αυτά τα αποτελέσματα χαρακτηρίζουν τους περιορισμούς των εννοιών δικαιοσύνης που κληρονομούνται εξαιτίας της αδιαιρετότητας των αγαθών και όχι μόνο. Τα αποτελέσματά μας συνδράμουν στην ουσιαστικότερη κατανόηση του χάσματος μεταξύ επιτευξιμότητας λόγων προσέγγισης και των θεωρητικών ορίων. Συμπερασματικά, με την παρούσα εργασία προσφέρουμε ταυτόχρονα βελτιωμένα αποτελέσματα με χρήση γνωστών μεθόδων αλλά και νέα αποτελέσματα μη προσεγγισιμότητας στον τομέα αυτό.","abstract_has_math":false,"creators":["ΜΑΤΙΑΤΟΣ ΣΠΥΡΙΔΩΝ","MATIATOS SPYRIDON"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-11-19T05:20:51Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5452509"],"render_values":[{"text":"uoadl:5452509","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/5452509","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/5452509","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%3A5452509","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["ΜΑΤΙΑΤΟΣ ΣΠΥΡΙΔΩΝ","MATIATOS SPYRIDON"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2026"]},{"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":["Θετικές Επιστήμες","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:5452509","https://pergamos.lib.uoa.gr/uoa/dl/object/5452509"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η δίκαιη κατανομή αδιαίρετων αγαθών είναι ένα κεντρικό πρόβλημα των Μαθηματικών και της Θεωρητικής Πληροφορικής όπου στόχος είναι να διανεμηθούν πόροι μεταξύ οντοτήτων με τέτοιο τρόπο ώστε να πληρούνται αυστηρά τεκμηριωμένες έννοιες δικαιοσύνης. Η παρούσα εργασία μελετά προσεγγιστικές λύσεις ως προς το Maximin Share (MMS) σε συνδυασμό με άλλα κριτήρια, ενώ εστιάζει τόσο στην αλγοριθμική υλοποίηση όσο και στους στοιχειώδεις περιορισμούς της προσεγγισιμότητας. Μελετάμε κλασικές μεθοδολογίες διανομής, συμπεριλαμβανομένου των Round-Robin και Κύκλων Απαλλαγής Φθόνου και αξιολογούμε την ικανότητά τους να προσφέρουν προσεγγιστικές εγγυήσεις για αρκετά πρωτόκολλα διακαιοσύνης (EF1, EFX, MMS, PMMS). Πέρα από τον σχεδιασμό αλγορίθμων, καθιερώνουμε άνω φράγματα προσεγγισιμότητας, δείχνωντας ότι κάτω από ορισμένα κριτήρια, δεν υπάρχει αλγόριθμος που να πετυχαίνει καλυτερα αποτελέσματα από τα άνω φράγματα που παρουσιάζουμε. Αυτά τα αποτελέσματα χαρακτηρίζουν τους περιορισμούς των εννοιών δικαιοσύνης που κληρονομούνται εξαιτίας της αδιαιρετότητας των αγαθών και όχι μόνο. Τα αποτελέσματά μας συνδράμουν στην ουσιαστικότερη κατανόηση του χάσματος μεταξύ επιτευξιμότητας λόγων προσέγγισης και των θεωρητικών ορίων. Συμπερασματικά, με την παρούσα εργασία προσφέρουμε ταυτόχρονα βελτιωμένα αποτελέσματα με χρήση γνωστών μεθόδων αλλά και νέα αποτελέσματα μη προσεγγισιμότητας στον τομέα αυτό.","Fair division of indivisible goods is a central problem in mathematics and computer science, where the goal is to allocate resources among agents in a way that satisfies formal notions of fairness. This work studies approximation guaranties for Maximin Share (MMS) fairness and related criteria, with a focus on both algorithmic performance and fundamental limits of approximability. We analyze classical allocation procedures, including Round-Robin and Envy Cycle Elimination, and evaluate their ability to achieve approximate MMS guarantees. Beyond algorithm design, we establish upper bounds on approximability, showing that under certain natural criteria no algorithm can achieve better guarantees than the bounds we identify. These results characterize inherent limitations of fairness notions in the indivisible goods setting. Our findings sharpen the understanding of the gap between achievable approximation ratios and theoretical limits. Overall, this work contributes both improved results using known procedures and new impossibility results for fairness approximations in combinatorial allocation."]},{"key":"dc:title","label":"Title","values":["Improvements in Discrete Fair Division Topics"]}]}],"canonical_facts":{"dc:creator":["ΜΑΤΙΑΤΟΣ ΣΠΥΡΙΔΩΝ","MATIATOS SPYRIDON"],"dc:date":["2026"],"dc:description":["Η δίκαιη κατανομή αδιαίρετων αγαθών είναι ένα κεντρικό πρόβλημα των Μαθηματικών και της Θεωρητικής Πληροφορικής όπου στόχος είναι να διανεμηθούν πόροι μεταξύ οντοτήτων με τέτοιο τρόπο ώστε να πληρούνται αυστηρά τεκμηριωμένες έννοιες δικαιοσύνης. Η παρούσα εργασία μελετά προσεγγιστικές λύσεις ως προς το Maximin Share (MMS) σε συνδυασμό με άλλα κριτήρια, ενώ εστιάζει τόσο στην αλγοριθμική υλοποίηση όσο και στους στοιχειώδεις περιορισμούς της προσεγγισιμότητας. Μελετάμε κλασικές μεθοδολογίες διανομής, συμπεριλαμβανομένου των Round-Robin και Κύκλων Απαλλαγής Φθόνου και αξιολογούμε την ικανότητά τους να προσφέρουν προσεγγιστικές εγγυήσεις για αρκετά πρωτόκολλα διακαιοσύνης (EF1, EFX, MMS, PMMS). Πέρα από τον σχεδιασμό αλγορίθμων, καθιερώνουμε άνω φράγματα προσεγγισιμότητας, δείχνωντας ότι κάτω από ορισμένα κριτήρια, δεν υπάρχει αλγόριθμος που να πετυχαίνει καλυτερα αποτελέσματα από τα άνω φράγματα που παρουσιάζουμε. Αυτά τα αποτελέσματα χαρακτηρίζουν τους περιορισμούς των εννοιών δικαιοσύνης που κληρονομούνται εξαιτίας της αδιαιρετότητας των αγαθών και όχι μόνο. Τα αποτελέσματά μας συνδράμουν στην ουσιαστικότερη κατανόηση του χάσματος μεταξύ επιτευξιμότητας λόγων προσέγγισης και των θεωρητικών ορίων. Συμπερασματικά, με την παρούσα εργασία προσφέρουμε ταυτόχρονα βελτιωμένα αποτελέσματα με χρήση γνωστών μεθόδων αλλά και νέα αποτελέσματα μη προσεγγισιμότητας στον τομέα αυτό.","Fair division of indivisible goods is a central problem in mathematics and computer science, where the goal is to allocate resources among agents in a way that satisfies formal notions of fairness. This work studies approximation guaranties for Maximin Share (MMS) fairness and related criteria, with a focus on both algorithmic performance and fundamental limits of approximability. We analyze classical allocation procedures, including Round-Robin and Envy Cycle Elimination, and evaluate their ability to achieve approximate MMS guarantees. Beyond algorithm design, we establish upper bounds on approximability, showing that under certain natural criteria no algorithm can achieve better guarantees than the bounds we identify. These results characterize inherent limitations of fairness notions in the indivisible goods setting. Our findings sharpen the understanding of the gap between achievable approximation ratios and theoretical limits. Overall, this work contributes both improved results using known procedures and new impossibility results for fairness approximations in combinatorial allocation."],"dc:identifier":["uoadl:5452509","https://pergamos.lib.uoa.gr/uoa/dl/object/5452509"],"dc:language":["English"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Improvements in Discrete Fair Division Topics"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:20:51Z"}