משתמש:Dor Minzer/ארגז חול

בתורת המשחקים ובאקולוגיה התנהגותית, אסטרטגיה יציבה אבולוציונית (באנגלית: Evolutionarily Stable Strategy, בקיצור ESS) היא אסטרטגיה שכאשר היא משוחקת על ידי רוב הפרטים באוכלוסייה, היא מונעת התפשטות של אסטרטגיות אחרות באוכלוסייה. כלומר, בהינתן אוכלוסייה שבה ננקטת אסטרטגיה יציבה אבולוציונית, ברירה טבעית הינה תנאי מספיק למניעת התפשטות אסטרטגיות אלטרנטיביות (מוטציות).

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

אינטואיציה

נתבונן במשחק שני שחקנים המתואר על-ידי מטריצת התשלומים:

	יונה (D)	נץ (H)
יונה (D)	(3,3)	(1,5)
נץ (H)	(5,1)	(0,0)

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

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

אם נניח שבאוכלוסיה יש 50% נצים ו50% יונים, כיצד פרט "יעדיף" להיוולד? אם הוא ייוולד כיונה, תוחלת מספר הצאצאים תהיה $~2~$, ואם ייוולד כנץ, תוחלת מספר הצאצאים תיהיה ${\frac {5}{2}}$, לכן במקרה זה יעדיף הפרט להיוולד נץ. במצב כזה שכיחות הנצים באוכלוסיה תגדל, ולכן האסטרטגיה המעורבת $[{\frac {1}{2}}(D),{\frac {1}{2}}(H)]$ אינה יציבה אבולוציונית. המשמעות של אסטרטגיה יציבה אבולוציונית היא שכאשר האוכלוסייה נמצאת ביחס כזה, הפרט אדיש בין היוולדות כנץ לבין היוולדות כיונה. כלומר, היחס בין מספר הנצים לבין מספר היונים באוכלוסיה נשמר.

הגדרה פורמלית

נתון משחק שני שחקנים סימטרי בצורה אסטרטגית,ותהי $\!u_{1}(x,y)$ פונקציית התועלת של שחקן 1 כאשר הוא משחק את האסטרטגיה המעורבת $\!x$ והשחקן השני משחק לפי האסטרטגיה המעורבת $\!y$. אסטרטגיה $\!x^{*}$ נקראת אסטרטגיה יציבה אבולוציונית, אם ורק אם לכל אסטרטגיה מעורבת$\!x\neq \!x^{*}$ קיים $\epsilon _{0}>0$ כך שלכל $0<\epsilon <\epsilon _{0}$ מתקיים $(1-\epsilon )u_{1}(x,x^{*})+\epsilon u_{1}(x,x)<(1-\epsilon )u_{1}(x^{*},x^{*})+\epsilon u_{1}(x^{*},x)$.

משמעות ההגדרה

נניח שהתפלגות הטיפוסים באוכלוסיה היא $\!x^{*}$. משמעות התנאי היא שאם באוכלוסיה השכיחות של המוטציה $\!x$ היא $\epsilon$,אז בהסתברות $\epsilon$ היא פוגשת מוטציה מאותו סוג ומקבל תשלום $u_{1}(x,x)$. בהסתברות $1-\epsilon$ היא פוגשת טיפוס לפי התפלגות $\!x^{*}$ ומקבלת תשלום $u_{1}(x,x^{*})$. בסך-הכל תועלתה היא $(1-\epsilon )u_{1}(x,x^{*})+\epsilon u_{1}(x,x)$(אגף שמאל של האי שוויון לעיל). צד ימין של האי-שוויון מתאר באופן דומה את תועלתו של פרט מסוג $\!x^{*}$. לכן משמעות התנאי היא שתועלת פרט מטיפוס $\!x^{*}$ גדולה מתועלת פרט מטיפוס $\!x$. בצורה כזאת שכיחות המוטציה תקטן והתפלגות האוכלוסייה תתקרב ל$\!x^{*}$.

