Muž, který uměl párovat

29. března 2016, 00:00 - LUBO HEGER
29. března 2016, 00:00

Lloyd Shapley se nejprve pokoušel vymyslet algoritmus na stabilní manželství. To se mu nepovedlo, ale uspěl při hledání vhodných dárců orgánů

Studie z roku 1962 vznikla tak, že kamarád z vysoké školy David Gale mladého matematika požádal o pomoc s následujícím problémem: v jedné místnosti spolu sedí deset mužů a deset žen, kteří se zběžně znají. Mohou se spárovat tak, aby byli všichni spokojení a nemuseli se stále rozcházet při hledání vhodnějšího protějšku?

Shapley (2. 6. 1923 – 12. 3. 2016) se podrbal na hlavě a večer téhož dne přišel s algoritmem. Muži i ženy si vytvoří žebříček vhodných protějšků. Každý muž požádá o ruku ženu, kterou ohodnotil nejlépe. Každá žena odmítne nabídky, které dostane, až na tu s nejvyšším hodnocením. Tak to běží pořád dokola, dokud všechny ženy nedostanou uspokojivou nabídku. Jde o algoritmus „odloženého přijetí“, který se vyznačuje vysokou stabilitou výsledku a minimálními manipulacemi při jeho dosahování.

NEJSEM EKONOM

V širší známost vešel tento párovací algoritmus opět v roce 2012, kdy u Shapleyů v Los Angeles zazvonil v noci telefon (naučí se někdy Švédové ze stockholmské Akademie věd počítat s časovým rozdílem?) a hlas s přízvukem 89letému profesorovi oznámil, že se díky algoritmu (mezitím rozšířenému na „teorii tržních alokací“) stal nositelem Nobelovy ceny za ekonomii. Shapley cenu odmítal přijmout. „Nikdy v životě jsem neabsolvoval ani jeden semestr z ekonomie. Jsem matematik,“ říkal. Nakonec jej přesvědčila rodina.

Galeův­Shapleyův algoritmus podle týdeníku The Economist našel široké využití v řadě oborů. Například v programu směny ledvin v Nové Anglii v USA. Muž, který by za jiných okolností nedaroval ledvinu, změní názor, když ji bude potřebovat jeho žena. Pokud nemají shodnou krevní skupinu, mohou být propojeni s párem, který je jejich zrcadlovým obrazem. Program Nové Anglie pro výměnu ledvin zahrnul složité řetězce dárců a příjemců na tomto základě a výrazně zvýšil nabídku ledvin.

Jiným příkladem byl systém veřejného školství v New Yorku a v Bostonu. Studenti se často musejí rozhodovat pro nějakou vysokou školu, ještě než znají všechny možnosti. Tisíce jich proto končí ve školách, o něž vůbec neměli zájem. Aplikátoři Shapleyho metod jim pomohli navrhnout algoritmy, které tyto neshody výrazně omezily.

ROZBIL SOVĚTSKÝ KÓD

Lloyd Shapley pochází z Massachusetts a za druhé světové války sloužil na letecké základně v západní Číně, kde jeho matematické schopnosti našly uplatnění při předpovědích počasí. Podařilo se mu i rozbít kód, jímž předpovědi – celkem zásadní informace pro úspěch náletů – šifroval SSSR, který byl sice spojencem USA, ale vůči Japonsku neutrální. Shapley jako expert na teorii her a člen různých vědeckých institucí po celý život vyvíjel matematické modely, které zvyšovaly výkon trhů tím, že sváděly dohromady různé hospodářské aktéry. Vymýšlel též společenské hry, například So Long, Sucker (něco jako „člověče, pomiň se“), při nichž byli hráči odměňováni za porušování koalic, takže se zpravidla rozhádaly i nejsoudržnější páry.

Svůj párovací algoritmus Shapley nikdy v praxi nezkoušel, oženil se s kolegyní z práce a zůstal s ní po celý život.

O autorovi| LUBO HEGER, heger@mf.cz

Hodnocení

Zaujala Vás tato zpráva?
Ohodnoťte ji

Loading

Děkujeme za Vaše hodnocení

Komentáře

Mohlo by vás zajímat

Finance
Když za škodu může sport...
O dědictví IV: Dědit, či darovat?
3 věci, na které není dobré zapomínat před odjezdem na služební cestu
Daňové přiznání za rok 2017: Změny u daňového zvýhodnění na děti a daňového bonusu
Bez potřebné doby pojištění vám důchod nedají
Auta
Retro: Kolik stála nová auta v listopadu 1989 a o kolik…
Kvíz: Víte, co se děje, když se na přístrojové desce rozsvítí tyto kontrolky?
Arrivo je systém, díky kterému pojede i Dacia Duster nebo Fabia 1.2 HTP 320 km/h
Škoda Superb 2.0 TSI 4×4 vs. BMW M760Li xDrive: Přesné porovnání neporovnatelného
Že je elektrická nákladní Tesla revoluční? Kdeže, elektrická Avia tu byla už dávno
Technologie
Velký přehled slev na Černý pátek 2017 (průběžně aktualizováno)
Že je elektrická nákladní Tesla revoluční? Kdeže, elektrická Avia tu byla už dávno
Procesory ARM proráží už i v superpočítačích. Na ThunderX2 s jádry Vulcan sází sám Cray
Parádní akce: Samsung Galaxy S7 za 8200 Kč a S7 Edge za 10 600 Kč
Mlácení dělníků, smrt v kantýně aneb Jak se dělá iPhone X
Hry pro příležitostné hráče
Zavřít