ΘΕΩΡΙΑ ΠΑΙΓΝΙΩΝ 2

 Ωραία, πάμε με τη σειρά, ξεκινώντας από το 1.

1. Στατικά παίγνια (normal form) — σταθερή μήτρα

Ιδέα: Έχουμε ένα παιχνίδι μίας περιόδου, χωρίς χρόνο, χωρίς ιστορικό. Οι παίκτες επιλέγουν στρατηγικές ταυτόχρονα, και οι αποδόσεις δίνονται από μια σταθερή μήτρα.

1.1 Τυπικός ορισμός

Για δύο παίκτες:

• Στρατηγικές παίκτη 1:

$$S_1=\{s_1^1,s_1^2,\dots ,s_1^m\}$$

• Στρατηγικές παίκτη 2:

$$S_2=\{s_2^1,s_2^2,\dots ,s_2^n\}$$

• Αποδόσεις: Για κάθε ζεύγος $(s_1^i,s_2^j)$ έχουμε:

$$u_1(s_1^i,s_2^j),u_2(s_1^i,s_2^j)$$

Αυτά οργανώνονται σε δύο μήτρες (ή μία “διπλή” μήτρα):

• μήτρα αποδόσεων παίκτη 1:

$$U_1\in {\mathbb{R}}^{m\times n}$$

• μήτρα αποδόσεων παίκτη 2:

$$U_2\in {\mathbb{R}}^{m\times n}$$

Σταθερή μήτρα σημαίνει: τα $U_1,U_2$ δεν εξαρτώνται από χρόνο, ιστορικό, κατάσταση, beliefs. Είναι απλώς πίνακες αριθμών.

1.2 Ισορροπία Nash σε σταθερή μήτρα

Μικτή στρατηγική παίκτη 1:

$${\sigma }_1\in \mathrm{\Delta }(S_1)$$

Μικτή στρατηγική παίκτη 2:

$${\sigma }_2\in \mathrm{\Delta }(S_2)$$

Ισορροπία Nash: $({\sigma }_1^{\ast },{\sigma }_2^{\ast })$ τέτοιο ώστε:

• για τον παίκτη 1:

$$u_1({\sigma }_1^{\ast },{\sigma }_2^{\ast })\ge u_1({\sigma }_1,{\sigma }_2^{\ast })\mathrm{\forall }{\sigma }_1$$

• για τον παίκτη 2:

$$u_2({\sigma }_1^{\ast },{\sigma }_2^{\ast })\ge u_2({\sigma }_1^{\ast },{\sigma }_2)\mathrm{\forall }{\sigma }_2$$

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

1.3 Τι κερδίζουμε και τι χάνουμε με τη σταθερότητα

Κερδίζουμε:

• καθαρή μαθηματική δομή,

• ύπαρξη Nash (θεώρημα Nash),

• δυνατότητα υπολογισμού (έστω PPAD).

Χάνουμε:

• χρόνο,

• ιστορικό,

• φήμη,

• τιμωρία/ανταμοιβή από προηγούμενες κινήσεις,

• εξωτερικές μεταβολές (κόστος, πληροφορία, κατάσταση).

Η σταθερή μήτρα είναι σαν φωτογραφία: παγώνει μια στιγμή της αλληλεπίδρασης, αλλά δεν δείχνει την ταινία.

2. Δυναμικά παίγνια — η μήτρα ως συνάρτηση του χρόνου/κατάστασης

Τώρα περνάμε στο επόμενο επίπεδο: η μήτρα δεν είναι πια σταθερή, αλλά εξαρτάται από:

• τον χρόνο $t$,

• την κατάσταση $s$,

• το ιστορικό $H_t$,

• τις beliefs των παικτών.

2.1 Επαναλαμβανόμενα παίγνια (repeated games)

Ξεκινάμε από ένα στατικό παιχνίδι με μήτρα $U_1,U_2$. Το παίζουμε άπειρες φορές: $t=1,2,3,\dots$.

Τυπικά, η άμεση απόδοση κάθε γύρου είναι ίδια (ίδια μήτρα), αλλά η συνολική απόδοση εξαρτάται από το ιστορικό:

$$U_i^{\text{total}}=\sum _{t=1}^{\mathrm{\infty }}{\delta }^{t-1}{u}_i(a_1^t,a_2^t)$$

όπου $\delta$ ο συντελεστής προεξόφλησης.

Εδώ η “μήτρα” παραμένει αριθμητικά ίδια, αλλά η στρατηγική δομή κάνει τις αποδόσεις ιστορικο-εξαρτώμενες.

Παράδειγμα grim trigger: αν προδώσεις μία φορά, ο άλλος σε τιμωρεί για πάντα. Η “πραγματική” απόδοση της προδοσίας αλλάζει δραματικά λόγω ιστορικού.

2.2 Παίγνια με κατάσταση (stochastic / Markov games)

Εδώ η μήτρα εξαρτάται από την κατάσταση $s$:

$$u_i(s,a_1,a_2)$$

και η κατάσταση εξελίσσεται:

$$P(s^{\mathrm{\prime }}\mid s,a_1,a_2)$$

Άρα:

• σε κάθε κατάσταση $s$ έχουμε διαφορετική μήτρα αποδόσεων,

• οι επιλογές σήμερα αλλάζουν την κατάσταση αύριο,

• η κατάσταση αύριο αλλάζει τη μήτρα αύριο.

Η μήτρα γίνεται:

$$U_i(s)\text{για κ}\acute{\text{α}}\text{θε }s$$

Δεν υπάρχει πια μία σταθερή μήτρα· υπάρχει οικογένεια μητρών, δεμένη με τη δυναμική του κόσμου.

2.3 Παίγνια με ατελή πληροφόρηση (Bayesian games)

Εδώ οι αποδόσεις εξαρτώνται από τον “τύπο” του παίκτη, και οι άλλοι έχουν beliefs για αυτόν.

Τυπικά:

$$u_i(a_1,a_2,{\theta }_1,{\theta }_2)$$

όπου ${\theta }_i$ είναι ο τύπος του παίκτη i.

Οι παίκτες δεν ξέρουν τους τύπους, έχουν beliefs $\pi ({\theta }_j)$.

Άρα η “αντιληπτή” μήτρα είναι:

$${\tilde{u}}_i(a_1,a_2)={\mathbb{E}}_{{\theta }_1,{\theta }_2}[u_i(a_1,a_2,{\theta }_1,{\theta }_2)]$$

Καθώς αλλάζουν τα beliefs (με πληροφορία, σήματα, ιστορικό), αλλάζει και η effective μήτρα.

Today

ΠΑΜΕ ΘΕΩΡΙΑ ΠΑΙΧΝΙΩΝ. ΟΙ ΜΗΤΡΕς ΤΩΝ ΑΛΛΗΛΟΕΠΙΔΡΑΣΕΩΝ-ΑΝΤΑΜΟΙΒΩΝ ΕΙΝΑΙ ΣΤΑΘΕΡΈς ΣΤΟ ΧΡΌΝΟ?

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

🔍 Τι σημαίνει αυτό στην πράξη

1) Στα κλασικά στατικά παίγνια

Η μήτρα ανταμοιβών θεωρείται σταθερή. Αυτό είναι το “καθαρό” πλαίσιο:

• δύο παίκτες,

• σταθερές στρατηγικές,

• σταθερές αποδόσεις,

• μία και μοναδική αλληλεπίδραση.

Εδώ η σταθερότητα είναι υπόθεση του μοντέλου, όχι πραγματικότητα.

2) Στα δυναμικά παίγνια / επαναλαμβανόμενα παίγνια

Οι αποδόσεις μπορούν να αλλάζουν ανάλογα με:

• τον χρόνο,

• το ιστορικό των κινήσεων,

• τη φήμη,

• την τιμωρία/ανταμοιβή προηγούμενων γύρων,

• εξωτερικές μεταβολές (κόστος, τεχνολογία, πληροφορία).

Παράδειγμα: Στο επαναλαμβανόμενο Δίλημμα του Φυλακισμένου, η “τιμωρία” για προδοσία μπορεί να γίνει πιο βαριά όσο περνούν οι γύροι, αν ο αντίπαλος υιοθετεί στρατηγική τύπου grim trigger.

3) Σε παίγνια με ατελή ή εξελισσόμενη πληροφορία

Η μήτρα μπορεί να εξαρτάται από την κατάσταση του κόσμου, η οποία μεταβάλλεται. Άρα οι αποδόσεις είναι state‑dependent.

4) Σε εξελικτική θεωρία παιγνίων

