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

https://twitter.com/OmerMadmon/status/1571471728798302209

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

https://twitter.com/OmerMadmon/status/1574734233645424640

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

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

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

אז מה עושים?

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

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

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

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

שיווי משקל מתואם

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

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

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

שאלה מתבקשת כעת, שמזכירה את הגישה שנקטנו כשדיברנו על ערך שפלי[1] או פתרון נאש לבעיות מיקוח[2], היא- אילו תכונות (אקסיומות) היינו מצפים שפונקציית בחירה חברתית כזו תקיים? כלומר, איך אפשר לייצר בצורה הוגנות יחס העדפות של כל הקבוצה, בהינתן העדפות של כל אחד מהפרטים?

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

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

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

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

אז מה המשמעות? זהו, הכל אבוד?

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

(למשל: ביצוע אגרגציה של מספר מודלי סיווג שונים עבור אותו הדאטהסט).

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

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

[1] https://twitter.com/OmerMadmon/status/1587351266484797440
[2] https://twitter.com/OmerMadmon/status/1635575430483943425

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


https://twitter.com/OmerMadmon/status/1644981785384611841

בחירה חברתית, הוגנות ודיקטטורה

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

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

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

(S צריכה להיות קומפקטית וקמורה, אבל לא ניכנס זה)

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

בתור דוגמא, בואו נחשוב על זוג יזמים שעומדים לקראת סגירת עסקה שתניב להם רווח משותף של 100 מיליון דולר.>

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

בעיית המיקוח המתאימה לסיפור הזה מתוארת על ידי הקבוצה S שהיא המשולש המתואר בתמונה[1], ונקודת אי ההסכמה d=(0,0).

בהינתן בעיית מיקוח כלשהי, השאלה המתבקשת היא- מה צריך להיות ההסכם בין שני השחקנים? נרצה למצוא מושג פתרון, שהוא פונקציה שתתאים לכל בעיית מיקוח (S,d) פתרון אפשרי (כלומר, כזה שנמצא בתוך הקבוצה S).

אז בואו נחשוב- אילו תכונות היינו מצפים שמושג פתרון שכזה יקיים?

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

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

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

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

אז האם יש מושג פתרון שמקיים את כל ארבע התכונות האלה? אולי יש כמה כאלה? ב1951 הראה נאש[2] שקיים מושג פתרון אחד ויחיד המקיים את כל ארבע התכונות, והוא אפילו די פשוט: הפתרון של נאש לבעיית מיקוח הוא פשוט הנקודה x בקבוצה S (ומעל d) הממקסמת את שטח המלבן שהיא מייצרת עם נקודת אי ההסכמה d!

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

מקורות:
[1] https://he.wikipedia.org/wiki/%D7%9E%D7%A9%D7%97%D7%A7_%D7%9E%D7%99%D7%A7%D7%95%D7%97
[2] https://www.jstor.org/stable/1907266?origin=crossref

בעיות מיקוח ופתרון נאש

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

https://twitter.com/talitshe/status/1627429196820631552?t=ZBHt1N7mxlKHQXBGFL168w&s=19

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

https://twitter.com/OmerMadmon/status/1572988019283476481

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

נו, אז מה הבעיה?

https://twitter.com/OmerMadmon/status/1609508354820575232

כדי להבין את הבעיה נסתכל על הדוגמא של "משחק מרבה הרגליים"[1]: בכל תור אחד משני השחקנים צריך להחליט אם לעצור את המשחק או להעביר את התור לשחקן הבא. בואו נבצע אינדוקציה לאחור: בשלב האחרון שחקן 2 צריך לבחור אם לשחק r ולקבל 3, או לשחק d ולקבל 4, והוא כמובן יבחר בd.>

שחקן 1 יודע זאת, ולכן בשלב הלפני-אחרון הוא יעדיף לשחק D ולהרוויח 3 (ולא לשחק R ולקבל את ה2 ששחקן 2 ישאיר עבורו). כך הלאה נקפל את המשחק עד שנקבל את התוצאה שבה שחקן 1 כבר בשלב הראשון בוחר לסיים את המשחק, כלומר לשחק D בקודקוד ההחלטה הראשון - מה שיתן לשחקן 1 תועלת 1 ולשחקן 2 תועלת 0.

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

