Spieltheorie, Optimierungsproblem: Finde die beste Wohnung |
| 30.10.2013, 22:11 | Hubert1965 | Auf diesen Beitrag antworten » |
| Spieltheorie, Optimierungsproblem: Finde die beste Wohnung Für folgendes Problem kenne ich eine optimale Strategie: einfaches Problem: In einer Kneipe befinden sich n Personen die paarweise verschieden groß sind. Die größte dieser Personen ist ein gesuchter Verbrecher. Vor der Kneipe wartet ein einzelner Polizist um ihn zu verhaften und zu verhören. Der Polizist darf nicht ins Lokal weil im Lokal gerade eine geschlossene Veranstaltung mit geladenen Gästen stattfindet und der Polizist weder eine Einladung noch einen Durchsuchungsbefehl hat. Als die Veranstaltung zu Ende geht, verlassen die Gäste einzeln das Lokal, jeweils mit einem Abstand von mehreren Minuten. Wie sollte der Polizist vorgehen, um mit größtmöglicher Wahrscheinlichkeit den Verbrecher zu erwischen? Wichtige Zusatzinformation: Keiner der Gäste weiß, dass draußen ein Polizist wartet, es ist also damit zu rechnen, dass die Reihenfolge, in der die Gäste das Lokal verlassen, rein zufällig ist. Lösung (soweit ich mich daran erinnere und ohne Beweis): Der Polizist lässt die ersten m Personen unbehelligt gehen und merkt sich die maximale Größe dieser m Personen. Dann schnappt er sich die erste Person die danach das Lokal verlässt und größer als dieses Maximum ist. Diese Strategie kann auf zwei Arten schief gehen:
m hängt auf sehr einfache Weise von n ab (leider habe ich vergessen, wie genau dieser Zusammenhang beschaffen ist, aber es sollte nicht schwer sein, sich das zu überlegen). Diese Lösung ist insofern optimal, als es für den Polizisten keine andere Strategie gibt, die eine höhere Wahrscheinlichkeit dafür liefert den Verbrecher zu fassen. Ich habe nun aber ein anderes Problem, das mit dem eben beschriebenen viel gemeinsam hat, aber doch in einigen Details abweicht: Das reale Problem: Ich habe eine Wohnung, bin damit aber unzufrieden und suche eine neue, bessere Wohnung. Ich möchte zwar möglichst schnell umziehen, habe aber theoretisch bis zu 4 Jahre Zeit, denn dann läuft mein aktueller Mietvertrag aus. Fast jeden Tag tauchen neue Wohnungen auf dem Markt auf, und ich habe eine Funktion entwickelt, die eine angebotene Wohnung als Input entgegennimmt und dann eine positive Zahl ausspuckt, die wiedergibt, wie sehr mir diese Wohnung gefällt. Auf diese Weise könnte ich alle Wohnungen bewerten und dann die mit dem größten Wert auswählen und mieten. Leider verschwinden aber gerade jene Wohnungen, die (für mich) einen hohen Wert haben, sehr schnell wieder vom Markt, weil sie von anderen Wohnungssuchenden gemietet werden. Ich kann also nicht zuerst alle Wohnungen anschauen und bewerten und erst danach entscheiden welche ich nehme, sondern ich muss sofort (idealerweise direkt bei der Besichtigung) entscheiden, ob ich eine bestimmte Wohnung mieten will oder nicht. Mein Lösungsansatz: Ich orientiere mich an der Lösung des oben beschriebenen Polizisten-Problems: Ich besichtige und bewerte eine bestimmte Anzahl von Wohnungen, die ich aber nicht mieten werde. Auch meine aktuelle Wohnung bewerte ich. Die Wohnung mit der höchsten Wertung sei meine Referenzwohnung (die ich aber nicht mieten werde, außer es ist meine aktuelle Wohnung). Ich werde die erste Wohnung mieten, die besser ist (einen höheren Wert hat) als diese Referenzwohnung. Zwei wesentliche Unterschiede gibt es zwischen diesem Problem und dem Problem des Polizisten:
Folgende Fragen sind offen:
Kann mir jemand dabei helfen? - Danke! Liebe Grüße Hubert Schölnast |
||
|
|