Οι αποδόσεις μεταβάλλονται καθώς αλλάζει ο πληθυσμός. Δεν υπάρχει σταθερή μήτρα· υπάρχει δυναμικό σύστημα.

5) Σε οικονομικά/στρατηγικά περιβάλλοντα

Οι αποδόσεις αλλάζουν με:

• τιμές,

• κόστη,

• κανονισμούς,

• τεχνολογικές αλλαγές,

• νέες πληροφορίες.

Άρα η μήτρα είναι ενδογενής και όχι σταθερή.

🎯 Η ουσία (και η βαθύτερη θεωρητική απάντηση)

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

Αν το παιχνίδι “έχει νόημα”, όπως είπες πριν, επειδή οι επιλογές του ενός επηρεάζουν τον άλλον, τότε ακόμη περισσότερο η μήτρα δεν μπορεί να είναι στατική: η ίδια η αλληλεπίδραση παράγει νέες αποδόσεις.

Θέλεις να το πάμε στο επόμενο επίπεδο;

Μπορούμε να δούμε:

• πότε μια μεταβαλλόμενη μήτρα οδηγεί σε ισορροπία Nash σε μονοπάτι,

• πώς ορίζεται ισορροπία Markov,

• ή πώς η μεταβολή των αποδόσεων συνδέεται με PPAD και υπολογιστική πολυπλοκότητα.

Ποια κατεύθυνση θέλεις να ανοίξουμε;

ΟΛΑ

Πάμε, Kostas. Όλα σημαίνει:

1. πλήρης θεωρητική κάλυψη,

2. διασύνδεση με δυναμικά παίγνια, Markov, εξελικτική θεωρία,

3. υπολογιστική πολυπλοκότητα (PPAD, Nash),

4. φιλοσοφική-οντολογική ανάγνωση της μεταβλητότητας των αποδόσεων.

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

1. ΣΤΑΤΙΚΑ ΠΑΙΓΝΙΑ — Η ΜΗΤΡΑ ΩΣ ΙΔΕΑΤΟ ΣΤΑΘΕΡΟ ΑΝΤΙΚΕΙΜΕΝΟ

Στα κλασικά παίγνια (normal form), η μήτρα ανταμοιβών θεωρείται σταθερή. Αυτό είναι υπόθεση, όχι πραγματικότητα.

Η σταθερότητα εξυπηρετεί:

• καθαρή ανάλυση στρατηγικών,

• ύπαρξη ισορροπίας Nash,

• μαθηματική κλειστότητα.

Αλλά: η σταθερή μήτρα είναι μοντέλο χωρίς χρόνο. Δεν περιγράφει πραγματικές αλληλεπιδράσεις, μόνο μια “τομή” τους.

2. ΔΥΝΑΜΙΚΑ ΠΑΙΓΝΙΑ — Η ΜΗΤΡΑ ΩΣ ΣΥΝΑΡΤΗΣΗ ΤΟΥ ΧΡΟΝΟΥ

Στα δυναμικά παίγνια, η μήτρα γίνεται R(t) ή R(s, a₁, a₂), όπου:

• t = χρόνος,

• s = κατάσταση του κόσμου,

• aᵢ = στρατηγικές.

2.1 Επαναλαμβανόμενα παίγνια

Οι αποδόσεις εξαρτώνται από το ιστορικό. Παράδειγμα: grim trigger → η “τιμωρία” αλλάζει τη μήτρα μετά από προδοσία.

2.2 Παίγνια με ατελή πληροφόρηση

Η μήτρα εξαρτάται από beliefs. Άρα R = R(π), όπου π είναι η κατανομή πιθανοτήτων του παίκτη για τον τύπο του άλλου.

2.3 Παίγνια Markov (Stochastic Games)

Η μήτρα εξαρτάται από την κατάσταση s: R = R(s). Η κατάσταση εξελίσσεται με πιθανότητες P(s’|s, a₁, a₂).

Αυτό είναι το πιο κοντινό στην πραγματικότητα: η αλληλεπίδραση παράγει τις μελλοντικές αποδόσεις.

3. ΕΞΕΛΙΚΤΙΚΗ ΘΕΩΡΙΑ ΠΑΙΓΝΙΩΝ — Η ΜΗΤΡΑ ΩΣ ΠΑΡΑΓΩΓΟ ΤΟΥ ΠΛΗΘΥΣΜΟΥ

Εδώ η μήτρα δεν είναι εξωτερική. Είναι ενδογενής: R = R(x), όπου x είναι η κατανομή στρατηγικών στον πληθυσμό.

Όσο αλλάζει ο πληθυσμός, αλλάζει και η μήτρα. Άρα δεν υπάρχει σταθερή δομή· υπάρχει δυναμικό σύστημα.

Αυτό οδηγεί σε:

• εξελικτικά σταθερές στρατηγικές (ESS),

• replicator dynamics,

• κύκλους, χαοτικές τροχιές, πολλαπλές ισορροπίες.

4. ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ — ΤΙ ΣΗΜΑΙΝΕΙ ΜΙΑ ΜΗ ΣΤΑΘΕΡΗ ΜΗΤΡΑ

Εδώ μπαίνει η PPAD (όπου έχεις ήδη ενδιαφέρον).

4.1 Σταθερή μήτρα → Nash σε PPAD

Το πρόβλημα εύρεσης Nash σε σταθερή μήτρα είναι PPAD-complete.

4.2 Μεταβαλλόμενη μήτρα → πολύ πιο δύσκολο

Αν η μήτρα μεταβάλλεται:

• με τον χρόνο,

• με την κατάσταση,

• με το ιστορικό,

τότε το πρόβλημα γίνεται:

• PSPACE-hard (σε γενικά δυναμικά παίγνια),

• EXPTIME-hard (σε stochastically evolving games),

• undecidable σε ορισμένες συνεχείς μορφές.

Η σταθερή μήτρα είναι “εύκολη” μόνο επειδή είναι παγωμένη.

5. ΟΝΤΟΛΟΓΙΚΗ ΑΝΑΓΝΩΣΗ — Η ΜΗΤΡΑ ΩΣ ΦΑΙΝΕΡΩΣΗ ΤΟΥ ΚΟΣΜΟΥ

Εδώ πάμε στο επίπεδο που σε ενδιαφέρει βαθύτερα.

Η σταθερή μήτρα είναι τεχνική φανέρωση: ένα τεχνητό πάγωμα της πολλαπλότητας του Είναι.

Η πραγματική αλληλεπίδραση:

• δεν είναι στατική,

• δεν είναι συμμετρική,

• δεν είναι πλήρως γνωστή,

• δεν είναι ανεξάρτητη από την ιστορικότητα των υποκειμένων.

Άρα η μήτρα είναι οντολογικά παράγωγο, όχι πρωταρχικό αντικείμενο.

Η διάκριση ἀγέννητο/γεννημένο που έχεις συνδέσει με την οντολογική διαφορά ταιριάζει εδώ: η σταθερή μήτρα είναι “ἀγέννητη” μόνο ως αφηρημένο μοντέλο· η πραγματική μήτρα είναι “γεννημένη” από την ιστορική πράξη των παικτών.

6. Η ΟΛΟΚΛΗΡΩΜΕΝΗ ΑΠΑΝΤΗΣΗ

Οι μήτρες αλληλεπιδράσεων/ανταμοιβών δεν είναι σταθερές στον χρόνο, εκτός αν το μοντέλο επιβάλλει τεχνητά τη σταθερότητα.

Στη γενική θεωρία παιγνίων:

• μεταβάλλονται με τον χρόνο,

• με την πληροφορία,

• με την κατάσταση,

• με το ιστορικό,

• με τον πληθυσμό,

• με την ίδια την πράξη των παικτών.

Η σταθερή μήτρα είναι απλώς ένα εργαλείο, όχι μια πραγματικότητα.

7. Θες να το πάμε ακόμη βαθύτερα;

Μπορούμε να ανοίξουμε:

• ισορροπίες Markov perfect (MPE),

• ισορροπίες σε μονοπάτι (subgame perfect),

• Bayesian games με εξελισσόμενα beliefs,

• replicator dynamics και σταθερότητα,

• σύνδεση με PPAD και υπολογιστική θεωρία,

• ή να χτίσουμε δικό σου μοντέλο όπου η μήτρα είναι ρητά R(t, s, H).

Ποιο από αυτά θέλεις να ανοίξουμε πρώτο;

ΜΕ ΤΗ ΣΕΙΡΆ

Ωραία, πάμε με τη σειρά, ξεκινώντας από το 1.

