Θεωρία παιγνίων

Η **θεωρία παιγνίων** (*game theory*) είναι κλάδος των εφαρμοσμένων Μαθηματικών  που αναπτύχθηκε από τον Ούγγρο-Αμερικανό Μαθηματικό Τζον φον Νόιμαν *(John von Neumann)* και τον συνάδελφό του στο πανεπιστήμιο του Princeton, Όσκαρ Μόργκενστερν *(Oskar Morgenstern),*για την επίλυση προβλημάτων στην Οικονομία, στο βιβλίο τους  *Theory of Games and Economic Behaviour* πάνω σε παιχνίδια μηδενικού αθροίσματος (zero-sum games). Το κύριο αντικείμενό της είναι η ανάλυση των αποφάσεων σε καταστάσεις στρατηγικής αλληλεξάρτησης.

Η θεωρία παιγνίων ασχολείται με τη μελέτη στοιχείων που χαρακτηρίζουν καταστάσεις ανταγωνιστικής αλληλεξάρτησης με έμφαση στη διαδικασία λήψης αποφάσεων περισσοτέρων από ένα ληπτών απόφασης (αντιπάλων), δηλαδή είναι μία επιστημονική διαδικασία κατά την οποία, με χρήση απλών υπολογισμών και λογικής, μπορεί να μελετηθεί - και πιθανότατα προβλεφθεί - ο τρόπος με τον οποίο άτομα ή ομάδες ατόμων λαμβάνουν αποφάσεις, σ’ ένα ανταγωνιστικό πεδίο μεταξύ τους, περιβάλλον. Με (όσο γίνεται πιο) απλά λόγια, είναι η μελέτη των διαδικασιών λήψης στρατηγικών αποφάσεων.
* Παίγνια δύο παικτών μηδενικού αθροίσματος.
* Παίγνια δύο παικτών σταθερού αθροίσματος.
* Παίγνια n παικτών με n > 2.
* Παίγνια μη σταθερού αθροίσματος.
Οι πρώτες μελέτες της συγκεκριμένης θεωρίας εμφανίζονται στις αρχές του 18ου αιώνα αλλά αρχίζει να γίνεται ευρύτερα γνωστή και να λειτουργεί σαν ανεξάρτητο επιστημονικό πεδίο στα μέσα, περίπου, του εικοστού. Την ώθηση αυτή έδωσε ο John von Neumann με μια εργασία του το 1928 και το βιβλίο που συνέγραψε με τον Oskar Morgenstern «Θεωρία παιγνίων και οικονομική συμπεριφορά», το 1944. 

Θεωρείται δε πλέον τόσο σημαντική επιστημονικά ώστε, μέχρι και το 2014, να έχουν τιμηθεί με Βραβείο Νόμπελ 11 μελετητές/θεωρητικοί της. Γνωστότερος όλων στο ευρύ κοινό, ο John Forbes Nash που τιμήθηκε με το Βραβείο το 1994 (μαζί με τους John Harsanyi και Reinhard Selten) και του οποίου η ζωή του έγινε κινηματογραφική ταινία που κέρδισε 4 βραβεία Όσκαρ. (*Ένας υπέροχος άνθρωπος- A beautiful mind*)  

## Τι είναι τα παίγνια

Τα παίγνια είναι μία μαθηματική μέθοδος ανάλυσης προβλημάτων που αφορούν τον τρόπο λήψης αποφάσεων σε καταστάσεις σύγκρουσης και συνεργασίας. Ένας παίκτης μπορεί να είναι ένα πρόσωπο, μία οργάνωση, ένα κράτος ή ένας συνασπισμός. Διάφορα προβλήματα της πολιτικής επιστήμης, της ψυχολογίας, των κοινωνικών και οικονομικών επιστημών μπορούν να μοντελοποιηθούν ως παίγνια. 

