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

יישומים של תורת המשחקים

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

מכרזים - מכרז מחיר שני

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

לדוגמא: אם חיים הציע 2 ₪ משה הציע 5 ₪ ודוד הציע 20 ₪, דוד יזכה במכרז ויצטרך לשלם רק 5 ש"ח למרות שהוא הציע הרבה יותר.

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

בשיטת מכרז זו קיים שיווי משקל באסטרטגיות שולטות חלש, כשכל שחקן מציע את הערך האמיתי, עבורו, של הפריט המוצע למכירה:

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

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

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

הרשת החברתית Facebook מוכרת שטחי פירסום באתר שלה בשיטת מכרז מחיר שני, שבה המפרסמים שבוחרים לפרסם לפי קרטריונים דומים (כמו לדוגמא, פרסומות לאותה שכבת גיל, אותו מגדר ואותו מיקום גיאוגרפי) מתחרים זה מול זה במכרז מחיר שני. שיטה זו עוזרת לFacebook להעריך את השווי האמיתי של שטחי הפירסום שלה ורמת הביקוש לפרסומות באתר.

מיזוגים ורכישות

בשנת 1988 התקיים מכרז להשתלטות על חברת הקמעונאות, Federated, חברת האב של הרשת בלומינגדיילס. במכרז השתתפו שתי חברות- Macy’s ו-Campeau. שתי החברות שהיו מעוניינות במיזוג חברת Federated לתוך החברה שלהן היו צריכות לקנות 50% או יותר ממניות חברת Federated אשר היו מוחזקות בידי פרטים שונים.

הפירוט להלן הוא פישוט של תהליך המיזוג הארוך שהתרחש, שבסופו ניצחה Campeau, אולם זמן מה לאחר הרכישה החברה פשטה את הרגל וכיום Macy’s Inc היא ההמשך של חברת Federated.

מחיר מניית Federated בשוק היה 60$, וזו היה גם המחיר הצפוי של מניית החברה לאחר רכישתה בידי אחת החברות המתחרות.

Macy’s הציע הצעת רכישה של 70$ למניה, בתנאי שיקבלו יותר מ50% מהמניות.

Campeau לעומת זאת, הציעה 74$ למניה, ללא תנאי מקדים. במידה ויותר מ50% מהמניות היו מוצעות למכירה, Campeau הייתה משלמת,לכל מניה, $74-14*(x\%-50\%)/100\%$ כש%X הוא אחוז המניות הנמכרות. כלומר, אם 100% מהמניות היו מוצעות למכירה, Campeau הייתה משלמת רק 67$ למניה.

חברת Campeau עשתה שימוש באסטרטגיות שולטות כדי להבטיח את השתלטות על Federated תוך כדי תשלום נמוך יותר.

הסבר האסטרטגיה השולטת:

לכל המוכרים היה עדיף למכור את המניות שלהם לCampeau משום שהם הציעו מחיר גבוה יותר למניה. אם 50% מהמניות כבר הובטחו לCampeau להצעה של Macy’s לא הייתה משמעות, משום שהצעה של מעל 50% מהמניות למכירה תמורת 70$ לא הייתה אפשרית, במצב זה מוכרי המניות היו מעדיפים למכור את מניותיהם לCampeau ברווח נמוך יותר, על פני הישארות עם מניות בשווי של 60$.

ניתן לקרוא פירוט של תהליך המיזוג בלינק הבא: Campeau Corp.’s Acquisition of Federated Department Stores

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

שידוך יציב

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

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

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

על ידי אלגוריתם פשוט יחסית ניתן ליצור התאמה שבה אין זוגות של בית חולים ומתמחה שאינם מרוצים.

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

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

שימוש נוסף של משחק זה הוא בשידוך של תורמי כליות לנזקקים לתרומות.

מידע נוסף ניתן למצוא במאמר שפורסם באוניברסיטת הרווארד: Matching and market design כמו כן ניתן לקרוא על נושא זה גם בספר תורת המשחקים של שמואל זמיר, מיכאל משלר ואילון סולן.

משחק המפקח – אסטרטגיות מעורבות

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

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

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

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

התועלת של הסובייטים מביצוע ניסוי גרעיני שלא התגלה: 1, וביצוע ניסוי שהתגלה: 0

התועלת של האמריקאים מגילוי ניסוי גרעיני: 1, ואי-גילוי של ניסוי שהתבצע: 0

אם הסובייטים לא ביצעו ניסוי כלל, התועלת שלהם היא $1>{\beta }>0$ והתועלת של האמריקאים הינה ${\alpha }>1$