1. Στατικά παίγνια (normal form) — σταθερή μήτρα

Ιδέα: Έχουμε ένα παιχνίδι μίας περιόδου, χωρίς χρόνο, χωρίς ιστορικό. Οι παίκτες επιλέγουν στρατηγικές ταυτόχρονα, και οι αποδόσεις δίνονται από μια σταθερή μήτρα.

1.1 Τυπικός ορισμός

Για δύο παίκτες:

• Στρατηγικές παίκτη 1:

$$S_1=\{s_1^1,s_1^2,\dots ,s_1^m\}$$

• Στρατηγικές παίκτη 2:

$$S_2=\{s_2^1,s_2^2,\dots ,s_2^n\}$$

• Αποδόσεις: Για κάθε ζεύγος $(s_1^i,s_2^j)$ έχουμε:

$$u_1(s_1^i,s_2^j),u_2(s_1^i,s_2^j)$$

Αυτά οργανώνονται σε δύο μήτρες (ή μία “διπλή” μήτρα):

• μήτρα αποδόσεων παίκτη 1:

$$U_1\in {\mathbb{R}}^{m\times n}$$

• μήτρα αποδόσεων παίκτη 2:

$$U_2\in {\mathbb{R}}^{m\times n}$$

Σταθερή μήτρα σημαίνει: τα $U_1,U_2$ δεν εξαρτώνται από χρόνο, ιστορικό, κατάσταση, beliefs. Είναι απλώς πίνακες αριθμών.

1.2 Ισορροπία Nash σε σταθερή μήτρα

Μικτή στρατηγική παίκτη 1:

$${\sigma }_1\in \mathrm{\Delta }(S_1)$$

Μικτή στρατηγική παίκτη 2:

$${\sigma }_2\in \mathrm{\Delta }(S_2)$$

Ισορροπία Nash: $({\sigma }_1^{\ast },{\sigma }_2^{\ast })$ τέτοιο ώστε:

• για τον παίκτη 1:

$$u_1({\sigma }_1^{\ast },{\sigma }_2^{\ast })\ge u_1({\sigma }_1,{\sigma }_2^{\ast })\mathrm{\forall }{\sigma }_1$$

• για τον παίκτη 2:

$$u_2({\sigma }_1^{\ast },{\sigma }_2^{\ast })\ge u_2({\sigma }_1^{\ast },{\sigma }_2)\mathrm{\forall }{\sigma }_2$$

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

1.3 Τι κερδίζουμε και τι χάνουμε με τη σταθερότητα

Κερδίζουμε:

• καθαρή μαθηματική δομή,

• ύπαρξη Nash (θεώρημα Nash),

• δυνατότητα υπολογισμού (έστω PPAD).

Χάνουμε:

• χρόνο,

• ιστορικό,

• φήμη,

• τιμωρία/ανταμοιβή από προηγούμενες κινήσεις,

• εξωτερικές μεταβολές (κόστος, πληροφορία, κατάσταση).

Η σταθερή μήτρα είναι σαν φωτογραφία: παγώνει μια στιγμή της αλληλεπίδρασης, αλλά δεν δείχνει την ταινία.

2. Δυναμικά παίγνια — η μήτρα ως συνάρτηση του χρόνου/κατάστασης

Τώρα περνάμε στο επόμενο επίπεδο: η μήτρα δεν είναι πια σταθερή, αλλά εξαρτάται από:

• τον χρόνο $t$,

• την κατάσταση $s$,

• το ιστορικό $H_t$,

• τις beliefs των παικτών.

2.1 Επαναλαμβανόμενα παίγνια (repeated games)

Ξεκινάμε από ένα στατικό παιχνίδι με μήτρα $U_1,U_2$. Το παίζουμε άπειρες φορές: $t=1,2,3,\dots$.

Τυπικά, η άμεση απόδοση κάθε γύρου είναι ίδια (ίδια μήτρα), αλλά η συνολική απόδοση εξαρτάται από το ιστορικό:

$$U_i^{\text{total}}=\sum _{t=1}^{\mathrm{\infty }}{\delta }^{t-1}{u}_i(a_1^t,a_2^t)$$

όπου $\delta$ ο συντελεστής προεξόφλησης.

Εδώ η “μήτρα” παραμένει αριθμητικά ίδια, αλλά η στρατηγική δομή κάνει τις αποδόσεις ιστορικο-εξαρτώμενες.

Παράδειγμα grim trigger: αν προδώσεις μία φορά, ο άλλος σε τιμωρεί για πάντα. Η “πραγματική” απόδοση της προδοσίας αλλάζει δραματικά λόγω ιστορικού.

2.2 Παίγνια με κατάσταση (stochastic / Markov games)

Εδώ η μήτρα εξαρτάται από την κατάσταση $s$:

$$u_i(s,a_1,a_2)$$

και η κατάσταση εξελίσσεται:

$$P(s^{\mathrm{\prime }}\mid s,a_1,a_2)$$

Άρα:

• σε κάθε κατάσταση $s$ έχουμε διαφορετική μήτρα αποδόσεων,

• οι επιλογές σήμερα αλλάζουν την κατάσταση αύριο,

• η κατάσταση αύριο αλλάζει τη μήτρα αύριο.

Η μήτρα γίνεται:

$$U_i(s)\text{για κ}\acute{\text{α}}\text{θε }s$$

Δεν υπάρχει πια μία σταθερή μήτρα· υπάρχει οικογένεια μητρών, δεμένη με τη δυναμική του κόσμου.

2.3 Παίγνια με ατελή πληροφόρηση (Bayesian games)

Εδώ οι αποδόσεις εξαρτώνται από τον “τύπο” του παίκτη, και οι άλλοι έχουν beliefs για αυτόν.

Τυπικά:

$$u_i(a_1,a_2,{\theta }_1,{\theta }_2)$$

όπου ${\theta }_i$ είναι ο τύπος του παίκτη i.

Οι παίκτες δεν ξέρουν τους τύπους, έχουν beliefs $\pi ({\theta }_j)$.

Άρα η “αντιληπτή” μήτρα είναι:

$${\tilde{u}}_i(a_1,a_2)={\mathbb{E}}_{{\theta }_1,{\theta }_2}[u_i(a_1,a_2,{\theta }_1,{\theta }_2)]$$

Καθώς αλλάζουν τα beliefs (με πληροφορία, σήματα, ιστορικό), αλλάζει και η effective μήτρα.

Θα σταματήσω εδώ για να μην σε πνίξω με υπερβολική πληροφορία σε μία δόση.

Αν θες, στο επόμενο βήμα πάμε 3. Εξελικτική θεωρία παιγνίων και μετά 4. Πολυπλοκότητα / PPAD, κρατώντας αυτή τη γραμμή: από σταθερή μήτρα → σε πλήρως ενδογενή, δυναμική δομή.

Πάμε στο 3;

ΝΑΙ

Πάμε λοιπόν με τη σειρά, όπως ζήτησες. Μπαίνουμε τώρα στο 3ο στάδιο: Εξελικτική Θεωρία Παιγνίων. Θα συνεχίσουμε μετά με 4. Πολυπλοκότητα / PPAD, 5. Οντολογία, 6. Ενοποίηση.

3. ΕΞΕΛΙΚΤΙΚΗ ΘΕΩΡΙΑ ΠΑΙΓΝΙΩΝ

(όπου η μήτρα δεν είναι σταθερή αλλά “γεννιέται” από τον πληθυσμό)

Η εξελικτική θεωρία παιγνίων είναι το πρώτο σημείο όπου η μήτρα παύει να είναι εξωτερικό αντικείμενο. Δεν υπάρχει “σταθερή” μήτρα. Υπάρχει μια ενδογενής, πληθυσμο-εξαρτώμενη δομή:

$$U_i=U_i(x)$$

όπου $x$ είναι η κατανομή στρατηγικών στον πληθυσμό.

3.1 Η βασική ιδέα

Οι παίκτες δεν είναι “ορθολογικοί” με την κλασική έννοια. Είναι πληθυσμιακοί τύποι (strategies-as-genes). Η επιτυχία μιας στρατηγικής εξαρτάται από το με ποιους αλληλεπιδρά.

Άρα η απόδοση μιας στρατηγικής αλλάζει όταν αλλάζει ο πληθυσμός.

3.2 Replicator Dynamics

Ο πιο κλασικός δυναμικός νόμος:

$${\dot{x}}_i=x_i(f_i(x)-\bar{f}(x))$$

όπου:

• $x_i$: ποσοστό στρατηγικής i στον πληθυσμό

