פרדוקס ברס

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

הגדרה

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

דוגמה

דוגמה לפרדוקס של ברס

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

נניח בתחילה שהכביש המקווקו אינו קיים. אם A נהגים עוברים דרך נקודה A זה לוקח $A/100+45$ דקות ואם B נהגים בוחרים לעבור דרך נקודה B זה לוקח להם $B/100+45$ דקות. המקרה הגרוע ביותר הוא כאשר כל הנהגים יבחרו לנסוע באותו הנתיב. אז ההאטה מקסימלית והנסיעה כולה לוקחת 90 דקות. אך בחירה אקראית באחד הנתיבים תוביל לתוצאה טובה יותר. אילו חצי מהנהגים יסעו בכל אחד מהנתיבים הזמן של הנסיעה יתקצר ל-$2250/100+45=67.5$. (זהו שיווי משקל נאש.)

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

לקריאה נוספת

• Katharina Belaga-Werbitzky: „Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern“ מסת"ב 3-89959-123-2)

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

• גדי אלכסנדרוביץ', פרדוקס ברס ומנהרות הכרמל, באתר "לא מדויק",
• יותר זה פחות מאמר מאת ד״ר אורן שעיה העוסק בפרדוקס ברס, באתר מכון דוידסון לחינוך מדעי