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

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

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

Εφαρμογές της Θεωρίας Παιγνίων - Κοινωνικά Διλήμματα

Τα τελευταία 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”.