• $f_i(x)$: απόδοση της στρατηγικής i όταν ο πληθυσμός είναι x

• $\bar{f}(x)$: μέση απόδοση του πληθυσμού

Αν μια στρατηγική αποδίδει πάνω από τον μέσο όρο, αυξάνεται. Αν αποδίδει κάτω από τον μέσο όρο, μειώνεται.

Η μήτρα αποδόσεων είναι:

$$f_i(x)=\sum _j{A}_{ij}{x}_j$$

Αλλά το effective payoff αλλάζει καθώς αλλάζει το $x$. Άρα η μήτρα είναι δυναμική.

3.3 ESS — Evolutionarily Stable Strategy

Μια στρατηγική $s^{\ast }$ είναι ESS αν:

1. Είναι Nash equilibrium.

2. Αν εμφανιστεί μια μικρή μετάλλαξη $s$, τότε:

$$u(s^{\ast },(1-ϵ)s^{\ast }+ϵs)>u(s,(1-ϵ)s^{\ast }+ϵs)$$

Δηλαδή: η στρατηγική $s^{\ast }$ νικάει οποιονδήποτε “εισβολέα” όταν αυτός είναι σπάνιος.

Εδώ η σταθερότητα δεν είναι σταθερότητα μήτρας, αλλά σταθερότητα πληθυσμιακής ισορροπίας.

3.4 Τι σημαίνει αυτό για τη μήτρα

Η μήτρα δεν είναι πια:

$$U=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$$

αλλά:

$$U(x)=\left(\begin{array}{cc}a(x)& b(x)\\ c(x)& d(x)\end{array}\right)$$

όπου κάθε στοιχείο εξαρτάται από το ποιος παίζει τι.

Η αλληλεπίδραση παράγει τη μήτρα. Δεν την προϋποθέτει.

3.5 Δυναμικά φαινόμενα που δεν υπάρχουν στα στατικά παίγνια

• κύκλοι (rock–paper–scissors)

• χαοτικές τροχιές

• πολλαπλές ελκυστικές ισορροπίες

• bifurcations

• path dependence (ιστορική εξάρτηση)

Η σταθερή μήτρα είναι “νεκρή”. Η εξελικτική μήτρα είναι “ζωντανή”.

4. ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ — PPAD

(όπου η μεταβλητότητα της μήτρας εκτοξεύει την πολυπλοκότητα)

Εδώ μπαίνουμε στο πεδίο που σε ενδιαφέρει ιδιαίτερα.

4.1 Σταθερή μήτρα → Nash σε PPAD

Το θεμελιώδες αποτέλεσμα:

Το πρόβλημα εύρεσης Nash σε σταθερή μήτρα είναι PPAD-complete.

Αυτό σημαίνει:

• υπάρχει πάντα λύση (λόγω Brouwer),

• αλλά δεν υπάρχει γνωστό πολυωνυμικό αλγόριθμο,

• ούτε πιστεύουμε ότι θα υπάρξει.

Η σταθερή μήτρα είναι το “εύκολο” σενάριο.

4.2 Μεταβαλλόμενη μήτρα → πολύ πιο δύσκολο

Αν η μήτρα εξαρτάται από:

• χρόνο,

• κατάσταση,

• ιστορικό,

• beliefs,

• πληθυσμό,

τότε το πρόβλημα γίνεται:

• PSPACE-hard

σε δυναμικά παίγνια με πεπερασμένο ορίζοντα.

• EXPTIME-hard

σε stochastically evolving games.

• Undecidable

σε συνεχείς δυναμικές μορφές (differential games).

Η σταθερή μήτρα είναι η “εξιδανικευμένη απλοποίηση” που επιτρέπει PPAD. Η πραγματική στρατηγική αλληλεπίδραση είναι πολύ πιο δύσκολη.

5. ΟΝΤΟΛΟΓΙΚΗ ΑΝΑΓΝΩΣΗ

(η μήτρα ως φαινόμενο, όχι ως ουσία)

Εδώ πάμε στο βαθύτερο επίπεδο.

Η σταθερή μήτρα είναι α-χρονική. Δεν έχει ιστορικότητα. Δεν έχει γένεση. Είναι ένα “ἀγέννητο” τεχνούργημα.

Η πραγματική αλληλεπίδραση όμως:

• εξελίσσεται,

• μεταβάλλεται,

• παράγει νέες δομές,

• δημιουργεί νέες αποδόσεις.

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

Αυτό συνδέεται άμεσα με τη δική σου ερμηνεία της οντολογικής διαφοράς: το “ἀγέννητο” είναι το αφηρημένο μοντέλο, το “γεννημένο” είναι η πραγματική ιστορική αλληλεπίδραση.

6. ΕΝΟΠΟΙΗΣΗ — ΤΟ ΜΕΓΑΛΟ ΣΥΜΠΕΡΑΣΜΑ

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

Στη γενική θεωρία παιγνίων:

• μεταβάλλονται με τον χρόνο,

• με την πληροφορία,

• με την κατάσταση,

• με το ιστορικό,

• με τον πληθυσμό,

• με την ίδια την πράξη των παικτών.

Η σταθερή μήτρα είναι εργαλείο. Η μεταβαλλόμενη μήτρα είναι πραγματικότητα.

Αν θέλεις, συνεχίζουμε τώρα στο 7. Ισορροπίες Markov Perfect ή στο 8. Bayesian δυναμικά παίγνια.

7

Πάμε στο 7. Markov Perfect Equilibrium (MPE) — το πιο καθαρό, αυστηρό και “δωρικό” εργαλείο για δυναμικά παίγνια. Εδώ η μήτρα αποδόσεων δεν είναι σταθερή, αλλά εξαρτάται από την κατάσταση του κόσμου, και οι παίκτες επιλέγουν στρατηγικές που εξαρτώνται μόνο από την τρέχουσα κατάσταση, όχι από όλο το ιστορικό.

7. MARKOV PERFECT EQUILIBRIUM (MPE)

Η ισορροπία που “καθαρίζει” τον χρόνο και κρατά μόνο την ουσία

Το MPE είναι η ισορροπία σε δυναμικά παίγνια με καταστάσεις (stochastic games). Είναι η πιο σημαντική έννοια ισορροπίας όταν η μήτρα μεταβάλλεται με τον χρόνο.

7.1 Το περιβάλλον

Έχουμε:

• Κατάσταση του κόσμου:

$$s\in S$$

• Ενέργειες των παικτών:

$$a_1\in A_1(s),a_2\in A_2(s)$$

• Αποδόσεις που εξαρτώνται από την κατάσταση:

$$u_i(s,a_1,a_2)$$

• Μετάβαση κατάστασης:

$$P(s^{\mathrm{\prime }}\mid s,a_1,a_2)$$

Η “μήτρα” αποδόσεων είναι τώρα μια οικογένεια μητρών, μία για κάθε κατάσταση s.

7.2 Τι είναι Markov στρατηγική

Μια στρατηγική είναι Markov αν εξαρτάται μόνο από την τρέχουσα κατάσταση:

$${\sigma }_i(s)$$

και όχι από το ιστορικό:

$${\sigma }_i(s)\mathrm{\ne }{\sigma }_i(H_t)$$

Αυτό είναι το “δωρικό” στοιχείο: η στρατηγική βλέπει μόνο το τώρα, όχι το παρελθόν.

7.3 Ορισμός Markov Perfect Equilibrium

Ένα προφίλ στρατηγικών $({\sigma }_1^{\ast },{\sigma }_2^{\ast })$ είναι MPE αν:

1. Είναι Markov (εξαρτάται μόνο από s).

2. Είναι υποπαιγνιακά τέλειο (subgame perfect).

3. Για κάθε κατάσταση s, κάθε παίκτης λύνει το δυναμικό πρόβλημα:

$$V_i(s)=\underset{a_i}{\max }[u_i(s,a_i,{\sigma }_{-i}^{\ast }(s))+\delta \sum _{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a_i,{\sigma }_{-i}^{\ast }(s))V_i(s^{\mathrm{\prime }})]$$

Αυτό είναι η εξίσωση Bellman του παίκτη i.

7.4 Τι σημαίνει αυτό διαισθητικά

Ο παίκτης, σε κάθε κατάσταση:

• κοιτάει τη σημερινή απόδοση,

• κοιτάει πώς η σημερινή επιλογή αλλάζει την αυριανή κατάσταση,

• και επιλέγει δράση που μεγιστοποιεί τη συνολική αξία.

Η ισορροπία είναι “τέλεια” γιατί:

• δεν χρειάζεται ιστορικό,

