Minimax regret criterion (Savage criterion) — Κριτήριο Ελάχιστης Μεταμέλειας

Κριτήριο Savage (γνωστό επίσης ως κριτήριο ελάχιστης μεταμέλειας) — μία από τις μεθόδους λήψης αποφάσεων υπό συνθήκες αβεβαιότητας. Εφαρμόζεται σε καταστάσεις όπου οι πιθανότητες των διαφόρων αποτελεσμάτων είναι άγνωστες, και ο στόχος είναι η ελαχιστοποίηση των πιθανών απωλειών λόγω λήψης μη βέλτιστης απόφασης.

Γενικά χαρακτηριστικά

Υπό συνθήκες αβεβαιότητας, οι συνέπειες της επιλογής κάθε στρατηγικής δεν καθορίζονται με ακρίβεια. Για την αξιολόγηση των πιθανών εναλλακτικών χρησιμοποιείται μια σειρά κριτηρίων, όπως τα κριτήρια Wald, Hurwicz, Laplace και Savage. Το κριτήριο Savage δεν είναι προσανατολισμένο στην επίτευξη μέγιστου κέρδους, αλλά στην ελαχιστοποίηση της μέγιστης μεταμέλειας (απωλειών σε σχέση με το καλύτερο δυνατό αποτέλεσμα).

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

Αλγόριθμος εφαρμογής του κριτηρίου Savage

• Διαμόρφωση πίνακα πληρωμών: Κατασκευάζεται πίνακας, του οποίου οι γραμμές αντιστοιχούν στις δυνατές στρατηγικές και οι στήλες στα δυνατά αποτελέσματα των γεγονότων. Στη διασταύρωση καταγράφεται το αναμενόμενο αποτέλεσμα για τη συγκεκριμένη στρατηγική και αποτέλεσμα.
• Κατασκευή πίνακα μεταμελειών (πίνακα κινδύνων): Για κάθε αποτέλεσμα (στήλη) προσδιορίζεται η μέγιστη τιμή κέρδους. Στη συνέχεια για κάθε κελί υπολογίζεται το μέγεθος της μεταμέλειας:
• Προσδιορισμός των μέγιστων μεταμελειών για κάθε στρατηγική: Σε κάθε γραμμή του πίνακα μεταμελειών επιλέγεται η μέγιστη τιμή (η χειρότερη περίπτωση για τη δεδομένη στρατηγική).
• Επιλογή βέλτιστης στρατηγικής: Επιλέγεται η στρατηγική για την οποία η μέγιστη μεταμέλεια είναι ελάχιστη.

Έτσι, το κριτήριο Savage υλοποιεί την αρχή της ελαχιστοποίησης της πιθανής ζημίας από λανθασμένη απόφαση.

Μαθηματική διατύπωση

Έστω δοθέντα:

• $S=\{s_1,s_2,\dots ,s_m\}$ — σύνολο διαθέσιμων στρατηγικών (εναλλακτικών).
• $\Theta =\{{\theta }_1,{\theta }_2,\dots ,{\theta }_n\}$ — σύνολο δυνατών καταστάσεων φύσης.
• $u(s_i,{\theta }_j)$ — συνάρτηση κέρδους (χρησιμότητας) κατά την επιλογή στρατηγικής $s_i$ και επέλευση κατάστασης ${\theta }_j$. Συχνά αναπαρίσταται ως πίνακας πληρωμών $A=[a_{ij}]$, όπου $a_{ij}=u(s_i,{\theta }_j)$.

Το κριτήριο Savage βασίζεται στην έννοια της μεταμέλειας (regret) ή χαμένου οφέλους. Η μεταμέλεια $r(s_i,{\theta }_j)$ για τη στρατηγική $s_i$ υπό την κατάσταση φύσης ${\theta }_j$ ορίζεται ως η διαφορά μεταξύ του μέγιστου δυνατού κέρδους που θα μπορούσε να επιτευχθεί για τη δεδομένη κατάσταση φύσης ${\theta }_j$ (εάν είχε επιλεγεί η βέλτιστη στρατηγική για αυτήν την κατάσταση) και του πραγματικού κέρδους από τη στρατηγική $s_i$.

Αλγόριθμος εφαρμογής του κριτηρίου Savage:

1. Υπολογισμός πίνακα μεταμελειών (κινδύνων):

   α) Εύρεση μέγιστου κέρδους για κάθε κατάσταση φύσης (κάθε στήλη του πίνακα πληρωμών):

   $u_j^{\ast }=\underset{k=1,\dots ,m}{max}u(s_k,{\theta }_j)=\underset{k=1,\dots ,m}{max}{a}_{kj}$

   Αυτό είναι το καλύτερο δυνατό αποτέλεσμα εάν επέλθει η κατάσταση ${\theta }_j$.

   β) Υπολογισμός στοιχείων του πίνακα μεταμελειών $R=[r_{ij}]$:**

   $r_{ij}=r(s_i,{\theta }_j)=u_j^{\ast }-u(s_i,{\theta }_j)=(\underset{k=1,\dots ,m}{max}{a}_{kj})-a_{ij}$

   Το στοιχείο $r_{ij}$ δείχνει κατά πόσο το κέρδος από τη στρατηγική $s_i$ είναι μικρότερο από το μέγιστο δυνατό υπό την κατάσταση ${\theta }_j$. Όλα τα στοιχεία $r_{ij}\ge 0$.

1. Εύρεση μέγιστης μεταμέλειας για κάθε στρατηγική: Για κάθε στρατηγική $s_i$ (κάθε γραμμή του πίνακα μεταμελειών $R$) προσδιορίζεται η χειρότερη δυνατή έκβαση από άποψη μεταμέλειας:

   $r_i^{max}=\underset{j=1,\dots ,n}{max}{r}_{ij}=\underset{j=1,\dots ,n}{max}((\underset{k=1,\dots ,m}{max}{a}_{kj})-a_{ij})$

1. Επιλογή στρατηγικής με ελάχιστη μέγιστη μεταμέλεια (αρχή minimax μεταμελειών): Επιλέγεται εκείνη η στρατηγική $s_{\text{Savage}}^{\ast }$ που ελαχιστοποιεί τη βρεθείσα μέγιστη μεταμέλεια:

   $s_{\text{Savage}}^{\ast }=\arg \underset{i=1,\dots ,m}{min}(r_i^{max})=\arg \underset{s_i\in S}{min}(\underset{{\theta }_j\in \Theta }{max}r(s_i,{\theta }_j))$

   Ή, αντικαθιστώντας την έκφραση για $r_{ij}$:

   $s_{\text{Savage}}^{\ast }=\arg \underset{i=1,\dots ,m}{min}\left(\underset{j=1,\dots ,n}{max}[(\underset{k=1,\dots ,m}{max}{a}_{kj})-a_{ij}]\right)$

Η ελάχιστη τιμή της μέγιστης μεταμέλειας που επιτυγχάνεται με τη χρήση του κριτηρίου Savage είναι: $V_{\text{Savage}}=\underset{i=1,\dots ,m}{min}(r_i^{max})=\underset{i=1,\dots ,m}{min}\left(\underset{j=1,\dots ,n}{max}{r}_{ij}\right)$

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

Βασικά σημεία στη μαθηματική διατύπωση:

• Ορισμός μεταμέλειας $r_{ij}$: Αυτή είναι η κεντρική έννοια. Είναι σημαντικό να φανεί ότι υπολογίζεται ως διαφορά μεταξύ του καλύτερου αποτελέσματος στη στήλη j και του τρέχοντος αποτελέσματος a_{ij}.
• Πίνακας μεταμελειών $R$: Αναφέρεται ρητά ο τρόπος κατασκευής του.
• Εύρεση $r_i^{max}$: Παρουσιάζεται η αναζήτηση μεγίστου σε κάθε γραμμή του πίνακα μεταμελειών.
• Αρχή minimax: Διατυπώνεται σαφώς η επιλογή στρατηγικής μέσω $\arg min$ από $max$ μεταμελειών.
• Χρησιμοποιούμενες συμβολίσεις: Τυπικές για τη θεωρία παιγνίων και λήψης αποφάσεων (S, Θ, u, a_ij, r_ij, max, min, arg min).

Πλεονεκτήματα και μειονεκτήματα

Πλεονεκτήματα:

• Προσανατολισμένο στην ελαχιστοποίηση κινδύνων.
• Ιδιαίτερα αποτελεσματικό υπό συνθήκες υψηλής αβεβαιότητας.

Μειονεκτήματα:

• Αγνοεί το αναμενόμενο κέρδος, εστιάζοντας μόνο στις πιθανές απώλειες.
• Μπορεί να οδηγεί σε υπερβολικά συντηρητικές αποφάσεις.

Κριτήρια λήψης αποφάσεων

• Κριτήριο Hurwicz
• Κριτήριο Laplace
• Κριτήριο Wald