Den bortglömda algoritmen

1944, när kriget äntligen vände, stötte brittiska flygvapnet (RAF) på ett problem enkelt nog för ett barn att formulera — och svårt nog att de aldrig löste det innan kriget tog slut.

Skvadroner upplöstes. Tiotusentals utbildade människor — piloter, navigatörer, mekaniker, radiooperatörer — skulle flyttas till nya roller. En enda fråga, upprepad tusentals gånger: vem ska göra vad?

Arbetet föll till stor del på kvinnorna i WAAF — flygvapnets handläggare och registerförare. Inga datorer. Allt man visste om varje person fanns på papper — tjänstgöringskort, yrkesklassificeringar, mycket av det månader inaktuellt — som drogs fram, sorterades och bars mellan skrivborden för hand. Rum fulla av kvinnor som parade ihop människor med tjänster, en mapp i taget.

Och även med perfekta register hade de kört fast. För frågan är en fälla.

En fälla förklädd till trivialitet

Den bästa personen för ett jobb är oftast bäst för flera andra också. Ge dem till en tjänst, och du har i tysthet gjort de andra sämre. Du kan inte välja en i taget — varje val rör vid alla andra. För att göra det rätt måste du väga varje person mot varje roll samtidigt och hitta den enda bästa helhetslösningen.

Med en handfull personer går det. Med tiotusentals är antalet möjliga kombinationer större än något någon någonsin skulle kunna gå igenom. För hand är det omöjligt.

Så de gjorde sitt bästa på känsla, och kriget tog slut innan någon knäckte det. Problemet var verkligt nog att starta ett decennium av forskning — det fick ett namn, "tilldelningsproblemet", 1952, och en fungerande lösning 1955.

Men inget av det hade behövts. Svaret fanns redan. Det hade bara glömts bort.

Uppfunnet av misstag, ett sekel för tidigt

Hundra år tidigare hade den tyske matematikern Carl Gustav Jacobi redan löst det — och inte för att han brydde sig om jobb eller tjänster. Han var djupt inne i den klassiska mekanikens differentialekvationer. Någon gång mellan 1829 och 1836, när han räknade ut hur man avgränsar komplexiteten i ett ekvationssystem, stötte han på ett delproblem — para ihop n saker med n saker så billigt som möjligt — och uppfann, nästan i förbigående, en metod att lösa det.

Han byggde, på 1830-talet, en bit optimering som inte skulle "behövas" förrän ett sekel senare — som ett sidoverktyg för himlamekanik. Sedan dog han, 1851, innan det kunde betyda något för någon. Hans metod publicerades efter hans död, på latin, i en volym nästan ingen läste. Och där låg den — svaret på ett problem som arméer och företag skulle fortsätta gå rakt in i — i över hundra år.

Vilket betyder att kvinnorna i registerrummen 1944 slet för hand, år efter år, med ett problem som redan var löst — och bortlagt, på ett språk nästan ingen av dem kunde läsa.

Hittat, tappat, hittat, tappat

Så världen härledde det på nytt från grunden. I Budapest byggde två matematiker — Dénes Kőnig och Jenő Egerváry — grafteorin som knäckte samma problem igen, 1916 och 1931. Bortglömt igen. Tills amerikanen Harold Kuhn satte ihop det till en praktisk procedur 1955 och döpte det till "den ungerska metoden", till Kőnigs och Egervárys ära — utan en aning om att Jacobi slagit dem alla med ett sekel. Ingen visste förrän 2005, då den franske matematikern François Ollivier gick tillbaka till Jacobis latinska papper, översatte dem, och insåg att verktyget begravt där i grunden var samma metod.

Ett löst problem, tappat och återfunnet genom tre århundraden.

Så vad var svaret?

Tänk dig problemet som ett rutnät: varje person längs ena sidan, varje jobb längs överkanten, och i varje ruta ett tal — hur bra, eller hur dyr, just den parningen vore.

Det självklara draget är girigt: hitta den enskilt bästa rutan, lås den, stryk dess rad och kolumn, upprepa. Det känns rätt. Det är precis fällan — den bästa rutan för en person stjäl det bästa alternativet från tre andra.

Genombrottet — funnet, och återfunnet, av alla i den här historien — var att bearbeta hela rutnätet på en gång:

Jacobi kom på att man systematiskt kan subtrahera värden över rutnätet för att blottlägga vilka parningar som i praktiken var "gratis", och reducera alltihop tills den enda bästa helhetslösningen föll ut.
Kőnig och Egerváry ritade om det som en bild: två rader prickar — människor på ena sidan, roller på den andra — sammanbundna med linjer. Deras satser bevisade exakt när man kan koppla ihop alla på en gång med bästa möjliga uppsättning linjer.
Kuhn gjorde det till ett rent, upprepbart recept: dra bort det minsta talet i varje rad, sedan i varje kolumn; täck alla nollor som uppstår med så få linjer som möjligt; om du ännu inte kan plocka en komplett uppsättning parningar ur nollorna, justera rutnätet och upprepa. När du kan — är du klar, och det är bevisbart den bästa lösningen, nådd på en handfull genomgångar istället för att testa de oändligt många.

Inte ett bättre sätt att ranka. Ett sätt att optimera hela parningen på en gång. Det kontraintuitiva i det: den bästa personen ska ofta inte få den roll de är bäst på, eftersom helheten blir bättre om de hamnar någon annanstans. Ranking kan inte se det. Matchning kan.

Vilket gör nutiden lite absurd

Den idén driver i tysthet den moderna världen — flygbolagens besättningar, logistik, ride-hailing. En angränsande gren, stabil matchning, placerar läkare på sjukhus och njurar i patienter, och belönades med Nobelpriset 2012. Matchning, rätt gjort, är en av de mest dekorerade idéerna i tillämpad matematik.

Och ändå gör det mesta av dagens "AI-matchning" det enda som ett sekel av teori säger att man inte ska: den rankar. Ta ena sidan, poängsätt den mot den andra med en språkmodell, returnera en sorterad lista. Det ser ut som matchning. Det är sök med extra steg.

Varför faller vi alltid tillbaka på det? För att ranking är intuitivt, sök är paradigmet vi vuxit upp med, och språkmodeller gör ranking trivialt — så alla griper efter det. Och det har exakt det fel RAF skulle ha känt igen: ranka alla mot samma måttstock och alla jagar samma topp-tio-procent. De "bästa" drunknar i uppmärksamhet, resten blir osynliga, och systemet matchar dåligt — även om varje enskild poäng var "rätt".

Riktig matchning är väsensskild. Den behandlar båda sidor som väljande. Den respekterar kapacitet — en plats fylls, en person tar ett jobb. Den optimerar helheten, inte den-bästa-för-var-och-en. Inget av det faller ut ur en större modell eller en smartare prompt. Det är ett annat problem — med ett mycket gammalt, mycket bortglömt svar.

Matchar du, eller rankar du bara?

Det anmärkningsvärda är inte att matchning är svårt. Det är att vi löser det och glömmer det, om och om igen. Jacobi på latin. Ungrarna i grafteori. Kuhn 1955. Ett Nobelpris 2012. Och här är vi igen — boltar språkmodeller på sök och kallar det matchning.

Så om du bygger något som parar ihop två sidor — människor med jobb, köpare med säljare, vad som helst med vad som helst — är den verkliga frågan inte vilken modell du använder. Det är den RAF inte kunde svara på 1944, och den Jacobi tyst hade svarat på ett sekel tidigare:

Matchar du? Eller rankar du bara?

Tim Brandin har byggt matchning av det riktiga slaget i åtta år — det är det mesta han tänker på, på tr8s.