Tag Archives: WiWi

Einführung in BPMN

So, nachdem ich nun schon einige Artikel mit Ablaufdiagrammen gepostet habe (so zum Beipiel zur Optionsauswahl, zum allgemeinen Ablauf der KI und zur Kaufentscheidung) wurde ich nun gefragt, wie man diese eigentlich liest. Kurz gestockt, hmm, stimmt, das gehört wohl nicht zum Standardausbildungskanon ^^ Also die genutzte Notation ist die BPMN, also die Business Process Modelling Notation.

In diesem Artikel möchte ich kurz auf diese eingehen und die zentralen (also die von mir genutzten) Symbole erläutern, nach dieser kurzen Einführung sollte das Lesen der von mir geposteten Ablaufdiagramme also kein Problem mehr sein :)

Continue reading

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

Ablauf Kaufangebot

Nachdem ich in den letzten Artikeln einige Tools / Änderungen (Zeitreihenanalyse, Nutzen von Gegenständen, Geld.., Sekretärinnenproblem mit Lösungsansätzen) zur Evaluation von Kaufangeboten zusammen getragen habe, ist es wohl mal an der Zeit, die Ergebnisse des Brainstormings zu ordnen. Unten seht ihr ein Ablaufdiagramm, wie ich mir momentan die Kaufentscheidung vorstelle.

Der Plan ist also folgender: Der NSC erhält ein Kaufangebot, hierdurch wird der ganze Prozess getriggert. Der Erhalt des Kaufangebots kann natürlich einmal wirklich ein “spontan” erhaltenes Angebot sein, aber auch ein eingeholtes Kaufangebot, weil sich für die Option “Item xy kaufen” entschieden wurde. Der NSC ermittelt dann (aus der SOM) einerseits den Nutzen des Gutes bzw. der Güter und andererseits den Nutzen des zu zahlenden Geldes. Wenn der Nutzen des Geldes überwiegt, brauchen keine weiteren Überlegungen angestellt werden -> das Angebot ist für den NSC unattraktiv und kann abgelehnt werden. Überwiegt der Nutzen des Gutes / der Güter den Nutzen des Geldes, dann ist das Angebot generell attraktiv für den NSC. Statt das Gut aber sofort zu kaufen, muss der NSC nun entscheiden, ob er das Angebot annimmt, oder (woanders) ein anderes Angebot einholt. Entsprechend wird das vorliegende Angebot dann angenommen oder abgelehnt.

Dieser Ablauf lässt sich natürlich noch verfeinern, für die Zukunft schwebt mir als erste kleine Erweiterung vor, dass der NSC handelt. Sowohl im Falle der Ablehnung eines unattraktiven Angebots, als auch im Falle eines attraktiven Angebots kann der NSC die vorhandenen Info als sehr gute Verhandlungsgrundlage nutzen. Aber das ist mal wieder Zukunftsmusik.. Aber Musik ist schließlich was Feines..

Ablauf Kaufangebot

Ablauf Kaufangebot

 

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

mehr zum Sekretärinnenproblem

Nachdem das Sekretärinnenproblem in seiner Grundform unseren Anforderungen nicht gerecht wurde, will ich in diesem zweiten Artikel ein paar Erweiterungen aus der Literatur vorstellen. Vier (erste) Kritikpunkte wurden schon erwähnt, mal sehen was die Literatur dazu sagt:

Der Zielfunktionwert ist im Standardproblem entweder 1 (bester Kandidat gewählt) oder 0 (sonst).  Bei uns ist der Zielfunktionswert der Nutzen des angenommenen Kaufangebots (abzüglich der Evaluationskosten). Allgemeine Nutzenfunktionen wurden schon 1973 von Mucci vorgestellt. Diese sind (mit einigen Voraussetzungen, die bei uns gelten) wie die Grundform lösbar [1].

Im Standardproblem kommen die Kandidaten zum Entscheider, der NSC nachher muss den nächsten Händler (wahrscheinlich) aufsuchen. Dadurch entstehen Evaluationskosten (also Wegezeit). Auch Evaluationskosten wurden bereits in der Literatur behandelt, zuerst von Lorenzen in 1978 [4]. Mit allgemeiner Nutzenfunktion (ohne die Möglichkeit, zurück zu gehen und eine abgelehnte Option anzunehmen) lässt sich auch diese Aufgabe (unter gewissen Voraussetzungen) geschlossen lösen [5].

