Η Ισορροπία Nash

Η ζωή του John Nash

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

Ο Nash γεννήθηκε στη Δυτική Βιρτζίνια το 1928. Αν και ενδιαφερόταν για τα μαθηματικά, αποφάσισε να γίνει ηλεκτρολόγος μηχανικός όπως και ο πατέρας του. Όταν το 1945 γράφτηκε στο “Carnegie Institute of Technology” στο Pittsburgh αποφάσισε να γίνει χημικός μηχανικός, κάτι που στην πορεία δεν του άρεσε και έτσι επέστρεψε στα μαθηματικά με τα οποία ασχολήθηκε.

Όταν πήγε το 1948 στο “Princeton” ήταν ήδη ένας από τους κορυφαίους στην θεωρία παιγνίων και είχε ήδη ασχοληθεί με “προβλήματα συμφωνιών”, δηλαδή προβλήματα στα οποία οι παίκτες μοιράζονται κάποια κοινά συμφέροντα. Με τη φράση “αυτός ο άντρας είναι ιδιοφυΐα” περιέγραψε τον John Nash, στους υπόλοιπους καθηγητές του Princeton University, ο καθηγητής R. L. Duffin.

Η σημαντικότερη του εργασία όμως ήταν αυτή που ασχολήθηκε με την ισορροπία στη θεωρία παιγνίων και χάρη στην πολύτιμη συμβολή του πήρε το όνομα “Nash ισορροπία”. Ο Nash δημοσίευσε την ιδέα του για την ισορροπία αμέσως σε ηλικία 21 ετών! Μια δισέλιδη αναφορά έγινε το 1950 στο “Proceedings of the National Academy of Sciences”. Με τίτλο “Equilibrium Points in n-Person Games”, το άρθρο δημοσίευσε περιληπτικά την ύπαρξη λύσεων για παίγνια με ν παίκτες. Επέκτεινε την έρευνα του και μια μεγαλύτερη έκδοση δημοσιεύτηκε το 1951 στο “Annals of Mathematics” με τίτλο “Non-cooperative Games”.

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

Ο Nash σκαρφίστηκε μια γενική “λύση” για όλα τα (πεπερασμένα) παίγνια και απέδειξε ότι κάθε τέτοιο παίγνιο διαθέτει τουλάχιστον μια τέτοια λύση.

Προσέγγιση της ισορροπίας Nash

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

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

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

Όπως είναι φανερό η θεωρία για την ισορροπία Nash, έχει δύο μέρη: πρώτα κάθε παίκτης κάνει την επιλογή του βασιζόμενος στην ορθολογική απόφαση που προέρχεται από το τι πιστεύει ότι θα κάνει ο αντίπαλος και δεύτερον, το ότι πιστεύει ότι κάθε κίνηση που θα κάνει ο αντίπαλος, είναι σωστή για εκείνον.

Εξέταση διαφόρων παιγνίων

Ένα από τα παράδοξα της ισορροπίας Nash που μπορεί να θεωρηθεί και σαν αδυναμία της είναι ότι σε κάποια παίγνια οι παίκτες έχουν μεγαλύτερο όφελος αν δεν διαλέξουν την ισορροπία Nash και διαλέξουν άλλη στρατηγική. Ενώ η ισορροπία Nash δίνει την ελκυστικότερη λύση για όλους τους παίκτες, οδηγώντας στο σημείο ισορροπίας, εντούτοις υπάρχουν κάποια διάσημα παίγνια που είναι εξαίρεση στον κανόνα. Κάποια από αυτά τα παίγνια χρησιμοποιήθηκαν στην έρευνα και θα αναλυθούν στη συνέχεια.

Το δίλημμα του φυλακισμένου “Prisoner’s dilemma”

Το πιο γνωστό και σημαντικό παίγνιο στην ιστορία της θεωρίας παιγνίων είναι το παίγνιο του διλήμματος του φυλακισμένου (Prisoner’s Dilemma).

Τον Ιανουάριο του 1950 οι Melvin Dresher και Merrill Flood επινόησαν το συγκεκριμένο παίγνιο και το χρησιμοποίησαν σαν παράδειγμα στο RAND Corporation. Αργότερα όταν παρουσιάστηκε αυτό το παράδειγμα σε ένα σεμινάριο στο Stanford University, ο Albert W. Tucker σκαρφίστηκε μία ιστορία πάνω στην οποία βάσισε όλη του την διάλεξη. Το παίγνιο αυτό έμεινε από τότε στην ιστορία κάνοντας την θεωρία παιγνίων γνωστή σε όλες τις κοινωνικές επιστήμες, ενώ και πάρα πολλοί μελετητές έχουν ασχοληθεί με αυτό γράφοντας διάφορα βιβλία .

