הלמה של סקרף

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

פירוט

יהי $m<n$ ו $B_{mxn}$ מטריצה של מספרים ממשיים כך ש $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\not \in J$
2. לכל $k\in [n]$ קיים $i\in [m]$ כך ש $c_{i,k}\leq c_{i,j}$ לכל $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.

ראו גם

הערות שוליים

^ Herbert E. Scarf. The core of an N person game., pp. 60–65.
^ 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
^ Herbert E. Scarf. The core of an N person game. Econometrica, 35 1967
^ Ron Aharoni, Ron Holzman : Fractional Kernels in Digraphs. J. Comb. Theory, Ser. B 73(1) 1998
^ Ron Aharoni, Tamás Fleiner : On a lemma of Scarf. J. Comb. Theory, Ser. B 87(1) 2003
^ Penny E. Haxell, Gordon T. Wilfong : A fractional model of the border gateway protocol (BGP). 2008
^ Tamas Kiraly and Julia Pap. Kernels, Stable Matchings and Scarf's Lemma. The Egervry Research Group Technical Report 2008

Read other articles:

Cámara de Diputadas y Diputados de Chile

Honorable Cámara de Diputadas y Diputados Insignia de la Cámara desde 2020 Cámara de Diputados de Chile, en el edificio del Congreso Nacional.Información generalÁmbito República de ChileCreación 4 de julio de 1811(Primer Congreso Nacional)Atribuciones Ley Orgánica ConstitucionalTipo Cámara baja del Congreso Nacional de ChileInicio de sesiones 11 de marzo de 2022Salario CLP$ 7 012 388.-[1]Límite 4 años, con posibilidad de reelección dos veces[2]LiderazgoPres...

Banco Santander

Santander Consumer Bank beralih ke halaman ini. Untuk bank asal Norwegia, lihat Santander Consumer Bank (Norwegia). Banco Santander, S.A.Fasad kantor pusat Banco Santander di Santander, SpanyolJenisSociedad AnónimaKode emitenBMAD: SANNYSE: SANISINES0113900J37IndustriJasa keuanganDidirikan15 Mei 1857; 166 tahun lalu (1857-05-15)KantorpusatSantander (kantor pusat resmi) dan Boadilla del Monte, Madrid (kantor pusat operasional), SpanyolWilayah operasiSeluruh duniaTokohkunciAna Patrici...

Jon Bentley (TV presenter)

British journalist and television presenter (born 1961) Jon BentleyBentley in 2008NationalityBritishEducationMillfieldAlma materOriel College, OxfordOccupations Presenter journalist producer Known for The Gadget Show Top Gear Fifth Gear SpouseMarriedChildren2Websitejonbentley.com Jon Bentley is a British journalist and television presenter. He was educated at Millfield in Street, Somerset from 1972 to 1978 and at Oriel College in Oxford from 1979 to 1982, where he studied geography....

Departemen Transportasi Amerika Serikat

Departemen TransportasiAmerika SerikatLambang Departemen TransportasiMarkas Departemen Transportasi A.S., dibuka tahun 2007 di Washington, D.C., dekat Washington Navy Yard dan Nationals ParkInformasi DepartemenDibentuk1 April 1967; 56 tahun lalu (1967-04-01)Wilayah hukumAmerika SerikatKantor pusat1200 New Jersey Avenue SE, Washington, D.C.38°52′32.92″N 77°0′10.26″W / 38.8758111°N 77.0028500°W / 38.8758111; -77.0028500Koordinat: 38°52′32.92″N 77°0...

Viennese coffee house

Type of café The Café Hawelka coffee house on a quiet Thursday morning The Viennese coffee house (German: das Wiener Kaffeehaus, Bavarian: as Weana Kafeehaus) is a typical institution of Vienna that played an important part in shaping Viennese culture. Since October 2011 the Viennese Coffee House Culture is listed as Intangible Cultural Heritage in the Austrian inventory of the National Agency for the Intangible Cultural Heritage, a part of UNESCO. The Viennese coffee house is described in ...

Old Spanish Trail (trade route)

For other uses, see Old Spanish Trail. United States historic placeThe Old Spanish TrailU.S. National Register of Historic PlacesU.S. Historic districtNevada Historical Markers No. 31, 32, 33, 34, 139, 140, 141, 142 The route of the Old Spanish Trail.LocationNew Mexico, Colorado, Utah, Arizona, Nevada, CaliforniaNRHP reference No.88001181 (original)01000863 (increase 1)08000229 (increase 2)MARKERS No.31, 32, 33, 34, 139, 140, 141, 142Significa...

منتخب غانا لكرة القدم

منتخب غانا لكرة القدم معلومات عامة اللقب Black Stars (النجوم السوداء) بلد الرياضة غانا الفئة كرة القدم للرجال رمز الفيفا GHA الاتحاد اتحاد غانا لكرة القدم كونفدرالية كاف (أفريقيا) كونفدرالية فرعية وافو (غرب أفريقيا) الملعب الرئيسي ملعب أكرا الرياضي الموقع الرسمي الموقع...

Ross Shafer

American comedian (born 1954) This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This biography of a living person needs additional citations for verification, as its only attribution is to self-published sources; articles should not be based solely on such sources. Please help by adding reliable, independent sources. Immediately remove contentious material about living people that is unsour...

Toxicodendron radicans

Toxicodendron radicans TumbuhanJenis buahbuah berbiji Status konservasiRisiko rendahIUCN124270453 TaksonomiDivisiTracheophytaSubdivisiSpermatophytesKladAngiospermaeKladmesangiospermsKladeudicotsKladcore eudicotsKladSuperrosidaeKladrosidsKladmalvidsOrdoSapindalesFamiliAnacardiaceaeSubfamiliAnacardioideaeGenusToxicodendronSpesiesToxicodendron radicans Kuntze, 1891 Tata namaBasionimRhus radicans lbs Radicans Toxicodendron , umumnya dikenal sebagai sumak racun atau sumak racun timur , adalah...

