הלמה של סקרף

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

פירוט

יהי $B_{mxn},m<n$ מטריצה של מספרים ממשיים עבורה $b_{i,j}=\delta _{i,j}$ לכל $1\leq i,j\leq m$ .

יהי $b\in \mathbb {R} ^{m}$ וקטור חיובי כך שהקבוצה $\ \{\alpha \in \mathbb {R} _{+}^{n}:B\alpha =b\}$ חסומה.

תהי $C_{mxn}$ מטריצה עבורה $c_{i,i}\leq c_{i,k}\leq c_{i,j}$ כאשר $i,j\leq m;i\neq j;k>m$ .

אזי קיימת תת-קבוצה $\left|J\right|=m;J\subseteq [n]$ המקיימת:

1. $B\alpha =b$ עבור $\alpha \in \mathbb {R} ^{n}$ חיובי כלשהוא כך ש-${\boldsymbol {\alpha }}_{j}=0$ כאשר $j\notin J$
2. לכל $k\in [n]$ קיים $i\in [m]$ עבורו $c_{i,k}\leq 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