| Περίληψη: | Το πρόβλημα της δίκαιης κατανομής είναι ένα πολύ σημαντικό πρόβλημα που έχει ανακύψει στον τομέα της επιστήμης των υπολογιστών και όχι μόνο. Κάποιες από τις μορφές που έχει εμφανιστεί είναι π.χ. στην κατανομή πόρων σε δίκτυα υπολογιστών, στο διακανονισμό συνόρων σε διεθνείς διαφωνίες, στο οικογενειακό δίκαιο και ως πρόβλημα της μείωσης των εκπομπών αερίων του θερμοκηπίου.
Θεωρούμε προβλήματα αναθέσεων στα οποία ένα σύνολο αγαθών είτε αγγαρειών πρέπει να ανατεθεί σε κάποιους παίκτες. Κάθε παίκτης έχει μία συνάρτηση κέρδους (κόστους) που δείχνει πόσο εκτιμά κάθε αγαθό (αγγαρεία, αντίστοιχα) και το κέρδος (κόστος) του παίκτη για κάθε πιθανό σύνολο αντικειμένων προκύπτει αθροιστικά. Στόχος του προβλήματος είναι, φυσικά, η αποδοτικότητα και η δικαιοσύνη της ανάθεσης, περιορισμοί όμως, όπως η εγωιστική συμπεριφορά των παικτών οδηγούν σε πολύ ενδιαφέρουσες παραλλαγές του προβλήματος.
Το πρώτο αποτέλεσμα της εργασίας προκύπτει από τη μελέτη του προβλήματος ανάθεσης ενός συνόλου αδιαίρετων αγαθών σε παίκτες όταν μας ενδιαφέρει να μην υπάρχει μεγάλη ζήλεια μεταξύ των παικτών. Αδιαίρετα λέγονται τα αντικείμενα που δεν μπορούν να κοπούν σε κομμάτια και πρέπει να ανατεθούν ακέραια σε κάποιο παίκτη, ενώ ζήλεια, διαισθητικά, είναι η προτίμηση που έχει κάποιος παίκτης για το σύνολο αγαθών που ανατέθηκαν σε κάποιον άλλον σε σχέση με τα αγαθά που ανατέθηκαν στον ίδιο. Όπως έχουμε αναφέρει, στην πράξη οι παίκτες έχουν εγωιστική συμπεριφορά, υπό την έννοια ότι προσπαθούν να μεγιστοποιήσουν το κέρδος τους. Για αυτό το λόγο, μπορεί να αναφέρουν εσφαλμένες συναρτήσεις κέρδους για να πετύχουν μία καλύτερη ανάθεση. Ως ειλικρινής χαρακτηρίζεται ένας μηχανισμός ανάθεσης ο οποίος εγγυάται ότι η ανάθεση των αντικειμένων βασίζεται στις σωστές συναρτήσεις κέρδους των παικτών. Υπό μία έννοια, ένας ειλικρινής μηχανισμός ανάθεσης αναγκάζει τους παίκτες να πουν την αλήθεια για τις συναρτήσεις κέρδους τους, ή αλλιώς, εγγυάται πως το κέρδος ενός παίκτη από την ανάθεση που βασίζεται σε εσφαλμένη συνάρτηση κέρδους δεν είναι μεγαλύτερο από το κέρδος που θα είχε αν η ανάθεση είχε βασιστεί στην πραγματική συνάρτηση κέρδους του, δεδομένου του ότι οι υπόλοιποι παίκτες λένε την αλήθεια.
Παρουσιάζουμε μία απλή απόδειξη ότι ειλικρινείς ντετερμινιστικοί μηχανισμοί ανάθεσης δεν ελαχιστοποιούν τη ζήλεια, χαρακτηρίζοντας τέτοιους μηχανισμούς για δύο παίκτες και δύο αντικείμενα. Συγκεκριμένα, στην απόδειξη μας φαίνεται ότι για κάθε τέτοιο ειλικρινή μηχανισμό υπάρχουν στιγμιότυπα για τα οποία η ζήλεια σχεδόν μεγιστοποιείται. Επίσης, παρουσιάζουμε μία ανάλυση για ομοιόμορφα τυχαίες αναθέσεις οι οποίες είναι ειλικρινείς μηχανισμοί κατά μέσο όρο. Τα αποτελέσματα αυτά απλοποιούν και βελτιώνουν προηγούμενα αποτελέσματα των Lipton, Markakis, Mossel και Saberi. Συγκεκριμένα, δείχνουμε ότι η ζήλεια φράσσεται εκ των άνω από την ποσότητα O(a√(m ln n)) με μεγάλη πιθανότητα, όπου a είναι το μέγιστο κέρδος για κάθε αντικείμενο για κάθε παίκτη, n είναι ο αριθμός των παικτών και m ο αριθμός των αντικειμένων. Για την περίπτωση που το κέρδος κάθε παίκτη στο σύνολο των αντικειμένων είναι 1, το φράγμα γίνεται O(√(a ln n)).
Στη συνέχεια μελετούμε την επίπτωση της δικαιοσύνης στην αποδοτικότητα των αναθέσεων. Στα ακόλουθα θα θεωρούμε ότι όντως είναι γνωστές οι πραγματικές συναρτήσεις κέρδους των παικτών. Επίσης, θεωρούμε και αναθέσεις αγγαρειών εκτός από αγαθών, καθώς επίσης και αναθέσεις διαιρετών εκτός από αδιαίρετων αντικειμένων. Ασχολούμαστε με τρείς διαφορετικές έννοιες δικαιοσύνης ανάμεσα στους παίκτες, συγκεκριμένα την αναλογικότητα, τη μη ύπαρξη ζήλειας και την ισοτιμία για αναθέσεις διαιρετών και αδιαίρετων αγαθών και αγγαρειών. Γενικά, μία ανάθεση αντικειμένων σε n παίκτες είναι αναλογική εάν σε κάθε παίκτη δίνεται η εντύπωση ότι παίρνει ένα σύνολο αντικειμένων “καλύτερο” από ποσοστό 1/n του συνόλου των αντικειμένων προς ανάθεση. Μία ανάθεση είναι χωρίς-ζήλεια εάν κάε παίκτης προτιμά όσα του έχουν ανατεθεί σε σύγκριση με το τι έχει πάρει οποιοσδήποτε άλλος παίκτης, ενώ μία ανάθεση είναι ισότιμη όταν όλοι οι παίκτες είναι εξ'ίσου ικανοποιημένοι με αυτά που τους έχουν ανατεθεί. Τέλος, μία ανάθεση είναι βέλτιστη εάν μεγιστοποιεί το κέρδος (ελαχιστοποιεί το κόστος, αντίστοιχα) του συνόλου των παικτών, δηλ. κάθε αντικείμενο ανατίθεται σε εκείνον τον παίκτη που το εκτιμά περισσότερο (του κοστίζει λιγότερο, αντίστοιχα).
Παρουσιάζουμε μία σειρά αποτελεσμάτων για το κόστος της δικαιοσύνης όσον αφορά σε κάθε μία από τις τρείς έννοιες δικαιοσύνης που αναφέρθηκαν παραπάνω, πάνω σε διαιρετά και αδιαίρετα αντικείμενα αγαθών και αγγαρειών και ποσοτικοποιούμε την απώλεια αποδοτικότητας σε δίκαιες αναθέσεις σε σύγκριση με τις βέλτιστες. Παρουσιάζουμε άνω και κάτω φράγματα για κάθε περίπτωση, τα περισσότερα από τα οποία είτε συμπίπτουν είτε απέχουν κατά σταθερούς πολλαπλασιαστικούς παράγοντες.
|
|---|
