Η Μέθοδος Πολλαπλασιαστικών Συντελεστών Στο Σχεδιασμό Μηχανισμών

Abstract

Η Μέθοδος Πολλαπλασιαστικών Συντελεστών αποσκοπεί στην τυποποίηση μίας πολύ χρήσιμης ιδέας η οποία συναντάται σε μία ποικιλία ερευνητικών αντικειμένων και εφαρμόζεται πιο συχνά σε προβλήματα βελτιστοποίησης ή μηχανικής μάθησης. Οιαλγόριθμοι που λειτουργούν με βάση αυτή την ιδέα, διατηρούν μία κατανομή πιθανότητας (την οποία μπορούμε να φανταστούμε με τη μορφή βαρών) επάνω στα στοιχεία ενός συγκεκριμένου συνόλου, η οποία ανανεώνεται με ένα πολλαπλασιαστικό κανόνα. Παράλληλα, η ανάλυσή τους βασίζεται σε μία ‘συνάρτηση δυναμικού’, που αντικατοπτρίζει τις αλλαγές στα βάρη. Σε αυτή τη διπλωματική εργασία, θα παρουσιάσουμετο πλαίσιο της Μεθόδου, καθώς και πολλές από τις εφαρμογές της, επικεντρώνοντας το ενδιαφέρον μας σε αυτές που εμφανίζονται στο πεδίο της Αλγοριθμικής Θεωρίας Παιγνίων, και πιο συγκεκριμένα του Σχεδιασμού Μηχανισμών.