Το παίγνιο εξισορρόπησης φορτίου με τρεμάμενο χέρι
Στην παρούσα διπλωματική εργασία εφαρμόζουμε τις αρχές της Θεωρίας Παιγνίων και πιο συγκεκριμένα τις έννοιες των Ισορροπιών Nash και των Παιγνίων Εξισορρόπησης Φορτίου, με σκοπό να αναλύσουμε την επίδραση που έχει στην απόδοση των δικτύων και των κατανεμημένων συστημάτων η εγωιστική και ανταγωνιστικ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2012
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/5058 |
| id |
nemertes-10889-5058 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-50582022-09-05T20:52:34Z Το παίγνιο εξισορρόπησης φορτίου με τρεμάμενο χέρι Φίλιππας, Απόστολος Σπυράκης, Παύλος Σπυράκης, Παύλος Filippas, Apostolos Θεωρία παιγνίων Εξισορρόπηση φορτίου Τρεμάμενο χέρι Game theory Load balancing Trembling hand 519.3 Στην παρούσα διπλωματική εργασία εφαρμόζουμε τις αρχές της Θεωρίας Παιγνίων και πιο συγκεκριμένα τις έννοιες των Ισορροπιών Nash και των Παιγνίων Εξισορρόπησης Φορτίου, με σκοπό να αναλύσουμε την επίδραση που έχει στην απόδοση των δικτύων και των κατανεμημένων συστημάτων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών τους. Πρώτα εξετάζουμε το παίγνιο της εξισορρόπησης φορτίου με τρεμάμενο χέρι σε ταυτόσημες μηχανές ως προς την ύπαρξη αγνών ισορροπιών Nash. Δείχνουμε πως υπάρχει πάντα μία αγνή ισορροπία Nash με αναγωγή από τα αποτελέσματα για τα παίγνια εξισορρόπησης φορτίου. Έπειτα, δίνουμε αλγόριθμο πολυωνυμικού χρόνου για τον υπολογισμό της ισορροπίας αυτής. Τέλος, εξετάζουμε το κόστος της Αναρχίας του παιγνίου. Το κόστος της Αναρχίας εκφράζει την απόκλιση της απόδοσης της χειρότερης Ισορροπίας Nash από την βέλτιστη απόδοση. Αποδεικνύουμε πως το κόστος της Αναρχίας του παιχνιδιού φράσσεται εκ των άνω από μία μικρή σταθερά. In the present diploma thesis we will be using basic concepts of Game Theory, more specifically the concepts of Nash Equilibrium and Load Balancing Games, in order to analyse the effect of egoistic and competitive user's behaviour on the efficiency of networks and distributed systems. Firstly, we prove that the trembling hand load balancing game on identical machines always admits a pure Nash equilibrium. Secondly, we find an algorithm that computes this Nash equilibrium in polynomial time. Finally, we compare the social cost of pure equilibria with optimal solutions. This ratio is called pure price of Anarchy. We prove that the pure price of anarchy is bounded by a small constant factor. 2012-02-14T11:38:39Z 2012-02-14T11:38:39Z 2011-10-27 2012-02-14 Thesis http://hdl.handle.net/10889/5058 gr 0 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Θεωρία παιγνίων Εξισορρόπηση φορτίου Τρεμάμενο χέρι Game theory Load balancing Trembling hand 519.3 |
| spellingShingle |
Θεωρία παιγνίων Εξισορρόπηση φορτίου Τρεμάμενο χέρι Game theory Load balancing Trembling hand 519.3 Φίλιππας, Απόστολος Το παίγνιο εξισορρόπησης φορτίου με τρεμάμενο χέρι |
| description |
Στην παρούσα διπλωματική εργασία εφαρμόζουμε τις αρχές της Θεωρίας Παιγνίων και πιο συγκεκριμένα τις έννοιες των Ισορροπιών Nash και των Παιγνίων Εξισορρόπησης Φορτίου, με σκοπό να αναλύσουμε την επίδραση που έχει στην απόδοση των δικτύων και των κατανεμημένων συστημάτων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών τους. Πρώτα εξετάζουμε το παίγνιο της εξισορρόπησης φορτίου με τρεμάμενο χέρι σε ταυτόσημες μηχανές ως προς την ύπαρξη αγνών ισορροπιών Nash. Δείχνουμε πως υπάρχει πάντα μία αγνή ισορροπία Nash με αναγωγή από τα αποτελέσματα για τα παίγνια εξισορρόπησης φορτίου. Έπειτα, δίνουμε αλγόριθμο πολυωνυμικού χρόνου για τον υπολογισμό της ισορροπίας αυτής. Τέλος, εξετάζουμε το κόστος της Αναρχίας του παιγνίου. Το κόστος της Αναρχίας εκφράζει την απόκλιση της απόδοσης της χειρότερης Ισορροπίας Nash από την βέλτιστη απόδοση. Αποδεικνύουμε πως το κόστος της Αναρχίας του παιχνιδιού φράσσεται εκ των άνω από μία μικρή σταθερά. |
| author2 |
Σπυράκης, Παύλος |
| author_facet |
Σπυράκης, Παύλος Φίλιππας, Απόστολος |
| format |
Thesis |
| author |
Φίλιππας, Απόστολος |
| author_sort |
Φίλιππας, Απόστολος |
| title |
Το παίγνιο εξισορρόπησης φορτίου με τρεμάμενο χέρι |
| title_short |
Το παίγνιο εξισορρόπησης φορτίου με τρεμάμενο χέρι |
| title_full |
Το παίγνιο εξισορρόπησης φορτίου με τρεμάμενο χέρι |
| title_fullStr |
Το παίγνιο εξισορρόπησης φορτίου με τρεμάμενο χέρι |
| title_full_unstemmed |
Το παίγνιο εξισορρόπησης φορτίου με τρεμάμενο χέρι |
| title_sort |
το παίγνιο εξισορρόπησης φορτίου με τρεμάμενο χέρι |
| publishDate |
2012 |
| url |
http://hdl.handle.net/10889/5058 |
| work_keys_str_mv |
AT philippasapostolos topaignioexisorropēsēsphortioumetremamenocheri |
| _version_ |
1771297335678074880 |
