National and Kapodistrian University of Athens
Improvements in Discrete Fair Division Topics
Abstract
dc:descriptionΗ δίκαιη κατανομή αδιαίρετων αγαθών είναι ένα κεντρικό πρόβλημα των Μαθηματικών και της Θεωρητικής Πληροφορικής όπου στόχος είναι να διανεμηθούν πόροι μεταξύ οντοτήτων με τέτοιο τρόπο ώστε να πληρούνται αυστηρά τεκμηριωμένες έννοιες δικαιοσύνης. Η παρούσα εργασία μελετά προσεγγιστικές λύσεις ως προς το Maximin Share (MMS) σε συνδυασμό με άλλα κριτήρια, ενώ εστιάζει τόσο στην αλγοριθμική υλοποίηση όσο και στους στοιχειώδεις περιορισμούς της προσεγγισιμότητας. Μελετάμε κλασικές μεθοδολογίες διανομής, συμπεριλαμβανομένου των Round-Robin και Κύκλων Απαλλαγής Φθόνου και αξιολογούμε την ικανότητά τους να προσφέρουν προσεγγιστικές εγγυήσεις για αρκετά πρωτόκολλα διακαιοσύνης (EF1, EFX, MMS, PMMS). Πέρα από τον σχεδιασμό αλγορίθμων, καθιερώνουμε άνω φράγματα προσεγγισιμότητας, δείχνωντας ότι κάτω από ορισμένα κριτήρια, δεν υπάρχει αλγόριθμος που να πετυχαίνει καλυτερα αποτελέσματα από τα άνω φράγματα που παρουσιάζουμε. Αυτά τα αποτελέσματα χαρακτηρίζουν τους περιορισμούς των εννοιών δικαιοσύνης που κληρονομούνται εξαιτίας της αδιαιρετότητας των αγαθών και όχι μόνο. Τα αποτελέσματά μας συνδράμουν στην ουσιαστικότερη κατανόηση του χάσματος μεταξύ επιτευξιμότητας λόγων προσέγγισης και των θεωρητικών ορίων. Συμπερασματικά, με την παρούσα εργασία προσφέρουμε ταυτόχρονα βελτιωμένα αποτελέσματα με χρήση γνωστών μεθόδων αλλά και νέα αποτελέσματα μη προσεγγισιμότητας στον τομέα αυτό.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- ΜΑΤΙΑΤΟΣ ΣΠΥΡΙΔΩΝ
- MATIATOS SPYRIDON
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:5452509