פרדוקס ברס
פרדוקס בְּרָס (Braess's paradox), הנקרא על שם המתמטיקאי הגרמני דיטריך ברס, הוא דוגמה למצב שבו הוספת קשת נוספת לרשת שבה הישויות הנעות בוחרות את מסלול הזרימה האופטימלי באופן אנוכי, יכולה לגרום לירידה בביצועים הממוצעים של הרשת (זאת כמובן על אף האינטואיציה שאומרת שיותר מסלולים תמיד יובילו לביצועים משופרים).
הגדרה
נתבונן ברשת כבישים. נניח שעבור כל צומת ברשת ידוע מספר המכוניות שיוצאות ממנו (דרגת היציאה) ומספר המכוניות שנכנסות אליו (דרגת כניסה). תחת תנאים אלה נרצה לשערך את התפלגות התנועה ברשת. ההחלטה אם לנסוע בכביש כזה או אחר תלויה לא רק באיכות הכביש, אלא גם בצפיפות התנועה עליו. אם כל נהג יבחר בדרך שנראית לו אופטימלית (עבורו בלבד) התוצאה לא בהכרח תהיה אופטימלית עבור כל הנהגים. יתר על כן, קיימת דוגמה שבה הרחבת רשת הכבישים אינה גורמת לקיצור זמני הנסיעה ואף מאריכה אותם.
דוגמה
נסתכל על מערכת כבישים כמו בציור. יש 4000 מכוניות הנוסעות מהמקור אל היעד. הזמן שלוקח לעבור כל כביש מצוין באיור, כאשר T הוא מספר המכוניות שנמצאות על אותו הכביש. על שניים מהכבישים זמן הנסיעה קבוע, ואילו על השניים האחרים זמן הנסיעה תלוי בעומס.
נניח בתחילה שהכביש המקווקו אינו קיים. אם a נהגים עוברים דרך נקודה A זה לוקח דקות ואם b נהגים בוחרים לעבור דרך נקודה B זה לוקח להם דקות. המקרה הגרוע ביותר הוא כאשר כל הנהגים יבחרו לנסוע באותו הנתיב. אז ההאטה מקסימלית והנסיעה כולה לוקחת 85 דקות. אך בחירה אקראית באחד הנתיבים תוביל לתוצאה טובה יותר. אם מחצית מהנהגים יסעו בכל אחד מהנתיבים, זמן הנסיעה של כולם יתקצר ל- דקות. (זהו שיווי משקל נאש.)
כעת נניח שבונים כביש נוסף שמחבר את A עם B וזמן הנסיעה בו כל כך קצר שניתן אפילו לומר שהוא 0. לנהג יש עכשיו שלוש אפשרויות: הוא יכול לסוע בדרך התחתית, ישירות ל-B ומשם ליעד; הוא יכול לנסוע בעקיפין, ל-B דרך A ומשם אל היעד; והוא יכול לסוע בדרך העילית, ל-A ומשם ישירות אל היעד. דרך העקיפין עדיפה על הדרך התחתית, משום שהדרך העוקפת ל-B היא קצרה יותר בכל מקרה מאשר הדרך הישירה לשם. דרך העקיפין עדיפה גם על הדרך העילית, משום שהדרך ליעד מ-B קצרה יותר מאשר ישירות מ-A. לכן כל הנהגים יסעו ראשית ל-A ואז ל-B, והדרך תיקח לכולם 80 דקות. הפתרון האופטימלי, שבו מחצית הנהגים נוסעים דרך B והמחצית השנייה ישירות דרך A (ב-65 דקות לכולם) אינו יציב, משום שלכל נהג בדרך העילית עדיף לקצר ולסוע מ-A אל היעד דרך B, ולכל נהג בדרך התחתית עדיף לקצר ולסוע ל-B דרך A. הוספת הכביש הרעה את ביצועי המערכת.
לקריאה נוספת
- Katharina Belaga-Werbitzky: „Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern“ מסת"ב 3-89959-123-2)
קישורים חיצוניים
- גדי אלכסנדרוביץ', פרדוקס ברס ומנהרות הכרמל, באתר "לא מדויק", 23 באוקטובר 2010
- יותר זה פחות מאמר מאת ד״ר אורן שעיה העוסק בפרדוקס ברס, באתר מכון דוידסון לחינוך מדעי
34584316פרדוקס ברס