Βασική υπόθεση της Θεωρίας Παιγνίων είναι αυτή της "ευφυούς" και "λογικής" συμπεριφοράς των παικτών. Ένας παίκτης χαρακτηρίζεται ως "ευφυής", εννοώντας πως έχει τέλεια γνώση του πώς να παίξει το παίγνιο, και ως "λογικός", εννοώντας πως παίζει με αντικειμενικό στόχο τη μεγιστοποίηση του προσωπικού του οφέλους. Είναι σημαντικό να τονιστεί ότι το όφελος του κάθε παίκτη ενός παιγνίου δεν εξαρτάται μόνο απ' την επιλογή του, αλλά και από τις επιλογές των υπολοίπων παικτών (οι οποίοι δεν αντιμετωπίζονται, υποχρεωτικά, ως αντίπαλοί του). 

Παίγνιο (game) είναι η κατάσταση εκείνη κατά την οποία δύο ή περισσότεροι
ορθολογικοί παίκτες με αντικρουόμενους στόχους επιλέγουν τρόπους
ενέργειας, δημιουργώντας συνθήκες ανταγωνιστικής αλληλεξάρτησης. 

### Στοιχεία παιγνίου
* **Παίκτης**: αυτόνομη μονάδα λήψης απόφασης. Άτομο, ομάδα, επιχείρηση, κράτος κλπ. Προσπαθεί να βελτιστοποιήσει τη δική του ευημερία έναντι των αντιπάλων του βασιζόμενος στους κανόνες, στους πόρους και στις πληροφορίες που έχει στη διάθεσή του. Είναι ορθολογιστής. Υπάρχουν τουλάχιστον n ≥ 2 παίκτες.   Για n = 2 Παίγνιο Δύο Παικτών.
* **Στρατηγική**: το σύνολο των κανόνων που ορίζουν τις εφικτές επιλογές τις οποίες δύναται να ακολουθεί σε κάθε κίνησή του ο παίκτης μέχρι το τέλος του παιγνίου. Αναζητούμε τις στρατηγικές που βελτιστοποιεί το στόχο του κάθε παίκτη.
** Αμιγής Στρατηγική: Κάθε παίκτης επιλέγει μία μόνο από τις δυνατές στρατηγικές του με πιθανότητα ίση με τη μονάδα.
** Μικτή Στρατηγική: Περιλαμβάνει συνδυασμό στρατηγικών οι οποίες επιλέγονται με πιθανότητα μικρότερη της μονάδας.
* **Πίνακας αποτελεσμάτων** (πληρωμών, ανταμοιβών): Δείχνει τα αποτελέσματα του παιγνίου για κάθε συνδυασμό στρατηγικών.
* **Λύση του παιγνίου:** Η βέλτιστη στρατηγική όλων των παικτών.

### Άλλα στοιχεία
* Οι δύο παίκτες είναι ορθολογιστές, επιλέγουν τις στρατηγικές τους με αποκλειστικό στόχο τη δική τους ευημερία βάσει των στοιχείων του πίνακα, δεν αντιδρούν συναισθηματικά.
* Τα στοιχεία του πίνακα αντιπροσωπεύουν κέρδος υπό την ευρεία έννοια. Γενικά, είναι η χρησιμότητα (utility) για τον παίκτη Α από κάθε συνδυασμό δύο στρατηγικών.
* Αρχή κοινής γνώσης. Οι παίκτες γνωρίζουν τη δομή του πίνακα πληρωμών, γνωρίζουν ότι οι αντίπαλοί τους γνωρίζουν τη δομή αυτή, γνωρίζουν ότι οι αντίπαλοί τους γνωρίζουν ότι γνωρίζουν τη δομή αυτή, κ.ο.κ.
* Οι παίκτες επιλέγουν ταυτόχρονα στρατηγική, χωρίς να επικοινωνούν, χωρίς συνεργασία και χωρίς να έχουν ενημερωθεί εκ των προτέρων για την επιλογή του αντιπάλου τους.

### Χαρακτηρισμός ενός παιγνίου

