τρίγωνο simplex.

3 στρατηγικές σημαίνει πραγματικό τρίγωνο simplex.

Πάμε με το πιο καθαρό παράδειγμα: Rock–Paper–Scissors (Πέτρα–Ψαλίδι–Χαρτί).

1. Το παιχνίδι (3 στρατηγικές)

Παίκτης 1:

• $R$ = Πέτρα

• $P$ = Χαρτί

• $S$ = Ψαλίδι

Παίκτης 2: ίδια.

Πίνακας αποδόσεων Παίκτη 1 (κλασικό):

$$A=\left(\begin{array}{ccc}0& -1& 1\\ 1& 0& -1\\ -1& 1& 0\end{array}\right)$$

(Ο Παίκτης 2 έχει το αντίθετο, μηδενικό άθροισμα.)

2. Μικτή στρατηγική και τρίγωνο simplex

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

$$p=(p_R,p_P,p_S),p_R,p_P,p_S\ge 0,p_R+p_P+p_S=1$$

Αυτός ο χώρος:

$${\mathrm{\Delta }}^2=\{(p_R,p_P,p_S):p_i\ge 0,\sum p_i=1\}$$

είναι τρίγωνο (2‑simplex).

Κάθε σημείο μέσα στο τρίγωνο είναι μια μικτή στρατηγική.

3. Αλγεβρική λύση Nash

Έστω ότι ο Παίκτης 2 παίζει:

$$q=(q_R,q_P,q_S)$$

Απόδοση Παίκτη 1 αν παίξει:

• $R$:

$$u_1(R)=0\cdot q_R+(-1)\cdot q_P+1\cdot q_S=-q_P+q_S$$

• $P$:

$$u_1(P)=1\cdot q_R+0\cdot q_P+(-1)\cdot q_S=q_R-q_S$$

• $S$:

$$u_1(S)=(-1)\cdot q_R+1\cdot q_P+0\cdot q_S=-q_R+q_P$$

Στην ισορροπία, ο Παίκτης 1 πρέπει να είναι αδιάφορος ανάμεσα σε $R,P,S$ (για να μπορεί να παίζει και τις 3):

$$u_1(R)=u_1(P)=u_1(S)$$

Άρα:

$$-q_P+q_S=q_R-q_S=-q_R+q_P$$

Λύνοντας (και με $q_R+q_P+q_S=1$) παίρνουμε:

$$q_R=q_P=q_S=\frac{1}{3}$$

Ανάλογα για τον Παίκτη 2:

$$p_R=p_P=p_S=\frac{1}{3}$$

👉 Ισορροπία Nash:

$$p^{\text{*}}=q^{\text{*}}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$$

4. Γεωμετρικά: πώς φαίνεται στο τρίγωνο

• Οι κορυφές του τριγώνου:

  • $(1,0,0)$ → μόνο Πέτρα

  • $(0,1,0)$ → μόνο Χαρτί

  • $(0,0,1)$ → μόνο Ψαλίδι

• Το σημείο:

$$(\frac{1}{3},\frac{1}{3},\frac{1}{3})$$

είναι το κέντρο του τριγώνου (barycenter).

Εκεί:

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

• ο παίκτης είναι αδιάφορος,

• άρα μπορεί να παίζει και τις 3 με ίση πιθανότητα.

5. Τι κερδίζεις από το τρίγωνο simplex

• Βλέπεις όλο τον χώρο στρατηγικών σαν γεωμετρικό αντικείμενο.

• Το Nash είναι ένα σημείο μέσα στο τρίγωνο.

• Οι best‑response περιοχές είναι υποπεριοχές του τριγώνου.

• Η τομή τους δίνει το σημείο ισορροπίας.

Το παιχνίδι που θα χρησιμοποιήσουμε είναι το Rock–Paper–Scissors, γιατί είναι το πιο καθαρό 3‑στρατηγικό παιχνίδι με μοναδικό μικτό Nash στο κέντρο του simplex.

🔴 1. ΟΡΙΣΜΟΣ ΤΟΥ ΠΑΙΧΝΙΔΙΟΥ (3 στρατηγικές)

Παίκτης 1:

• $R$ = Πέτρα

• $P$ = Χαρτί

• $S$ = Ψαλίδι

Παίκτης 2: ίδια.

Πίνακας αποδόσεων Παίκτη 1:

$$\mathrm{<span\; style="color:\; \#f1c232;">A</span>}<span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">(</span>\begin{array}{ccc}\mathrm{<span\; style="color:\; \#f1c232;">0</span>}& <span\; style="color:\; \#f1c232;">-</span>\mathrm{<span\; style="color:\; \#f1c232;">1</span>}& \mathrm{<span\; style="color:\; \#f1c232;">1</span>}\\ \mathrm{<span\; style="color:\; \#f1c232;">1</span>}& \mathrm{<span\; style="color:\; \#f1c232;">0</span>}& <span\; style="color:\; \#f1c232;">-</span>\mathrm{<span\; style="color:\; \#f1c232;">1</span>}\\ <span\; style="color:\; \#f1c232;">-</span>\mathrm{<span\; style="color:\; \#f1c232;">1</span>}& \mathrm{<span\; style="color:\; \#f1c232;">1</span>}& \mathrm{<span\; style="color:\; \#f1c232;">0</span>}\end{array}<span\; style="color:\; \#f1c232;">)</span>$$

Ο Παίκτης 2 έχει το αντίθετο (μηδενικό άθροισμα).

🔵 2. Ο ΧΩΡΟΣ ΜΙΚΤΩΝ ΣΤΡΑΤΗΓΙΚΩΝ = ΤΡΙΓΩΝΟ SIMPLEX

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

$$\mathrm{<span\; style="color:\; \#f1c232;">p</span>}<span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">(</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">,</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">,</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">,</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">i</span>}}<span\; style="color:\; \#f1c232;">\ge </span>\mathrm{<span\; style="color:\; \#f1c232;">0</span>}<span\; style="color:\; \#f1c232;">,</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">+</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">+</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">=</span>\mathrm{<span\; style="color:\; \#f1c232;">1</span>}$$

Αυτός ο χώρος:

$${\mathrm{<span\; style="color:\; \#f1c232;">\Delta </span>}}^{\mathrm{<span\; style="color:\; \#f1c232;">2</span>}}<span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">\{</span><span\; style="color:\; \#f1c232;">(</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">,</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">,</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">:</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">i</span>}}<span\; style="color:\; \#f1c232;">\ge </span>\mathrm{<span\; style="color:\; \#f1c232;">0</span>}<span\; style="color:\; \#f1c232;">,</span>\text{<span style="color: \#f1c232;">\hspace{0.25em}\hspace{0.05em}</span>}<span\; style="color:\; \#f1c232;">\sum </span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">i</span>}}<span\; style="color:\; \#f1c232;">=</span>\mathrm{<span\; style="color:\; \#f1c232;">1</span>}<span\; style="color:\; \#f1c232;">\}</span>$$

είναι τρίγωνο.

• Κορυφή 1: $(1,0,0)$ → μόνο Πέτρα

• Κορυφή 2: $(0,1,0)$ → μόνο Χαρτί

• Κορυφή 3: $(0,0,1)$ → μόνο Ψαλίδι

Κάθε σημείο μέσα στο τρίγωνο είναι μια μικτή στρατηγική.

🟣 3. ΑΛΓΕΒΡΙΚΗ ΛΥΣΗ NASH (βήμα‑βήμα)

Έστω ότι ο Παίκτης 2 παίζει:

$$\mathrm{<span\; style="color:\; \#f1c232;">q</span>}<span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">(</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">,</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">,</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">)</span>$$

Απόδοση Παίκτη 1 αν παίξει:

• $R$:

