Σε σενάρια ανταγωνισμού μεταξύ παικτών με εγωιστικά κίνητρα, ένα ισχυρό σημείο ισορροπίας είναι μία κατάσταση όπου καμία δυνατή συμμαχία παικτών δεν μπορεί να δράσει με τρόπο κερδοφόρο προς όλα τα μέλη της. Το ισχυρό τίμημα της αναρχίας ορίζεται ως ο λόγος του χείριστου ισχυρού σημείου ισορροπίας προς το κοινωνικό βέλτιστο. Μετράει την απώλεια κέρδους που προκύπτει σε ένα παίγνιο που επιτρέπει συνεργασία μεταξύ των παικτών του, εξαιτίας της έλλειψης κεντρικού σχεδιασμού.
Η παρούσα Πτυχιακή Εργασία στοχεύει να διερευνήσει το ισχυρό τίμημα της αναρχίας στο πλαίσιο της χρονοδρομολόγησης εργασιών, όπου οι παίκτες - εργασίες επιλέγουν μηχανές, μονομερώς ή συνεργατικά, με στόχο την ελαχιστοποίηση του ατομικού τους κόστους. Συγκεκριμένα, παρουσιάζουμε και αποδεικνύουμε φράγματα για το ισχυρό τίμημα της αναρχίας από προϋπάρχουσα επιστημονική έρευνα. Στη γενική περίπτωση, βρίσκουμε άνω και κάτω φράγματα συναρτήσει του αριθμού των παικτών, του βαθμού συνεργασίας μεταξύ τους και του πλήθους των μηχανών, ενώ στην περίπτωση ίδιων μηχανών, βρίσκουμε σταθερό άνω φράγμα.
(EL)
In competitive settings with selfish players, a strong equilibrium is a state where no possible coalition of players can act in a way that is beneficial to all of its members. The
strong price of anarchy is defined as the ratio of the worst strong equilibrium to the social optimum. It measures the loss of efficiency that arises in a game allowing cooperation between its players, due to the lack of central design.
This thesis aims to examine the strong price of anarchy in the context of job scheduling,
where jobs choose machines, either unilaterally or cooperatively, with the goal of minimizing their individual cost. Specifically, we present and prove bounds for the strong price of anarchy from existing scientific research. In the general case, we obtain upper and lower bounds as a function of the number of players, the degree of cooperation between them and the number of machines, while in the case of identical machines, we obtain a fixed upper bound.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
