© Jozef Polc, 123RF

Wann ist es statistisch günstig, etwa die Suche nach einem geeigneten Ehepartner mit einer Auserwählten abzuschließen? Solide Algorithmen weisen den Weg zum Erfolg.

Man soll aufhören, wenn es am schönsten ist, heißt es. Im wahren Leben ist die Entscheidung, etwa ein Auswahlverfahren abzuschließen, oft nicht so einfach. In der mathematischen Statistik bringt es das so genannte “Sekretärinnenproblem” [2] auf den Punkt. Gegeben sei eine Reihe von Bewerberinnen für den Posten einer Sekretärin. Im Auswahlverfahren muss sich der Arbeitgeber nach jedem Bewerbungsgespräch entscheiden, ob er die Kandidatin einstellt oder eine Absage erteilt und hofft, später eine geeignetere Bewerberin zu finden. Die Entscheidung ist endgültig, abgelehnte Bewerber darf er nicht wieder einladen.

Ein logisch denkender Arbeitgeber dürfte die ersten paar Kandidatinnen sorgsam prüfen und nicht die erstbeste einstellen. Später, wenn die Schlange sich dem Ende zuneigt, wird er vielleicht schon bei einer halbwegs passenden Bewerberin zupacken, aus Furcht, am Ende mit einer ungeeigneten Kandidatin dazusitzen und keine Wahl zu haben, als sie zähneknirschend einzustellen.

Optimal: 37 Prozent

Wie soll der Arbeitgeber vorgehen, damit sich ihm mathematisch gesichert die besten Chancen bieten, eine überdurchschnittliche Kandidatin einzustellen? Wie lange soll die Schnüffelphase dauern, in der er die unbekannten Fähigkeiten der Kandidatinnen sondiert, um später jene, die besser ist als alle bisherigen, sofort einzustellen? Solche optimalen Stopp-Probleme [3] beschäftigen Mathematiker schon ewig.

Wie das kürzlich erschienene Buch “Algorithms to Live By” [4] unterhaltend erläutert, liegt die Antwort bei 37 Prozent, genauer gesagt »1/e * 100 Prozent« . Bei 100 Kandidatinnen ist der Arbeitgeber gut beraten, die ersten 37 ohne Einstellungsabsicht zu sondieren, um sich ein Bild von den auf dem Arbeitsmarkt verfügbaren Talenten zu machen. Ab Kandidatin Nummer 38 schnürt der schlaue Boss dann sofort den Sack zu, falls eine besser als alle bisherigen ist.

Liebestoller Sterngucker

Diese Aufgabe ist auch als Heiratsproblem bekannt. Legendär ist die Geschichte des berühmten Sternguckers Johannes Kepler, der 1611 nach dem Tod seiner ersten Ehefrau verzweifelt eine neue suchte. Mathematisch akribisch erforschte er in einem langwierigen Prozess der Reihe nach nicht weniger als elf Kandidatinnen, um dann völlig ausgelaugt und reumütig zur Kandidatin Nummer fünf zurückzukehren, ihr einen Antrag zu machen und darauf zu seinem großen Glück ein glühendes “Ja!” zu erhalten.

Wirklichkeit simulieren

Um das Sekretärinnenproblem mit einem Perl-Skript durchzuspielen, muss dies gewisse Annahmen über die Verteilung des Angebots auf dem Arbeitsmarkt machen. Die umstrittene “20-70-10”-Regel des amerikanischen Tycoons Jack Welch [5] diktiert, dass in einem Unternehmen 20 Prozent Top-Performer-Leistung bringen, 70 Prozent ordentlich arbeiten und 10 Prozent unproduktiv sind. Für das Experiment soll der Arbeitsmarkt diesem Schema folgen, die zur Auswahl stehenden Talente liegen also in etwa auf einer Glockenkurve der Gaußschen Normalverteilung (Abbildung 1).