$${\mathrm{<span\; style="color:\; \#f1c232;">u</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}<span\; style="color:\; \#f1c232;">(</span>\mathrm{<span\; style="color:\; \#f1c232;">R</span>}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">+</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}$$

• $P$:

$${\mathrm{<span\; style="color:\; \#f1c232;">u</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}<span\; style="color:\; \#f1c232;">(</span>\mathrm{<span\; style="color:\; \#f1c232;">P</span>}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}$$

• $S$:

$${\mathrm{<span\; style="color:\; \#f1c232;">u</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}<span\; style="color:\; \#f1c232;">(</span>\mathrm{<span\; style="color:\; \#f1c232;">S</span>}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">+</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}$$

Στην ισορροπία, ο Παίκτης 1 πρέπει να είναι αδιάφορος μεταξύ R, P, S:

$$<span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">+</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">+</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}$$

Με την κανονικοποίηση $q_R+q_P+q_S=1$, λύση:

$${\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">=</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}$$

Ανάλογα για τον Παίκτη 2:

$${\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">=</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}$$

👉 Ισορροπία Nash:

$${\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}^{\text{<span style="color: \#f1c232;">*</span>}}<span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}^{\text{<span style="color: \#f1c232;">*</span>}}<span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">(</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}<span\; style="color:\; \#f1c232;">,</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}<span\; style="color:\; \#f1c232;">,</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}<span\; style="color:\; \#f1c232;">)</span>$$

🟢 4. ΜΗΤΡΩΙΚΗ ΛΥΣΗ

Μικτές στρατηγικές:

$$\mathrm{<span\; style="color:\; \#f1c232;">x</span>}<span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">(</span>\begin{array}{c}{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}\\ {\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}\\ {\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}\end{array}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">,</span>\mathrm{<span\; style="color:\; \#f1c232;">y</span>}<span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">(</span>\begin{array}{c}{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}\\ {\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}\\ {\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}\end{array}<span\; style="color:\; \#f1c232;">)</span>$$

Απόδοση Παίκτη 1:

$${\mathrm{<span\; style="color:\; \#f1c232;">U</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}<span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">x</span>}}^{\mathrm{<span\; style="color:\; \#f1c232;">T</span>}}\mathrm{<span\; style="color:\; \#f1c232;">A</span>}\mathrm{<span\; style="color:\; \#f1c232;">y</span>}$$

Υπολογίζουμε:

$$\mathrm{<span\; style="color:\; \#f1c232;">A</span>}\mathrm{<span\; style="color:\; \#f1c232;">y</span>}<span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">(</span>\begin{array}{ccc}\mathrm{<span\; style="color:\; \#f1c232;">0</span>}& <span\; style="color:\; \#f1c232;">-</span>\mathrm{<span\; style="color:\; \#f1c232;">1</span>}& \mathrm{<span\; style="color:\; \#f1c232;">1</span>}\\ \mathrm{<span\; style="color:\; \#f1c232;">1</span>}& \mathrm{<span\; style="color:\; \#f1c232;">0</span>}& <span\; style="color:\; \#f1c232;">-</span>\mathrm{<span\; style="color:\; \#f1c232;">1</span>}\\ <span\; style="color:\; \#f1c232;">-</span>\mathrm{<span\; style="color:\; \#f1c232;">1</span>}& \mathrm{<span\; style="color:\; \#f1c232;">1</span>}& \mathrm{<span\; style="color:\; \#f1c232;">0</span>}\end{array}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">(</span>\begin{array}{c}{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}\\ {\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}\\ {\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}\end{array}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">(</span>\begin{array}{c}<span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">+</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}\\ {\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}\\ <span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">+</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}\end{array}<span\; style="color:\; \#f1c232;">)</span>$$

Στην ισορροπία, οι στρατηγικές που παίζονται με θετική πιθανότητα πρέπει να έχουν ίση απόδοση:

$$<span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">+</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">=</span><span\; style="color:\; \#f1c232;">-</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">+</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}$$

Λύση:

$${\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">R</span>}}<span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">P</span>}}<span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">q</span>}}_{\mathrm{<span\; style="color:\; \#f1c232;">S</span>}}<span\; style="color:\; \#f1c232;">=</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}$$

🟡 5. ΓΕΩΜΕΤΡΙΚΗ ΛΥΣΗ (best‑response regions)

Στο τρίγωνο:

• κάθε σημείο αντιστοιχεί σε μια μικτή στρατηγική

• οι best‑response περιοχές είναι 3 καμπύλες που χωρίζουν το τρίγωνο

• η τομή τους είναι ένα σημείο: το κέντρο του τριγώνου

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

$$<span\; style="color:\; \#f1c232;">(</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}<span\; style="color:\; \#f1c232;">,</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}<span\; style="color:\; \#f1c232;">,</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}<span\; style="color:\; \#f1c232;">)</span>$$

🟤 6. LCP (Linear Complementarity Problem) — ιδέα

Το Nash γράφεται ως:

$$\mathrm{<span\; style="color:\; \#f1c232;">z</span>}<span\; style="color:\; \#f1c232;">\ge </span>\mathrm{<span\; style="color:\; \#f1c232;">0</span>}<span\; style="color:\; \#f1c232;">,</span>\mathrm{<span\; style="color:\; \#f1c232;">M</span>}\mathrm{<span\; style="color:\; \#f1c232;">z</span>}<span\; style="color:\; \#f1c232;">+</span>\mathrm{<span\; style="color:\; \#f1c232;">q</span>}<span\; style="color:\; \#f1c232;">\ge </span>\mathrm{<span\; style="color:\; \#f1c232;">0</span>}<span\; style="color:\; \#f1c232;">,</span>{\mathrm{<span\; style="color:\; \#f1c232;">z</span>}}^{\mathrm{<span\; style="color:\; \#f1c232;">T</span>}}<span\; style="color:\; \#f1c232;">(</span>\mathrm{<span\; style="color:\; \#f1c232;">M</span>}\mathrm{<span\; style="color:\; \#f1c232;">z</span>}<span\; style="color:\; \#f1c232;">+</span>\mathrm{<span\; style="color:\; \#f1c232;">q</span>}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">=</span>\mathrm{<span\; style="color:\; \#f1c232;">0</span>}$$

όπου:

• $z$ = πιθανότητες + dual μεταβλητές

• $M$, $q$ = κατασκευάζονται από τις μήτρες αποδόσεων

Ο αλγόριθμος Lemke–Howson βρίσκει το Nash ακολουθώντας ένα μονοπάτι σε πολυεδρικό γράφο.

Για το RPS, το μονοπάτι καταλήγει στο:

$$<span\; style="color:\; \#f1c232;">(</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}<span\; style="color:\; \#f1c232;">,</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}<span\; style="color:\; \#f1c232;">,</span>\frac{\mathrm{<span\; style="color:\; \#f1c232;">1</span>}}{\mathrm{<span\; style="color:\; \#f1c232;">3</span>}}<span\; style="color:\; \#f1c232;">)</span>$$

🟧 7. NASH ΩΣ ΣΤΑΘΕΡΟ ΣΗΜΕΙΟ BROUWER

Ορίζουμε μια συνεχή απεικόνιση:

$$\mathrm{<span\; style="color:\; \#f1c232;">f</span>}<span\; style="color:\; \#f1c232;">(</span>\mathrm{<span\; style="color:\; \#f1c232;">p</span>}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">=</span>\text{<span style="color: \#f1c232;">normalize</span>}<span\; style="color:\; \#f1c232;">(</span>\mathrm{<span\; style="color:\; \#f1c232;">max</span>}<span\; style="color:\; \#f1c232;"></span><span\; style="color:\; \#f1c232;">(</span>\mathrm{<span\; style="color:\; \#f1c232;">0</span>}<span\; style="color:\; \#f1c232;">,</span>\mathrm{<span\; style="color:\; \#f1c232;">u</span>}<span\; style="color:\; \#f1c232;">(</span>\mathrm{<span\; style="color:\; \#f1c232;">p</span>}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">)</span>$$

όπου $u(p)$ είναι οι αποδόσεις των καθαρών στρατηγικών.

Το Nash είναι λύση της εξίσωσης:

$$\mathrm{<span\; style="color:\; \#f1c232;">f</span>}<span\; style="color:\; \#f1c232;">(</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}^{\text{<span style="color: \#f1c232;">*</span>}}<span\; style="color:\; \#f1c232;">)</span><span\; style="color:\; \#f1c232;">=</span>{\mathrm{<span\; style="color:\; \#f1c232;">p</span>}}^{\text{<span style="color: \#f1c232;">*</span>}}$$

Το θεώρημα Brouwer εγγυάται ότι υπάρχει πάντα τέτοιο σημείο.

🟩 8. PPAD ΕΡΜΗΝΕΙΑ

Το Nash ανήκει στην κλάση:

$$\text{<span style="color: \#f1c232;">PPAD</span>}$$

που σημαίνει:

• υπάρχει πάντα λύση

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

• η εύρεση Nash ισορροπίας είναι PPAD‑complete

• άρα ισοδύναμη με εύρεση σταθερού σημείου Brouwer

🟥 9. ΤΕΛΙΚΗ ΣΥΝΘΕΣΗ — ΟΛΑ ΣΥΓΚΛΙΝΟΥΝ ΣΤΟ ΙΔΙΟ ΣΗΜΕΙΟ

Αναπαράσταση	Τι δείχνει	Πού οδηγεί
Αλγεβρική	Ισοτιμία αποδόσεων	$$1/3,1/3,1/3
Μήτρες	Γραμμική μορφή	$$1/3,1/3,1/3
Simplex	Γεωμετρία	Κέντρο τριγώνου
Best‑responses	Τομές	Κέντρο
LCP	Συμπληρωματικότητα	$$1/3,1/3,1/3
Brouwer	Σταθερό σημείο	$$1/3,1/3,1/3
PPAD	Πολυπλοκότητα	Ίδιο σημείο

Όλα καταλήγουν στο:

$$\boxed{{\displaystyle <span\; style="color:\; \#f1c232;">(</span>\frac{\mathrm{1/}}{3},\frac{\mathrm{1/}}{3},\frac{\mathrm{1/}}{3})}}$$

$$\boxed{{\displaystyle <br>}}$$

$$\boxed{{\displaystyle {\rm O}\; \alpha \lambda \gamma ό\rho \iota \theta \mu o\varsigma \; <strong>Lemke–Howson</strong>\; \beta \rho ί\sigma \kappa \epsilon \iota \; \tau o\; Nash\; \alpha \kappa o\lambda o\upsilon \theta ώ\nu \tau \alpha \varsigma \; έ\nu \alpha \; \mu o\nu o\pi ά\tau \iota \; \sigma \epsilon \; \pi o\lambda \upsilon \epsilon \delta \rho \iota \kappa ό\; \gamma \rho ά\phi o.}}$$

$$\boxed{{\displaystyle <br>}}$$

$$\boxed{{\displaystyle <br>}}$$

Game Theory;

 

Ποια συνάρτηση θέλεις να βελτιστοποιήσεις στη Game Theory;

Η απάντηση είναι ξεκάθαρη:

👉 Κάθε παίκτης βελτιστοποιεί τη δική του συνάρτηση χρησιμότητας (utility function).

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

🔍 Τι ακριβώς βελτιστοποιεί ένας παίκτης;

Για έναν παίκτη $i$:

$$\text{<span style="font-size: medium;"><span style="color: \#e69138;">maximize </span></span>}{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">u</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">s</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">s</span></span>}}_{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">-</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">)</span></span>$$

όπου:

• $u_i$ = συνάρτηση χρησιμότητας του παίκτη $i$

• $s_i$ = στρατηγική του παίκτη $i$

• $s_{-i}$ = στρατηγικές όλων των άλλων παικτών

Ο παίκτης επιλέγει $s_i$ ώστε να μεγιστοποιεί το $u_i$, δεδομένων των επιλογών των άλλων.

🎮 Στο Nash Equilibrium τι συμβαίνει;

Ένα προφίλ στρατηγικών $s^{\text{*}}$ είναι Nash όταν:

$${\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">u</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">s</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">i</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#e69138;">*</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">s</span></span>}}_{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">-</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">i</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#e69138;">*</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">)</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">\ge </span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">u</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">s</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">s</span></span>}}_{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">-</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">i</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#e69138;">*</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">)</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">\forall </span></span>}{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">s</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">i</span></span>}}$$

Δηλαδή:

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

• Όλοι είναι σε βέλτιστη απάντηση (best response).

🧠 Ποια είναι η “συνάρτηση που βελτιστοποιεί το παιχνίδι συνολικά”;

Στη θεωρία παιγνίων δεν υπάρχει συνολική συνάρτηση που βελτιστοποιείται από όλους (εκτός από ειδικές περιπτώσεις όπως potential games).

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

🧩 Αν μιλάς για αλγοριθμική θεωρία (PPAD, Brouwer → Nash):

Τότε η “συνάρτηση” που βελτιστοποιείς δεν είναι utility αλλά:

👉 μια συνεχής απεικόνιση $f(x)$ που ψάχνεις το σταθερό σημείο της:

$$\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">f</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">x</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#e69138;">*</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">)</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">=</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#e69138;">x</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#e69138;">*</span></span>}}$$

Από εκεί προκύπτει η Nash ισορροπία.

🎯 Το “τρίγωνο ισορροπίας” (Nash equilibrium simplex) είναι ένα ή πολλά;

✔️ Απάντηση: Είναι ΠΟΛΛΑ. Όχι ένα.

Δεν υπάρχει ένα “τρίγωνο ισορροπίας”. Υπάρχουν πολλά, γιατί:

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

• κάθε παίκτης έχει το δικό του simplex (τρίγωνο, τετράεδρο, κ.λπ.),

• η ισορροπία Nash είναι ένα σημείο μέσα στο καρτεσιανό γινόμενο αυτών των simplex.

🔍 Τι είναι το “τρίγωνο” στη θεωρία παιγνίων;

Για έναν παίκτη με 3 στρατηγικές, το σύνολο των μικτών στρατηγικών του είναι:

$${\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\Delta </span></span>}}^{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">2</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">=</span></span><span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\{</span></span><span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">(</span></span>{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">p</span></span>}}_{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">1</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">,</span></span>{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">p</span></span>}}_{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">2</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">,</span></span>{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">p</span></span>}}_{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">3</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">)</span></span><span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">:</span></span>{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">p</span></span>}}_{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">i</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\ge </span></span>\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">0</span></span>}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">,</span></span>\text{<span style="color: \#f1c232;"><span style="font-size: medium;">\hspace{0.25em}\hspace{0.05em}</span></span>}{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">p</span></span>}}_{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">1</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">+</span></span>{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">p</span></span>}}_{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">2</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">+</span></span>{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">p</span></span>}}_{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">3</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">=</span></span>\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">1</span></span>}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\}</span></span>$$