In der Grundform des Sekretärinnenproblems ist eine einmal abgelehnte Option dauerhaft verloren. Dem NSC wird es möglich sein, den Händler eines abgelehnten Angebots noch einmal zu besuchen und das Angebot (so der Händler es noch anbietet) doch noch anzunehmen. Schon 1974 wurde diese Erweiterung von Yang vorgestellt [2], gelöst wird auch diese Form mit dynamischer Programmierung [1].

Auch eine unbekannte Anzahl an Kandidaten wurde in der Literatur schon behandelt [1]. Doch diesen Punkt können wir uns eigentlich schenken – man kann leicht abschätzen, wie viele Händler besuchen ob der Evaluationskosten überhaupt Sinn macht und darüber lässt sich die Anzahl der Kandidaten schon gleich ab Anfang beschränken.

Soo, soweit zu den einzelnen Punkten.. Aber wir brauchen ja alle Punkte zusammen.. Das dann demnächst mit eigenem Hirnschmalz.

[1] P.R. Freeman. (1983). The Secretary Problem and its Extensions: A Review. International Statistical Review, 51 (1983), pp. 189-206.
[2] Smith, M.H. (1975). A secretary problem with uncertain employment. J. Appl. Prob. 12, pp. 620-624.
[3] Mucci, A.G. (1973). Differential equations and optimal choice problems. Ann. Statist. 1, pp. 104-113.
[4] Lorenzen, T. J. (1978). Generalising the secretary problem. Adv. Appl. Prob. 11, pp. 384-396.
[5] Lorenzen, T. J. (1981). Optimal stopping with sampling cost: the secretary problem. Ann. Prob. 9, pp. 167-172.

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

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 , , .

Geld und Nutzen

Wenn der NSC nun mit Hilfe der Zeitreihenanalyse festgestellt hat, welchen Preis er momentan für fair hält, muss er entscheiden, ob der das Gut kauft oder eben nicht. Klar, zu einem guten Preis, der nah am ermittelten aktuellen “Marktpreis” oder sogar darunter liegt, wird der NSC das gewünschte Gut kaufen. Doch je nach subjektiver Wichtigkeit des Gutes, wird er vielleicht auch zu einem höheren Preis kaufen. Wenn er Hunger leidet, sollte er in Betracht ziehen, auch überteuerte Lebensmittel zu kaufen, nicht in jeder Situation und nicht um jeden Preis, aber es sollte nicht kategorisch abgelehnt werden.

Also werde ich wohl nicht umhin kommen, eine für wesentlich später geplante Erweiterung vorzuziehen: Momentan haben lediglich Optionen einen (erwarteten) Nutzen, also einen sich verändernden Eintrag in der SOM. Die Optionen lauten dann zum Beispiel “Brot essen”. Für später war geplant, dass es sowohl elementare Optionen als auch zusammengesetzte Optionen (z.B. [kaufen, Preis, Item], [laufen, Aufenthaltsort, Zielort], [anheuern, Art der Arbeit, Lohn], [essen, Item]) geben wird. Die elementaren Optionen haben jeweils einen SOM Wert. Bei den zusammengesetzten Optionen ist dem NPC bekannt, welche Änderung in Aufenthaltsort und Inventar (inklusive Geld) sich aus der Option (evtl. mit welcher Wahrscheinlichkeit) ergeben werden. Für jedes Item (inklusive Geld), jeden Ort und jede Wegstrecke wird je ein SOM Eintrag für Besitz (bzw. Nichtbesitz), Aufenthalt und Nutzungsmöglichkeiten (z.B. essen, passieren) gespeichert. Aus diesen Werten ermittelt der NSC dann den Nutzen für diese Option, also zum Beispiel bei einem Kaufangebot für ein Item x zum Preis y wird nachgesehen, welcher Nutzen u(Item x) für den Besitz für Item x eingetragen ist, wie viel Nutzen u(Geld) er pro Besitz von einer Einheit Geld erwartet und der Nutzen der Kaufoption ist dann u(Item x) – y * u(Geld).

Welche Objekte bekommen dann jeweils einen SOM Eintrag? Meine momentane Auflistung enthält:

  • elementare Optionen
  • jedes Item für jede mögliche, definierte Nutzung von eben diesem (z.B. [(Brot, 100g), essen]), inklusive der Spezialfälle
    • [Item, besitzen] und
    • [Geld, besitzen],
  • jeder Ort (jede Art Ort?) für den Aufenthalt (z.B. ),
  • jeder Weg zwischen zwei benachbarten Orten mit der Aktivität laufen (z.B. [laufen, Taverne, Marktplatz]) und
  • Zeit.
Posted in Code-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 , , , .