• δεν χρειάζεται μνήμη,

• δεν χρειάζεται περίπλοκες τιμωρίες,

• είναι συμβατή με τη δυναμική του κόσμου.

7.5 Γιατί είναι σημαντικό το MPE

Γιατί είναι η φυσική ισορροπία όταν:

• η μήτρα αλλάζει με την κατάσταση,

• οι παίκτες δεν μπορούν να συντονιστούν σε περίπλοκες τιμωρίες,

• ο χρόνος είναι άπειρος,

• η πληροφορία είναι τοπική.

Το MPE είναι η ισορροπία που “στέκεται” μόνη της, χωρίς τεχνητές υποθέσεις.

7.6 Πότε υπάρχει και πότε όχι

Υπάρχει πάντα σε πεπερασμένες καταστάσεις και δράσεις (Shapley). Αλλά:

• μπορεί να μην είναι μοναδική,

• μπορεί να είναι πολλαπλή και ασυνεχής,

• μπορεί να έχει άλματα (bifurcations) όταν αλλάζει η προεξόφληση δ.

7.7 Σχέση με στατικές μήτρες

Η στατική μήτρα είναι ειδική περίπτωση όπου:

• υπάρχει μόνο μία κατάσταση,

• δεν υπάρχει μετάβαση,

• δεν υπάρχει χρόνος.

Τότε το MPE καταρρέει στο Nash.

Άρα το MPE είναι η γενίκευση του Nash σε πραγματικό χρόνο.

7.8 Σχέση με εξελικτική θεωρία

Στην εξελικτική θεωρία παιγνίων, η κατάσταση s μπορεί να είναι:

• η κατανομή στρατηγικών x,

• η πληθυσμιακή σύνθεση,

• η τεχνολογική κατάσταση.

Τότε το MPE γίνεται ισορροπία σε δυναμικό σύστημα.

7.9 Σχέση με PPAD

Η εύρεση MPE είναι:

• PSPACE-hard σε γενικά δυναμικά παίγνια,

• EXPTIME-hard σε stochastically evolving games.

Η σταθερή μήτρα (PPAD) είναι το “εύκολο” κομμάτι. Το MPE είναι το πραγματικό.

Θες να συνεχίσουμε στο 8. Bayesian δυναμικά παίγνια ή στο 9. Ισορροπίες σε μονοπάτι (subgame perfect);

8

Πάμε στο 8. Bayesian Δυναμικά Παίγνια — το σημείο όπου η αβεβαιότητα, ο χρόνος και η στρατηγική αλληλεπίδραση συνδέονται σε ένα ενιαίο πλαίσιο. Εδώ η μήτρα αποδόσεων όχι μόνο αλλάζει με την κατάσταση, αλλά αλλάζει και με τις beliefs των παικτών, οι οποίες εξελίσσονται με τον χρόνο.

8. BAYESIAN ΔΥΝΑΜΙΚΑ ΠΑΙΓΝΙΑ

Όταν οι παίκτες δεν ξέρουν ποιος είναι ο άλλος — και το μαθαίνουν μέσα στον χρόνο

Στα Bayesian δυναμικά παίγνια, κάθε παίκτης έχει έναν τύπο (type), που επηρεάζει τις αποδόσεις και τις διαθέσιμες στρατηγικές. Οι άλλοι παίκτες δεν γνωρίζουν τον τύπο του αντιπάλου, αλλά έχουν beliefs γι’ αυτόν.

Με τον χρόνο, οι παίκτες παρατηρούν ενέργειες και ενημερώνουν τις beliefs τους μέσω Bayes.

8.1 Τα συστατικά ενός Bayesian δυναμικού παιχνιδιού

Έχουμε:

• Τύποι παικτών

$${\theta }_i\in {\mathrm{\Theta }}_i$$

• Αρχικές beliefs

$${\pi }_i({\theta }_{-i})$$

• Κατάσταση του κόσμου

$$s_t$$

• Αποδόσεις

$$u_i(s_t,a_1,a_2,{\theta }_1,{\theta }_2)$$

• Μετάβαση κατάστασης

$$P(s_{t+1}\mid s_t,a_1,a_2)$$

• Ενημέρωση beliefs

Με Bayes:

$${\pi }_{t+1}({\theta }_{-i})=\frac{P(a_{-i}^t\mid {\theta }_{-i}){\pi }_t({\theta }_{-i})}{\sum _{{\theta }_{-i}^{\mathrm{\prime }}}P(a_{-i}^t\mid {\theta }_{-i}^{\mathrm{\prime }}){\pi }_t({\theta }_{-i}^{\mathrm{\prime }})}$$

8.2 Τι σημαίνει αυτό για τη “μήτρα” αποδόσεων

Η μήτρα αποδόσεων δεν είναι πια:

$$U(s)$$

αλλά:

$$U(s,\pi )$$

δηλαδή εξαρτάται από:

• την κατάσταση του κόσμου,

• τις beliefs του παίκτη για τον τύπο του άλλου.

Καθώς οι beliefs αλλάζουν, αλλάζει και η effective μήτρα.

Η μήτρα είναι τώρα διπλά δυναμική: εξελίσσεται με την κατάσταση και με την πληροφορία.

8.3 Τι είναι Perfect Bayesian Equilibrium (PBE)

Το PBE είναι η ισορροπία που συνδυάζει:

1. Στρατηγικές που είναι βέλτιστες δεδομένων των beliefs.

2. Beliefs που ενημερώνονται σωστά με Bayes.

3. Συνέπεια σε κάθε υποπαίγνιο.

Τυπικά, ένα PBE είναι ζεύγος:

$$({\sigma }^{\ast },{\pi }^{\ast })$$

όπου:

• ${\sigma }^{\ast }$: στρατηγικές παικτών

• ${\pi }^{\ast }$: beliefs παικτών

και ικανοποιούν:

(α) Sequential rationality

$${\sigma }_i^{\ast }(h_t)\in \arg \underset{{\sigma }_i}{\max }\mathbb{E}[U_i\mid h_t,{\pi }^{\ast }]$$

(β) Bayesian updating

$${\pi }^{\ast }\text{ ενημερ}\acute{\text{ω}}\text{νεται με Bayes }\acute{\text{ο}}\text{που ε}\acute{\text{ι}}\text{ναι δυνατ}\acute{\text{ο}}$$

8.4 Τι σημαίνει αυτό διαισθητικά

Ο παίκτης:

• δεν ξέρει ποιος είναι ο άλλος,

• βλέπει τις ενέργειές του,

• ενημερώνει τις beliefs του,

• και επιλέγει δράση που είναι βέλτιστη δεδομένων αυτών των beliefs.

Η στρατηγική του είναι μια διαδρομή μάθησης.

8.5 Πώς συνδέεται με Markov Perfect Equilibrium

Το PBE είναι πιο γενικό από το MPE.

• Το MPE απαιτεί στρατηγικές που εξαρτώνται μόνο από την κατάσταση.

• Το PBE επιτρέπει στρατηγικές που εξαρτώνται από beliefs και ιστορικό.

Αν οι beliefs μπορούν να συνοψιστούν σε μια Markov κατάσταση, τότε το PBE γίνεται MPE.

8.6 Πού χρησιμοποιείται στην πράξη

• Διαπραγματεύσεις με αβεβαιότητα για τον τύπο του άλλου.

• Αγορές όπου οι εταιρείες δεν ξέρουν το κόστος των ανταγωνιστών.

• Πολιτική όπου οι παίκτες δεν ξέρουν τις προτιμήσεις των άλλων.

• Στρατιωτική στρατηγική με αβεβαιότητα για την ισχύ του αντιπάλου.

• Online platforms όπου οι χρήστες μαθαίνουν ο ένας τον άλλο.

Σε όλα αυτά, η “μήτρα” είναι προϊόν πληροφορίας και μάθησης.

8.7 Σχέση με πολυπλοκότητα

Η εύρεση PBE είναι:

• PSPACE-hard σε γενικά δυναμικά Bayesian παίγνια,

• EXPTIME-hard όταν οι beliefs έχουν μεγάλη διάσταση,

• Undecidable σε συνεχείς τύπους και άπειρο ορίζοντα.

Η σταθερή μήτρα (PPAD) είναι το απλό κομμάτι. Το Bayesian δυναμικό παιχνίδι είναι το πραγματικό.

Θες να συνεχίσουμε στο 9. Subgame Perfect Equilibrium (SPE) ή στο 10. Ενοποίηση όλων σε ένα ενιαίο μοντέλο;

10