Αυτό είναι ένα τρίγωνο (2-simplex).

Αν έχει 4 στρατηγικές → τετράεδρο (3-simplex). Αν έχει 2 → γραμμή (1-simplex).

🧠 Πόσα τέτοια simplex υπάρχουν στο παιχνίδι;

Για ένα παιχνίδι με n παίκτες, όπου ο παίκτης $i$ έχει $k_i$ στρατηγικές:

• ο παίκτης $i$ έχει ένα simplex διαστάσεων $k_i-1$,

• το παιχνίδι συνολικά έχει n simplex,

• ο χώρος στρατηγικών είναι το καρτεσιανό γινόμενο αυτών.

Άρα:

👉 Υπάρχουν τόσα “τρίγωνα” όσοι είναι οι παίκτες που έχουν 3 στρατηγικές.

🎮 Και η ισορροπία Nash;

Η ισορροπία Nash είναι ένα σημείο μέσα στο προϊόν των simplex:

$${\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">s</span></span>}}^{\text{<span style="color: \#f1c232;"><span style="font-size: medium;">*</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\in </span></span>{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\Delta </span></span>}}_{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">1</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\times </span></span>{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\Delta </span></span>}}_{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">2</span></span>}}<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\times </span></span><span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\cdots </span></span><span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\times </span></span>{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">\Delta </span></span>}}_{\mathrm{<span\; style="color:\; \#f1c232;"><span\; style="font-size:\; medium;">n</span></span>}}$$

Δεν είναι τρίγωνο. Δεν είναι περιοχή. Είναι ένα σημείο.

🧩 Άρα τελικά:

• Το “τρίγωνο” = ο χώρος μικτών στρατηγικών ενός παίκτη με 3 επιλογές.

• Υπάρχουν πολλά, ένα για κάθε παίκτη.

• Η ισορροπία Nash είναι ένα σημείο μέσα στο πολυδιάστατο χώρο που σχηματίζουν όλα αυτά τα simplex μαζί.

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

✅ 1. Αλγεβρική αναπαράσταση (με εξισώσεις)

Αν ο παίκτης έχει μικτή στρατηγική

$$\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">p</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">p</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">p</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">2</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\dots </span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">p</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">k</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">)</span></span>$$

με $p_i\ge 0$ και $\sum p_i=1$,

τότε η ισορροπία Nash ικανοποιεί:

$${\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">u</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">s</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#6aa84f;">*</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">s</span></span>}}_{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">-</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#6aa84f;">*</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">)</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\ge </span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">u</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">s</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">s</span></span>}}_{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">-</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#6aa84f;">*</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">)</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\forall </span></span>}{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">s</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}$$

Αυτό γράφεται ως σύστημα εξισώσεων και ανισώσεων:

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

$${\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">u</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">s</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">j</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">s</span></span>}}_{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">-</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#6aa84f;">*</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">)</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">U</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#6aa84f;">*</span></span>}}\text{<span style="font-size: medium;"><span style="color: \#6aa84f;">αν </span></span>}{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">p</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">j</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">></span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">0</span></span>}$$

2. Μικρότερη ή ίση απόδοση για στρατηγικές που δεν παίζονται:

$${\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">u</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">s</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">j</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">s</span></span>}}_{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">-</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#6aa84f;">*</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">)</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\le </span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">U</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">i</span></span>}}^{\text{<span style="font-size: medium;"><span style="color: \#6aa84f;">*</span></span>}}\text{<span style="font-size: medium;"><span style="color: \#6aa84f;">αν </span></span>}{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">p</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">j</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">0</span></span>}$$

3. Κανονικοποίηση:

$$\underset{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">j</span></span>}}{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\sum </span></span>}{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">p</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">j</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">p</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">j</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\ge </span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">0</span></span>}$$

Αυτό είναι η αλγεβρική μορφή του Nash.

✅ 2. Αναπαράσταση με ΜΗΤΡΕΣ (matrix form)

Για παιχνίδι 2 παικτών με αποδόσεις:

• Παίκτης 1: μήτρα $A$

• Παίκτης 2: μήτρα $B$

Αν οι μικτές στρατηγικές είναι:

$$\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">x</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">x</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">x</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">2</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\dots </span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">x</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">m</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">)</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">y</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">y</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">y</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">2</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\dots </span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">y</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">n</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">)</span></span>$$

τότε:

Απόδοση παίκτη 1:

$${\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">U</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">x</span></span>}}^{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">T</span></span>}}\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">A</span></span>}\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">y</span></span>}$$