Υποθέτουμε αρχικά ότι υπάρχει μία κατάσταση, όπου ορισμένοι παίκτες παίρνουν αποφάσεις (ενέργειες), οι οποίες οδηγούν σε ορισμένα αποτελέσματα. Οι παίκτες αυτοί μπορεί να είναι δύο ή και περισσότεροι. Στην πρώτη περίπτωση εμφανίζονται τα "**παίγνια δύο παικτών**" (two-player-games), και στη δεύτερη περίπτωση τα "**παίγνια ν-παικτών**" (n-player-games). Φυσικά ένα παίγνιο διαφέρει από μία πραγματική κατάσταση απλού ανταγωνισμού ή σύγκρουσης στο ότι η πραγμάτωσή του γίνεται ακριβώς κάτω από ορισμένες συνθήκες και σύμφωνα με ορισμένους κανόνες. Όλα τα παίγνια περιέχουν το χαρακτηριστικό του ανταγωνισμού μεταξύ των παικτών τους και το αποτέλεσμά του οδηγεί σε "*κέρδη*" ή "*απώλειες*".

Για να ορίσουμε τυπικά ένα παίγνιο, χρειαζόμαστε:
* Ένα μη-κενό και πεπερασμένο σύνολο παικτών.
* Για τον κάθε παίκτη, ένα μη κενό σύνολο ενεργειών.
* Για τον κάθε παίκτη, μια συνάρτηση ωφέλειας που απεικονίζει όλες τις δυνατές πλειάδες ενεργειών των παικτών σε πραγματικούς αριθμούς.
Ένα παίγνιο στο οποίο όλα τα σύνολα ενεργειών των παικτών είναι πεπερασμένα, καλείται πεπερασμένο.

Οι δύο βασικότερες μορφές αναπαράστασης ενός παιγνίου είναι η στρατηγική (strategic) και η επεκταμένη (extensive) του μορφή. Στα παίγνια στρατηγικής μορφής, οι συμμετέχοντες κάνουν την επιλογή τους μία μόνο φορά και ο κάθε παίκτης επιλέγει την ενέργειά του "ταυτόχρονα" με τους υπόλοιπους. Στα παίγνια επεκταμένης μορφής, οι συμμετέχοντες παίζουν ακολουθιακά. Ένα παίγνιο επεκταμένης μορφής αναπαριστάται από ένα δέντρο παιγνίου (game tree).

Ως παράδειγμα, δίνεται το στρατηγικό παίγνιο "η μάχη των φύλων" (battle of the sexes). Σ' αυτό το παίγνιο, ένας άντρας και η γυναίκα του επιλέγουν το μέρος που θα διασκεδάσουν το βράδυ μιας συγκεκριμένης ημέρας. Ο άντρας προτιμά να παρακολουθήσουν έναν αγώνα ποδοσφαίρου στο γήπεδο, η γυναίκα προτιμά να παρακολουθήσουν μια παράσταση στο θέατρο, όμως κανείς από τους δύο δε θέλει να περάσει μόνος του το βράδυ.
* Το σύνολο παικτών αυτού του παιγνίου είναι {Α, Γ}.
* Το σύνολο ενεργειών των παικτών είναι το {Π, Θ}, ίδιο και για τους δύο παίκτες.
* Οι συναρτήσεις ωφελειών των παικτών μπορούν να παρασταθούν όπως στον παρακάτω πίνακα:

## Σημαντικοί παιγνιοθεωρητικοί επιστήμονες και η συνεισφορά τους
Στους περαιτέρω θεμελιωτές ανήκουν
* ο Τζων Φορμπς Νας *(John Forbes Nash)* (η ζωή του έγινε θέμα της ταινίας "ένας υπέροχος άνθρωπος"), ο οποίος γενίκευσε το πρόβλημα σε παιχνίδια μη μηδενικού αθροίσματος και πρόσφερε ως λύση την ισορροπία Νας *(Nash Equilibrium).*
* ο Ράινχαρντ Ζέλτεν *(Reinhard Selten)* άνοιξε το δρόμο για ικανοποιητική λύση του προβλήματος σε δυναμικά παιχνίδια με την έννοια της ισορροπίας στα υποπαιχνίδια *(Subgame Perfect Nash Equilibrium)* και της ισορροπίας τρεμάμενου χεριού *(trembling hand perfect equilibrium).*
* ο Κωνσταντίνος Δασκαλάκης ασχολείται ερευνητικά με την θεωρία υπολογισμού και τον τρόπο που συνδέεται με την Θεωρία παιγνίων, τα οικονομικά, την στατιστική και την μηχανική μάθηση. Έχει συμβάλει στην λύση αρκετών ανοικτών προβλημάτων που αφορούν την υπολογιστική πολυπλοκότητα της ισορροπίας Νας, της μαθηματικής δομής και υπολογιστικής περιγραφής των βέλτιστων δημοπρασιών, και της ανάλυσης γνωστών μεθόδων μηχανικής μάθησης του Τζων Χαρσάνυι *(John Harsanyi)*.
 
Για τις εργασίες τους, οι τρεις τελευταίοι τιμήθηκαν το 1994 με το βραβείο της Σουηδικής Ακαδημίας Επιστημών στην μνήμη του Άλφρεντ Νομπέλ *(Alfred Bernhard Nobel)*. Είναι σίγουρο, βέβαια, ότι αν ο Τζων φον Νόιμαν ζούσε θα μοιραζόταν και αυτός το βραβείο.

Το 2005 οι θεωρητικοί παιγνίων Τόμας Σέλλινγκ (*Thomas Schelling*) και Ρόμπερτ Άουμαν (Robert Aumann) κέρδισαν το Βραβείο Νομπέλ για τις Οικονομικές Επιστήμες.

## Εφαρμογές της Θεωρίας Παιγνίων - Κοινωνικά Διλήμματα
Τα τελευταία 30 χρόνια, η θεωρία παιγνίων έχει βρει ευρύτατη εφαρμογή στα οικονομικά, όπου ολόκληροι κλάδοι στηρίζονται στις μεθόδους της, όπως π.χ. η βιομηχανική οργάνωση *(industrial organisation)*, ο σχεδιασμός μηχανισμών *(mechanism design)* με σπουδαιότερο υποκλάδο τον σχεδιασμό δημοπρασιών (auctions) κ.α. 

Επίσης, η θεωρία παιγνίων χρησιμοποιείται και στην Πολιτική Οικονομία και ειδικά στη θεωρία της συλλογικής δράσης, όπου εξηγεί ενδεχόμενα συνεργασίας μεταξύ των παικτών. Στη συγκεκριμένη εκδοχή, μιλάμε για παίγνια συνεργασίας (Cooperative Game Theory). Αυτό βρίσκεται σε άμεση συσχέτιση με τον ρόλο του κράτους και των θεσμών σε θέματα συνεργασίας. Χαρακτηριστικό παράδειγμα είναι η παροχή δημόσιων αγαθών και η φορολογία.

Επιπρόσθετα χρησιμοποιείται ευρέως και σε άλλες επιστήμες με τις οποίες παράλληλα αλληλεπιδρά, όπως η εξελικτική βιολογία, η ψυχολογία, η κοινωνιολογία κλπ.

Ένα γνωστό παράδειγμα στη θεωρία των παιγνίων είναι το δίλημμα του φυλακισμένου. Το παιχνίδι αυτό έχει χρησιμοποιηθεί ευρέως για την ανάλυση καταστάσεων κοινωνικών διλημμάτων (social dilemmas).

