Krutá, ale užitečná matematika: Problém nejlepší volby

28.10.2024. Představte si, že jedete po dálnici a zjistíte, že vám dochází palivo. GPS ukazuje, že na vaší trase je před vámi 10 čerpacích stanic. Přirozeně chcete tu nejlevnější. Minete první hrstku a sledujete jejich ceny, než se přiblížíte k jedné se zdánlivě výhodnou nabídkou. Zastavíte, aniž byste věděli, jak výhodné nabídky se mohou po cestě objevit? Nebo budete pokračovat v průzkumu a riskovat, že budete litovat, že jste odmítli ptáčka v ruce? Dvakrát se nevrátíte, takže stojíte před volbou teď, nebo nikdy. Jaká strategie maximalizuje vaše šance na výběr nejlevnější stanice?

Tento elegantní matematický problém vám pomůže najít nejlepší volbu pro najímání zaměstnanců, hledání domu a dokonce i pro lásku. Matematický „problém nejlepší volby“ by mohl lidem pomoci lépe se rozhodovat, a to ve všech oblastech od výběru nejlepšího kandidáta na zaměstnání až po hledání romantického partnera.

Vědci tento tzv. problém nejlepší volby a jeho mnoho variant důkladně studovali, přitahováni jeho reálnou přitažlivostí a překvapivě elegantním řešením. Empirické studie naznačují, že lidé mají tendenci nedosahovat optimální strategie, takže poznání tohoto tajemství z vás může udělat lepšího rozhodovatele – a to všude od benzinového čerpadla až po profil na seznamce.

Scénář má několik názvů: „Problém sekretářky“ https://en.wikipedia.org/wiki/Secretary_problem, kde místo hodnocení benzínových pump nebo podobných míst podle cen hodnotíte uchazeče o zaměstnání podle jejich kvalifikace, nebo „problém manželství“ kde hodnotíte nápadníky podle jejich způsobilosti. Všechny inkarnace mají stejnou základní matematickou strukturu, v níž se postupně objevuje známý počet řaditelných příležitostí. Musíte se zavázat, že každou z nich na místě přijmete nebo odmítnete bez možnosti vzít zpět, pokud odmítnete všechny, zůstanete u poslední volby. Příležitosti mohou přicházet v libovolném pořadí, takže nemáte důvod tušit, že lepší kandidáti se s větší pravděpodobností nacházejí na začátku nebo na konci řady.

Vyzkoušejme si vaši intuici. Kdyby dálnici lemovalo 1 000 čerpacích stanic (nebo vaši kancelář 1 000 uchazečů či seznamovací profil 1 000 protějšků) a vy byste měli každou z nich postupně vyhodnotit a vybrat, kdy zastavit, jaká je šance, že byste vybrali absolutně nejlepší možnost? Kdybyste vybírali náhodně, našli byste tu nejlepší jen v 0,1 % případů. I kdybyste zkusili strategii chytřejší než náhodné tipování, mohli byste mít smůlu, pokud by se nejlepší možnost náhodou objevila poměrně brzy, kdy vám chyběly srovnávací informace k jejímu odhalení, nebo poměrně pozdě, kdy už byste se mohli rozhodnout ze strachu z ubývajících příležitostí.

Optimální strategie vede k tomu, že si téměř v 37 % případů vyberete tip číslo jedna. Její úspěšnost také nezávisí na počtu kandidátů. I s miliardou možností a odmítnutím spokojit se s druhým nejlepším můžete najít svou jehlu v kupce sena ve více než třetině případů. Vítězná strategie je jednoduchá: Odmítněte prvních přibližně 37 procent bez ohledu na cokoli. Použijte je jen k tomu, abyste získali představu a povědomí o reálné nabídce. Pak si vyberte první následující nabídku, která je lepší než všechny předešlé, s nimiž jste se dosud setkali. Pokud takovou možnost nikdy nenajdete, pak si vyberete tu poslední.

K zábavě přispěje i oblíbená malá konstanta matematiků, e = 2,7183…, která se v řešení objeví. Známé také jako Eulerovo číslo. To je proslulé tím, že se objevuje po celé matematické krajině ve zdánlivě nesouvisejících situacích. Zdá se, že včetně problému nejlepší volby. Pod pokličkou jsou tyto odkazy na 37 procent v optimální strategii a odpovídající pravděpodobnost úspěchu ve skutečnosti 1/e, tedy asi 0,368. Magické číslo vychází z napětí mezi tím, že chcete vidět dostatek vzorků, abyste se mohli informovat o rozložení možností, ale nechcete čekat příliš dlouho, aby vás ta nejlepší neminula. Důkaz tvrdí, že 1/e tyto síly vyvažuje.