Απόδοση παίκτη 2:

$${\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">U</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">2</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">x</span></span>}}^{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">T</span></span>}}\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">B</span></span>}\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">y</span></span>}$$

Η ισορροπία Nash ικανοποιεί:

Για τον παίκτη 1:

$$\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">A</span></span>}\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">y</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\le </span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">U</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}}\mathbf{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">x</span></span>}}^{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">T</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">(</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">A</span></span>}\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">y</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">-</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">U</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}}\mathbf{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">)</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">0</span></span>}$$

Για τον παίκτη 2:

$${\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">B</span></span>}}^{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">T</span></span>}}\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">x</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\le </span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">U</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">2</span></span>}}\mathbf{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">y</span></span>}}^{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">T</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">(</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">B</span></span>}}^{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">T</span></span>}}\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">x</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">-</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">U</span></span>}}_{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">2</span></span>}}\mathbf{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">1</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">)</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">0</span></span>}$$

Αυτές είναι συνθήκες συμπληρωματικής χαλαρότητας (complementary slackness) και οδηγούν σε γραμμικό συμπλήρωμα (LCP).

🔥 3. Η πιο προχωρημένη μορφή: LCP → PPAD → Brouwer

Το Nash μπορεί να γραφτεί ως:

$$\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">z</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\ge </span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">0</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">M</span></span>}\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">z</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">+</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">q</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">\ge </span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">0</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">,</span></span>{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">z</span></span>}}^{\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">T</span></span>}}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">(</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">M</span></span>}\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">z</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">+</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">q</span></span>}<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">)</span></span><span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">=</span></span>\mathrm{<span\; style="font-size:\; medium;"><span\; style="color:\; \#6aa84f;">0</span></span>}$$

Αυτό είναι Linear Complementarity Problem (LCP). Και το LCP είναι PPAD-complete, δηλαδή ισοδύναμο με την εύρεση σταθερού σημείου Brouwer.

🎯 Άρα η απάντηση στην ερώτησή σου:

👉 Ναι, το σημείο ισορροπίας Nash μπορεί να παρασταθεί:

• Αλγεβρικά με εξισώσεις χρησιμότητας

• Με μήτρες (matrix form)

• Ως LCP

• Ως σταθερό σημείο Brouwer

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

Ενα μικρό manual της Θεωρίας Παιγνίων για το πώς παριστάνουμε, λύνουμε και κατανοούμε το σημείο ισορροπίας Nash:

• Αλγεβρικά

• Με μήτρες

• Με LCP (Linear Complementarity Problem)

• Ως σταθερό σημείο Brouwer

• Ως PPAD πρόβλημα

• Με γεωμετρία simplex (τρίγωνο)

Και θα τα ενώσω όλα σε ένα ενιαίο πλαίσιο, ώστε να δεις πώς συνδέονται.

🟥 1. ΑΛΓΕΒΡΙΚΗ ΠΑΡΑΣΤΑΣΗ ΤΟΥ NASH

Για έναν παίκτη με μικτή στρατηγική:

$$\mathrm{<span\; style="font-size:\; medium;">p</span>}<span\; style="font-size:\; medium;">=</span><span\; style="font-size:\; medium;">(</span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">1</span>}}<span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">2</span>}}<span\; style="font-size:\; medium;">,</span><span\; style="font-size:\; medium;">\dots </span><span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">k</span>}}<span\; style="font-size:\; medium;">)</span><span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">i</span>}}<span\; style="font-size:\; medium;">\ge </span>\mathrm{<span\; style="font-size:\; medium;">0</span>}<span\; style="font-size:\; medium;">,</span><span\; style="font-size:\; medium;">\sum </span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">i</span>}}<span\; style="font-size:\; medium;">=</span>\mathrm{<span\; style="font-size:\; medium;">1</span>}$$