נניח ש$\!x^{*}$ אסטרטגיה יציבה אבולוציונית. אז לכל $\!x\neq \!x^{*}$ נקבל שהאי שוויון למעלה מתקיים עבור ערכי $\epsilon$ קרובים לאפס, וע"י השאפה ${\epsilon \to 0}$ נקבל את האי שוויון $u_{1}(x,x^{*})\leq u_{1}(x^{*},x^{*})$. כלומר אם פרט סוטה מהאסטרטגיה המעורבת $\!x^{*}$ הוא לא מרוויח, לכן נקבל ש$(x^{*},x^{*})$ שיווי משקל נאש סימטרי.

טענה

אסטרטגיה מעורבת $\!x^{*}$ היא אסטרטגיה יציבה אבולוציונית אם ורק אם לכל $\!x\neq \!x^{*}$ מתקיים בדיוק אחד משני התנאים:

1. $\!u_{1}(x,x^{*})<u_{1}(x^{*},x^{*})$
2. $\!u_{1}(x,x^{*})=u_{1}(x^{*},x^{*})$ וגם $\!u_{1}(x,x)<u_{1}(x^{*},x)$

הוכחה

כיוון ראשון: אם$\!x^{*}$ יציבה אבולוציונית, אז לכל $\!x\neq \!x^{*}$ מתקיים $u_{1}(x,x^{*})\leq u_{1}(x^{*},x^{*})$. אם תנאי (1) מתקיים-סיימנו. אחרת, בהכרח ש $u_{1}(x,x^{*})=u_{1}(x^{*},x^{*})$. על-פי ההגדרה עבור $\epsilon$ חיובי קטן מספיק מתקיים $(1-\epsilon )u_{1}(x,x^{*})+\epsilon u_{1}(x,x)<(1-\epsilon )u_{1}(x^{*},x^{*})+\epsilon u_{1}(x^{*},x)$, ולפי השוויון נקבל ש $\epsilon u_{1}(x,x)<\epsilon u_{1}(x^{*},x)$, ולכן מתקיים תנאי (2).

כיוון שני: אם עבור $\!x\neq \!x^{*}$ תנאי (1) מתקיים, אז האי שוויון בהגדרה שקול ל $\epsilon (u_{1}(x,x)-u_{1}(x^{*},x)+u_{1}(x^{*},x^{*})-u_{1}(x,x^{*}))<u_{1}(x^{*},x^{*})-u_{1}(x,x^{*})$. לכן אם נבחר $\epsilon _{0}={\frac {u_{1}(x^{*},x^{*})-u_{1}(x,x^{*})}{4M}}$, כאשר $M$ הוא התשלום המקסימלי, אז האי שוויון בהגדרה יתקיים עבור כל $0<\epsilon <\epsilon _{0}$.

אם תנאי (2) מתקיים, אפשר לבחור $\epsilon _{0}=1$.

דוגמאות

• בדוגמא לעיל,

	יונה (D)	נץ (H)
יונה (D)	(3,3)	(1,5)
נץ (H)	(5,1)	(0,0)

קל לראות שהאסטרטגיות $(D,H),(H,D)$ הן ש"מ באסטרטגיות טהורות, אך הן לא סימטריות ולכן אינן שיווי משקל יציב אבולוציונית. האסטרטגיה המעורבת $\!x^{*}=[{\frac {1}{3}}(D),{\frac {2}{3}}(H)]$ היא שיווי משקל נאש סימטרי היחיד במשחק. עבור אסטרטגיה מעורבת $\!x=[x(D),(1-x)(H)]$, מתקיים:

$u(x^{*},x^{*})={\frac {5}{3}}=u(x,x^{*}),u(x,x)=6x-3x^{2},u(x^{*},x)=4x+{\frac {1}{3}}$

לכן:

$u(x^{*},x)-u(x,x)=3x^{2}-2x+{\frac {1}{3}}=3(x-{\frac {1}{3}})^{2}>0~\forall x\neq {\frac {1}{3}}$

מכאן ש $\!x^{*}$ יציבה אבולוציונית.

• נתבונן באוכלוסיית חיפושיות, שבהן יש חיפושיות קטנות(S) וחיפושיות גדולות(L).

	S	L
