Tag Archives: Mathe

Das Sekretärinnenproblem

Der NSC kann nun nicht nur mit Hilfe der Zeitreihenanalyse ermitteln, welchen Preis er für das angebotene Gut für fair hält,  sondern kann über die Nutzendifferenz von Gut und Geld auch genau den erwarteten Nutzen ermitteln (siehe auch Geld und Nutzen). Doch wie entscheidet er nun, ob er das Kaufangebot annimmt oder in der Hoffnung nach einem besseren Angebot (vorerst) ablehnt und weitersucht? Ein erster Schritt zur Antwort könnte das Sekretärinnenproblem sein, dessen Grundform ich in diesem Artikel vorstellen möchte.

In der Grundform des Sekretärinnenproblems werden nacheinander n Bewerber(innen) vorgestellt und nach der Evaluation des jeweils aktuellen Bewerbers muss sofort entschieden werden, ob die Bewerbung angenommen oder abgelehnt wird. Es darf nur genau eine Bewerbung angenommen werden (also wenn eine Bewerbung angenommen wird, gehen alle vielleicht noch kommenden besseren Bewerber verloren) und eine einmal abgelehnte Bewerber(in) ist dauerhaft verloren. Es gibt nur zwei Ausgänge: Sieg (die beste Bewerbung wurde angenommen, Zielfunktionswert 1) oder Niederlage (die beste Bewerbung wurde nicht angenommen, Zielfunktionswert 0). Die Aufgabe ist es, eine optimale Annehm- / Ablehnstrategie zu finden, also eine Strategie, in der die Chance, die beste Bewerbung anzunehmen, maximal ist. [1]

In dieser einfachen Version gibt es für das Sekretärinnenproblems geschlossene Lösungen [1]. Doch die Situation mit unserem NSC wird von den Annahmen der Grundform nicht abgedeckt, so zum Beispiel:

  • Der Zielfunktionwert entspricht dem Nutzen des angenommenen Kaufangebots (abzüglich der Evaluationskosten) und wird nicht 0, wenn es eine bessere Option gegeben hätte.
  • Die Evaluation einer weiteren Option kostet Zeit (Weg zum nächsten Händler..).
  • Es ist möglich, eine abgelehnte Option noch einmal zu evaluieren, dies verursacht erneut Evaluationskosten (Weg zurück zum Händler) und eventuell ist das Angebot nicht mehr gültig.
  • Die Anzahl der möglichen Kaufangebote ist a priori nicht notwendigerweise bekannt.

[1] P.R. Freeman. 1983. The Secretary Problem and its Extensions: A Review. International Statistical Review, 51 (1983), pp. 189-206.

Posted in Inspiration-O-Matic, Theory-O-Matic. Tagged with , , .

KI und Preisentwicklung

Während die Testumgebung für die erste Version der KI für unsere NSCe noch im Bau ist, kann man ja schon einmal über erste Erweiterungen nachdenken :) Der momentan größte Dorn in meinem Auge ist das fehlende Preisgefühl der NSCe. Momentan ist es so, dass der NPC Dinge kauft (weil sich das als gut erwiesen hat) und zwar unabhängig vom Preis, zu dem das Gut gerade angeboten wird. Das ist für die spätere Integration in ein größeres System mit einem Wirtschaftssystem natürlich fatal. Zum einen ist es geradezu eine Aufforderung zum Exploit an alle Spieler. Zum anderen macht es das Wirtschaftssystem unberechenbar, wenn eine nicht vernachlässigbare Anzahl an Teilnehmernsich eben nicht rational verhält. Das erste neue Ziel ist also die Antizipation des NSCs von Preisentwicklungen.

Als Mittel der Wahl, um Preisentwicklungen mathematisch zu berücksichtigen, ist die Zeitreihenanalyse. Genauer gesagt war mein erster Gedanke ein in den Wirtschaftswissenschaften gängiger Ansatz der Zeitreihenanamyse, das Trend-Saison-Modell. Hier werden Preisdaten über die Zeit erhoben und in Trend-, Saison- und Rauschkomponente unterteilt. Die Trendkomponente beinhaltet die langfristige, nicht periodische Entwicklung des Preises. Die Saisonkomponente enthält saisonal periodisch wiederkehrende Effekte. Die Rauschkomponente enthält nicht erklärbare, unregelmäßige Effekte. Momentan ist nicht absehbar, dass wir überhaupt Saisoneffekte haben werden, also können wir wohl auf die Saisonkomponenete verzichten. Plan?

Posted in Theory-O-Matic. Tagged with , , , .

Fast ein Baum im Baum..

Wie versprochen möchte ich immer mal wieder auf interessante Aspekte in Konzeption und Coding der von mir implementierten Features eingehen. Dabei geht es mir nicht so sehr um eine flächendeckende Beschreibung – ich habe nicht vor, die Doku in den Blog zu verlagern ;) – sondern darum, einzelne, aus meiner Sicht schöne oder interessante Stellen zu erläutern. Beginnen möchte ich dabei mit einer Stelle in der Simulation der Umwelt, genauer mit der Auswertungsreihenfolge der Umweltfaktoren.