Abbildung 1: Die Gaußsche Glockenkurve normalverteilter Ereignisse.

Da die Kandidatinnen in zufälliger Reihenfolge eintrudeln, braucht das Skript einen Zufallsgenerator, der einen normalverteilten Talentpool erzeugt. Das CPAN-Modul Math::Random verfügt mit der Funktion »random_normal()« schon über einen solchen Generator, der in Listing 1 mit den Parametern »100_000, 10, 2« genau 100000 Zufallswerte zurückgibt, die mit einer Standardabweichung von 2 um den Mittelwert 10 schwärmen.

1 #!/usr/local/bin/perl -w
2 use strict;
3 use Math::Random qw( random_normal );
4 use Statistics::Histogram;
5
6 my @data = random_normal( 100_000, 10, 2 );
7
8 print get_histogram( \@data, 20 );

Um zu prüfen, ob die Verteilung auch optisch grob den Vorgaben entspricht, gibt Listing 1 mit der Funktion »get_histogram()« aus dem CPAN-Modul Statistics::Histogram ein Histogramm der verteilten Werte als ASCII-Art im Terminal aus. Die Glockenform stellt sich in der Tat ein (Abbildung 2), und während der Mittelpunkt der Zufallsdaten bei etwa 10 liegt, fällt die Häufigkeit zu den Seiten hin ab, es finden sich kaum Werte kleiner als 4,5 oder größer als 15,5.

Abbildung 2: Glockenkurve normalverteilter Ereignisse.

Das Skript für die Bewerbungsgespräche (Listing 2) knöpft sich die zufällig eintrudelnden Kandidatinnen der Reihe nach vor. Gemäß der 37-Prozent-Regel zerlegt es das Array »@data« in zwei Teile. Der in »@look« liegende erste Teil enthält die ersten 37 Prozent der Zufallszahlen, die nur der Analyse des Arbeitsmarkts ohne Einstellungsabsicht dienen, der zweite (»@act« ) die übrigen 63 Prozent, bei denen der Arbeitgeber sofort zugreift, falls eine Kandidatin aus der Masse herausragt. Zeile 41 stoppt das Skript, wenn dieser Fall eintritt.

01 #!/usr/local/bin/perl -w
02 use strict;
03 use Math::Random qw( random_normal );
04 use Log::Log4perl qw(:easy);
05 use Getopt::Long;
06
07 GetOptions( \my %opts, "verbose" );
08
09 Log::Log4perl->easy_init(
10   $opts{ verbose } ? $DEBUG :
11   $INFO );
12
13 my $nof_candidates = 10;
14 my @data = random_normal(
15     $nof_candidates, 10, 2 );
16
17 my $ratio  = 37.0;
18 my $cutoff = $nof_candidates *
19              $ratio / 100;
20
21 my @look = splice @data, 0, $cutoff;
22 my @act  = @data;
23
24 my $best = 0;
25
26 for my $talent ( @look ) {
27   DEBUG "Testing: $talent";
28
29   if( $talent > $best ) {
30     $best = $talent if $talent > $best;
31     DEBUG "New best: $best";
32   }
33 }
34
35 for my $talent ( @act ) {
36   DEBUG "Acting on: $talent";
37
38   if( $talent > $best ) {
39     DEBUG "Taking: $talent";
40     print "$talent\n";
41     exit 0;
42   }
43 }
44
45 DEBUG "Forced to take $act[ -1 ]";
46 print "$act[ -1 ]\n";

Zeigt sich bis zum Ende des Array keine bessere Kandidatin, hat der Boss allerdings verspielt und muss wider Willen die letzte Bewerberin einstellen, was Zeile 46 ausgibt. Mit der Option »–verbose« aufgerufen, schaltet Listing 2 in Zeile 9 Log4perls Logging-Funktionen in den Debug-Modus.