S	(5,5)	(1,8)
L	(8,1)	(3,3)

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

במשחק הזה קיים שיווי משקל נאש יחיד והוא $(L,L)$. נוכיח שהאסטרטגיה $L$ יציבה אבולוציונית.

עבור אסטרטגיה מעורבת $\!x=[x(S),(1-x)(L)]$, $u_{1}(x,L)=x+3(1-x)=3-2x<3=u_{1}(L,L)$

לכן על-פי הטענה האסטרטגיה $L$ יציבה אבולוציונית. המשמעות האינטואיטיבית היא שבהינתן אוכלוסיה של חיפושיות קטנות, אם נוסיף לה מספר קטן של חיפושיות גדולות- השכיחות של החיפושיות הגדולות באוכלוסיה תגדל עם הזמן, מכיוון שחיפושית גדולה לרוב תפגוש חיפושית קטנה. במקרה זה היא תוליד 8 צאצאים לעומת צאצא אחד של החיפושית הקטנה. במצב ההפוך בו נתונה אוכלוסיה שרובה חיפושיות גדולות, השכיחות של החיפושיות הקטנות באוכלוסיה לא תגדל כי הן לרוב יפגשו חיפושית גדולה- ויולידו רק צאצא אחד ורק לעתים נדירות יפגשו חיפושית קטנה.

• חשוב לציין שלא לכל משחק שני שחקנים סימטרי יש אסטרטגיה יציבה אבולוציונית. נתבונן במשחק "אבן (R), נייר (P) ומספריים (S)":

	R	P	S
R	(${\frac {2}{3}}$,${\frac {2}{3}}$)	(0,1)	(1,0)
P	(1,0)	(${\frac {2}{3}}$,${\frac {2}{3}}$)	(0,1)
S	(0,1)	(1,0)	(${\frac {2}{3}}$,${\frac {2}{3}}$)

למשחק זה אין שיווי משקל נאש באסטרטגיות טהורות. כמוכן, בשיווי משקל באסטרטגיות מעורבות שחקן חייב לשחק את שלוש האסטרטגיות הטהורות בהסתברות חיובית. אחרת, נניח שהוא משחק רק אבן ונייר. אז השחקן השני ישחק נייר והשחקן הראשון יקבל תשלום אפס. מעקרון האדישות ניתן להסיק שהאסטרטגיות הן בהכרח $\!x^{*}=[{\frac {1}{3}}(R),{\frac {1}{3}}(P),{\frac {1}{3}}(S)]$. לכן למשחק זה קיים שיווי משקל נאש יחיד באסטרטגיות מעורבות. נראה שזו לא אסטרטגיה יציבה אבולוציונית. ניקח $\!x=[1(R),0(P),0(S)]$, אז: $u(x,x^{*})={\frac {1}{3}}*{\frac {2}{3}}+{\frac {1}{3}}*0+{\frac {1}{3}}*1={\frac {5}{9}}$, $u(x^{*},x^{*})={\frac {1}{9}}*({\frac {2}{3}}+1+{\frac {2}{3}}+1+{\frac {2}{3}}+1)={\frac {5}{9}}$ כלומר, $u(x,x^{*})=u(x^{*},x^{*})$.

$u(x,x)={\frac {2}{3}}$, $u(x^{*},x)={\frac {5}{9}}$ ולכן $u(x,x)>u(x^{*},x)$, ולכן על פי הטענה זוהי לא אסטרטגיה יציבה אבולוציונית.

ראו גם

• מונחים בתורת המשחקים

לקריאה נוספת

• ריצ'רד דוקינס, הגן האנוכיי, תרגם עמנואל לוטם, הוצאת דביר, מהדורה שנייה, 1991. ISBN 0-19-286092-5.
• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, הוצאת הספרים ע"ש י"ל מאגנס, 2008.
• ISBN 0262231816, Weibull (1995): Evolutionary game theory. MIT Press.

קישורים חיצוניים

• יהודה בלו, היונה והנץ – על אסטרטגיה יציבה מבחינה אבולוציונית, באתר "רשימות מן התיבה הלבנה", 1 בפברואר 2007