Die Menge der durch Photosynthese umgewandelte und damit der Pflanze zur Verfügung stehenden Energie hängt von einer Reihe von abiotischen Faktoren ab, die sich gegenseitig beeinflussen (siehe auch Wikipedia). In der realen Welt sind dies Kohlenstoffdioxid, Licht, Wasser und Temperatur. In einer fiktiven Welt können natürlich beliebige Umweltfaktoren wie Magie, Schall oder eine andere Art Licht hinzukommen. Diese Umweltfaktoren beeinflussen sich gegenseitig und beeinflussen die Effektivität der Photosynthese, ein paar Beispiele aus der realen Welt sind: Die Menge an aufnehmbaren Kohlenstoffdioxid kann gedrosselt werden durch die Wassermenge bzw. die Luftfeuchtigkeit, die Temperatur beeinflusst die Photosyntheserate. Wenn man beliebige Kombinationen von beliebig vielen verschiedenen Umweltfaktoren zulassen möchte, stellen sich vor allem zwei Probleme:
1. In welcher Reihenfolge können die Umweltfaktoren ausgewertet werden? Im obigen Beispiel sollte die Wassermenge berechnet werden, bevor die Kohlenstoffdioxidmenge berechnet wird, da dieses Ergebnis von der aufgenommenen Wassermenge abhängt.
2. Wie bildet man alle möglichen Beeinflussungsarten wie “beeinflusst die Photosyntheserate” oder “setzt eine obere Grenze” ab?

Wir beschäftigen uns zunächst (also in diesem Beitrag) mit der ersten Frage. Da theoretisch beliebige Kombinationen von a priori nicht bekannten Umweltfaktoren möglich sein sollen, kann dem Programm keine vorher festgelegte Reihenfolge vorgegeben werden. Wie soll eine solche Reihenfolge also festgelegt werden? Dazu zunächst ein wenig Graphentheorie [1], wirklich nur ein ganz wenig. Ein gerichteter Graph G = (V, E) besteht aus einer Menge von Knoten V und eine Menge von gerichteten Kanten E, wobei jede Kante definiert ist als ein geordnetes Paar von Knoten. Ein solcher gerichteter Graph ist kreisfrei, falls es keinen Weg gibt, der aus einem Knoten heraus und später wieder in ihn hinein führt. Wenn wir unsere Problemstellung nun übersetzen in die neu gelernten Begriffe, so ist jeder Umweltfaktor ein Knoten und immer, wenn ein Umweltfaktor einen anderen Umweltfaktor beeinflusst, zeichnen wir eine Kante vom Knoten des ersten Umweltfaktors zum Knoten des zweiten Umweltfaktors. Wenn in diesem Graph ein Kreis auftritt heißt das, dass sich die Umweltfaktoren ringförmig beeinflussen, also zum Beispiel wäre “Wassermenge beeinflusst Kohlenstoffdioxidmenge beeinflusst Magie beeinflusst Wassermenge” ein Kreis. Diesen Fall wollen wir ausschließen, da man sich in der Berechnung sonst ewig im Kreis drehen könnte. Wir haben nun also einen kreisfreien, gerichteten Graphen vorliegen. Ein solcher Graph ist topologisch sortiert, wenn man eine Reihenfolge der Knoten gefunden hat, in der für jede Kante der Endknoten weiter hinten in der Reihenfolge liegt als der Anfangsknoten. Wenn man eine solche topologische Sortierung der Umweltfaktoren hat und die Umweltfaktoren in dieser Reihenfolge auswertet, dann beeinflusst jeder Umweltfaktor nur Umweltfaktoren, die später ausgewertet werden -> perfekt :)

Ist man erst einmal zu dieser Erkenntnis gelangt, dann ist der Rest kein Hexenwerk mehr – ein Algorithmus zum topologischen Sortieren von Graphen ist schnell gefunden. Man startet mit einer leeren Liste bereits sortierter Knoten und sucht in jeder Iteration im Graphen nach Knoten ohne eingehende Kanten, nimmt diese ans Ende der Liste bereits sortierter Knoten auf und entfernt den Knoten und alle ausgehenden Kanten aus dem Graphen. Am Ende ist der Graph leer und die Knoten sind topologisch sortiert. In der so ermittelten Reihenfolge werden die Umweltfaktoren dann vom Programm ausgewertet. Das obige Beispiel hat als eine mögliche topologische Sortierung Wasser -> Temperatur -> Luftfeuchtigkeit ->Kohlenstoffdioxid -> Licht.

[1] Algorithmische Graphentheorie, Volker Turau, Oldenbourg Verlag, 3. Auflage, 2009

Posted in Code-O-Matic, Theory-O-Matic. Tagged with , , .