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

Το πρόβλημα της Δίκαιης Κατανομής αποτελεί ενεργό ερευνητικό πρόβλημα εδώ και πολλά χρόνια. Το πρόβλημα αυτό είναι ουσιαστικά πρόβλημα κατανομής ενός συνόλου πόρων, το οποίο διεκδικούν άνθρωποι (παίκτες) έτσι ώστε καθένας από αυτούς να λαμβάνει το κατάλληλο μερίδιο που...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριος συγγραφέας:	Παπαδημητρίου, Άγγελος
Άλλοι συγγραφείς:	Papadimitriou, Angelos
Γλώσσα:	Greek
Έκδοση:	2022
Θέματα:	Κατάρτιση Δίκαιη κατανομή Θεωρία παιγνίων Training Fair division Game theory
Διαθέσιμο Online:	http://hdl.handle.net/10889/15835

id	nemertes-10889-15835
record_format	dspace
institution	UPatras
collection	Nemertes
language	Greek
topic	Κατάρτιση Δίκαιη κατανομή Θεωρία παιγνίων Training Fair division Game theory
spellingShingle	Κατάρτιση Δίκαιη κατανομή Θεωρία παιγνίων Training Fair division Game theory Παπαδημητρίου, Άγγελος Θεωρητική και πειραματική μελέτη αλγορίθμων για δίκαιη κατανομή
description	Το πρόβλημα της Δίκαιης Κατανομής αποτελεί ενεργό ερευνητικό πρόβλημα εδώ και πολλά χρόνια. Το πρόβλημα αυτό είναι ουσιαστικά πρόβλημα κατανομής ενός συνόλου πόρων, το οποίο διεκδικούν άνθρωποι (παίκτες) έτσι ώστε καθένας από αυτούς να λαμβάνει το κατάλληλο μερίδιο που του αντιστοιχεί. Είναι ένα πρόβλημα κατανομής ενός ή περισσότερων αγαθών μεταξύ δύο ή περισσότερων παικτών, με τρόπο που να ικανοποιεί ένα κατάλληλο κριτήριο «δικαιοσύνης». Παραδοσιακά, είναι ένα πρόβλημα που έχει απασχολήσει την Οικονομική Επιστήμη και σε κάποιο βαθμό τα Μαθηματικά, τη Φιλοσοφία και την Πολιτική Επιστήμη, αλλά πλέον αποτελεί ένα ερευνητικό αντικείμενο που απασχολεί και την Επιστήμη των Υπολογιστών (ιδιαίτερα σε συστήματα AI) και σχετίζεται στενά με πολλές εφαρμογές. Επιπλέον, η Δίκαιη Κατανομή αποτελεί ένα πρόβλημα του πραγματικού κόσμου σε διάφορες πραγματικές συνθήκες όπως είναι επιχειρήσεις, μοίρασμα περιουσίας, κέρδη τυχερών παιγνίων, μοίρασμα φυσικών πόρων κ.ά. Μία μέθοδος Δίκαιης Κατανομής είναι μια διαδικασία που μπορεί να ακολουθηθεί και να οδηγήσει σε μοίρασμα αντικειμένων με τέτοιο τρόπο ώστε κάθε διεκδικητής (παίκτης) να αισθάνεται ότι έχει λάβει το δίκαιο μερίδιο που του αντιστοιχεί. Θα πρέπει όμως να υπάρχουν μερικές παραδοχές έτσι ώστε να λειτουργήσουν αυτές οι μέθοδοι. Οι παίκτες δεν θα πρέπει να συνεργάζονται μεταξύ τους και κατά συνέπεια δεν θα πρέπει να γνωρίζουν τις προτιμήσεις των άλλων παικτών. Επιπλέον, θα πρέπει οι παίκτες να λειτουργούν με ορθολογική σκέψη, δηλαδή θα πρέπει να ενεργούν συνεχώς με την λογική τους και δεν θα πρέπει να επηρεάζονται από συναισθηματικούς παράγοντες. Οι μέθοδοι θα πρέπει να επιτρέπουν στα άτομα που συμμετέχουν μια δίκαιη κατανομή, χωρίς να απαιτείται εξωτερική παρέμβαση από άλλο τρίτο μέρος. Επομένως, μια μέθοδος Δίκαιης Κατανομής θα πρέπει να εγγυάται ότι κάθε παίκτης θα λάβει ένα μερίδιο το οποίο θεωρεί δίκαιο με τέτοιο τρόπο ώστε να είναι ικανοποιημένος με αυτό. Επιπλέον, οι μέθοδοι δεν θα πρέπει να καλλιεργούν το φθόνο μεταξύ των παικτών, και δεν θα πρέπει στο τέλος μιας μεθόδου να κατακερματίζεται ή να ευνοείται κάποιος παίκτης σε σχέση με τους υπόλοιπους συμμετέχοντες. Στόχος των αλγορίθμων Δίκαιης Κατανομής δεν είναι να υλοποιήσουμε την καλύτερη δυνατή «διαίρεση», αλλά να δώσουμε σε κάθε διεκδικητή το δίκαιο μερίδιο που του αναλογεί. Στην συγκεκριμένη διπλωματική εργασία μελετάμε δύο προβλήματα δίκαιης κατανομής παρουσιάζουμε μια εφαρμογή που μπορεί να χρησιμοποιηθεί για τη χρήση δύο μεθόδων/αλγορίθμων δίκαιης κατανομής. Οι μέθοδοι δίκαιης κατανομής μπορούν σε κάποιες περιπτώσεις να εκφραστούν σαν ένα παιχνίδι όπου οι παίκτες, δηλαδή τα άτομα, αξιολογούν διαφορετικά τα αντικείμενα. Οι μέθοδοι στις οποίες εστιάσαμε στο πλαίσιο της παρούσας διπλωματικής εργασίας εγγυώνται ότι όλα τα άτομα που συμμετέχουν λαμβάνουν ένα δίκαιο μερίδιο. Συγκεκριμένα ασχοληθήκαμε με την μέθοδο των Σφραγισμένων Προσφορών (the Method of Sealed Bids) που μπορεί να χρησιμοποιηθεί για την δίκαιη κατανομή μη διαιρέσιμων (δηλαδή διακριτών) ειδών (διαμέρισμα) μεταξύ ατόμων που αποτιμούν διαφορετικά αυτά τα είδη. Επιπλέον, εφαρμόσαμε μια μέθοδο για ένα πρόβλημα χρεοκοπίας, η οποία περιγράφηκε αρχικά στο Ταλμούδ και αργότερα αποδείχθηκε τυπικά με επιχειρήματα τα οποία βασίζονται στην θεωρία των παιγνίων, όπου ο στόχος είναι να διαιρεθεί με δίκαιο τρόπο μια ανεπαρκής ποσότητα διαιρέσιμων στοιχείων (χρηματικό ποσό) μεταξύ ατόμων με διαφορετικές απαιτήσεις. Η εφαρμογή μας περιέχει υλοποιήσεις των δύο μεθόδων και θα μπορούσε να χρησιμοποιηθεί και για εκπαιδευτικούς σκοπούς, προκειμένου να βοηθηθούν οι μαθητές να εξοικειωθούν με όρους, έννοιες και τεχνικές από την αλγοριθμική θεωρία παιγνίων. Επιπλέον, θα μπορούσε να χρησιμοποιηθεί σε σενάρια πραγματικού κόσμου που σχετίζονται με τον νόμο, για παράδειγμα, για τη διαίρεση μιας περιουσίας μεταξύ πιστωτών όταν οι συνολικές απαιτούμενες οφειλές υπερβαίνουν την υπάρχουσα περιουσία ή για σκοπούς κατανομής κληρονομιάς όταν οι δικαιούχοι αποδίδουν διαφορετική αξία στα διαθέσιμα αντικείμενα. Η εφαρμογή διαθέτει εύχρηστη διεπαφή και μπορεί να εκτελεστεί σε τυπικό υπολογιστή χωρίς να απαιτούνται προηγμένες δεξιότητες εκ μέρους των εμπλεκόμενων χρηστών.
author2	Papadimitriou, Angelos
author_facet	Papadimitriou, Angelos Παπαδημητρίου, Άγγελος
author	Παπαδημητρίου, Άγγελος
author_sort	Παπαδημητρίου, Άγγελος
title	Θεωρητική και πειραματική μελέτη αλγορίθμων για δίκαιη κατανομή
title_short	Θεωρητική και πειραματική μελέτη αλγορίθμων για δίκαιη κατανομή
title_full	Θεωρητική και πειραματική μελέτη αλγορίθμων για δίκαιη κατανομή
title_fullStr	Θεωρητική και πειραματική μελέτη αλγορίθμων για δίκαιη κατανομή
title_full_unstemmed	Θεωρητική και πειραματική μελέτη αλγορίθμων για δίκαιη κατανομή
title_sort	θεωρητική και πειραματική μελέτη αλγορίθμων για δίκαιη κατανομή
publishDate	2022
url	http://hdl.handle.net/10889/15835
work_keys_str_mv	AT papadēmētriouangelos theōrētikēkaipeiramatikēmeletēalgorithmōngiadikaiēkatanomē AT papadēmētriouangelos theoreticalandexperimentalstudyofalgorithmsforfairdivision
_version_	1771297183519211520
spelling	nemertes-10889-158352022-09-05T09:40:41Z Θεωρητική και πειραματική μελέτη αλγορίθμων για δίκαιη κατανομή Theoretical and experimental study of algorithms for fair division Παπαδημητρίου, Άγγελος Papadimitriou, Angelos Κατάρτιση Δίκαιη κατανομή Θεωρία παιγνίων Training Fair division Game theory Το πρόβλημα της Δίκαιης Κατανομής αποτελεί ενεργό ερευνητικό πρόβλημα εδώ και πολλά χρόνια. Το πρόβλημα αυτό είναι ουσιαστικά πρόβλημα κατανομής ενός συνόλου πόρων, το οποίο διεκδικούν άνθρωποι (παίκτες) έτσι ώστε καθένας από αυτούς να λαμβάνει το κατάλληλο μερίδιο που του αντιστοιχεί. Είναι ένα πρόβλημα κατανομής ενός ή περισσότερων αγαθών μεταξύ δύο ή περισσότερων παικτών, με τρόπο που να ικανοποιεί ένα κατάλληλο κριτήριο «δικαιοσύνης». Παραδοσιακά, είναι ένα πρόβλημα που έχει απασχολήσει την Οικονομική Επιστήμη και σε κάποιο βαθμό τα Μαθηματικά, τη Φιλοσοφία και την Πολιτική Επιστήμη, αλλά πλέον αποτελεί ένα ερευνητικό αντικείμενο που απασχολεί και την Επιστήμη των Υπολογιστών (ιδιαίτερα σε συστήματα AI) και σχετίζεται στενά με πολλές εφαρμογές. Επιπλέον, η Δίκαιη Κατανομή αποτελεί ένα πρόβλημα του πραγματικού κόσμου σε διάφορες πραγματικές συνθήκες όπως είναι επιχειρήσεις, μοίρασμα περιουσίας, κέρδη τυχερών παιγνίων, μοίρασμα φυσικών πόρων κ.ά. Μία μέθοδος Δίκαιης Κατανομής είναι μια διαδικασία που μπορεί να ακολουθηθεί και να οδηγήσει σε μοίρασμα αντικειμένων με τέτοιο τρόπο ώστε κάθε διεκδικητής (παίκτης) να αισθάνεται ότι έχει λάβει το δίκαιο μερίδιο που του αντιστοιχεί. Θα πρέπει όμως να υπάρχουν μερικές παραδοχές έτσι ώστε να λειτουργήσουν αυτές οι μέθοδοι. Οι παίκτες δεν θα πρέπει να συνεργάζονται μεταξύ τους και κατά συνέπεια δεν θα πρέπει να γνωρίζουν τις προτιμήσεις των άλλων παικτών. Επιπλέον, θα πρέπει οι παίκτες να λειτουργούν με ορθολογική σκέψη, δηλαδή θα πρέπει να ενεργούν συνεχώς με την λογική τους και δεν θα πρέπει να επηρεάζονται από συναισθηματικούς παράγοντες. Οι μέθοδοι θα πρέπει να επιτρέπουν στα άτομα που συμμετέχουν μια δίκαιη κατανομή, χωρίς να απαιτείται εξωτερική παρέμβαση από άλλο τρίτο μέρος. Επομένως, μια μέθοδος Δίκαιης Κατανομής θα πρέπει να εγγυάται ότι κάθε παίκτης θα λάβει ένα μερίδιο το οποίο θεωρεί δίκαιο με τέτοιο τρόπο ώστε να είναι ικανοποιημένος με αυτό. Επιπλέον, οι μέθοδοι δεν θα πρέπει να καλλιεργούν το φθόνο μεταξύ των παικτών, και δεν θα πρέπει στο τέλος μιας μεθόδου να κατακερματίζεται ή να ευνοείται κάποιος παίκτης σε σχέση με τους υπόλοιπους συμμετέχοντες. Στόχος των αλγορίθμων Δίκαιης Κατανομής δεν είναι να υλοποιήσουμε την καλύτερη δυνατή «διαίρεση», αλλά να δώσουμε σε κάθε διεκδικητή το δίκαιο μερίδιο που του αναλογεί. Στην συγκεκριμένη διπλωματική εργασία μελετάμε δύο προβλήματα δίκαιης κατανομής παρουσιάζουμε μια εφαρμογή που μπορεί να χρησιμοποιηθεί για τη χρήση δύο μεθόδων/αλγορίθμων δίκαιης κατανομής. Οι μέθοδοι δίκαιης κατανομής μπορούν σε κάποιες περιπτώσεις να εκφραστούν σαν ένα παιχνίδι όπου οι παίκτες, δηλαδή τα άτομα, αξιολογούν διαφορετικά τα αντικείμενα. Οι μέθοδοι στις οποίες εστιάσαμε στο πλαίσιο της παρούσας διπλωματικής εργασίας εγγυώνται ότι όλα τα άτομα που συμμετέχουν λαμβάνουν ένα δίκαιο μερίδιο. Συγκεκριμένα ασχοληθήκαμε με την μέθοδο των Σφραγισμένων Προσφορών (the Method of Sealed Bids) που μπορεί να χρησιμοποιηθεί για την δίκαιη κατανομή μη διαιρέσιμων (δηλαδή διακριτών) ειδών (διαμέρισμα) μεταξύ ατόμων που αποτιμούν διαφορετικά αυτά τα είδη. Επιπλέον, εφαρμόσαμε μια μέθοδο για ένα πρόβλημα χρεοκοπίας, η οποία περιγράφηκε αρχικά στο Ταλμούδ και αργότερα αποδείχθηκε τυπικά με επιχειρήματα τα οποία βασίζονται στην θεωρία των παιγνίων, όπου ο στόχος είναι να διαιρεθεί με δίκαιο τρόπο μια ανεπαρκής ποσότητα διαιρέσιμων στοιχείων (χρηματικό ποσό) μεταξύ ατόμων με διαφορετικές απαιτήσεις. Η εφαρμογή μας περιέχει υλοποιήσεις των δύο μεθόδων και θα μπορούσε να χρησιμοποιηθεί και για εκπαιδευτικούς σκοπούς, προκειμένου να βοηθηθούν οι μαθητές να εξοικειωθούν με όρους, έννοιες και τεχνικές από την αλγοριθμική θεωρία παιγνίων. Επιπλέον, θα μπορούσε να χρησιμοποιηθεί σε σενάρια πραγματικού κόσμου που σχετίζονται με τον νόμο, για παράδειγμα, για τη διαίρεση μιας περιουσίας μεταξύ πιστωτών όταν οι συνολικές απαιτούμενες οφειλές υπερβαίνουν την υπάρχουσα περιουσία ή για σκοπούς κατανομής κληρονομιάς όταν οι δικαιούχοι αποδίδουν διαφορετική αξία στα διαθέσιμα αντικείμενα. Η εφαρμογή διαθέτει εύχρηστη διεπαφή και μπορεί να εκτελεστεί σε τυπικό υπολογιστή χωρίς να απαιτούνται προηγμένες δεξιότητες εκ μέρους των εμπλεκόμενων χρηστών. In this work we present an application which can be used to perform fair division. In general, fair division addresses the way that sets of items can be distributed among individuals so that they all feel satisfied with the share they received. Fair division can also be considered as a game where players, i.e., individuals, valuate items differently. The division methods we selected to implement guarantee that all individuals receive a fair share. In particular, we implemented a method for a bankruptcy problem, first described in Talmud and later typically proved via game-theoretic arguments, where the objective is to divide in a fair way an insufficient amount of divisible items (e.g., money units) among individuals with different claims. We also implemented the method of sealed bids which can be used for the fair division of indivisible (i.e., discrete) items (e.g., an apartment) among individuals who valuate these items differently. Our application could be used for educational and training purposes in order to help students familiarize with terms, concepts and techniques from algorithmic game theory. It could also be exploited in law-related real-world scenaria like for example dividing an estate among creditors when the total debts claimed exceed the existing estate or for the purposes of inheritance sharing when beneficiaries assign different values to the available items. The application has an easy-to-use interface and can run on a standard computer without requiring advanced skills on behalf of involved users. 2022-02-28T07:16:13Z 2022-02-28T07:16:13Z 2022-02-04 http://hdl.handle.net/10889/15835 gr application/pdf

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

Παρόμοια τεκμήρια