Back to search

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 × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:5452509

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

ΜΑΤΙΑΤΟΣ ΣΠΥΡΙΔΩΝ; MATIATOS SPYRIDON. Improvements in Discrete Fair Division Topics. 2026. https://pergamos.lib.uoa.gr/uoa/dl/object/5452509