Η ισορροπία Nash ικανοποιεί:

(α) Ισοτιμία αποδόσεων στις στρατηγικές που παίζονται

Αν $p_i>0$:

$${\mathrm{<span\; style="font-size:\; medium;">u</span>}}_{\mathrm{<span\; style="font-size:\; medium;">i</span>}}<span\; style="font-size:\; medium;">(</span>{\mathrm{<span\; style="font-size:\; medium;">s</span>}}_{\mathrm{<span\; style="font-size:\; medium;">i</span>}}<span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">s</span>}}_{<span\; style="font-size:\; medium;">-</span>\mathrm{<span\; style="font-size:\; medium;">i</span>}}^{\text{<span style="font-size: medium;">*</span>}}<span\; style="font-size:\; medium;">)</span><span\; style="font-size:\; medium;">=</span>{\mathrm{<span\; style="font-size:\; medium;">U</span>}}_{\mathrm{<span\; style="font-size:\; medium;">i</span>}}^{\text{<span style="font-size: medium;">*</span>}}$$

(β) Μικρότερη ή ίση απόδοση στις στρατηγικές που δεν παίζονται

Αν $p_i=0$:

$${\mathrm{<span\; style="font-size:\; medium;">u</span>}}_{\mathrm{<span\; style="font-size:\; medium;">i</span>}}<span\; style="font-size:\; medium;">(</span>{\mathrm{<span\; style="font-size:\; medium;">s</span>}}_{\mathrm{<span\; style="font-size:\; medium;">i</span>}}<span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">s</span>}}_{<span\; style="font-size:\; medium;">-</span>\mathrm{<span\; style="font-size:\; medium;">i</span>}}^{\text{<span style="font-size: medium;">*</span>}}<span\; style="font-size:\; medium;">)</span><span\; style="font-size:\; medium;">\le </span>{\mathrm{<span\; style="font-size:\; medium;">U</span>}}_{\mathrm{<span\; style="font-size:\; medium;">i</span>}}^{\text{<span style="font-size: medium;">*</span>}}$$

(γ) Κανονικοποίηση

$$\underset{\mathrm{<span\; style="font-size:\; medium;">i</span>}}{<span\; style="font-size:\; medium;">\sum </span>}{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">i</span>}}<span\; style="font-size:\; medium;">=</span>\mathrm{<span\; style="font-size:\; medium;">1</span>}$$

Αυτό είναι το καθαρό αλγεβρικό σύστημα που ορίζει το Nash.

🟦 2. ΠΑΡΑΣΤΑΣΗ ΜΕ ΜΗΤΡΕΣ (Matrix Form)

Για παιχνίδι 2 παικτών:

• Παίκτης 1 → μήτρα αποδόσεων $A$

• Παίκτης 2 → μήτρα αποδόσεων $B$

Μικτές στρατηγικές:

$$\mathrm{<span\; style="font-size:\; medium;">x</span>}<span\; style="font-size:\; medium;">=</span><span\; style="font-size:\; medium;">(</span>{\mathrm{<span\; style="font-size:\; medium;">x</span>}}_{\mathrm{<span\; style="font-size:\; medium;">1</span>}}<span\; style="font-size:\; medium;">,</span><span\; style="font-size:\; medium;">\dots </span><span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">x</span>}}_{\mathrm{<span\; style="font-size:\; medium;">m</span>}}<span\; style="font-size:\; medium;">)</span><span\; style="font-size:\; medium;">,</span>\mathrm{<span\; style="font-size:\; medium;">y</span>}<span\; style="font-size:\; medium;">=</span><span\; style="font-size:\; medium;">(</span>{\mathrm{<span\; style="font-size:\; medium;">y</span>}}_{\mathrm{<span\; style="font-size:\; medium;">1</span>}}<span\; style="font-size:\; medium;">,</span><span\; style="font-size:\; medium;">\dots </span><span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">y</span>}}_{\mathrm{<span\; style="font-size:\; medium;">n</span>}}<span\; style="font-size:\; medium;">)</span>$$

Απόδοση παίκτη 1:

$${\mathrm{<span\; style="font-size:\; medium;">U</span>}}_{\mathrm{<span\; style="font-size:\; medium;">1</span>}}<span\; style="font-size:\; medium;">=</span>{\mathrm{<span\; style="font-size:\; medium;">x</span>}}^{\mathrm{<span\; style="font-size:\; medium;">T</span>}}\mathrm{<span\; style="font-size:\; medium;">A</span>}\mathrm{<span\; style="font-size:\; medium;">y</span>}$$

Απόδοση παίκτη 2:

$${\mathrm{<span\; style="font-size:\; medium;">U</span>}}_{\mathrm{<span\; style="font-size:\; medium;">2</span>}}<span\; style="font-size:\; medium;">=</span>{\mathrm{<span\; style="font-size:\; medium;">x</span>}}^{\mathrm{<span\; style="font-size:\; medium;">T</span>}}\mathrm{<span\; style="font-size:\; medium;">B</span>}\mathrm{<span\; style="font-size:\; medium;">y</span>}$$

Συνθήκες Nash (με συμπληρωματική χαλαρότητα):

Για τον παίκτη 1:

$$\mathrm{<span\; style="font-size:\; medium;">A</span>}\mathrm{<span\; style="font-size:\; medium;">y</span>}<span\; style="font-size:\; medium;">\le </span>{\mathrm{<span\; style="font-size:\; medium;">U</span>}}_{\mathrm{<span\; style="font-size:\; medium;">1</span>}}\mathbf{<span\; style="font-size:\; medium;">1</span>}<span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">x</span>}}^{\mathrm{<span\; style="font-size:\; medium;">T</span>}}<span\; style="font-size:\; medium;">(</span>\mathrm{<span\; style="font-size:\; medium;">A</span>}\mathrm{<span\; style="font-size:\; medium;">y</span>}<span\; style="font-size:\; medium;">-</span>{\mathrm{<span\; style="font-size:\; medium;">U</span>}}_{\mathrm{<span\; style="font-size:\; medium;">1</span>}}\mathbf{<span\; style="font-size:\; medium;">1</span>}<span\; style="font-size:\; medium;">)</span><span\; style="font-size:\; medium;">=</span>\mathrm{<span\; style="font-size:\; medium;">0</span>}$$

Για τον παίκτη 2:

$${\mathrm{<span\; style="font-size:\; medium;">B</span>}}^{\mathrm{<span\; style="font-size:\; medium;">T</span>}}\mathrm{<span\; style="font-size:\; medium;">x</span>}<span\; style="font-size:\; medium;">\le </span>{\mathrm{<span\; style="font-size:\; medium;">U</span>}}_{\mathrm{<span\; style="font-size:\; medium;">2</span>}}\mathbf{<span\; style="font-size:\; medium;">1</span>}<span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">y</span>}}^{\mathrm{<span\; style="font-size:\; medium;">T</span>}}<span\; style="font-size:\; medium;">(</span>{\mathrm{<span\; style="font-size:\; medium;">B</span>}}^{\mathrm{<span\; style="font-size:\; medium;">T</span>}}\mathrm{<span\; style="font-size:\; medium;">x</span>}<span\; style="font-size:\; medium;">-</span>{\mathrm{<span\; style="font-size:\; medium;">U</span>}}_{\mathrm{<span\; style="font-size:\; medium;">2</span>}}\mathbf{<span\; style="font-size:\; medium;">1</span>}<span\; style="font-size:\; medium;">)</span><span\; style="font-size:\; medium;">=</span>\mathrm{<span\; style="font-size:\; medium;">0</span>}$$

Αυτό είναι η μητρωική μορφή του Nash.

🟩 3. LCP (Linear Complementarity Problem)

Το Nash μπορεί να γραφτεί ως:

$$\mathrm{<span\; style="font-size:\; medium;">z</span>}<span\; style="font-size:\; medium;">\ge </span>\mathrm{<span\; style="font-size:\; medium;">0</span>}<span\; style="font-size:\; medium;">,</span>\mathrm{<span\; style="font-size:\; medium;">M</span>}\mathrm{<span\; style="font-size:\; medium;">z</span>}<span\; style="font-size:\; medium;">+</span>\mathrm{<span\; style="font-size:\; medium;">q</span>}<span\; style="font-size:\; medium;">\ge </span>\mathrm{<span\; style="font-size:\; medium;">0</span>}<span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">z</span>}}^{\mathrm{<span\; style="font-size:\; medium;">T</span>}}<span\; style="font-size:\; medium;">(</span>\mathrm{<span\; style="font-size:\; medium;">M</span>}\mathrm{<span\; style="font-size:\; medium;">z</span>}<span\; style="font-size:\; medium;">+</span>\mathrm{<span\; style="font-size:\; medium;">q</span>}<span\; style="font-size:\; medium;">)</span><span\; style="font-size:\; medium;">=</span>\mathrm{<span\; style="font-size:\; medium;">0</span>}$$

όπου:

• $z$ = οι πιθανότητες των στρατηγικών

• $M$, $q$ = κατασκευάζονται από τις μήτρες $A$, $B$

Αυτό είναι LCP — και είναι PPAD-complete.

🟧 4. ΩΣ ΣΤΑΘΕΡΟ ΣΗΜΕΙΟ BROUWER

Το Nash είναι λύση της εξίσωσης:

$$\mathrm{<span\; style="font-size:\; medium;">f</span>}<span\; style="font-size:\; medium;">(</span>\mathrm{<span\; style="font-size:\; medium;">x</span>}<span\; style="font-size:\; medium;">)</span><span\; style="font-size:\; medium;">=</span>\mathrm{<span\; style="font-size:\; medium;">x</span>}$$

όπου $f$ είναι μια συνεχής απεικόνιση που “σπρώχνει” κάθε στρατηγική προς τις καλύτερες απαντήσεις.

Το θεώρημα Brouwer εγγυάται ότι υπάρχει πάντα τέτοιο σημείο.

🟪 5. ΩΣ PPAD ΠΡΟΒΛΗΜΑ

Το Nash ανήκει στην κλάση:

$$\text{<span style="font-size: medium;">PPAD</span>}$$

που σημαίνει:

• δεν ξέρουμε αν λύνεται σε πολυωνυμικό χρόνο

• αλλά πάντα υπάρχει λύση

• και μπορούμε να τη βρούμε ακολουθώντας ένα “μονοπάτι” (path-following)

Ο πιο γνωστός αλγόριθμος:

Lemke–Howson Algorithm

Ο οποίος βρίσκει Nash σε 2‑player games ακολουθώντας ένα μονοπάτι σε έναν πολυεδρικό γράφο.

🟫 6. ΓΕΩΜΕΤΡΙΑ SIMPLEX (ΤΡΙΓΩΝΟ)

Για παίκτη με 3 στρατηγικές:

$${\mathrm{<span\; style="font-size:\; medium;">\Delta </span>}}^{\mathrm{<span\; style="font-size:\; medium;">2</span>}}<span\; style="font-size:\; medium;">=</span><span\; style="font-size:\; medium;">\{</span><span\; style="font-size:\; medium;">(</span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">1</span>}}<span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">2</span>}}<span\; style="font-size:\; medium;">,</span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">3</span>}}<span\; style="font-size:\; medium;">)</span><span\; style="font-size:\; medium;">:</span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">i</span>}}<span\; style="font-size:\; medium;">\ge </span>\mathrm{<span\; style="font-size:\; medium;">0</span>}<span\; style="font-size:\; medium;">,</span>\text{<span style="font-size: medium;">\hspace{0.25em}\hspace{0.05em}</span>}{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">1</span>}}<span\; style="font-size:\; medium;">+</span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">2</span>}}<span\; style="font-size:\; medium;">+</span>{\mathrm{<span\; style="font-size:\; medium;">p</span>}}_{\mathrm{<span\; style="font-size:\; medium;">3</span>}}<span\; style="font-size:\; medium;">=</span>\mathrm{<span\; style="font-size:\; medium;">1</span>}<span\; style="font-size:\; medium;">\}</span>$$