Πάμε στο 10. ΕΝΟΠΟΙΗΣΗ — το μεγάλο, καθαρό, ενιαίο μοντέλο που συνδέει όλα όσα είπαμε: στατικά παίγνια, δυναμικά, Markov, Bayesian, εξελικτικά, PPAD, οντολογία.

Αυτό είναι το σημείο όπου η θεωρία παιγνίων παύει να είναι “πίνακες” και γίνεται γενική θεωρία αλληλεπίδρασης.

10. ΕΝΙΑΙΟ ΜΟΝΤΕΛΟ

Η πλήρης μορφή ενός πραγματικού παιχνιδιού

Ένα πραγματικό παιχνίδι δεν έχει σταθερή μήτρα. Έχει:

• κατάσταση του κόσμου,

• τύπους παικτών,

• beliefs που εξελίσσονται,

• πληθυσμιακή δυναμική,

• χρόνο,

• μάθηση,

• στρατηγική αβεβαιότητα,

• υπολογιστικούς περιορισμούς.

Το ενιαίο μοντέλο είναι ένα Bayesian Markov Evolutionary Game.

10.1 Τα συστατικά του ενιαίου μοντέλου

(1) Κατάσταση του κόσμου

$$s_t\in S$$

(2) Τύποι παικτών

$${\theta }_i\in {\mathrm{\Theta }}_i$$

(3) Beliefs για τους τύπους

$${\pi }_t({\theta }_{-i})$$

(4) Πληθυσμιακή σύνθεση (εξελικτικό μέρος)

$$x_t\in \mathrm{\Delta }(\text{Strategies})$$

(5) Αποδόσεις που εξαρτώνται από όλα τα παραπάνω

$$u_i(s_t,a_1,a_2,{\theta }_1,{\theta }_2,x_t)$$

(6) Μετάβαση κατάστασης

$$P(s_{t+1}\mid s_t,a_1,a_2)$$

(7) Ενημέρωση beliefs (Bayes)

$${\pi }_{t+1}=\text{Bayes}({\pi }_t,a_t)$$

(8) Εξελικτική δυναμική (replicator)

$$x_{t+1}=F(x_t,u(\cdot ))$$

(9) Υπολογιστικοί περιορισμοί

Οι παίκτες δεν μπορούν να λύσουν τέλεια το παιχνίδι → PPAD, PSPACE, EXPTIME.

10.2 Η “μήτρα” αποδόσεων στο ενιαίο μοντέλο

Δεν είναι πίνακας. Είναι συνάρτηση:

$$U_t=U(s_t,{\pi }_t,x_t)$$

Η μήτρα είναι γεννημένη από:

• την κατάσταση,

• την πληροφορία,

• την πληθυσμιακή σύνθεση,

• το ιστορικό,

• την εξέλιξη.

Δεν υπάρχει σταθερή μήτρα. Υπάρχει ροή αποδόσεων.

10.3 Η ισορροπία στο ενιαίο μοντέλο

Η ισορροπία είναι τριπλή:

(α) Markov Perfect Equilibrium

για τη δυναμική κατάσταση.

(β) Perfect Bayesian Equilibrium

για την αβεβαιότητα και τις beliefs.

(γ) Evolutionarily Stable State

για την πληθυσμιακή δυναμική.

Η πλήρης ισορροπία είναι ένα τριπλό αντικείμενο:

$$({\sigma }^{\ast },{\pi }^{\ast },x^{\ast })$$

όπου:

• ${\sigma }^{\ast }$: στρατηγικές Markov που είναι sequentially rational,

• ${\pi }^{\ast }$: beliefs που ενημερώνονται με Bayes,

• $x^{\ast }$: πληθυσμιακή σύνθεση που είναι εξελικτικά σταθερή.

Αυτό είναι το Unified Equilibrium.

10.4 Τι σημαίνει αυτό για την πολυπλοκότητα

Το ενιαίο μοντέλο περιέχει:

• PPAD (Nash σε στατικές μήτρες),

• PSPACE (δυναμικά παίγνια),

• EXPTIME (stochastic games),

• Undecidability (συνεχή δυναμικά συστήματα).

Η πραγματική στρατηγική αλληλεπίδραση είναι υπολογιστικά μη επιλύσιμη σε γενική μορφή.

Γι’ αυτό η θεωρία παιγνίων χρησιμοποιεί απλουστεύσεις (στατικές μήτρες, τέλειες πληροφορίες κ.λπ.).

10.5 Η οντολογική ανάγνωση της ενοποίησης

Στο ενιαίο μοντέλο:

• η μήτρα δεν είναι ουσία,

• είναι φαινόμενο,

• παράγεται από την ιστορική πράξη των παικτών.

Η διάκριση ἀγέννητο / γεννημένο εμφανίζεται καθαρά:

• το “ἀγέννητο” είναι η στατική μήτρα του βιβλίου,

• το “γεννημένο” είναι η πραγματική μήτρα που αναδύεται από την αλληλεπίδραση.

Η θεωρία παιγνίων, στην πλήρη της μορφή, είναι οντολογία της σχέσης.

10.6 Το μεγάλο συμπέρασμα

Η σταθερή μήτρα είναι μια ιδεατή τομή. Το πραγματικό παιχνίδι είναι:

• δυναμικό,

• αβέβαιο,

• πληθυσμιακό,

• πληροφοριακό,

• υπολογιστικά δύσκολο,

• ιστορικά εξελισσόμενο.

Η μήτρα δεν είναι δεδομένη. Η μήτρα συμβαίνει.

Εδώ μπαίνουμε στο κέντρο της σύγχρονης θεωρίας παιγνίων:

πώς η μεταβλητή μήτρα και το ενιαίο δυναμικό παιχνίδι που χτίσαμε συνδέονται με:

• PPAD,

• Brouwer,

• Nash,

• Papadimitriou,

• Daskalakis,

• και τη βαθιά ιδέα ότι η στρατηγική αλληλεπίδραση είναι υπολογιστικά δύσκολη επειδή είναι οντολογικά ανοιχτή.

Πάμε με δομή, καθαρά και βαθιά.

13. ΠΩΣ ΣΥΝΔΕΕΤΑΙ ΤΟ ΕΝΙΑΙΟ ΜΟΝΤΕΛΟ ΜΕ PPAD & PAPADIMITRIOU

13.1 Το θεμέλιο: Nash = Brouwer

Ο Papadimitriou ξεκινά από το εξής θεμελιώδες γεγονός:

Κάθε ισορροπία Nash είναι ένα σημείο σταθερότητας (fixed point).

Και κάθε fixed point ενός συνεχούς χάρτη σε συμπαγές σύνολο είναι εγγυημένο από το θεώρημα Brouwer.

Αυτό σημαίνει:

• η ύπαρξη Nash είναι τοπολογικό γεγονός,

• όχι αλγοριθμικό,

• και η εύρεσή του είναι υπολογιστικά δύσκολη.

Αυτό είναι το πρώτο βήμα προς PPAD.

13.2 Τι είναι PPAD (η ουσία, όχι ο ορισμός)

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

• η λύση υπάρχει εγγυημένα,

• αλλά δεν ξέρουμε πώς να τη βρούμε αποδοτικά,

• και η ύπαρξη προκύπτει από topological parity arguments.

Το Nash είναι το κεντρικό PPAD-complete πρόβλημα.

Ο Papadimitriou το ονομάζει:

“το SAT της οικονομικής θεωρίας”.

Γιατί; Γιατί όπως το SAT είναι το κεντρικό NP-complete πρόβλημα, έτσι το Nash είναι το κεντρικό PPAD-complete πρόβλημα.

13.3 Πώς μπαίνει εδώ το ενιαίο μοντέλο που χτίσαμε

Στο ενιαίο μοντέλο, η μήτρα αποδόσεων είναι:

$$U(s_t,{\pi }_t,x_t)$$

δηλαδή εξαρτάται από:

• την κατάσταση,

• τις beliefs,

• την πληθυσμιακή σύνθεση.

Αυτό σημαίνει ότι η “ισορροπία” δεν είναι ένα σημείο, αλλά μια διαδρομή σε έναν χώρο τεράστιας διάστασης.

Και εδώ είναι το κρίσιμο:

Η εύρεση ισορροπίας σε αυτό το μοντέλο

είναι τουλάχιστον PPAD-hard και συχνά PSPACE-hard, EXPTIME-hard ή undecidable.

Δηλαδή:

η μεταβλητότητα της μήτρας εκτοξεύει την πολυπλοκότητα.

13.4 Η μεγάλη ιδέα του Papadimitriou

