Minimax regret criterion (Savage criterion) — קריטריון סאוו'יג'

קריטריון סאוו'יג' (המכונה גם קריטריון החרטה המינימלית) — אחת משיטות קבלת ההחלטות בתנאי אי-ודאות. הוא מיושם במצבים שבהם הסתברויות התוצאות השונות אינן ידועות, והמטרה היא מזעור ההפסדים הפוטנציאליים הנובעים מקבלת החלטה לא אופטימלית.

אפיון כללי

בתנאי אי-ודאות, השלכות בחירת כל אסטרטגיה אינן מוגדרות במדויק. להערכת האלטרנטיבות האפשריות משמשים מספר קריטריונים, כגון קריטריוני Wald, Hurwicz, Laplace ו-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)$.

קריטריון סאוו'יג' מבוסס על מושג החרטה (regret) או הרווח שנפספס. החרטה $r(s_i,{\theta }_j)$ עבור אסטרטגיה $s_i$ במצב טבע ${\theta }_j$ מוגדרת כהפרש בין הרווח המרבי האפשרי שניתן היה להשיג במצב טבע זה ${\theta }_j$ (אילו הייתה נבחרת האסטרטגיה האופטימלית עבור מצב זה) לבין הרווח בפועל מהאסטרטגיה $s_i$.

אלגוריתם יישום קריטריון סאוו'יג':

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. בחירת האסטרטגיה עם החרטה המרבית המינימלית (עיקרון המיניmax של חרטות): נבחרת האסטרטגיה $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)$

הערך המינימלי של החרטה המרבית המושג בשימוש בקריטריון סאוו'יג' שווה ל: $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)$

כך, קריטריון סאוו'יג' מכוון לבחירת האסטרטגיה המבטיחה את ההפסדים הקטנים ביותר ביחס לפעולה הטובה ביותר האפשרית לכל מצב טבע.

נקודות מפתח בניסוח המתמטי:

• הגדרת החרטה $r_{ij}$: זהו המושג המרכזי. חשוב להראות שהיא מחושבת כהפרש בין התוצאה הטובה ביותר בעמודה j לבין התוצאה הנוכחית a_{ij}.
• מטריצת החרטות $R$: מצוין במפורש כיצד היא נבנית.
• מציאת $r_i^{max}$: מוצג חיפוש המקסימום בכל שורה של מטריצת החרטות.
• עיקרון המיניmax: מנוסחת בבירור בחירת האסטרטגיה באמצעות $\arg min$ מתוך $max$ חרטות.
• סימונים בשימוש: סטנדרטיים לתורת המשחקים וקבלת ההחלטות (S, Θ, u, a_ij, r_ij, max, min, arg min).

יתרונות וחסרונות

יתרונות:

• מכוון למזעור סיכונים.
• יעיל במיוחד בתנאי אי-ודאות גבוהה.

חסרונות:

• מתעלם מהרווח הצפוי, תוך התמקדות בהפסדים אפשריים בלבד.
• עלול להוביל להחלטות שמרניות מדי.

קריטריונים לקבלת החלטות

• קריטריון Hurwicz
• קריטריון Laplace
• קריטריון Wald