Θεωρητική και πειραματική μελέτη αλγορίθμων για δίκαιη κατανομή

Thumbnail Image
Date
Authors
Παπαδημητρίου, Άγγελος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Το πρόβλημα της Δίκαιης Κατανομής αποτελεί ενεργό ερευνητικό πρόβλημα εδώ και πολλά χρόνια. Το πρόβλημα αυτό είναι ουσιαστικά πρόβλημα κατανομής ενός συνόλου πόρων, το οποίο διεκδικούν άνθρωποι (παίκτες) έτσι ώστε καθένας από αυτούς να λαμβάνει το κατάλληλο μερίδιο που του αντιστοιχεί. Είναι ένα πρόβλημα κατανομής ενός ή περισσότερων αγαθών μεταξύ δύο ή περισσότερων παικτών, με τρόπο που να ικανοποιεί ένα κατάλληλο κριτήριο «δικαιοσύνης». Παραδοσιακά, είναι ένα πρόβλημα που έχει απασχολήσει την Οικονομική Επιστήμη και σε κάποιο βαθμό τα Μαθηματικά, τη Φιλοσοφία και την Πολιτική Επιστήμη, αλλά πλέον αποτελεί ένα ερευνητικό αντικείμενο που απασχολεί και την Επιστήμη των Υπολογιστών (ιδιαίτερα σε συστήματα AI) και σχετίζεται στενά με πολλές εφαρμογές. Επιπλέον, η Δίκαιη Κατανομή αποτελεί ένα πρόβλημα του πραγματικού κόσμου σε διάφορες πραγματικές συνθήκες όπως είναι επιχειρήσεις, μοίρασμα περιουσίας, κέρδη τυχερών παιγνίων, μοίρασμα φυσικών πόρων κ.ά. Μία μέθοδος Δίκαιης Κατανομής είναι μια διαδικασία που μπορεί να ακολουθηθεί και να οδηγήσει σε μοίρασμα αντικειμένων με τέτοιο τρόπο ώστε κάθε διεκδικητής (παίκτης) να αισθάνεται ότι έχει λάβει το δίκαιο μερίδιο που του αντιστοιχεί. Θα πρέπει όμως να υπάρχουν μερικές παραδοχές έτσι ώστε να λειτουργήσουν αυτές οι μέθοδοι. Οι παίκτες δεν θα πρέπει να συνεργάζονται μεταξύ τους και κατά συνέπεια δεν θα πρέπει να γνωρίζουν τις προτιμήσεις των άλλων παικτών. Επιπλέον, θα πρέπει οι παίκτες να λειτουργούν με ορθολογική σκέψη, δηλαδή θα πρέπει να ενεργούν συνεχώς με την λογική τους και δεν θα πρέπει να επηρεάζονται από συναισθηματικούς παράγοντες. Οι μέθοδοι θα πρέπει να επιτρέπουν στα άτομα που συμμετέχουν μια δίκαιη κατανομή, χωρίς να απαιτείται εξωτερική παρέμβαση από άλλο τρίτο μέρος. Επομένως, μια μέθοδος Δίκαιης Κατανομής θα πρέπει να εγγυάται ότι κάθε παίκτης θα λάβει ένα μερίδιο το οποίο θεωρεί δίκαιο με τέτοιο τρόπο ώστε να είναι ικανοποιημένος με αυτό. Επιπλέον, οι μέθοδοι δεν θα πρέπει να καλλιεργούν το φθόνο μεταξύ των παικτών, και δεν θα πρέπει στο τέλος μιας μεθόδου να κατακερματίζεται ή να ευνοείται κάποιος παίκτης σε σχέση με τους υπόλοιπους συμμετέχοντες. Στόχος των αλγορίθμων Δίκαιης Κατανομής δεν είναι να υλοποιήσουμε την καλύτερη δυνατή «διαίρεση», αλλά να δώσουμε σε κάθε διεκδικητή το δίκαιο μερίδιο που του αναλογεί. Στην συγκεκριμένη διπλωματική εργασία μελετάμε δύο προβλήματα δίκαιης κατανομής παρουσιάζουμε μια εφαρμογή που μπορεί να χρησιμοποιηθεί για τη χρήση δύο μεθόδων/αλγορίθμων δίκαιης κατανομής. Οι μέθοδοι δίκαιης κατανομής μπορούν σε κάποιες περιπτώσεις να εκφραστούν σαν ένα παιχνίδι όπου οι παίκτες, δηλαδή τα άτομα, αξιολογούν διαφορετικά τα αντικείμενα. Οι μέθοδοι στις οποίες εστιάσαμε στο πλαίσιο της παρούσας διπλωματικής εργασίας εγγυώνται ότι όλα τα άτομα που συμμετέχουν λαμβάνουν ένα δίκαιο μερίδιο. Συγκεκριμένα ασχοληθήκαμε με την μέθοδο των Σφραγισμένων Προσφορών (the Method of Sealed Bids) που μπορεί να χρησιμοποιηθεί για την δίκαιη κατανομή μη διαιρέσιμων (δηλαδή διακριτών) ειδών (διαμέρισμα) μεταξύ ατόμων που αποτιμούν διαφορετικά αυτά τα είδη. Επιπλέον, εφαρμόσαμε μια μέθοδο για ένα πρόβλημα χρεοκοπίας, η οποία περιγράφηκε αρχικά στο Ταλμούδ και αργότερα αποδείχθηκε τυπικά με επιχειρήματα τα οποία βασίζονται στην θεωρία των παιγνίων, όπου ο στόχος είναι να διαιρεθεί με δίκαιο τρόπο μια ανεπαρκής ποσότητα διαιρέσιμων στοιχείων (χρηματικό ποσό) μεταξύ ατόμων με διαφορετικές απαιτήσεις. Η εφαρμογή μας περιέχει υλοποιήσεις των δύο μεθόδων και θα μπορούσε να χρησιμοποιηθεί και για εκπαιδευτικούς σκοπούς, προκειμένου να βοηθηθούν οι μαθητές να εξοικειωθούν με όρους, έννοιες και τεχνικές από την αλγοριθμική θεωρία παιγνίων. Επιπλέον, θα μπορούσε να χρησιμοποιηθεί σε σενάρια πραγματικού κόσμου που σχετίζονται με τον νόμο, για παράδειγμα, για τη διαίρεση μιας περιουσίας μεταξύ πιστωτών όταν οι συνολικές απαιτούμενες οφειλές υπερβαίνουν την υπάρχουσα περιουσία ή για σκοπούς κατανομής κληρονομιάς όταν οι δικαιούχοι αποδίδουν διαφορετική αξία στα διαθέσιμα αντικείμενα. Η εφαρμογή διαθέτει εύχρηστη διεπαφή και μπορεί να εκτελεστεί σε τυπικό υπολογιστή χωρίς να απαιτούνται προηγμένες δεξιότητες εκ μέρους των εμπλεκόμενων χρηστών.
Description
Keywords
Κατάρτιση, Δίκαιη κατανομή, Θεωρία παιγνίων
Citation