Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for +publisher:"University of Patras" +contributor:("Panagopoulou, Panagiota"). Showing records 1 – 2 of 2 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Παναγοπούλου, Παναγιώτα. Αλγοριθμική και εξελικτική θεωρία παιγνίων.

Degree: 2008, University of Patras

Στα πλαίσια της διατριβής αναπτύξαμε δύο από τους πρώτους αλγορίθμους υπολογισμού μιας ε-προσεγγιστικής ισορροπίας Nash για την περίπτωση όπου το ε είναι κάποια σταθερά. Οι προσεγγίσεις που επιτυγχάνουν οι αλγόριθμοί μας είναι ε=3/4 και ε=(2+λ)/4 αντίστοιχα, όπου λ είναι το ελάχιστο, μεταξύ όλων των ισορροπιών Nash, κέρδος για έναν παίκτη. Επιπλέον, μελετήσαμε μια ευρεία κλάση τυχαίων παιγνίων δύο παικτών, για την οποία υπολογίσαμε μια πολύ καλή ε-προσεγγιστική ισορροπία Nash, με το ε να τείνει στο 0 καθώς το πλήθος των διαθέσιμων στρατηγικών των παικτών τείνει στο άπειρο. Οι αρχές της θεωρίας παιγνίων είναι χρήσιμες στην ανάλυση της επίδρασης που έχει στην καθολική απόδοση ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Προς την κατεύθυνση αυτή, εστιάσαμε στο πρόβλημα της εξισορρόπησης φορτίου. Μελετήσαμε διάφορα μοντέλα πληροφόρησης (π.χ. όταν όλα τα φορτία είναι άγνωστα ή όταν κάθε παίκτης γνωρίζει το μέγεθος του δικού του φορτίου) και αναλύσαμε για το καθένα το σύνολο και τις ιδιότητες των ισορροπιών Nash. Yπολογίσαμε επίσης φράγματα στο λόγο απόκλισης, ο οποίος εκφράζει την επίδραση που έχει στην απόδοση του συστήματος η εγωιστική συμπεριφορά των χρηστών του. Εκτός από τα υπολογιστικά θέματα που σχετίζονται με τη θεωρία παιγνίων, έχει ενδιαφέρον να μελετηθεί κατά πόσο μπορεί η θεωρία παιγνίων να βοηθήσει στην ανάπτυξη και ανάλυση αλγορίθμων για υπολογιστικά δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης. Προς αυτήν την κατεύθυνση, μελετήσαμε από παιγνιοθεωρητική σκοπιά το πρόβλημα χρωματισμού των κορυφών ενός γραφήματος. Ορίσαμε κατάλληλα το παίγνιο χρωματισμού γραφήματος και αποδείξαμε ότι κάθε παίγνιο χρωματισμού γραφήματος έχει πάντα μια αγνή ισορροπία Nash, και ότι κάθε αγνή ισορροπία Nash αντιστοιχεί σε ορθό χρωματισμό του γραφήματος. Δείξαμε επίσης ότι υπάρχει πάντα μια αγνή ισορροπία Nash που χρησιμοποιεί βέλτιστο αριθμό χρωμάτων, δηλαδή ίσο με το χρωματικό αριθμό του γραφήματος. Επιπλέον, περιγράψαμε και αναλύσαμε έναν πολυωνυμικό αλγόριθμο που υπολογίζει μια αγνή ισορροπία Nash για ένα οποιοδήποτε παίγνιο χρωματισμού γραφήματος και χρησιμοποιεί συνολικά ένα πλήθος χρωμάτων που ικανοποιεί ταυτόχρονα τα περισσότερα κλασικά γνωστά φράγματα στο χρωματικό αριθμό.

We developed two algorithms for computing an e-approximate Nash equilibrium for the case where e is an absolute constant. The approximations achieved by our algorithms are e=3/4 and e=(2+l)/4 respectively, where λ is the minimum, among all Nash equilibria, payoff of either player. Furthermore, we studied a wide class of random two player games, for which we showed how to compute an e-approximate Nash equilibrium, where e tends to zero as the number of strategies of the players tends to infinity. Game theoretic concepts are useful in determining the impact that selfish behavior plays on the global performance of a system involving selfish entities. Towards this direction, we focused on the problem of load balancing. We studied the case where the agents are not necessarily fully…