אם שחקן 2 קיבל את הזכות לשחק בשלב השני, הוא אמור היה גם לקבל סיגנל לגבי מידת הרציונליות של שחקן 1 - או שהוא לא רציונלי, או שהוא לא מאמין ששחקן 2 יהיה רציונלי. אז איך כל זה קשור למשחקים בין אנשים למכונות? האמת, זאת שאלה ממש טובה.>

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

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

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

האמת שאני לא יודע עד כמה פתרונות מודרניים הולכים בכיוונים האלה, ואם מישהו בפיד מבין בזה יותר ממני אני אשמח לשמוע :)


מקור:

[1] https://en.wikipedia.org/wiki/Centipede_game

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

ב-#שרשור_תורת_המשחקים הקודם הכרנו את משפחת משחקי העומסים[1], והבטחנו להסביר מדוע הם כ"כ מיוחדים ומעניינים. בשביל זה נצטרך לדבר על מושג אחר בתורת המשחקים, שנקרא פוטנציאל:

https://twitter.com/OmerMadmon/status/1618159468130471936

מושג הפוטנציאל הוצג במאמר משנת 96 ע"י דב מונדרר ולויד שפלי[2], והוא מוגדר כך: אנחנו אומרים שלמשחק מסוים יש פוטנציאל מדויק אם קיימת פונקציה יחידה (שנקראת פונקציית הפוטנציאל) שמסוגלת לבטא במדויק את התמריץ של כל אחד מהשחקנים לעבור מפעולה אחת לאחרת[3].

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

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

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

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

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

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

כלומר, קיימת שקילות בין משחקי פוטנציאל למשחקי עומסים, ולכן בפרט אם עומד בפנינו משחק עומסים שמגיע מאיזשהו יישום מעניין (כמו שראינו כאן[1]), אז אנחנו יודעים שכל התכונות ה"טובות" של משחקי פוטנציאל תקפות!

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

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

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

בונוס: יכולים לחשוב על משחק שאין לו פוטנציאל?

מקורות:
[1] https://twitter.com/OmerMadmon/status/1618159468130471936
[2] https://www.sciencedirect.com/science/article/abs/pii/S0899825696900445?via%3Dihub
[3] https://en.wikipedia.org/wiki/Potential_game

משחקי פוטנציאל והקשר למשחקי עומסים

ב-#שרשור_תורת_המשחקים הזה נדבר על משפחה מאוד מיוחדת של משחקים, הנקראת משחקי עומסים. משחקי עומסים עוזרים לנו לתאר מצבים רבים בעולם האמיתי, ומסתבר שיש להם גם כמה תכונות מעניינות ומיוחדות. בתור היכרות עם משחקי פוטנציאל נתחיל מלהציג את פרדוקס הבא, שנקרא פרדוקס ברס[1]:

נסתכל על המערכת כבישים בתמונה המצורפת[1]. נניח ש-4000 מכוניות צריכות לנסוע מSTART לEND, ונניח שישנם שני סוגים של כבישים: על כבישים מהסוג הראשון זמן הנסיעה הוא תמיד 45 דקות, ללא תלות במספר הנהגים שעליו. על כבישים מהסוג השני זמן הנסיעה הינו T/100, כאשר T הוא מספר המכוניות על הכביש.

בתור התחלה, בואו נניח שהכביש המסומן בקו מקווקו אינו קיים. איך ייראה שיווי משקל נאש במערכת הזו? אפשר לראות שכל מצב שבו חצי מהנהגים יבחרו במסלול העליון וחצי יבחרו במסלול התחתון מהווה ש"מ: כל נהג ייסע גם במקטע מהסוג הראשון (45 דקות) וגם במקטע מהסוג השני (שייארך 20 דקות).>

בסך הכל כל נהג יבלה בדיוק 65 דקות על הכביש. לאף נהג כמובן לא כדאי לסטות למסלול השני, כיוון שאז זמן הנסיעה שלו יתארך.

כעת מתכנן הכבישים מציע רעיון- בואו נבנה כביש סופר-דופר מהיר מA לB על מנת לקצר את זמן הנסיעה של הנהגים! הכביש הזה כ"כ מהיר עד שזמן הנסיעה בו הוא אפס. נשמע טוב, לא?

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

זאת כיוון שזמן הנסיעה בכביש מהסוג T/100 תמיד קצר יותר מזמן הנסיעה בכביש עם זמן הנסיעה הקבוע (הרי T יהיה לכל היותר 4000). לכן בש"מ כל הנהגים יבחרו באופציה השלישית, וכולם יבלו על הכביש 80 דקות! רגע, מה? באופן לא אינטואיטיבי, הוספת הכביש המהיר האריכה את זמן הנסיעה של כלל הנהגים.

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

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

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

