בעיית פשיטת רגל

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

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

==דוגמה==

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

{| bgcolor="#f7f8ff" cellpadding="6" cellspacing="0" border="1" style="font-size: 95%; text-align:center; border: gray solid 1px; border-collapse: collapse;"
| 
| 
! colspan=3 BGCOLOR=yellow | הכתובה
|- 
| 
| 
| BGCOLOR=yellow | 100
| BGCOLOR=yellow | 200
| BGCOLOR=yellow | 300
|- 
! rowspan=3 BGCOLOR=yellow | גודלהעיזבון
| BGCOLOR=yellow | 100
| <math>\ 33 \frac{1}{3}</math>
| <math>\ 33 \frac{1}{3}</math>
| <math>\ 33 \frac{1}{3}</math>
|- 
| BGCOLOR=yellow | 200
| <math>\ 50 </math>
| <math>\ 75</math>
| <math>\ 75</math>
|- 
| BGCOLOR=yellow | 300
| <math>\ 50 </math>
| <math>\ 100</math>
| <math>\ 150</math>
|}

==הגדרה פורמלית==
בעיית פשיטת רגל נתונה על ידי:
* קבוצת שחקנים <math>\ N = {1, 2,\dots, n}</math> (קבוצת הנושים)
* לכל שחקן <math>i \in N</math> מספר ממשי אי שלילי <math>d_i \in \R_+</math> (החוב לנושה).
* מספר ממשי אי שלילי <math> E \in \R_+ </math> (רכושו של פושט הרגל).
מסמנים את הבעיה כ <math>\ [E;d_1,\dots,d_n]</math> או באופן מקוצר <math>\ [E;d]</math>

מגדירים וקטור תשלומים להיות וקטור ב<math>x \in \R_+^n</math> אשר מקיים <math>\ x_1 + x_2 + \cdots + x_n = E</math>. וקטור זה הוא הצעה כיצד לחלק את הרכוש בין הנושים. פרט למקרה בו <math>E=0</math> וקטור זה אינו יחיד.

==משחק בצורה קואליציונית==
ניתן להגדיר הצגה קואליציונית של בעיית פשיטת הרגל:
מגדירים משחק <math>\ (N;v)</math> בו קבוצת השחקנים היא קבוצת הנושים והפונקציה הקואליציונית מוגדרת באופן הבא: <math>v(S) = max \Big\{E - \sum_{i \notin S}d_i,0\Big\}, \quad \forall S \subseteq N</math>.<br />
כלומר כשקואליציה <math>\ S </math> רוצה לקבוע מה תוכל להבטיח לעצמה היא מחשבת את המקרה הגרוע ביותר, שבו כל השחקנים שאינם ב <math>\ S </math> מקבלים את חובם במלואו, אם הרכוש <math>\ E </math> מאפשר זאת.

==פתרונות לבעיה==
פתרון נקודתי לבעיית פשיטת רגל הוא פונקציה <math>\ \phi</math> אשר מתאימה וקטור תשלומים יעיל (כלומר <math>\ x_1 + x_2 + \cdots + x_n = E</math>) לכל בעיית פשיטת רגל.
מציאת הפתרון עצמו תלויה בעקרונות אותם מחשיבים להיות "הוגנים". פתרונות אפשריים הם:

=== חלוקה פרופורציונלית לחוב ===
כל נושה מקבל את אותו אחוז מתביעתו. זוהי הגישה הנהוגה במשפט המודרני. בדוגמה לעיל כאשר גודל העיזבון הוא 100 החלוקה תהיה <math>\ 16 \frac{2}{3}</math> לאישה הראשונה, <math>\ 33 \frac{1}{3}</math> לשנייה ו-50 לשלישית. 

=== חלוקת הרכוש שווה בשווה ===
חלוקה של הרכוש שווה בשווה אך לא יותר מאשר מגיע לכל נושה. בדוגמה לעיל אם גודל העיזבון הוא 400 החלוקה תהיה 100 לאישה הראשונה, 150 לשנייה ו-150 לשלישית.

=== עקרון שניים אוחזין בטלית ===
עקרון שניים אוחזין בטלית הוא כלל הלקוח מהמשנה הראשונה במסכת בבא מציעא, וקובע חלוקה שווה של הסכום השנוי במחלוקת. הוא מוגדר לחלוקה בין שני נושים.
אם החובות לשני נושים הם <math>\ d_1</math> ו-<math>\ d_2</math> בהתאמה וללא הגבלת הכלליות <math>\ d_1 \ge d_2</math>, אז פונקציית החלוקה של הרכוש <math>\ f</math> מוגדרת כך:<br />
:<math>
f(E,d_1,d_2) = 
\begin{cases} 
 (E/2,E/2) & \mbox{if }\ d_1,d_2 \ge E\\
 (E-d_2/2,d_2/2) & \mbox{if } d_1 \ge E \ge d_2\\
 ((E+d_1-d_2)/2,(E+d_2-d_1)/2) & \mbox{if } E \ge d_1,d_2\\
\end{cases}
</math><br />

פתרון <math>\ \phi</math> לבעיית פשיטת רגל עבור <math>\ n</math> נושים נקרא עקבי עם כלל "שניים אוחזין בטלית" אם לכל בעיית פשיטת רגל וקטור התשלומים <math>\ (x_1,...,x_n) </math> מקיים כי לכל שני שחקנים <math>\ i\ne j </math> הווקטור <math>\ (x_i,x_j) </math> הוא פתרון על פי שניים אוחזין בטלית לבעיה <math>\ (x_i+x_j,d_i,d_j)</math>.

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

==== מימוש פיזיקלי עבור n שחקנים====
ניתן לחשב את הפתרון <math>\ \phi</math> המקיים עקביות עם כלל "שניים אוחזין בטלית" בדרך פיזיקלית המבוססת על חוק הכלים השלובים. 

בתרשים הבא הדרישות של הנושים מתוארות על ידי מכלים בעלי שטח בסיס של יחידה. כאשר דרישה של <math>\ d_i</math> מתוארת על ידי שני מכלים בגובה <math>\ d_i/2</math>, האחד מונח על הקרקע והשני תלוי על התקרה. שני מכלים אלה מחוברים בצינור חסר נפח ושני המכלים מונחים על הקרקע ואף הם מחוברים בצינורות חסרי נפח. נסדר את המכלים מהקטן לגדול: 
<br />

התמונה לקוחה מתוך הספר 'תורת המשחקים', שמואל זמיר, מיכאל משלר, אילון סולן. הוצאת ספרים ע"ש י"ל מאגנס האוניברסיטה העברית בירושלים בע"מ, ירושלים 2008.
<br />

כדי לחשב את <math>\ f(E,d_1,...,d_n) </math> נזרים לתוך מערכת הצינורות מים בנפח E (בגודל רכושו של פושט הרגל) ולפי חוק הכלים השלובים גובה המים בכל המכלים ישתווה.<br />

נסמן ב-<math>\ x_i </math> את כמות הנוזל <math>\ i </math> (על שני חלקיו) והוא יסמן את התשלום לנושה <math>\ i </math> (שהוא לכל היותר <math>\ d_i </math>).<br />
נקבל ש <math>\ x_1+...+x_n=E </math> ולכן הווקטור <math>\ (x_1,...,x_n) </math> יגדיר לנו פתרון לבעיית פשיטת הרגל.<br />

== ראו גם ==
* משחק שיתופי

== לקריאה נוספת ==
* 
==הערות שוליים==

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