הלמה של סקרף

הלֶמה של סקרף (Scarf's Lemma) היא אחת מהתוצאות היסודיות בתחום קומבינטוריקה. בארבעת העשורים האחרונים היא שימשה כנקודת מפתח בפתרון בעיות קומבינטורית השואפות למציאת פתרון יציב. נקראת ע"ש הרברט סקרף.

פירוט

יהי $m<n$ ו $B_{mxn}$ מטריצה של מספרים ממשיים כך ש $b_{i,j}={\delta }_{i,j}$ לכל $1\le i,j\le m$.
יהי $b\in {ℝ}^m$ וקטור חיובי כך שהקבוצה $\{\alpha \in {ℝ}_{+}^n:B\alpha =b\}$ חסומה.
תהי $C_{mxn}$ מטריצה כך ש $c_{i,i}\le c_{i,k}\le c_{i,j}$ כאשר $i,j\le m;i\ne j;k>m$
אזי קיימת תת-קבוצה $\left|J\right|=m;J\subseteq [n]$ המקיימת:
1. $B\alpha =b$ עבור $\alpha \in {ℝ}^n$ חיובי כשלהוא כך ש ${\mathit{\alpha }}_j=0$ כאשר $j\in ̸J$
2. לכל $k\in [n]$ קיים $i\in [m]$ כך ש $c_{i,k}\le c_{i,j}$ לכל $j\in J$

הוכחה

את ההוכחה המלאה ללמה המבוססת על אלגוריתם Lemke-Howson ניתן למצוא במאמר המקורי של הרברט סקרף (H. E. Scarf).תבנית:כתבנית:הערה

סיבוכיות

לא מזמן הוכח שהסיבוכיות החישובית של הלמה שייכת למחלקת הסיבוכיות PPAD.תבנית:כתבנית:הערה

שימושים

הלמה משמשת הוכחה למספר בעיות "fractional stability type" להלן רשימה חלקית:

1. Every balanced game with non-transferable utilities has a non-empty coreתבנית:הערה.
2. Every clique-acyclic digraph has a strong fractional kernelתבנית:הערה.
3. Every hypergraphic preference system has a fractional stable solutionתבנית:הערה.
4. Every instance of stable paths problem has a fractional stable solutionתבנית:הערה.
5. Stable matchings and Scarf's lemma.תבנית:הערה.

מקורות

• Herbert E. Scarf, The core of an N person game, Econometrica, 35, 1967.
• Ron Aharoni, Tamás Fleiner, On a lemma of Scarf. J. Comb. Theory, Ser. B 87(1) 2003.
• Lemke, C. E., Howson, Jr., J. T., Equilibrium Points of Bimatrix Games, 1964.

ראו גם

• PPAD (מחלקת סיבוכיות)
• List of PPAD-complete problems
• הלמה של שפרנר
• אלגוריתם Lemke-Howson