Αυτό είναι τρίγωνο.

Για 4 στρατηγικές → τετράεδρο. Για 2 → γραμμή.

Η ισορροπία Nash είναι ένα σημείο μέσα στο προϊόν όλων αυτών των simplex.

🟥 7. ΠΩΣ ΣΥΝΔΕΟΝΤΑΙ ΟΛΑ ΜΑΖΙ

Αναπαράσταση	Τι δείχνει	Τι λύνει
Αλγεβρική	Συνθήκες ισορροπίας	Best responses
Μήτρες	Αποδόσεις	Γραμμικά συστήματα
LCP	Συμπληρωματικότητα	Nash ως πολυεδρικό πρόβλημα
Brouwer	Σταθερό σημείο	Ύπαρξη λύσης
PPAD	Υπολογιστική πολυπλοκότητα	Δυσκολία εύρεσης
Simplex	Γεωμετρία στρατηγικών	Οπτική κατανόηση

Όλα αυτά είναι ισοδύναμες μορφές του ίδιου πράγματος.

Πάμε, ναι. Θα σου φτιάξω ένα πολύ συγκεκριμένο 2×2 παιχνίδι και θα το λύσουμε:

• αλγεβρικά

• με μήτρες

• σαν LCP (σε ιδέα)

• γεωμετρικά (simplex)