Η γνωστότερη στρατηγική επίλυσης της εκτεταμένης μορφής του διλήμματος του φυλακισμένου είναι η «μία σου και μία μου» (tit for tat).
Αυτή η στρατηγική παρουσιάστηκε από τον Ανατόλ Ράποπορτ (Anatol Rapoport) στο τουρνουά που διεξήχθη από τον Ρόμπερτ Άξελροντ (Robert Axelrod), πολιτικό επιστήμονα στο Πανεπιστήμιο του Michigan στα τέλη της δεκαετίας του 1970.
Η στρατηγική συνίσταται στο ότι η πρώτη κίνηση που κάνει ο παίκτης είναι πάντα η συνεργασία, ενώ στα επόμενα βήματα επιλέγει την στρατηγική του αντιπάλου του στον προηγούμενο γύρο. Στο τουρνουά του Άξελροντ, η στρατηγική αυτή κατέλαβε την πρώτη θέση (με κριτήριο το άθροισμα τιμών ωφέλειας που απέσπασε παίζοντας ενάντια σε όλες τις υπόλοιπες στρατηγικές).

## Τύποι παιγνίων

### Συνεταιριστικά / Μη συνεταιριστικά

Ένα παιχνίδι είναι συνεταιριστικό αν οι παίκτες είναι σε θέση να σχηματίσουν δεσμεύσεις. Απαιτεί από τους παίκτες να τηρούν τις υποσχέσεις τους. Σε μη-συνεταιριστικά παιχνίδια, αυτό δεν είναι δυνατό.
Συχνά γίνεται η υπόθεση ότι η επικοινωνία μεταξύ των παικτών επιτρέπεται σε συνεταιριστικά παιχνίδια αλλά όχι σε μη συνεταιριστικά. Ωστόσο, αυτή η κατάταξη σε δύο δυαδικά κριτήρια έχει αμφισβητηθεί, και μερικές φορές απορρίπτεται.
Από τα δύο είδη παιχνιδιών, τα μη συνεταιριστικά παιχνίδια είναι σε θέση να διαμορφώσουν καταστάσεις έως την τελευταία λεπτομέρεια, παράγοντας ακριβή αποτελέσματα. Τα συνεταιριστικά παιχνίδια επικεντρώνονται στο παιχνίδι γενικότερα.

### Συμμετρικά / Ασύμμετρα

Ένα συμμετρικό παιχνίδι είναι ένα παιχνίδι όπου τα κέρδη για την αναπαραγωγή μιας συγκεκριμένης στρατηγικής εξαρτάται μόνο από τις άλλες στρατηγικές που χρησιμοποιούνται, όχι από το ποιος παίζει.
Αν οι ταυτότητες των παικτών μπορεί να αλλάξει χωρίς να αλλάζει τα κέρδη στις στρατηγικές, τότε ένα παιχνίδι είναι συμμετρικό. Πολλά από τα 2 × 2 παιχνίδια που μελετήθηκαν  είναι συμμετρική. Ωστόσο, οι πιο κοινές απολαβές για κάθε ένα από αυτά τα παιχνίδια είναι συμμετρικές.
Συνηθέστερα τα ασύμμετρα παιχνίδια είναι παιχνίδια όπου δεν υπάρχουν όμοια σύνολα στρατηγικής για δύο παίκτες. Είναι δυνατόν, ωστόσο, για ένα παιχνίδι να έχει πανομοιότυπη στρατηγική για δύο παίκτες, ακόμη μπορεί να είναι ασύμμετρη. 

### Μηδενικού αθροίσματος / μη-μηδενικού αθροίσματος

Ένα παιχνίδι μηδενικού αθροίσματος είναι μια ειδική περίπτωση παιχνιδιών σταθερού αθροίσματος στα οποία οι επιλογές από τους παίκτες δεν μπορεί ούτε να μειώσει ούτε να αυξήσει τους διαθέσιμους πόρους. Σε ένα παιχνίδι μηδενικού αθροίσματος το συνολικό πλεονέκτημα για όλους τους παίκτες στο παιχνίδι, για κάθε συνδυασμό στρατηγικών, πάντα προστίθεται στο μηδέν. Το πόκερ είναι ένα παράδειγμα ενός παιχνιδιού μηδενικού αθροίσματος επειδή όταν ένας κερδίζει το ποσό οι αντιπάλοι χάνουν. Άλλο ένα παιχνίδι μηδενικού αθροίσματος είναι και το σκάκι.
Ανεπίσημα, σε παιχνίδια μη μηδενικού αθροίσματος το κέρδος ενός παίκτη δεν αντιστοιχεί αναγκαστικά με μια απώλεια του κέρδους του άλλου παίχτη.

