1. Home page
  2. Search

Υπολογισμός σημείων ισορροπίας Nash σε παίγνια μηδενικού αθροίσματος με δύο ομάδες

This item is provided by the institution :
Εθνικό Μετσόβιο Πολυτεχνείο   

Repository :
Ψηφιακό Αποθετήριο της Κεντρικής Βιβλιοθήκης του ΕΜΠ | Dspace@NTUA   

see the original item page
in the repository's web site and access all digital files if the item*



Υπολογισμός σημείων ισορροπίας Nash σε παίγνια μηδενικού αθροίσματος με δύο ομάδες (EL)
Min-max optimization in two-team zero-sum games (EN)
Καλογιάννης, Φοίβος (EL)
Kalogiannis, Fivos (EN)
ntua (EL)
Φωτάκης, Δημήτριος (EL)
Βλατάκης Γκαραγκούνης, Εμμανουήλ Βασίλειος (EL)
Παναγέας, Ιωάννης (EL)
Παγουρτζής, Αριστείδης (EL)
Fotakis, Dimitrios (EN)
Vlatakis Gkaragkounis, Emmanouil Vasileios (EN)
Panageas, Ioannis (EN)
bachelorThesis
2022-11-18T10:33:27Z
2022-07-19
Στην παρούσα εργασία εξετάζουμε τη (μη-)σύγκλιση μίας ειράς γνωστών αλγορίθμων βελτιστοποίησης για τον υπολογισμό σημείων ισορροπίας Nash σε παίγνια δύο ομάδων μηδενικού αθροίσματος. Τα παίγνια δύο ομάδων μηδενικού αθροίσματος μπορούν να μοντελοποιήσουν τη δυναμική της σύγκρουσης μεταξύ δύο αντιτιθέμενων μερών χωρίς να καταφεύγουν σε απλοϊκοποίηση του μοντέλου ως μία σύγκρουση μεταξύ δύο μετα-παικτών. Από άποψη υπολογιστικής πολυπλοκότητας, δείχνουμε ότι το πρόβλημα υπολογισμού σημείων ισορροπίας Nash είναι CLS-δύσκολο. Στη συνέχεια, αποδεικνύουμε ότι για μία οικογένεια παιγνίων δύο ομάδων, μία σειρά αλγορίθμων πρώτου βαθμού (GDA, OGDA, EG, OMWU) αποτυγχάνουν να συγκλίνουν. Στον αντίποδα, συνεισφέρουμε τον σχεδιασμό ενός νέου αλγορίθμου πρώτου βαθμού που κάτω από ικανές συνθήκες συγκλίνει σε σημείο ισορροπίας Nash τόσο στη συγκεκριμένη οικόγενεια παιγνίων όσο και σε οποιοδήποτε παίγνιο (πιθανά μη κυρτό-μη κοίλο). Τέλος, παρουσιάζουμε έναν αριθμό πειραμάτων σε αρχιτεκτονικές νευρωνικών δικτύων (GANs) όπου η μοντελοποίηση τους ως σύγκρουση δύο ομάδων έχει προνομιακό πεδίο εφαρμογής. (EL)
In this dissertation we examine the (non-)convergence of an array of commonly used min-max optimization algorithms for the purpose of computing Nash equilibria in two-team zero-sum games. Two-team zero-sum games can model the dynamics of a conflict between two opposing parties without over-simplifying the model into a mere conflict between two meta-players. From a computational complexity perspective, we show that the problem of computing Nash equilibria in this class of games is CLS-hard. Consecutively, we prove that in a simple, yet non-trivial, family of two-team zero-sum games a list of first-order methods (GDA, OGDA, EG, OMWU) fail to converge. On a brighter note, we contribute the design of a novel first-order algorithm that provably converges under some sufficient conditions that we provide both in the aforementdioned family of games as well as any (possibly nonconvex-nonconcave) game. Finally, we present a number of experiments in "multi-agent" generative adversarial neural networks whose training process can favorably be modelled as a two-team zero-sum game. (EN)
Θεωρία Παιγνίων (EL)
Υπολογιστική Πολυπλοκότητα (EL)
Σημείο ισορροπίας Nash (EL)
Βελτιστοποίηση (EL)
Game Theory (EN)
Nash equilibrium (EN)
CLS (EN)
Optimization (EN)
Computational Complexity (EN)
Greek
English
Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών (EL)
Corelab (EL)
Αναφορά Δημιουργού - Μη Εμπορική Χρήση - Παρόμοια Διανομή 3.0 Ελλάδα
http://creativecommons.org/licenses/by-nc-sa/3.0/gr/
Εθνικό Μετσόβιο Πολυτεχνείο
Ψηφιακό Αποθετήριο της Κεντρικής Βιβλιοθήκης του ΕΜΠ | Dspace@NTUA
Κεντρική Βιβλιοθήκη Ε.Μ.Π.
Ιδρυματικό Αποθετήριο
Διπλωματικές Εργασίες



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)