מקור: [1] https://en.wikipedia.org/wiki/Braess%27s_paradox

משחקי עומסים ופרדוקס ברס

על החשיבות של מנגנונים שהם Strategy-proof קשקשנו ב-#שרשור_תורת_המשחקים הקודם. בואו נסתכל על דוגמא נוספת למצב בו מתכננת המנגנון צריכה לקחת בחשבון את ההתנהגות האסטרטגית של הפרטים כאשר היא מקבלת החלטה אשר משפיעה באופן ישיר על תועלתם:

https://twitter.com/OmerMadmon/status/1613084992804126722

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

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

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

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

למשל, עבור התושב שגר בבית מספר 4: אם כולם ידווחו אמת, הספרייה תמוקם בבית מספר 10 (כי הממוצע הוא 9.666). לעומת זאת, התושב יכול לדווח באופן שקרי שהוא גר בבית מספר 1, ובכך להזיז את הספרייה מבית מספר 10 לבית מספר 9 (כי עכשיו הממוצע יהיה 8.666), ובכך לקרב את הספרייה אל מיקומו האמיתי!

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

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

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

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

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


(מקורות: איורים מצוינים - אני)

איך למקם ספרייה על הרחוב?

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

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

נשים לב שהרשימות שהוגשו ע"י כל העובדים משרות גרף מכוון, שבו כל קודקוד הוא עובד בחברה, וקשת מקודקוד א' לקודקוד ב' אומרת שא' בחר בב' (או: ב' מופיע ברשימת העובדים המצטיינים של א'). תמונה להמחשה[1]:

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

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

במאמר מ2009[2] מראים הכותבים שתי תוצאות: האחת פסימית והשניה אופטימית. התוצאה הפסימית היא שלא קיים מנגנון דטרמיניסטי (כלומר, לא הסתברותי) שבו מובטח לנו שהבחירה של המנגנון היא לא רחוקה מאוד מאופטימלית. התוצאה האופטימית היא שדווקא קיים מנגנון הסתברותי שכזה, והוא אפילו די פשוט:

בשלב הראשון, נחלק את העובדים בחברה לשתי קבוצות באופן אקראי לחלוטין. כעת נבחר מכל קבוצה את k/2 העובדים עבורם סכום דרגות הכניסה הוא מקסימלי, אבל נתחשב רק בקשתות שנכנסות מתוך הקבוצה האחרת. באופן הזה המנגנון הוא Strategy-proof:

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

(הערה קטנה: בתיאור האלגוריתם השמטנו קצת פרטים טכניים, למשל- מה אם אחת הקבוצות שהוגרלו קטנה מk/2? ומה אם k לא מתחלק ב2? כל הפרטים האלה לגמרי פתירים, כמובן, והם הושמטו לשם פשטות בלבד)

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

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

מקורות:

[1] https://en.wikipedia.org/wiki/Directed_graph
[2] https://arxiv.org/pdf/0910.4699.pdf

איך לבחור עובדים מצטיינים? מנגנון לבחירת קודקודים בגרף

בשנת 1997 תוכנת המחשב Deep Blue ניצחה את אלוף העולם בשח, גארי קספרוב. ב-#שרשור_תורת_המשחקים הזה נתאר את הגישה האלגוריתמית שעומדת מאחורי Deep Blue ודומיו, ואת הקשר שלה לתורת המשחקים.

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


בפרט, ניתן לתאר את משחק השחמט באמצעות עץ משחק, שבו כל קודקוד מתאר החלטה של אחד השחקנים, הקשתות האפשריות היוצאות מכל קודקוד הן הפעולות האפשריות מהמצב הנתון, והעלים מתארים מצבים בהם המשחק הסתיים. כלומר, כל קודקוד מתאר נצחון של שחקן 1, נצחון של שחקן 2 או תיקו. תמונה להמחשה[1]:


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

לכן, על מנת למצוא את האסטרטגיה האופטימלית של אחד השחקנים במשחק שח, אפשר לכאורה פשוט לבנות את עץ המשחק ולבצע אינדוקציה לאחור[2], ובכך למצוא שיווי משקל פרפקטי ו"לאמץ" ממנו את האסטרטגיה של השחקן מתאים. נשמע בסך הכל די פשוט, לא?

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

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

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

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

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

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