První známá písemná zmínka o problému nejlepší volby se objevila v oblíbeném sloupku Martina Gardnera „Matematické hry“ v Scientific American. Problém se v padesátých letech minulého století rozšířil ústním podáním v matematické komunitě a Gardner jej v únorovém čísle roku 1960 předložil jako malou hádanku pod názvem „Googol“ a následující měsíc přinesl jeho řešení. Dnes tento problém generuje tisíce přístupů na Google Scholar, protože matematici pokračují ve studiu jeho mnoha variant: Co když si můžete vybrat více než jednu možnost a vyhrajete, pokud je některá z vašich možností nejlepší? Co když protivník zvolil pořadí možností, aby vás oklamal? Co když nevyžadujete absolutně nejlepší volbu a cítili byste se spokojeni s druhou nebo třetí? Tyto a nespočet dalších scénářů, kdy zastavit, studují vědci v oboru matematiky zvaném „teorie optimálního zastavení“.

Hledáte dům – nebo manžela či manželku? Tvůrce matematických osnov David Wees aplikoval strategii nejlepší volby na svůj osobní život. Při hledání bytu si Wees uvědomil, že aby mohl konkurovat na trhu prodávajících, musel by se zavázat k bytu na místě při prohlídce dříve, než jej získá jiný kupující. Při svém tempu prohlídek a šestiměsíční lhůtě extrapoloval, že má čas navštívit 26 bytů. A 37 procent z 26 se zaokrouhluje na 10, takže Wees odmítl prvních 10 míst a podepsal první následující byt, kterému dal přednost před všemi předchozími. Bez prohlídky zbývající várky nemohl vědět, zda si skutečně zajistil to nejlepší, ale mohl být alespoň klidný, protože věděl, že maximalizoval své šance.

Michael Trick, dnes děkan Carnegie Mellon University v Kataru, ve svých dvaceti letech použil podobné úvahy i ve svém milostném životě. Usoudil, že lidé začínají randit v 18 letech, a předpokládal, že po čtyřicítce už randit nebude a že bude mít stálou frekvenci setkávání s potenciálními partnerkami. Pokud by vzal 37 procent z této doby, dostal by se do věku 26 let, kdy si slíbil, že požádá o ruku první ženu, kterou potká a která se mu bude líbit víc než všechny jeho předchozí schůzky. Potkal slečnu Pravou, poklekl na jedno koleno a okamžitě byl odmítnut. Problém nejlepší volby nezahrnuje případy, kdy vás příležitost může odmítnout. Možná bude lepší, když matematiku z romantiky vynecháme.

Empirický výzkum zjistil, že lidé mají tendenci zastavit hledání příliš brzy, když čelí scénáři nejlepší volby. Naučit se pravidlo 37 procent by tedy mohlo zlepšit vaše rozhodování, ale nezapomeňte si dvakrát ověřit, že vaše situace splňuje všechny podmínky problému: známý počet seřaditelných možností předložených po jedné v libovolném pořadí, chcete tu nejlepší a nemůžete se dvakrát vrátit. Téměř všechny myslitelné varianty problému byly analyzovány a úprava podmínek může změnit optimální strategii velkým i malým způsobem. Například Wees a Trick ve skutečnosti neznali celkový počet potenciálních kandidátů, takže místo nich dosazovali rozumné odhady. Pokud není třeba rozhodovat na místě, pak tím potřeba strategie zcela zaniká: stačí vyhodnotit každého kandidáta a vybrat svého favorita. Pokud zmírníte požadavek na výběr absolutně nejlepší možnosti a místo toho chcete pouze obecně dobrý výsledek, pak podobná strategie stále funguje, ale optimální se stává jiná prahová hodnota, obvykle dříve než 37 % (viz diskuse zde a zde). Ať už stojíte před jakýmkoli dilematem, pravděpodobně existuje strategie nejlepší volby, která vám pomůže skončit, dokud máte náskok.

Autor: Jack Murtagh je nezávislý matematický spisovatel a tvůrce hádanek. Píše sloupek o matematických zajímavostech pro časopis Scientific American a denně vytváří hádanky pro zpravodaj Morning Brew. Je držitelem doktorátu z teoretické informatiky na Harvardově univerzitě. Sledujte Jacka na X @JackPMurtagh

Zdroj: https://www.scientificamerican.com/ September 19, 2024 , This Elegant Math Problem Helps You Find the Best Choice for Hiring, House Hunting and Even Love, Jack Murtagh

---

Pozn.

Výraz Googol vznikl v roce 1938 tak, že se matematik Edward Kasner zeptal svého devítiletého synovce Miltona Sirrotu, jak by takové číslo nazval. Číslo je nesmírně velké – natolik, že převyšuje odhad počtu elementárních částic ve známém vesmíru. Název firmy Google je pravopisně chybný tvar slova „Googol“, který vytvořili zakladatelé společnosti Larry Page a Sergey Brin. (wiki)

Ilustrační obrázek je umělecká halucinace umělé „inteligence“ na téma:

„Euler’s number
little constant of mathematicians,
it seems to include the best choice problem,
under the hood,
these references to 37 percent optimal strategy,
magic number comes from the tension,
inform yourself about distribution of options,
but not wanting to wait too long,
the proof claims, 1/e balances these forces.“