הלמה של סקרף

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

פירוט

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

הוכחה

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

סיבוכיות

לא מזמן הוכח שהסיבוכיות החישובית של הלמה שייכת למחלקת הסיבוכיות PPAD.‏^[2]

שימושים

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

1. Every balanced game with non-transferable utilities has a non-empty core^[3].
2. Every clique-acyclic digraph has a strong fractional kernel^[4].
3. Every hypergraphic preference system has a fractional stable solution^[5].
4. Every instance of stable paths problem has a fractional stable solution^[6].
5. Stable matchings and Scarf's lemma.^[7].

מקורות

• 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

הערות שוליים

1. Herbert E. Scarf. The core of an N person game., pp. 60–65.
2. Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng Reducibility Among Fractional Stability Problems Electronic Colloquium on Computational Complexity (ECCC) TR09-041 2009
3. Herbert E. Scarf. The core of an N person game. Econometrica, 35 1967
4. Ron Aharoni, Ron Holzman : Fractional Kernels in Digraphs. J. Comb. Theory, Ser. B 73(1) 1998
5. Ron Aharoni, Tamás Fleiner : On a lemma of Scarf. J. Comb. Theory, Ser. B 87(1) 2003
6. Penny E. Haxell, Gordon T. Wilfong : A fractional model of the border gateway protocol (BGP). 2008
7. Tamas Kiraly and Julia Pap. Kernels, Stable Matchings and Scarf's Lemma. The Egervry Research Group Technical Report 2008