Advisors/Committee Members: Σπυράκης, Παύλος, Panagopoulou, Panagiota, Σπυράκης, Παύλος, Κακλαμάνης, Χρήστος, Κυρούσης, Ελευθέριος, Γαροφαλάκης, Ιωάννης, Ζαρολιάγκης, Χρήστος, Κοντογιάννης, Σπυρίδων, Νικολετσέας, Σωτήρης.

Subjects/Keywords: Θεωρία παιγνίων; Ισορροπία Nash; Προσεγγιστικός αλγόριθμος; Χρωματισμός κορυφών γραφήματος; Κόστος της αναρχίας; Λόγος συνεργασίας; 519.3; Game theory; Nash equilibrium; Approximation algorithm; Vertex coloring; Price of anarchy; Coordination ratio

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Παναγοπούλου, . (2008). Αλγοριθμική και εξελικτική θεωρία παιγνίων. (Doctoral Dissertation). University of Patras. Retrieved from http://nemertes.lis.upatras.gr/jspui/handle/10889/1485

Chicago Manual of Style (16th Edition):

Παναγοπούλου, Παναγιώτα. “Αλγοριθμική και εξελικτική θεωρία παιγνίων.” 2008. Doctoral Dissertation, University of Patras. Accessed April 14, 2021. http://nemertes.lis.upatras.gr/jspui/handle/10889/1485.

MLA Handbook (7th Edition):

Παναγοπούλου, Παναγιώτα. “Αλγοριθμική και εξελικτική θεωρία παιγνίων.” 2008. Web. 14 Apr 2021.

Vancouver:

Παναγοπούλου . Αλγοριθμική και εξελικτική θεωρία παιγνίων. [Internet] [Doctoral dissertation]. University of Patras; 2008. [cited 2021 Apr 14]. Available from: http://nemertes.lis.upatras.gr/jspui/handle/10889/1485.

Council of Science Editors:

Παναγοπούλου . Αλγοριθμική και εξελικτική θεωρία παιγνίων. [Doctoral Dissertation]. University of Patras; 2008. Available from: http://nemertes.lis.upatras.gr/jspui/handle/10889/1485

2. Παναγοπούλου, Παναγιώτα. Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων.

Degree: 2005, University of Patras

