1558 - Ο πυρήνας ως κοινή τομή της θεωρίας παιγνίων και της θεωρίας γραφημάτων
Ν. Λυγερός
Τα παίγνια που μπορεί να κωδικοποιηθούν πάνω σε γραφήματα, επιτρέπουν μια αποτελεσματική ανάλυση μέσω της έννοιας του πυρήνα. Αυτή καθορίζεται ως εξής. Ο πυρήνας Κ ενός γραφήματος G = ( V , E ) είναι ένα υποσύνολο κορυφών K V που έχει τις ιδιότητες:
– Οι κορυφές του Κ είναι ανεξάρτητες.
– Αν v G και v K , τότε υπάρχει τουλάχιστον μια κορυφή κ Κ με ( v , K ) E .
Η δύναμη του πυρήνα προέρχεται από την ύπαρξη μιας στρατηγικής που μπορεί να ακολουθήσει ο ορθολογικός παίκτης. Στην ουσία, ο ορισμός του πυρήνα εξασφαλίζει στον παίκτη να μη χάσει το παίγνιο. Διότι αν με την κίνησή του μπορεί να μεταφέρει όλο το παίγνιο σε μια κορυφή του πυρήνα λόγω της πρώτης ιδιότητας του πυρήνα, ο δεύτερος παίκτης θα παίξει εκτός πυρήνα. Επομένως, μέσω της δεύτερης ιδιότητας του πυρήνα, ο πρώτος παίκτης θα επαναφέρει το παίγνιο στην κορυφή του πυρήνα. Συνεπώς, έχει πάντα την επιλογή. Ενώ ο δεύτερος παίκτης θα πέσει, σε κάποια φάση του παιγνίου, σε μία αναγκαστική κορυφή. Επιπλέον, αν το γράφημα δεν εμπεριέχει κύκλους ή διαδρομές απείρου μήκους, τότε ο παίκτης που οδηγεί το παίγνιο σε κορυφή του πυρήνα, έχει εξασφαλισμένη τη νίκη.
Η δυσκολία της έννοιας εξηγείται από την έλλειψη συνεκτικότητας του πυρήνα. Η δομή του πυρήνα δεν είναι άμεση σε τοπικό επίπεδο διότι ο πυρήνας είναι μια ολική έννοια. Όλο το παίγνιο δεν είναι παρά μια κωδικοποίηση με κύριο στοιχείο τον πυρήνα και τη στρατηγική αντίληψη. Ενώ ο πυρήνας υπάρχει μέσα στο γράφημα και στο παίγνιο, μόνο η στρατηγική μπορεί να τον ανοίξει. Το όργανο χρειάζεται νόημα για να ενεργοποιηθεί.