Specialist Firearms Command

London police firearms unit Specialist Firearms CommandActiveDecember 1966 – present[1]CountryUnited KingdomAgencyMetropolitan PoliceTypeFirearms unitPart ofMet Operations The Specialist Firearms Command (MO19, previously SO19, CO19 and SCO19) is the firearms unit of the Metropolitan Police.[2][3][4][5][6] The Command is responsible for providing a firearms-response capability, assisting the rest of the service which is not routinely arme...

قائمة حلقات كولمبو

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (مايو 2016) الصورة الدعائية للمسلسل يظهر بها الممثل بيتر فالك بدور كولمبو فيما يلي قائمة حلقات مسلسل الجريمة الخيالي التلفزيوني كولمبو. بعد عامين من إطلاق الحلقات التجر�...

Metropolitan Museum of Art

Art museum in New York City Not to be confused with the Museum of Modern Art. The Metropolitan Museum of ArtEntrance façades to The Met Fifth Avenue and The CloistersEstablishedApril 13, 1870; 154 years ago (April 13, 1870)[2][3][4]Location1000 Fifth Avenue (The Met Fifth Avenue)99 Margaret Corbin Drive (The Cloisters)New York City, U.S.Coordinates40°46′46″N 73°57′47″W / 40.7794°N 73.9631°W / 40.7794; -73.9631TypeArt mu...

Accident d'un B-52 à Elephant Mountain

Accident d'un B-52 à Elephant Mountain Un B-52C. Caractéristiques de l'accident Date24 janvier 1963 TypePerte d'éléments structurels SiteElephant Mountain, comté de Piscataquis Maine Coordonnées 45° 31′ 40″ nord, 69° 26′ 05″ ouest Caractéristiques de l'appareil Type d'appareilBoeing B-52C Stratofortress CompagnieStrategic Air Command No d'identification53-0406 Lieu d'origineWestover Air Force Base Passagers3 Équipage6 Morts7 Blessés2 Sur...

Eamon Duffy

Irish historian (born 1947) Eamon DuffyFSA FBA KSGDuffy in 2010Born (1947-02-09) 9 February 1947 (age 77)Dundalk, IrelandNationalityIrishAcademic backgroundAlma materUniversity of HullUniversity of CambridgeDoctoral advisorOwen ChadwickGordon RuppAcademic workDisciplineHistorySub-disciplineHistory of ChristianityInstitutionsMagdalene College, CambridgeDoctoral studentsPaul C. H. LimNotable worksThe Stripping of the Altars (1992) Eamon Duffy FSA FBA KSG (born 1947) is an Irish histor...

2025 ATP Tour

Men's tennis circuit 2025 ATP TourDetailsDuration27 December 2024 – December 2025Edition56thTournaments64CategoriesGrand Slam (4)ATP FinalsNext Generation ATP FinalsATP Masters 1000 (9)ATP 500 (16)ATP 250 (30)Davis CupUnited CupLaver CupAchievements (singles)← 2024 2026 → The 2025 ATP Tour is the global elite men's professional tennis circuit organized by the Association of Tennis Professionals (ATP) for the 2025 tennis season. The 2025 ATP Tour calendar comprises the Grand Slam...

Галилеевы спутники

Три внутренних галилеевых спутника вращаются в резонансе 4:2:1 Сравнение галилеевых спутников с Юпитером. Сверху вниз: Ио, Европа, Ганимед и Каллисто Прибор середины XVIII века, демонстрирующий орбиты спутников Юпитера Сравнение с Землёй и Луной Юпитер со спутниками (объе...

Abraham Bosse

French artist (1604–1676) Abraham BosseBornc. 1604Tours, FranceDied14 February 1676(1676-02-14) (aged 71–72)Paris, FranceOccupationprintmaker Engravers and etchers at work, 1643 Abraham Bosse (c. 1604 – 14 February 1676) was a French artist, mainly as a printmaker in etching, but also in watercolour.[1] Life Valet de Chambre from a series of etchings of trades, Les Metiers 1635 He was born to Huguenot (Calvinist) parents in Tours, France, where his father had move...

Pingley POW Camp

Historic Prisoner of War Camp Photograph showing the main dividing road of the camp from the front Pingley POW (prisoner of war) camp is one of the few remaining POW camps in the United Kingdom in good condition. Unlike the nearby Eden Camp which is preserved as a Second World War museum, Pingley Camp lies in a semi derelict state in the grounds of Pingley Farm. It is situated on the outskirts of Brigg, Lincolnshire. The camp was used to house mainly Italian prisoners of war, though Germans w...

Gabriel Malagrida

Italian Jesuit missionary This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Gabriel Malagrida – news · newspapers · books · scholar · JSTOR (May 2014) (Learn how and when to remove this message) Gabriel Malagrida, National Library of Portugal Gabriel Malagrida, SJ (18 September or 6 December 1689 – 21 Septem...

Stéphane Audoin-Rouzeau

Pour les articles homonymes, voir Audoin, Rouzeau et Audoin-Rouzeau. Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » (novembre 2014). Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aid...

/profillengkap.com/index.php/article/Buzz (Ryanair)

/profillengkap.com/index.php/article/Casspir

/profillengkap.com/index.php/article/Hudson River State Hospital

/profillengkap.com/index.php/article/MacMillan Provincial Park

Jean-Paul Fleri Soler

García López de Cárdenas

Imperial Library of Constantinople

1667