### Ταυτόχρονα / Ακολουθιακά

Ταυτόχρονα παιχνίδια είναι παιχνίδια όπου και οι δύο παίκτες κινούνται ταυτόχρονα ή εάν δεν κινούνται ταυτόχρονα, οι παίκτες που παίζουν αργότερα αγνοούν τις ενέργειες των παικτών που έπαιξαν νωρίτερα. 
Ακολουθιακά παιχνίδια  είναι παιχνίδια στα οποία οι παίκτες οι παίκτες που παίζουν αργότερα  έχουν κάποιες γνώσεις σχετικά με προηγούμενες δράσεις. Αυτό δεν χρειάζεται να είναι τέλεια πληροφόρηση για κάθε δράση που θα είχε εκτελεστεί νωρίτερα. Θα μπορούσε να είναι πολύ λίγη γνώση. 

### Τέλειας πληροφορίας και ελλιπούς ενημέρωσης

Ένα σημαντικό υποσύνολο διαδοχικών παιχνιδιών αποτελείται από παιχνίδια τέλειας πληροφόρησης. Ένα παιχνίδι είναι παιχνίδι τέλειας πληροφόρησης, εάν όλοι οι παίκτες γνωρίζουν τις κινήσεις που έχουν ήδη πραγματοποιηθεί από όλους τους άλλους παίκτες. Έτσι, μόνο τα ακολουθιακά παιχνίδια θεωρούνται παιχνίδια τέλειας πληροφόρησης επειδή οι παίκτες στα ταυτόχρονα  παιχνίδια δεν γνωρίζουν τις ενέργειες των άλλων παικτών. Τα περισσότερα παιχνίδια που μελετήθηκαν στην θεωρία των παιγνίων είναι παιχνίδια ατελούς πληροφορίας. Τέλειας πληροφορίας παιχνίδια συγχέονται με πλήρεις πληροφορίες. Παιχνίδια πλήρους πληροφορίας απαιτούν ότι κάθε παίκτης γνωρίζει τις στρατηγική και τα  κέρδη άλλων παικτών, αλλά όχι τις δράσεις που έχουν αναληφθεί. Παιχνίδια ελλιπής πληροφορίας μπορεί να μειωθεί, ωστόσο, σε παιχνίδια ατελής πληροφοριών με την εισαγωγή των "κινήσεων από τη φύση".

### Συνδυαστικά παιχνίδια

Συνδυαστικά παιχνίδια είναι αυτά στα οποία η δυσκολία εύρεσης της βέλτιστης στρατηγικής προέρχεται από την πολλαπλότητα των δυνατών κινήσεων. Παράδειγμα είναι το σκάκι. Παιχνίδια που περιλαμβάνουν ατελή ή ελλιπείς πληροφορίες μπορεί επίσης να έχουν ένα ισχυρό συνδυαστικό χαρακτήρα όπως είναι το τάβλι. Δεν υπάρχει ενιαία θεωρία για την αντιμετώπιση των συνδυαστικών στοιχείων στα παιχνίδια.

### Παιχνίδια άπειρου μήκους

Όπως μελετήθηκε από τους οικονομολόγους και στον πραγματικό κόσμο οι παίκτες των παιχνιδιών τελειώνουν το παιχνίδι σε ένα πεπερασμένο πλήθος κινήσεων. Ο νικητής δεν είναι γνωστός παρά μόνο όταν όλες οι κινήσεις έχουν ολοκληρωθεί.Το επίκεντρο της προσοχής δεν αφορά συνήθως τον καλύτερο τρόπο για να παιχτεί ένα παιχνίδι, αλλά αν κάποιος παίκτης έχει μια στρατηγική νίκης. Η ύπαρξη αυτών των στρατηγικών για έξυπνα σχεδιασμένα παιχνίδια έχει σημαντικές συνέπειες στην περιγραφική θεωρία των συνόλων.