האלגוריתם שתארנו נקרא אלגוריתם ה-Minimax, ואפשר לייעל אותו אפילו יותר ע"י שימוש בטכניקה שנקראת alpha-beta pruning, שבה מתבצע "גיזום" של ענפים מיותרים בעץ המשחק בצורה מתוחכמת[4]. כלומר, זיהוי מראש של מהלכים שבסבירות גבוהה מובילים לתוצאה גרועה והסרה שלהם על מנת לייעל את האלגוריתם.

מקורות:

[1] https://chrisbutner.github.io/ChessCoach/high-level-explanation.html
[2] https://twitter.com/OmerMadmon/status/1572988019283476481
[3] https://medium.com/@SereneBiologist/the-anatomy-of-a-chess-ai-2087d0d565
[4] https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning


איך מחשבים משחקים שחמט?

המון פעמים אנחנו תלויים במישהו אחר שיקבל החלטה שתשפיע עלינו, באופן ישיר או עקיף. איך ניתן לשכנע את המישהו האחר הזה לקבל את ההחלטה העדיפה עבורנו? #שרשור_תורת_המשחקים על אחד הנושאים הכי חמים בתורת המשחקים – שכנוע בייסיאני:

המודל של שכנוע בייסיאני, שהוצג על ידי קמניצה וג׳נטסקאו במאמר שהתפרסם ב2011[1] (וזכה לכמות בלתי נתפסת של ציטוטים) עוסק במשחקים עם שני שחקנים, בהם לשחקן אחד יש אינפורמציה שחסרה לשחקן השני, והשחקן השני צריך לקבל החלטה שתשפיע על שני השחקנים. כדי להדגים את המודל נחשוב על הדוגמא הבאה:

נניח שהשחקן הראשון (נקרא לו "המוכר") מנסה למכור מכונית לשחקן השני (נקרא לו "הקונה"). המוכר יודע אם המכונית שברשותו איכותית או לא, והקונה כמובן לא יודע. כל מה שהקונה יודע הוא שסטטיסטית, רק 30% מהמכוניות הן איכותיות.

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

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

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


כעת נשאלת השאלה: האם המוכר יכול לחלוק עם הקונה אינפורמציה שתשכנע אותו לרכוש את המכונית?

מה יקרה אם המוכר תמיד יגלה לקונה מהי איכות המכונית שברשותו? אם זה מה שיבחר לעשות, הוא יצליח למכור את המכונית ב30% מהמקרים ותוחלת התועלת שלו תהיה 0.3. אוקיי, נחמד, אבל האם אפשר לעשות יותר מזה?

נניח שהמוכר בא לקונה ואומר לו: שמע, בכל פעם שהמכונית איכותית, אני ממליץ לך לקנות ממני את המכונית. אבל כאשר המכונית לא איכותית, אני ממליץ לך לקנות את המכונית בהסתברות 3/7. רגע... מה? המוכר פשוט אומר לקונה בפנים שהוא הולך לשקר אותו! איזה מין קונה הולך לעשות איתו עסקים?

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

כדי לחשב את ההסתברות הזו נעשה שימוש בכלל בייס[2], שמקשר בין ההסתברות של מאורע A בהינתן מאורע לB לבין ההסתברות של מאורע B בהינתן מאורע A. החישוב המלא (מצורף בתמונה) מראה לנו כי בהינתן שהמוכר המליץ לקונה לקנות את המכונית, ההסתברות שהמכונית אינה איכותית היא בדיוק חצי:


לכן, תוחלת התועלת של הקונה מקניית המכונית היא 0 (בהסתברות חצי המכונית איכותית ומקבל תועלת 1, ובהסתברות חצי המכונית אינה איכותית ומקבל תועלת -1). כלומר, הקונה אדיש בין לקנות ולא לקנות, ואנו נניח שבמקרה זה הוא קונה.

אז מהי תוחלת התועלת למוכר מאסטרטגיית חשיפת המידע הזו? כל פעם שהוא ממליץ הוא מצליח למכור, וזה קורה או כשהמכונית איכותית (בהסתברות 0.3) או כשהמכונית אינה איכותית וגם הוא מחליט לשקר (בהסתברות 0.7 כפול 3/7), כלומר בסך הכל בהסתברות של 0.5 (שזה הרבה יותר טוב ביחס ל0.3 שממנו התחלנו)!


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


מקורות:

[1] https://web.stanford.edu/~gentzkow/research/BayesianPersuasion.pdf
[2] https://en.wikipedia.org/wiki/Bayes%27_theorem