Στην παρούσα διπλωματικής εργασία εφαρμόζουμε τις αρχές της Θεωρίας Παιγνίων, και συγκεκριμένα τις έννοιες των Ισορροπιών Nash και των Παι­γνίου Συμφόρησης, ώστε να αναλύσουμε την επίδραση που έχει στην καθο­λική απόδοση ενός δικτύου και γενικότερα ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Αρχικά ασχολούμαστε με το πρόβλημα της εγωιστικής δρομολόγησης φορ­τίων από μια κοινή πηγή προς έναν κοινό προορισμό σε ένα δίκτυο επικοι­νωνίας. Σε ένα τέτοιο περιβάλλον οι χρήστες επιλέγουν εγωιστικά τις στρα­τηγικές τους, οι οποίες στην περίπτωση μας αντιστοιχούν σε μονοπάτια από την πηγή προς τον προορισμό Όταν οι χρήστες δρομολογούν τα φορτία τους σύμφωνα με τις στρατηγικές που επιλέγουν, έρχονται αντιμέτωποι με μια κα­θυστέρηση που προκαλείται από τα φορτία όλων των χρηστών καθώς διαμοι­ράζονται τις ακμές. Κάθε χρήστης στοχεύει στην ελαχιστοποίηση του εγωι­στικού τον κόστους, που αντιστοιχεί σε αυτήν ακριβώς την καθυστέρηση, γεγονός που συνήθως έρχεται σε αντίθεση με το στόχο της βελτιστοποίησης της καθολικής απόδοσης του δικτύου. Η θεωρία των ισορροπιών Nash μας παρέχει μία σημαντική αρχή επίλυ­σης για τέτοιου είδους καταστάσεις: μια ισορροπία Nash, είναι μια κατάσταση του συστήματος τέτοια ώστε δεν υπάρχει κάποιος χρήστης που να μπορεί να μειώσει το εγωιστικό του κόστος αλλάζοντας μονομερώς τη στρατηγική του. Σε ένα τέτοιο δίκτυο λοιπόν περιμένουμε οι χρήστες να καταλήξουν σε μια ισορροπία Nash. Ωστόσο, ο υπολογισμός μιας τέτοιας ισορροπίας παραμέ­νει ένα πρόβλημα του οποίου η πολυπλοκότητα είναι, στη γενική περίπτωση, άγνωστη. Στα πλαίσια αυτής της διπλωματικής εργασίας δείχνουμε πειραματικά ότι ο υπολογισμός μιας αγνής ισορροπίας Nash σε ένα περιβάλλον εγωιστικής δρομολόγησης, όπου η καθυστέρηση σε κάθε ακμή ισούται με το φορτίο της. μπορεί να γίνει σε πολυωνυμικό χρόνο για μια μεγάλη ποικιλία δικτύων και κατανομών των φορτίων των χρηστών. Επιπλέον, προτείνουμε μια αρχική ανάθεση χρηστών σε μονοπάτια η οποία, όπως δείχνουν οι προσομοιώσεις μας, οδηγεί σε μια αξιοσημείωτη μείωση του συνολικού αριθμού των βημάτων που απαιτούνται ώστε να καταλήξουμε σε μια αγνή ισορροπία Nash. Επίσης αποδεικνύουμε την ύπαρξη αγνών ισορροπιών Nash και για την περίπτωση που η καθυστέρηση σε κάθε ακμή είναι εκθετική συνάρτηση του φορτίου της. Στη συνέχεια προτείνουμε και αναλύουμε ένα νέο μηχανισμό κόστους που θέτει τιμές για την ανταγωνιστική χρησιμοποίηση πόρων από ένα σύνολο χρη­στών. Το βασικό πλεονέκτημα αυτού του μηχανισμού είναι ότι οι πόροι θέ­τουν τα κόστη με έναν ισοδύναμο, δίκαιο τρόπο, και το πλέον σημαντικό είναι ότι κανένας πόρος δεν επωφελείται εις βάρος των χρηστών. Αυτός ο δίκαιος μηχανισμός κόστους επαγάγει ένα μη συνεργατικό παί­γνιο μεταξύ των χρηστών, για το οποίο αναλύουμε τις ισορροπίες Nash. Απο­δεικνύουμε ότι δεν υπάρχουν αγνές ισορροπίες Nash, εκτός από την περί­πτωση όπου όλα τα φορτία είναι ίσα, ενώ δείχνουμε ότι υπάρχει πάντα μία πλήρως μικτή ισορροπία Nash. Επίσης αναλύουμε για το παίγνιο αυτό το Κόστος της Αναρχίας, που εκφράζει την απόκλιση της… Advisors/Committee Members: Σπυράκης, Παύλος, Panagopoulou, Panagiota, Σπυράκης, Παύλος, Κακλαμάνης, Χρήστος, Κυρούσης, Ελευθέριος.

Subjects/Keywords: Θεωρία παιγνίων; Παίγνια συμφόρησης; Παίγνια δυναμικού; 519.82; Game theory; Congestion games; Potential games; Price of anarchy

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Παναγοπούλου, . (2005). Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων. (Masters Thesis). University of Patras. Retrieved from http://nemertes.lis.upatras.gr/jspui/handle/10889/141

Chicago Manual of Style (16th Edition):

Παναγοπούλου, Παναγιώτα. “Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων.” 2005. Masters Thesis, University of Patras. Accessed April 14, 2021. http://nemertes.lis.upatras.gr/jspui/handle/10889/141.

MLA Handbook (7th Edition):

Παναγοπούλου, Παναγιώτα. “Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων.” 2005. Web. 14 Apr 2021.

Vancouver:

Παναγοπούλου . Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων. [Internet] [Masters thesis]. University of Patras; 2005. [cited 2021 Apr 14]. Available from: http://nemertes.lis.upatras.gr/jspui/handle/10889/141.

Council of Science Editors:

Παναγοπούλου . Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων. [Masters Thesis]. University of Patras; 2005. Available from: http://nemertes.lis.upatras.gr/jspui/handle/10889/141

.