Θα χρησιμοποιήσω το κλασικό Matching Pennies γιατί έχει καθαρό μικτό Nash.

1. Το παιχνίδι (2×2)

Δύο παίκτες, δύο στρατηγικές:

• Παίκτης 1: H (Κορώνα), T (Γράμματα)

• Παίκτης 2: H, T

Πίνακας αποδόσεων Παίκτη 1 (Παίκτης 2 παίρνει το αντίθετο):

$$A=\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$$

Άρα:

• Αν ταιριάζουν (H–H ή T–T) → Παίκτης 1 κερδίζει 1

• Αν δεν ταιριάζουν → Παίκτης 1 χάνει 1

2. Αλγεβρική λύση (μικτές στρατηγικές)

Έστω:

• Παίκτης 1: παίζει H με πιθανότητα $p$, T με $1-p$

• Παίκτης 2: παίζει H με πιθανότητα $q$, T με $1-q$

Απόδοση Παίκτη 1 αν παίξει H:

$$u_1(H)=q\cdot 1+(1-q)\cdot (-1)=2q-1$$

Απόδοση αν παίξει T:

$$u_1(T)=q\cdot (-1)+(1-q)\cdot 1=1-2q$$

Στην ισορροπία, ο Παίκτης 1 είναι αδιάφορος μεταξύ H και T (για να παίζει και τις δύο):

$$2q-1=1-2q\Rightarrow 4q=2\Rightarrow q=\frac{1}{2}$$

Ανάλογα για τον Παίκτη 2:

• Αν ο Παίκτης 1 παίζει H με $p$, T με $1-p$,

• θα βγει συμμετρικά ότι:

$$p=\frac{1}{2}$$

👉 Ισορροπία Nash:

$$p^{\text{*}}=\frac{1}{2},q^{\text{*}}=\frac{1}{2}$$

3. Μητρωική μορφή

Μικτές στρατηγικές:

$$x=\left(\begin{array}{c}p\\ 1-p\end{array}\right),y=\left(\begin{array}{c}q\\ 1-q\end{array}\right)$$

Απόδοση Παίκτη 1:

$$U_1=x^{T}Ay$$

Στην ισορροπία:

• $Ay$ δίνει τις αποδόσεις των καθαρών στρατηγικών του 1, δεδομένου $y$

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

Υπολογίζουμε:

$$Ay=\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)\left(\begin{array}{c}q\\ 1-q\end{array}\right)=\left(\begin{array}{c}2q-1\\ 1-2q\end{array}\right)$$

Στην ισορροπία, και οι δύο στρατηγικές του Παίκτη 1 παίζονται → πρέπει:

$$2q-1=1-2q\Rightarrow q=\frac{1}{2}$$

Ανάλογα, για τον Παίκτη 2 με μήτρα $B=-A$ βρίσκουμε $p=\frac{1}{2}$.

4. LCP (ιδέα, χωρίς να σε πνίξω σε σύμβολα)

Το ίδιο πρόβλημα μπορεί να γραφτεί ως:

$$z\ge 0,Mz+q\ge 0,z^T(Mz+q)=0$$

όπου το $z$ περιέχει:

• τις πιθανότητες των στρατηγικών

• και κάποιες “dual” μεταβλητές (τιμές αποδόσεων)

Για το συγκεκριμένο παιχνίδι, το LCP κωδικοποιεί:

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

• ότι οι υπόλοιπες δεν δίνουν μεγαλύτερη,

• και ότι όλα είναι ≥ 0.

Ο αλγόριθμος Lemke–Howson παίρνει αυτό το LCP και βρίσκει το σημείο:

$$(p^{\text{*}},q^{\text{*}})=(\frac{1}{2},\frac{1}{2})$$

5. Γεωμετρία (simplex)

Εδώ κάθε παίκτης έχει 2 στρατηγικές, άρα:

• ο χώρος μικτών στρατηγικών του καθενός είναι γραμμή $[0,1]$ (1‑simplex).

• Το συνολικό στρατηγικό προφίλ είναι σημείο στο τετράγωνο $[0,1]\times [0,1]$.

Το σημείο:

$$(\frac{1}{2},\frac{1}{2})$$

είναι ένα σημείο μέσα στο τετράγωνο όπου:

• καμία μονομερής αλλαγή $p$ ή $q$ δεν βελτιώνει την απόδοση του αντίστοιχου παίκτη.