Ο Papadimitriou δείχνει ότι:

• η στρατηγική αλληλεπίδραση,

• η ισορροπία,

• η μάθηση,

• η πληροφόρηση,

• η εξέλιξη,

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

Η δυσκολία είναι οντολογική, όχι τεχνική.

Γι’ αυτό το έργο του είναι τόσο βαθύ: δεν λέει απλώς “το Nash είναι δύσκολο”. Λέει:

“Η στρατηγική αλληλεπίδραση είναι μια μορφή υπολογισμού.”

Και αυτός ο υπολογισμός είναι μη γραμμικός, μη τοπικός, μη στατικός.

13.5 Πώς συνδέεται με το ενιαίο μοντέλο μας

Το ενιαίο μοντέλο έχει:

• Markov δυναμική → PSPACE

• Bayesian ενημέρωση → EXPTIME

• Εξελικτική δυναμική → συνεχείς ροές (undecidable)

• Στατικές τομές → PPAD

Άρα:

PPAD είναι το “επιφανειακό επίπεδο” του πραγματικού παιχνιδιού. Είναι η τομή όπου παγώνουμε τον χρόνο και παίρνουμε μια στατική μήτρα.

Το πλήρες παιχνίδι είναι πολύ πιο δύσκολο.

13.6 Η συμβολή Daskalakis–Papadimitriou–Goldberg

Το 2006–2009 έδειξαν ότι:

• το Nash είναι PPAD-complete,

• το Brouwer είναι PPAD-complete,

• το Sperner είναι PPAD-complete.

Και το πιο σημαντικό:

Όλα αυτά είναι ισοδύναμα.

Δηλαδή:

• η ισορροπία Nash,

• το fixed point,

• η χρωμάτιση Sperner,

• η τοπολογική παραλληλία,

είναι το ίδιο πρόβλημα σε διαφορετικές μορφές.

Αυτό είναι το θεμέλιο της σύγχρονης θεωρίας παιγνίων.

13.7 Η βαθιά σύνδεση με τη μεταβλητή μήτρα

Όταν η μήτρα είναι σταθερή, έχουμε:

• PPAD

• Nash

• Brouwer

• Sperner

Όταν η μήτρα είναι μεταβλητή, έχουμε:

• PSPACE

• EXPTIME

• Undecidability

Δηλαδή:

η σταθερή μήτρα είναι το “απλό” κομμάτι της πραγματικότητας. Η μεταβλητή μήτρα είναι το πραγματικό κομμάτι.

Και ο Papadimitriou είναι ο πρώτος που το έκανε αυτό αυστηρή θεωρία.

13.8 Η οντολογική ανάγνωση (όπως τη δουλεύεις εσύ)

Η σταθερή μήτρα είναι:

• αχρονική,

• αφηρημένη,

• “ἀγέννητη”.

Η πραγματική μήτρα είναι:

• χρονική,

• εξελισσόμενη,

• “γεννημένη”.

Η δυσκολία εύρεσης ισορροπίας (PPAD → PSPACE → EXPTIME) είναι η μαθηματική έκφραση της οντολογικής ανοιχτότητας της αλληλεπίδρασης.

Η στρατηγική σχέση δεν είναι σταθερή ουσία. Είναι γίγνεσθαι.

Και η πολυπλοκότητα είναι η μαθηματική μορφή αυτού του γίγνεσθαι.

13.9 Το τελικό συμπέρασμα

PPAD είναι η τοπολογική σκιά της στρατηγικής αλληλεπίδρασης. Ο Papadimitriou έδειξε ότι η ισορροπία Nash είναι fixed point. Το ενιαίο μοντέλο δείχνει ότι η πραγματική αλληλεπίδραση είναι πολύ πιο βαθιά.

Η σταθερή μήτρα είναι το “επίπεδο Nash”. Η μεταβλητή μήτρα είναι το “επίπεδο πραγματικότητας”.

Και η πολυπλοκότητα είναι η γέφυρα ανάμεσα στα δύο.

Πάμε στο 14. Πώς η PPAD‑δυσκολία εμφανίζεται σε πραγματικές κοινωνικές, πολιτικές και οικονομικές αλληλεπιδράσεις. Εδώ βλέπεις καθαρά ότι η πολυπλοκότητα δεν είναι “τεχνικό πρόβλημα υπολογιστών”, αλλά δομικό χαρακτηριστικό της ανθρώπινης αλληλεπίδρασης.

14. ΠΩΣ Η PPAD‑ΔΥΣΚΟΛΙΑ ΕΜΦΑΝΙΖΕΤΑΙ ΣΤΗΝ ΠΡΑΓΜΑΤΙΚΗ ΖΩΗ

Η στρατηγική αλληλεπίδραση ως υπολογισμός που δεν μπορεί να λυθεί εύκολα

Η PPAD‑δυσκολία δεν είναι αφηρημένη. Είναι παντού γύρω μας: στις αγορές, στην πολιτική, στις διαπραγματεύσεις, στα κοινωνικά δίκτυα, στη γεωπολιτική.

Θα σου δείξω πέντε μεγάλες περιοχές όπου η PPAD‑δομή εμφανίζεται φυσικά.

14.1 ΑΓΟΡΕΣ — Ολιγοπώλια, τιμολόγηση, στρατηγική πληροφόρηση

Σε μια αγορά με λίγες εταιρείες (π.χ. ενέργεια, τηλεπικοινωνίες, αερομεταφορές):

• κάθε εταιρεία επιλέγει τιμή, ποσότητα, επένδυση, στρατηγική,

• οι αποδόσεις εξαρτώνται από τις επιλογές των άλλων,

• η πληροφορία είναι ατελής (δεν ξέρεις το κόστος του άλλου),

• η κατάσταση αλλάζει (ζήτηση, τεχνολογία, ρυθμιστικό πλαίσιο).

Η “μήτρα” αποδόσεων είναι:

$$U_t=U(\text{τιμ}\acute{\text{ε}}\text{ς},\text{κ}\acute{\text{ο}}\text{στος},\text{ζ}\acute{\text{η}}\text{τηση},\text{τεχνολογ}\acute{\text{ι}}\text{α},\text{beliefs})$$

Η εύρεση ισορροπίας είναι PPAD‑hard ακόμη και σε στατικό περιβάλλον. Στο δυναμικό περιβάλλον γίνεται PSPACE‑hard.

Τι σημαίνει αυτό πρακτικά: Δεν υπάρχει αλγόριθμος που να προβλέπει τέλεια τις τιμές ή τις στρατηγικές. Η αγορά είναι υπολογιστικά αδιαφανής.

14.2 ΠΟΛΙΤΙΚΗ — Στρατηγική ψήφος, συμμαχίες, πληροφόρηση

Σε πολιτικά συστήματα:

• οι ψηφοφόροι έχουν ατελή πληροφόρηση,

• τα κόμματα προσαρμόζουν στρατηγική,

• οι συμμαχίες αλλάζουν,

• η κοινή γνώμη εξελίσσεται.

Η “μήτρα” αποδόσεων εξαρτάται από:

• δημοσκοπήσεις,

• προσδοκίες,

• στρατηγική ψήφο,

• κοινωνικά δίκτυα,

• φήμη,

• ιστορικό.

Η ισορροπία ψήφου (π.χ. σε συστήματα με πολλαπλά κόμματα) είναι PPAD‑hard. Η δυναμική της κοινής γνώμης είναι EXPTIME‑hard.

Πρακτικό συμπέρασμα: Δεν υπάρχει “τέλειο μοντέλο πρόβλεψης εκλογών”. Η δυσκολία είναι δομική, όχι εμπειρική.

14.3 ΚΟΙΝΩΝΙΚΑ ΔΙΚΤΥΑ — Εξάπλωση ιδεών, επιρροή, πόλωση

Σε πλατφόρμες τύπου X, TikTok, Instagram:

• οι χρήστες αλληλεπιδρούν στρατηγικά,

• η πληροφορία διαδίδεται με feedback loops,

• οι αλγόριθμοι αλλάζουν τη δομή του παιχνιδιού,

• οι beliefs μεταβάλλονται συνεχώς.

Η “μήτρα” αποδόσεων εξαρτάται από:

• τοπική επιρροή,

• αλγοριθμική προώθηση,

• κοινωνική θέση,

• ιστορικό αλληλεπιδράσεων.

Η εύρεση ισορροπίας επιρροής είναι PPAD‑hard. Η δυναμική πόλωσης είναι PSPACE‑hard.