Das Skript gibt nun während des Ablaufs auf der Standardausgabe einige Meldungen aus. Abbildung 3 zeigt, dass die Messlatte für Kandidatinnen während der Screening-Phase bei 11.05 liegt, dann bei 11.52. Im Einstellungsmodus folgt dann erst eine Reihe von Kandidatinnen mit Eignungswerten unter der bisherigen Bestmarke von 11.52, bevor eine mit dem Wert 11.68 den Job bekommt.

Abbildung 3: Das Auswahlverfahren für Sekretärinnen, erster Lauf.

Das Verfahren ist zwar erwiesenermaßen optimal, läuft aber auch oft schief. Abbildung 4 zeigt einen Lauf, der in der Testphase einer Kandidatin mit extrem hohem Eignungswert (12.84) begegnet, gegen die später, als der Chef in Einstellungsstimmung ist, alle anderen verblassen. Pech, der Boss muss die letzte Kandidatin mit dem Wert 9.36 nehmen.

Abbildung 4: Nicht immer profitiert bei diesem Verfahren der Chef.

Wie oft treten solche für die Firma peinlichen Schwachstellen im Algorithmus auf? Um das zu messen, ruft Listing 3 das Skript »secretary« 100-mal auf und misst, wie häufig eine Kandidatin den Vorzug erhält, obwohl sie unter dem Mittelmaß liegt. Das CPAN-Modul Stats::Histogram stellt die Verteilung dar.

01 #!/usr/local/bin/perl -w
02 use strict;
03 use Log::Log4perl qw(:easy);
04 use Statistics::Histogram;
05 use Getopt::Long;
06
07 GetOptions( \my %opts, "verbose" );
08
09 Log::Log4perl->easy_init(
10     $opts{ verbose } ? $DEBUG :
11     $INFO );
12
13 my @data = ();
14
15 my $clowns = 0;
16 my $stars  = 0;
17
18 for ( 1..100 ) {
19     my $talent = `./secretary`;
20     chomp $talent;
21
22     DEBUG "Result: $talent";
23
24     if( $talent >= 10 ) {
25         $stars++;
26     } else {
27         $clowns++;
28     }
29
30     push @data, $talent;
31 }
32
33 INFO get_histogram( \@data, 20 );
34
35 INFO "Stars: $stars Clowns: $clowns";

Abbildung 5 zeigt, dass das Verfahren in etwa 80 Prozent der Fälle eine akzeptable Kandidatin findet, inklusive einiger Superstars mit Werten über 12. Allerdings versagt es in 20 Prozent der Fälle, in denen der Chef die letzte Kandidatin nehmen muss, egal ob Star oder Clown. Insgesamt ist die Strategie aber optimal, unter [2] lässt sich der Beweis nachlesen.

Las Vegas und Alltag

Genau wie es in Las Vegas korrekte und inkorrekte Verfahren gibt, um bestimmte Gewinnspiele zu spielen, und es mich jedes Mal erstaunt, wie wenige Leute sich Gedanken darüber machen, dem Casino wenigstens statistisch so wenig Chancen wie möglich zu lassen, ist es auch im Alltag wichtig, bei zufallsgesteuerten Prozessen die Oberhand zu wahren und immer den optimal möglichen Gewinn aus so einer Situation zu ziehen.

Abbildung 5: In 20 Prozent der Fälle bleibt dem Boss nur die letzte Kandidatin.

Bei einigen Stopp-Problemen ist die mathematisch beweisbar optimale Strategie allerdings wenig praktikabel: In einem Casino, das nach einem Münzwurf mit einer Gewinnwahrscheinlichkeit von 50 Prozent den dreifachen Einsatz zurückzahlt, lautet die spieltheoretisch korrekte Devise: Immer weiterspielen, nie aufhören. Nach Hause ginge der Spieler jedoch dann jedes Mal bankrott.

Der Autor

Michael Schilli arbeitet als Software Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen der Skriptsprache Perl. Unter mailto:mschilli@perlmeister.com beantwortet er gerne Fragen.