Algorithmic and mechanism design aspects of problems with limited -or no - payments
Authors: Αμανατίδης Γεώργιος 
Published: September 2021

Η πιο αξιοσημείωτη διάκριση μεταξύ της σχεδίασης αλγορίθμων και της σχεδίασης μηχανισμών είναι η έννοια της φιλαλήθειας (truthfulness). Κατά κανόνα, ένας από τους στόχους του σχεδιαστή μηχανισμών είναι να εξασφαλίσει ότι οι παίκτες που συμμετέχουν στον μηχανισμό δεν έχουν κανένα κίνητρο να παραποιήσουν το κομμάτι της εισόδου που αποτελεί προσωπική τους πληροφορία. Για την επίτευξη του στόχου αυτού, οι πληρωμές που πραγματοποιούνται στους παίκτες από τον μηχανισμό είναι κρίσιμες. Ωστόσο, υπάρχουν πολλά σενάρια στη μικροοικονομική θεωρία όπου οι πληρωμές είναι περιορισμένες (π.χ., λόγω ύπαρξης προϋπολογισμού) ή ακόμη και εντελώς ανεπιθύμητες. Η παρούσα διδακτορική διατριβή επικεντρώνεται σε δύο τέτοια προβλήματα που είναι ενδεικτικά των προκλήσεων που προκύπτουν όταν οι πληρωμές είναι περιορισμένες ή απουσιάζουν. Συγκεκριμένα, μελετάται ο δίκαιος διαμοιρασμός μη διαιρετών αντικειμένων και οι αντίστροφες δημοπρασίες με αυστηρούς περιορισμούς προϋπολογισμού, τόσο από την παιγνιοθεωρητική όσο και από την αλγοριθμική σκοπιά. Στο πρώτο μέρος της διατριβής, μελετάμε το πρόβλημα του υπολογισμού διανομών μη διαιρετών αγαθών, οι οποίες παρέχουν εγγυήσεις ως προς τα μεγιστοελάχιστα μερίδια (maximin shares) των παικτών, μια πρόσφατα ορισμένη έννοια δικαιότητας. Δεδομένου ενός συνόλου παικτών και ενός συνόλου αγαθών, ο στόχος είναι να βρεθεί μια διανομή που να εγγυάται σε κάθε παίκτη μια προσέγγιση του μεγιστοελαχίστου μεριδίου του. Το κύριο αλγοριθμικό αποτέλεσμά μας είναι ένας 2/3-προσεγγιστικός αλγόριθμος, ο οποίος τρέχει σε πολυωνυμικό χρόνο για οποιονδήποτε αριθμό παικτών και αγαθών. Επιπλέον, επιχειρούμε μια πιθανοτική ανάλυση και παρέχουμε μια θεωρητική αιτιολόγηση των πειραματικών δεδομένων που αναφέρονται στη σχετική βιβλιογραφία και που υποδεικνύουν ότι υπάρχουν σχεδόν πάντα καλύτερες προσεγγίσεις.Από τη σκοπιά της σχεδίασης μηχανισμών, αυτό είναι ένα περιβάλλον στο οποίο δεν επιτρέπονται πληρωμές. Ακόμη και για δύο παίκτες και λίγα αγαθά, το πρόβλημα είναι αυστηρά δυσκολότερο από το αντίστοιχο αλγοριθμικό και γίνονται προφανείς οι περιορισμοί που επιβάλλει η φιλαλήθεια στην προσεγγισιμότητα του προβλήματος. Εστιάζουμε στην περίπτωση των δύο παικτών και το κύριο αποτέλεσμά μας είναι ένας πλήρης χαρακτηρισμός των φιλαληθών μηχανισμών που κατανέμουν όλα τα αγαθά. Ο χαρακτηρισμός αυτός έχει άμεσες συνέπειες στο σχεδιασμό μηχανισμών με εγγυήσεις δικαιότητας, όπως η δικαιότητα μεγιστοελαχίστου μεριδίου (maximin share fairness) και η απουσία φθόνου εξαιρουμένου το πολύ ενός αντικειμένου (envy-freeness up to one item). Στο δεύτερο μέρος της διατριβής, μελετάμε μια οικογένεια αντίστροφων δημοπρασιών με περιορισμένο προϋπολογισμό. Το γενικότερο αλγοριθμικό πρόβλημα είναι να αγοράσουμε ένα σύνολο πόρων, καθένας από τους οποίους έχει κάποιο κόστος, έτσι ώστε να μην υπερβούμε έναν δεδομένο προϋπολογισμό και ταυτόχρονα να μεγιστοποιήσουμε μια δεδομένη συνάρτηση αποτίμησης. Αυτό το πλαίσιο περιλαμβάνει τις παραλλαγές πολλών γνωστών προβλημάτων βελτιστοποίησης όπου έχει προστεθεί και ένας περιορισμός προϋπολογισμού. Όταν οι πόροι ανήκουν σε στρατηγικούς παίκτες, ο στόχος είναι να σχεδιαστούν φιλαλήθεις μηχανισμοί που δεν παραβιάζουν τον προϋπολογισμό.Παίρνουμε μηχανισμούς με σημαντικά βελτιωμένους λόγους προσέγγισης για αρκετές υποκατηγορίες υπομετρικών (submodular) συναρτήσεων, όπως οι συναρτήσεις κάλυψης (coverage functions) και οι συναρτήσεις κοπής (cut functions). Στη συνέχεια παρέχουμε ένα γενικό σχήμα για τον σχεδιασμό ντετερμινιστικών και τυχαιοποιημένων μηχανισμών για μια υποκλάση των XOS συναρτήσεων που περιέχει προβλήματα των οποίων το σύνολο εφικτών λύσεων σχηματίζει ένα σύστημα ανεξαρτησίας. Ορισμένα αντιπροσωπευτικά προβλήματα είναι, μεταξύ άλλων, η εύρεση μέγιστων σταθμισμένων ταιριασμάτων (maximum weighted matchings) και μέγιστων σταθμισμένων μελών μητροειδών (maximum weighted matroid members). Για τα περισσότερα από τα παραπάνω, πριν από τα αποτελέσματά μας, ήταν γνωστοί μόνο τυχαιοποιημένοι μηχανισμοί με πολύ υψηλούς λόγους προσέγγισης. Ένα καθαρά αλγοριθμικό υποπροϊόν της δουλειάς μας είναι ένας πολυωνυμικός 2e/(e-1)-προσεγγιστικός αλγόριθμος για το πρόβλημα της μεγιστοποίησης συμμετρικών υπομετρικών συναρτήσεων υπό περιορισμό προϋπολογισμού. Πρόκειται για τον καλύτερο γνωστό λόγο προσέγγισης που επιτυγχάνεται από ντετερμινιστικό αλγόριθμο, υποθέτοντας μόνο κλήσεις σε ένα μαντείο για την αντικειμενική συνάρτηση.