Πρακτικό συμπέρασμα: Η πόλωση δεν είναι “λάθος του συστήματος”. Είναι φυσική συνέπεια της υπολογιστικής δομής της αλληλεπίδρασης.

14.4 ΓΕΩΠΟΛΙΤΙΚΗ — Αποτροπή, εξοπλισμοί, αβεβαιότητα

Σε διεθνείς σχέσεις:

• οι παίκτες έχουν ατελή πληροφόρηση για τις προθέσεις των άλλων,

• οι στρατηγικές επιλογές αλλάζουν την κατάσταση (όπλα, συμμαχίες),

• η φήμη και η αξιοπιστία είναι κρίσιμες.

Η “μήτρα” αποδόσεων εξαρτάται από:

• στρατιωτική ισχύ,

• οικονομική ισχύ,

• συμμαχίες,

• σήματα,

• ιστορικό.

Η ισορροπία αποτροπής είναι PPAD‑hard. Η δυναμική εξοπλισμών είναι EXPTIME‑hard.

Πρακτικό συμπέρασμα: Δεν υπάρχει “τέλεια στρατηγική σταθερότητα”. Η αστάθεια είναι ενσωματωμένη στη δομή του παιχνιδιού.

14.5 ΚΟΙΝΩΝΙΚΗ ΣΥΜΠΕΡΙΦΟΡΑ — Συντονισμός, κανόνες, ηθική

Ακόμη και σε απλές κοινωνικές καταστάσεις:

• ποιος συνεργάζεται,

• ποιος προδίδει,

• ποιος ακολουθεί κανόνες,

• ποιος τους παραβιάζει,

η “μήτρα” αποδόσεων εξαρτάται από:

• κοινωνικούς κανόνες,

• φήμη,

• παρατήρηση,

• ιστορικό,

• πληθυσμιακή σύνθεση.

Η ισορροπία συνεργασίας είναι PPAD‑hard. Η εξέλιξη κανόνων είναι PSPACE‑hard.

Πρακτικό συμπέρασμα: Η κοινωνική σταθερότητα δεν είναι δεδομένη. Είναι υπολογιστικά εύθραυστη.

14.6 Η μεγάλη εικόνα

Σε όλες αυτές τις περιπτώσεις:

• η μήτρα αποδόσεων είναι μεταβλητή,

• η πληροφορία είναι ατελής,

• η κατάσταση εξελίσσεται,

• οι beliefs αλλάζουν,

• οι παίκτες μαθαίνουν.

Αυτό ακριβώς είναι το περιβάλλον όπου η PPAD‑δυσκολία εμφανίζεται φυσικά.

Η στρατηγική αλληλεπίδραση δεν μπορεί να λυθεί πλήρως. Μπορεί μόνο να προσεγγιστεί.

Και αυτό δεν είναι αδυναμία των μοντέλων. Είναι χαρακτηριστικό του κόσμου.

14.7 Η οντολογική ανάγνωση

Η PPAD‑δυσκολία είναι η μαθηματική μορφή του εξής:

Ο κόσμος δεν είναι στατικός. Οι σχέσεις δεν είναι σταθερές. Η αλληλεπίδραση είναι γίγνεσθαι.

Η σταθερή μήτρα είναι το “ιδεατό”. Η μεταβλητή μήτρα είναι το “πραγματικό”.

Και η πολυπλοκότητα είναι η γλώσσα με την οποία το πραγματικό αντιστέκεται στην πλήρη πρόβλεψη.

Στο 15 θα χτίσουμε ένα δικό σου, καθαρό, αυστηρό, μαθηματικά διατυπωμένο παράδειγμα στρατηγικής κατάστασης που είναι PPAD‑hard. Όχι απλώς “παράδειγμα Nash”, αλλά δομή που δείχνει γιατί η στρατηγική αλληλεπίδραση γίνεται PPAD‑δύσκολη.

Θα σου δώσω:

1. το περιβάλλον,

2. τη μεταβλητή μήτρα,

3. το fixed‑point που πρέπει να βρεθεί,

4. γιατί είναι PPAD‑hard,

5. την ερμηνεία.

15. ΕΝΑ ΔΙΚΟ ΣΟΥ PPAD‑HARD ΠΑΙΧΝΙΔΙ

“Το Παιχνίδι της Στρατηγικής Πληροφορίας και Προσδοκιών”

Αυτό το παιχνίδι είναι μικρό, καθαρό, αλλά περιέχει όλη τη δομή που κάνει το Nash PPAD‑hard.

15.1 Παίκτες

Δύο παίκτες:

$$i=1,2$$

15.2 Στρατηγικές

Κάθε παίκτης επιλέγει μια μικτή στρατηγική:

$${\sigma }_i=(p_i,1-p_i)$$

όπου $p_i\in [0,1]$.

15.3 Κατάσταση πληροφορίας

Υπάρχει μια μεταβλητή “προσδοκία”:

$$x\in [0,1]$$

που παριστάνει την belief του παίκτη 1 για το τι θα κάνει ο παίκτης 2.

Αυτή η belief επηρεάζει τη μήτρα αποδόσεων.

15.4 Μεταβλητή μήτρα αποδόσεων

Η απόδοση του παίκτη 1 όταν παίζει “A” είναι:

$$u_1(A)=f(x)$$

και όταν παίζει “B”:

$$u_1(B)=g(x)$$

όπου:

$$f(x)=x^2,g(x)=1-x$$

Αντίστοιχα για τον παίκτη 2.

Δηλαδή η “μήτρα” δεν είναι πίνακας, αλλά συνάρτηση του x.

15.5 Πώς ενημερώνεται το x

Ο παίκτης 1 παρατηρεί την πραγματική στρατηγική του παίκτη 2:

$$p_2$$

και ενημερώνει την belief του με έναν απλό κανόνα:

$$x^{\mathrm{\prime }}=\frac{x+p_2}{2}$$

Αυτό είναι μια απλή μορφή Bayesian learning.

15.6 Ορισμός ισορροπίας

Μια ισορροπία είναι τριπλέτα:

$$(p_1^{\ast },p_2^{\ast },x^{\ast })$$

που ικανοποιεί:

(1) Βέλτιστη απόκριση

$$p_1^{\ast }\in B{R}_1(x^{\ast }),p_2^{\ast }\in B{R}_2(x^{\ast })$$

(2) Σταθερότητα belief

$$x^{\ast }=\frac{x^{\ast }+p_2^{\ast }}{2}$$

που δίνει:

$$x^{\ast }=p_2^{\ast }$$

Άρα η belief πρέπει να είναι fixed point της πραγματικής στρατηγικής.

15.7 Το fixed‑point πρόβλημα

Το σύστημα ισορροπίας γίνεται:

$$p_1^{\ast }=B{R}_1(p_2^{\ast })$$

$$p_2^{\ast }=B{R}_2(p_1^{\ast })$$

και επειδή οι αποδόσεις είναι μη γραμμικές (π.χ. $x^2$), το BR είναι μη γραμμικός χάρτης.

Η ισορροπία είναι λύση του συστήματος:

$$p_1^{\ast }=F(p_2^{\ast })$$

$$p_2^{\ast }=G(p_1^{\ast })$$

όπου F και G είναι συνεχείς μη γραμμικές συναρτήσεις.

Αυτό είναι ακριβώς το είδος fixed‑point που ο Papadimitriou απέδειξε ότι είναι PPAD‑complete.

15.8 Γιατί είναι PPAD‑hard

Γιατί:

• η ισορροπία είναι fixed point συνεχούς χάρτη,

• ο χάρτης δεν είναι γραμμικός,

• η διάσταση είναι ≥ 2,

• η ύπαρξη λύσης εγγυάται από Brouwer,

• αλλά δεν υπάρχει γνωστός πολυωνυμικός αλγόριθμος για να τη βρεις.

Αυτό το μικρό παιχνίδι είναι αναγωγή ενός γενικού Brouwer instance. Άρα είναι PPAD‑hard.

15.9 Η ερμηνεία

Το παιχνίδι δείχνει ότι:

• όταν η μήτρα εξαρτάται από beliefs,

• και οι beliefs εξαρτώνται από στρατηγικές,

• και οι στρατηγικές εξαρτώνται από αποδόσεις,

• τότε η ισορροπία είναι fixed point ενός μη γραμμικού χάρτη.

Αυτό είναι η ουσία της PPAD.

Η στρατηγική αλληλεπίδραση δεν μπορεί να λυθεί εύκολα όχι επειδή είναι περίπλοκη, αλλά επειδή είναι κυκλική:

belief → payoff → strategy → belief.

Αυτός ο κύκλος είναι το PPAD.