בפיתוח של משחק זה מתגלה שכדי שארה"ב תבטיח לעצמה את התועלת המקסימלית האפשרית, ארה"ב צריכה להשתמש באסטרטגיה מעורבת שבה היא מגרילה את המועד שבו פקחיה מגיעים לבדיקה. לפי אסטרטגיה זו, מועד הבדיקה הראשון יוגרל בהסתברות $(1-\beta )/(2-\beta )$ . לא רק זאת, אלא גם שלאמריקאים כדאי לגלות סיכויים אלה לסובייטים, כדי שהם יבצעו את המהלך המשתלם ביותר בשבילם שהוא הגרלה בסיכוי של $\alpha /(1-\alpha )$ לבצע את הניסוי הגרעיני במועד הראשון. מצב זה, שבו האמריקאים יכולים לגלות את האסטרטגיה המוערבת שלהם, ולהתחייב אליה, מביא לשיווי משקל עם התועלות הגבוהות ביותר לשני הצדדים.

חומר נוסף לגבי ההיסטוריה בנושא ניתן לקרוא באתר של משרד ההגנה האמריקאי

ניתן למצוא את המקור לדוגמא הנ"ל במאמר זה: מיכאל משלר, Inspection Games ניתן לקרוא על פיתוחים נוספים למשחק המתואר, ומשחקי פיקוח אחרים במאמר זה: רודולף אבנהאוס, ברנרד וון סטנגל ושמואל זמיר, Inspection Games

ניתוח משחק הטניס

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

ניתוח עוצמת הגשת מכת הפתיחה

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

נתוני עבר מראים שהגשה בעוצמה חזקה הינה תקינה (ללא שגיאה) בהסתברות 0.65 וההסתברות שהשחקן המגיש ינצח את המשחקון בהינתן שההגשה הייתה בעוצמה חזקה היא 0.75. בנוסף, הגשה בעוצמה בינונית הינה תקינה בהסתברות 0.9 וההסתברות שהשחקן המגיש ינצח את המשחקון בהינתן שההגשה הייתה בעוצמה בינונית היא 0.5.

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

לשחקן המגיש ישנן ארבע אפשריות: ראשונה חזקה ובמקרה שנדרשת הגשה שנייה היא תהיה חזקה(S,S), ראשונה חזקה ובמקרה שנדרשת הגשה שנייה היא תהיה בינונית(S,M), ראשונה בינונית ובמקרה שנדרשת הגשה שנייה היא תהיה חזקה(M,S), ראשונה בינונית ובמקרה שנדרשת הגשה שנייה היא תהיה בינונית(M,M). כל אפשרות כזו משרה הגרלה מסויימת שתוצאותיה הן ניצחון או הפסד.

באיזו הגרלה עדיף לשחקן המגיש לבחור?

נערוך כעת את חישובי ההסתברויות לכל אפשרות:

$P({S,S})=0.65*0.75+0.35*0.65*0.75=0.658125$

$P({S,M})=0.65*0.75+0.35*0.9*0.5=0.645$

$P({M,S})=0.9*0.5+0.1*0.65*0.75=0.49875$

$P({M,M})=0.9*0.5+0.1*0.9*0.5=0.495$

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

ניתוח כיוון מכת הפתיחה

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

נציג את הסיטואציה הנ"ל כמשחק בצורה אסטרטגית, שבו התשלומים לכל שחקן הם הסיכוי של השחקן לנצח במשחקון.

	מקבל בוחר ימין	מקבל בוחר שמאל
מגיש בוחר ימין	$\pi _{RR},1-\pi _{RR}$	$\pi _{RL},1-\pi _{RL}$
מגיש בוחר שמאל	$\pi _{LR},1-\pi _{LR}$	$\pi _{LL},1-\pi _{LL}$

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

כלומר, מתקיים ש: $\pi _{RR}<\pi _{LR},\pi _{LL}<\pi _{RL}$

באופן דומה, אם המקבל יתכונן לכיוון אחר מהכיוון בו בחר המגיש אז סיכויי המגיש לנצח יהיו גבוהים יותר. כלומר מתקיים ש: $\pi _{RR}<\pi _{RL},\pi _{LL}<\pi _{LR}$

המסקנה מהאי שיוונים שהנחנו היא כי במשחק הנ"ל אין שיווי משקל נאש באסטרגיות טהורות:

1. התגובה הטובה ביותר של המגיש לבחירה של המקבל באסטרטגיה "ימין" היא בחירה באסטרטגיה "שמאל" כיוון ש $\pi _{RR}<\pi _{LR}$.
2. התגובה הטובה ביותר של המקבל לבחירה של המגיש באסטרטגיה "שמאל" היא בחירה באסטרטגיה "שמאל" כיוון ש $1-\pi _{LR}<1-\pi _{LL}\Leftrightarrow \pi _{LR}>\pi _{LL}$.
3. התגובה הטובה ביותר של המגיש לבחירה של המקבל באסטרטגיה "שמאל" היא בחירה באסטרטגיה "ימין" כיוון ש $\pi _{RL}>\pi _{LL}$.
4. תגובה הטובה ביותר של המקבל לבחירה של המגיש באסטרטגיה "ימין" היא בחירה באסטרטגיה "ימין" כיוון ש $1-\pi _{RL}<1-\pi _{RR}\Leftrightarrow \pi _{RL}>\pi _{RR}$.

נניח כעת שכל שחקן יכול לבחור באסטרטגיה מעורבת. כלומר, המגיש יכול להחליט שבהסתברות $x$ ישחק ימין ובהסתברות $1-x$ ישחק שמאל והמקבל יכול להחליט לשחק בהסתברות $y$ ימין ובהסתברות $1-y$ לשחק שמאל. משפט נאש מבטיח לנו כי במשחק קיים שיווי משקל באסטרטגיות מעורבות.

נניח רק לשם הדוגמה את הסיכויים הבאים:

	מקבל בוחר ימין	מקבל בוחר שמאל
מגיש בוחר ימין	$0.1,0.9$	$0.7,0.3$
מגיש בוחר שמאל	$0.8,0.2$	$0.4,0.6$

(אנחנו מניחים שידו החזקה של המקבל היא ימין וכי הוא מתקשה יותר בחבטות גב יד מאשר בחבטות כף יד ולכן במקרה זה $\pi _{LL}>\pi _{RR}$)

חישוב של שיווי משקל באסטרטגיות מעורבות מגלה כי האסטרטגיה המעורבות $(x^{*},y^{*})=(0.4,0.3)$ הינה שיווי משקל של המשחק באסטרטגיות מעורבות. התשלום לשחקן המגיש במקרה זה הוא $0.4*0.3*0.1+0.6*0.3*0.8+0.4*0.7*0.7+0.6*0.7*0.4=0.52$ והתשלום לשחקן המקבל הוא $0.4*0.3*0.9+0.6*0.3*0.2+0.4*0.7*0.3+0.6*0.7*0.6=0.48$.

המסקנה מניתוח זה היא שבשיווי משקל, ב60% מהמקרים המגיש בוחר להגיש לשמאלו של המקבל, בד בבד שהמקבל מכין עצמו להגשה שכזו ב70% מהמקרים.

האם במציאות שחקני הטניס נוקטים באסטרטגיות מעורבות?

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

בנוסף, תחרות בשיווי משקל גוררת כי אסטרטגיות של כל שחקן ייבחרו באופן מקרי ובלתי תלוי באסטרטגיות אחרות במשך התחרות. המבחנים של Walker and Wooders הצביעו ששחקנים מחליפים את כיווני ההגשות משמאל לימין לעיתים תכופות מדי. מחקרים בפסיכולוגיה וכלכלה מראים שאנשים המנסים להתנהג באופן מקרי נוטים להחליף בחירות לעיתים תכופות מדי מה שמעיד לטענת Walker and Wooders על כך שהבחירות אינן בלתי תלויות. בעבודת המשך של Shih-Hsun Hsu, Chen-Ying Huang and Cheng-Tao Tang מ-2003 הוצגו ממצאים סטיסטיים המאששים את ההשערה כי אסטרטגיות השחקנים נבחרות באופן בלתי תלוי. בנוסף הם מצאו שבחירת ההגשה הנוכחית תלויה במשתנים שונים כמו איכות ההגשות הקודמות או משך זמן המשחק. ממצא זה הוביל אותם להראות כי ישנו מודל למידה שמתאר את המשחק בצורה מתאימה יותר מאשר שיווי משקל נאש.

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, הוצאת הספרים ע"ש י"ל מאגנס, 2008.
• אביעד חפץ, חשיבה אסטרטגית: תורת המשחקים ושימושיה בכלכלה וניהול, האוניברסיטה הפתוחה, 2008.

• Walker, M. and Wooders, J. (2001). “Minimax Play at Wimbledon,” American Economic Review 91, 1521-1538
• Hsu, S. H., C. Y. Huang, and C. T. Tang (2004): “Equilibrium at Wimbledon, or simple rules? An empirical study,” National Taiwan University Working Paper, p. 50.

הערות שוליים

קטגוריה:תורת המשחקים