Η ιστορία του Tucker έχει ως εξής:

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

Το παραπάνω πρόβλημα μπορεί να παρουσιαστεί στον επόμενο πίνακα:

Πίνακας 1

Α/Β	Β1: ο Β ομολογεί	Β2:  ο Β δεν ομολογεί
Α1: ο Α ομολογεί	3 χρόνια φυλάκισης	Α: ελευθερία Β: 5 χρόνια φυλάκισης
Α2: ο Α δεν ομολογεί	Α: 5 χρόνια φυλάκισης Β: ελευθερία	1 χρόνος φυλάκισης

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

Πίνακας 2

Α/Β	Β1: ο Β ομολογεί	Β2: ο Β δεν ομολογεί
Α1: ο Α ομολογεί	3,3	0,5
Α2: ο Α δεν ομολογεί	5,0	1,1

Το δίλημμα εμφανίζεται όταν κάποιος υποθέτει ότι και οι δύο φυλακισμένοι νοιάζονται μόνο για να ελαχιστοποιήσουν την ποινή τους. Κάθε παίκτης έχει δύο στρατηγικές επιλογές: είτε να ομολογήσει και να συνεργαστεί με την αστυνομία (confess), είτε να παραμείνει σιωπηλός (not confess). Για παράδειγμα το καλύτερο αποτέλεσμα για τον παίκτη Α, είναι να ομολογήσει και ο παίκτης Β να μείνει σιωπηλός. Το επόμενο καλύτερο αποτέλεσμα για τον Α είναι να μη μιλήσει κανένας από τους δύο, ενώ το χειρότερο σενάριο είναι να μιλήσει ο Β ενώ ο Α θα παραμείνει σιωπηλός. Το αντίστοιχο ισχύει και για τον παίκτη Β. Είναι λοιπόν φανερό πως ο,τιδήποτε και να σκοπεύει να κάνει ο Β, ο παίκτης Α θα πρέπει να επιλέξει την πρώτη στρατηγική (να ομολογήσει δηλαδή), αφού έτσι θα έχει καλύτερα αποτελέσματα. Ομοίως ισχύει και για τον Β παίκτη ο οποίος θα προτιμήσει και αυτός να μη μιλήσει. Σε αυτό το σημείο υπάρχει το δίλημμα αφού από τον πίνακα φαίνεται πως οι παίκτες θα αποκομίσουν μεγαλύτερο όφελος αν και οι δύο επιλέξουν να μη μιλήσουν από το να τα ομολογήσουν όλα. Έτσι η καλύτερη στρατηγική για τον καθένα ξεχωριστά, παράγει ένα αποτέλεσμα που δεν είναι καλό για την ομάδα, κάνοντας τα ατομικά κίνητρα να υπονομεύουν το κοινό συμφέρον .

Πρόκειται για ένα παιχνίδι όπου τα κέρδη προέρχονται από τη συνεργασία. Το καλύτερο αποτέλεσμα και για τους δύο παίκτες είναι να μη μιλήσουν στους αστυνομικούς . Παρόλα αυτά, κάθε παίκτης έχει ένα μεγάλο κίνητρο να γίνει προδότης. Οτιδήποτε και να κάνει ο ένας παίκτης, ο αντίπαλος προτιμάει να ομολογήσει. Έτσι το παίγνιο αυτό έχει μία μοναδική Nash ισορροπία, μία κυρίαρχη στρατηγική, η οποία είναι η λύση (Α₁,Β₁)=(3,3), η από κοινού ομολογία.

Σε κάθε παίγνιο η λύση παρουσιάζεται και με τη βοήθεια του προγράμματος Gambit, το οποίο είναι χρήσιμο εργαλείο στη θεωρία παιγνίων αφού έχει πολλές εφαρμογές και βρίσκει τις ισορροπίες Nash και σε καθαρές και σε μεικτές στρατηγικές.

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

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

Τέλος, θα ήθελα να αναφέρω, ότι το 2008, ο κύριος Δασκαλάκης Κωνσταντίνος, (για τον οποίο θα γράψουμε αναλυτικά σε επόμενο τεύχος) καθηγητής τώρα στο MIT, απέδειξε μαζί με δύο καθηγητές του τον κύριο Παπαδημητρίου Χρήστο και τον κύριο Paul Goldberg, από το πανεπιστήμιο του Liverpool, ότι η ισορροπία του Nash, στα σύνθετα συστήματα, είναι υπολογιστικά αδύνατο να βρεθεί, παρά μόνο προσεγγιστικά.