### Διακριτά και συνεχή παιχνίδια
Ένα μεγάλο μέρος της θεωρίας των παιγνίων ασχολείται με πεπερασμένα, διακριτά παιχνίδια, που έχουν ένα πεπερασμένο αριθμό παικτών, κινήσεων, εκδηλώσεων, αποτελεσμάτων κτλ. Πολλές έννοιες μπορούν να παραταθούν, ωστόσο. Τα συνεχή παιχνίδια επιτρέπουν στους παίκτες να επιλέξουν μια στρατηγική από ένα σύνολο η οποία συνεχίζει τη στρατηγική που είναι να παιχτεί.

## Ιστορική αναδρομή
Οι πρώτες πρόωρες συζητήσεις σχετικές με παίγνια δύο παικτών εμφανίστηκαν πολύ πριν την ανάπτυξη της σύγχρονης, μαθηματικής θεωρίας παιγνίων. Η πρώτη γνωστή αναφορά της θεωρίας παιγνίων παρουσιάστηκε σε μια επιστολή που γράφτηκε από τον James Waldegrave το 1713. Στην επιστολή αυτή, ο Waldegrave παρέχει μια λύση σε μια έκδοση δύο παικτών του παιχνιδιού καρτών le Her, η οποία ήταν βασισμένη σε μια  minimax μικτή στρατηγική. Το 1838, ο  Antoine Augustin Cournot στο βιβλίο του Recherches sur les principes mathématiques de la Théorie des Richesses, μελέτησε ένα δυοπώλιο και παρουσίασε μια λύση που είναι μια περιορισμένη έκδοση της ισορροπίας Nash. 

Το 1913 ο Ernst Zermelo στη δημοσίευση του Über eine Anwendung der auf die Mengenlehre Theorie des Schachspiels απέδειξε ότι η βέλτιστη στρατηγική στο σκάκι είναι αυστηρά προσδιορισμένη. Αυτό άνοιξε το δρόμο για πιο γενικά θεωρήματα.

Το 1938, στο βιβλίο του Applications aux Jeux de Hasard ,ο Émile Borel απέδειξε ένα minimax θεώρημα για παίγνια δύο παικτών και μηδενικού αθροίσματος στην ειδική περίπτωση που ο πίνακας κέρδους ήταν συμμετρικός.

Η θεωρία παιγνίων δεν υπάρχει στην πραγματικότητα ως ένα ξεχωριστό επιστημονικό πεδίο μέχρι το 1928 και την δημοσίευση του Zur Theorie der Gesellschaftsspiele από τον John von Neumann. Ο οποίος χρησιμοποίησε το θεώρημα σταθερού σημείου του Brouwer για συνεχείς αντιστοιχίσεις σε συμπαγή κυρτά σύνολα, η μέθοδος αυτή καθιερώθηκε στην θεωρία παιγνίων και τα Οικονομικά Μαθηματικά. Το έγγραφο ακολούθησε το βιβλίο του 1944 Theory of Games and Economic Behavior. Η δεύτερη έκδοση αυτού του βιβλίου περιέχει μια αξιωματική θεωρία της χρησιμότητας. Το έργο του von Neumann στη θεωρία παιγνίων κορυφώθηκε σε αυτό το βιβλίο το 1944. Αυτό το θεμελιώδες έργο περιέχει τη μέθοδο για την εύρεση αμοιβαία σταθερών λύσεων σε παίγνια δύο παικτών και μηδενικού αθροίσματος. Κατά την επόμενη περίοδο, οι εργασίες στη θεωρία παιγνίων εστιάζονται κυρίως σε συνεργατικά παίγνια. Οι εργασίες αυτές αναλύουν βέλτιστες στρατηγικές για ομάδες παικτών, με την προϋπόθεση ότι μπορούν να υπάρξουν συμφωνίες μεταξύ των παικτών σχετικές με τη κατάλληλη στρατηγική.

