הלמה של סקרף

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

פירוט[עריכת קוד מקור | עריכה]

יהי ו מטריצה של מספרים ממשיים כך ש לכל .
יהי וקטור חיובי כך שהקבוצה חסומה.
תהי מטריצה כך ש כאשר
אזי קיימת תת-קבוצה המקיימת:
1. עבור חיובי כשלהוא כך ש כאשר
2. לכל קיים כך ש לכל

הוכחה[עריכת קוד מקור | עריכה]

את ההוכחה המלאה ללמה המבוססת על אלגוריתם 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.

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  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