Πλοήγηση ανά Επιβλέποντα "Markakis, Vangelis"

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω

Τώρα δείχνει 1 - 1 από 1

Solution concepts and algorithms for fair division under constraints
(2025-10-01) Mancho, Alviona; Amanatidis, Georgios; Sgouritsa, Alkmini; Markakis, Vangelis
Το πρόβλημα της δίκαιης ανάθεσης πόρων—πώς να διαμοιραστούν οι πόροι μεταξύ ατόμων με διαφορετικές προτιμήσεις με δίκαιο τρόπο—έχει απασχολήσει τους μαθηματικούς και τους οικονομολόγους από την αρχαιότητα, με το πρόβλημα κατανομής της γης, έως τα προβλήματα που ανακύπτουν σε σύγχρονα περιβάλλοντα, όπως η ανάθεση πόρων στο cloud ή ο διαμοιρασμός της κληρονομιάς. Ενώ, όμως, τα διαιρετά αγαθά μπορούν να κατανεμηθούν χρησιμοποιώντας γνωστά πρωτόκολλα, τα αδιαίρετα αγαθά παρουσιάζουν προκλήσεις. Ένα καθιερωμένο κριτήριο δικαιοσύνης είναι η απουσία φθόνου (EF), η οποία απαιτεί κανένας συμμετέχοντας (στο εξής πράκτορας) να μην προτιμά το μερίδιο (στο εξής πακέτο) ενός άλλου από το δικό του. Ωστόσο, όσον αφορά τα αδιαίρετα αγαθά, η απουσία φθόνου είναι συχνά ανέφικτη, γεγονός που οδηγεί στη μελέτη χαλαρώσεων, όπως η απουσία φθόνου έως ένα αγαθό (envy-freeness up to one good, EF1) και η απουσία φθόνου έως οποιοδήποτε αγαθό (envy-freeness up to any good, EFX). Η παρούσα διπλωματική εργασία επικεντρώνεται στην περίπτωση όπου ισχύουν πρόσθετοι περιορισμοί σχετικά με τις εφικτές αναθέσεις. Ένα πραγματικό σενάριο είναι όταν οι πράκτορες πρέπει να λάβουν τον ίδιο αριθμό αγαθών. Για να αντιμετωπιστούν τέτοιες καταστάσεις, πρόσφατες εργασίες έχουν εισαγάγει έννοιες δικαιοσύνης βασισμένες στην ανταλλαγή, όπως οι EFF1 και EFFX, όπου ο φθόνος μπορεί να εξαλειφθεί με την ανταλλαγή ενός (ή, αντίστοιχα, οποιουδήποτε) αγαθού μεταξύ των πακέτων. Αυτοί οι ορισμοί ευθυγραμμίζονται φυσικά με τον περιορισμό που περιγράψαμε, αλλά οι ιδιότητές τους παραμένουν σε μεγάλο βαθμό ανεξερεύνητες. Η συμβολή της διπλωματικής εργασίας εκτείνεται σε δύο άξονες. Πρώτον, παρέχει μια ολοκληρωμένη επισκόπηση της βιβλιογραφίας σχετικά με τη δίκαιη κατανομή αδιαίρετων αγαθών, με έμφαση σε μοντέλα με περιορισμούς (πληθικότητας, συνδεσιμότητας, προϋπολογισμού και μητροειδών). Δεύτερον, παρουσιάζει νέα αποτελέσματα σχετικά με τα κριτήρια δικαιοσύνης βάσει ανταλλαγής, διερευνώντας την ύπαρξή τους και την επίδοση γνωστών αλγορίθμων όπως ο Envy Cycle Elimination. Επιπλέον, μελετάμε σε ποιο βαθμό μπορούν να συνυπάρξουν η δικαιοσύνη και η αποδοτικότητα.