Το 1950, εμφανίστηκε η πρώτη συζήτηση στους μαθηματικούς κύκλους σχετικά με το δίλημμα του φυλακισμένου, όταν έγινε και ένα πείραμα από τους αξιοσημείωτους μαθηματικούς Merrill M. Flood και Melvin Dresher, ως μέρος της έρευνας της RAND Corporation στη θεωρία παιγνίων. Την ίδια περίοδο, ο John Nash αναπτύσσει ένα κριτήριο σχετικό με την αμοιβαία σταθερότητα στρατηγικών, γνωστή ως ισορροπία Nash , το οποίο εφαρμόζεται σε μια ευρύτερη ποικιλία παιγνίων σε σχέση με αυτά που προτείνονται από τους von Neumann και Morgenstern. Αυτή η ισορροπία είναι επαρκώς γενική ώστε να καταστεί δυνατή η ανάλυση και των μη συνεργατικών παιγνίων.

Η θεωρία παιγνίων παρουσιάζει έντονη δραστηριότητα στη δεκαετία του 1950, διάστημα κατά το οποίο αναπτύχθηκαν έννοιες όπως  core, the extensive form game, fictitious play, repeated games, Shapley value. Επιπλέον, οι πρώτες εφαρμογές της θεωρίας παιγνίων στη φιλοσοφία και την πολιτική επιστήμη εμφανίστηκαν κατά τη διάρκεια αυτής της περιόδου.

Το 1965, ο Reinhard Selten παρουσίασε την subgame perfect equilibria, στην οποία επεξεργάστηκε περαιτέρω την ισορροπία Nash. Το 1967, ο John Harsanyi ανέπτυξε τις έννοιες  complete information και Bayesian games. Στους Nash, Selten και Harsanyi απονεμήθηκε το βραβείο Νόμπελ Οικονομικών Επιστημών το 1994 για τη συμβολή τους στην οικονομική θεωρία παιγνίων.

Στη δεκαετία του 1970, η θεωρία παιγνίων εφαρμόστηκε ευρέως στη βιολογία, κυρίως ως αποτέλεσμα των εργασιών του John Maynard Smith και της evolutionarily stable στρατηγικής του. Επιπλέον, οι έννοιες correlated equilibrium, trembling hand perfection, and common knowledge εισήχθησαν και αναλύθηκαν.

Το 2005, οι θεωρητικοί των παιγνίων  Thomas Schelling και Robert Aumann τιμήθηκαν με το βραβείο Νόμπελ Οικονομικών Επιστημών. Η εργασία του Schelling ήταν σχετική με δυναμικά μοντέλα, πρώιμα παραδείγματα της evolutionary game theory. Ο Aumann συνέβαλε περισσότερο προς την κατεύθυνση της έννοιας της ισορροπίας.

Το 2007, ο  Leonid Hurwicz, μαζί με τον Eric Maskin και τον Roger Myerson, τιμήθηκαν με το βραβείο Νόμπελ Οικονομικών Επιστημών. Η συνεισφορά του Myerson περιλαμβάνει την έννοια της proper equilibrium καθώς και μια σημαντική πτυχιακή διατριβή: Game Theory, Analysis of Conflict. Ο Hurwicz εισήγαγε και τυποποίησε την έννοια της incentive compatibility.

Το 2012, βραβείο Νόμπελ Οικονομικών Επιστημών απονεμήθηκε στους Alvin E. Roth και Lloyd S. Shapley για την εργασία τους  “for the theory of stable allocations and the practice of market design”.

## Παραπομπές


Θεωρία παιγνίων

Κατηγορία:Θετικές επιστήμες
Κατηγορία:Τεχνητή νοημοσύνη