Auswahl eines Forschungsthemas mit Hilfe der Spieltheorie

19

Diese aktuelle Frage zur Spieltheorie hat mich zum Nachdenken gebracht (das ist natürlich eine Tangente): Ist es möglich, eine persönliche Strategie zur Auswahl von Forschungsfragen für die Verwendung der Spieltheorie effizient zu optimieren?

Um zu einer Formalisierung der Frage zu gelangen, gehe ich von folgenden (informell formulierten) Annahmen aus:

  • Ich "genieße" gleichermaßen jedes Problem, an dem ich arbeiten kann (um die "weiche" (und korrekte!) Antwort "Mach was du willst!" Zu vermeiden).
  • Es kann mir gelingen oder nicht gelingen, eine Antwort auf ein bestimmtes Problem zu finden, an dem ich arbeite. Für jedes Problem habe ich eine Schätzung der Wahrscheinlichkeit, wie gut ich ein Problem lösen kann (nachdem ich Zeit in es investiert habe).
  • Mein Ziel ist es, meine Auszahlung zu maximieren, wenn ich später evaluiert werde (Bewerbung für eine Stelle, Bewerbung für eine Amtszeit, Bewerbung für ein Stipendium usw.). Dies hängt davon ab, wie viele Probleme ich löse und wie wichtig oder schwierig die Probleme sind . Ich habe keine klare Vorstellung von den genauen Auszahlungen pro Problem, kann aber eine vernünftige Schätzung abgeben.
  • Es gibt eine lockere umgekehrte Beziehung zwischen Problemauszahlung und Problemschwierigkeit. Eine andere Aussage meines Ziels ist es, die Unterschiede zu "spielen" (dh nach "tief hängenden Früchten" zu suchen).
  • Ein Beispiel für dieses Gesamtproblem ist eine Liste von (möglicherweise unendlich vielen) Forschungsfragen, an die ich eine Schätzung des Werts der Frage und der Schwierigkeit der Frage anhänge (ohne Rechenaufwand; als Eingabe). Ich spiele dieses Spiel gegen einen Gegner (die Person, die mich bewertet). Angesichts der Wahrscheinlichkeit, dass ich ein bestimmtes Problem löse, entscheidet die Natur, ob ich es erfolgreich löse, nachdem ich es versucht habe.

Um wirklich zu formalisieren, was vor sich geht (und uninteressante oder argumentative / diskussionsartige Antworten zu umgehen), werde ich dieses Problem als ein umfangreiches Spiel mit unvollständigen Informationen und einer unendlichen Menge von Aktionen betrachten .


Frage : Ich gehe davon aus, dass Spiele dieser Art nicht effizient berechenbar sind. Gibt es jedoch einen polynomiellen Zeitalgorithmus, um meine Auszahlung ungefähr zu maximieren? Was ist mit einem PTAS?

Oder gibt es alternativ ein genaueres spieltheoretisches Modell für dieses Problem? Wenn ja, stellt sich die gleiche Frage: Kann ich meine Auszahlung (ungefähr) effizient maximieren? Wenn das so ist, wie?

Daniel Apon
quelle
4
Ein mögliches Problem bei der Formulierung als Spiel ist, dass Ihr Gegner, die Person, die Sie bewertet, nicht unbedingt gegen Sie spielt. In der Tat ist es häufig so, dass sie auf Ihrer Seite stehen und nur bereit sind, Sie zum Scheitern zu bewegen, wenn Sie die Mindestanforderungen nicht erfüllt haben. Ein weiterer möglicher Gegner sind alle anderen Forscher , da sie möglicherweise (möglicherweise gemeinsam) an demselben Problem arbeiten und somit gegen Ihren Erfolg arbeiten, indem sie versuchen, die Ergebnisse zu erhalten, bevor Sie dies tun.
Dave Clarke
Nehmen wir für diese Frage (ich möchte so viel wie möglich von der Diskussion absehen, damit dies eine gute Frage ist ...) an, dass die Person, die mich bewertet, wirklich unter ernsthaftem Druck steht, eine und nur eine beste Person für mich auszuwählen eine besondere Belohnung, so dass sie kontrovers sind. Nehmen wir außerdem an, dass "alles, was wirklich originell ist, genau das ist: Original", sodass andere Forscher keine ernsthaften Bedenken haben. Ich bin (natürlich!) Persönlich an anderen Möglichkeiten interessiert, aber ich denke, wenn ich es offen lasse, werden schlechte Antworten kommen. :)
Daniel Apon
Ein Faktor in dem Problem, der möglicherweise ein anderes Modell verdient: Eine Bewertung der Erfolgswahrscheinlichkeit / Belohnungsstruktur pro Problem, an dem ich arbeite.
Daniel Apon
2
RTrichPich(t)t
2
Natürlich werden durch jede Frage, die Sie beantworten, im wirklichen Leben mehr Fragen freigeschaltet, die Sie nicht im Voraus vorhersagen können, die aber möglicherweise einfacher und / oder wertvoller sind als die Fragen, mit denen Sie begonnen haben dies wie die Chance, etwas zu finden , interessant man sagen kann , über das Spiel dramatisch nach unten geht.
Peter Shor

Antworten:

4

Ich werde versuchen Sie Fragen zu beantworten, indem ein alternatives Modell für die Frage vorschlägt. Normalerweise stelle ich mehr Fragen, als ich hier beantworte. Ich hoffe, dass Sie mir verzeihen, wenn meine Antwort nicht optimal ist, obwohl ich mein Bestes gebe.

Ich denke, dass der Weg, um die Frage zu formulieren, die für die Ermöglichung der Nützlichkeit der Spieltheorie optimal wäre, darin besteht, ein wettbewerbsfähigeres Szenario anzunehmen. Dh, es muss Konkurrenz unter einer Vielzahl von verschiedenen Akteuren sein. Also, ich würde davon ausgehen, wie folgt vor:

  • Es gibt eine große , aber endliche Anzahl n anderer Forscher versuchen , die gleiche Menge der verfügbaren Forschungsfragen zu verfolgen, die ich nennen Q , dass Sie interessiert sind.
  • Jedes Forschungsproblem wird durch folgende Merkmale definiert:
    • Zeit - Investition , oder mich , erforderliche Sichtbarkeit zu erreichen , ob Sie werden in der Lage , das Problem zu lösen
    • Erfolgswahrscheinlichkeit oder S bei der Lösung des Problems; Sobald Sie den "Moment der Wahrheit" erreicht haben und genügend Zeit investiert haben, entscheidet die Natur zufällig, ob Sie das Problem lösen können oder nicht
    • Der Nutzen für Ihre Karriere oder U (wie in Dienstprogramm) vorgesehen Erfolg
  • Jeder dieser Forscher hat unterschiedliche Niveaus der folgenden Quantitäten:
    • Zeit für Investitionen in die Forschung zur Verfügung, t
    • Talent in der Forschung, r
    • Soziale Kompetenz und andere Karriere-Unterstützung Qualitäten, l (wie in sympathischen), das bestimmt , wie gut die Forscher ihre Forschungserfolge für ihren beruflichen Aufstieg Kapital schlagen

Nun, auf jedem Problem keine Zusammenarbeit unter der Annahme möglich ist, überlegen, was ich beziehen werde als ein „dynamisches Spiel wiederholt.“ Dies ist ein Spiel, das wiederholt gespielt wird, das sich jedoch jedes Mal leicht ändert, wenn es gespielt wird.

Lasse M die Anzahl der Züge sein, oder Wendungen, im Spiel. Die Erstmanifestation des Spiels könnte als Liste dargestellt werden , die jeden Schauspieler (Forscher) und jedes Problem enthält , dass sie arbeiten könnten, zusätzlich zu allen Werten mit jedem Schauspieler und jedes Problem, dass ich oben aufgeführt ist . (Ich gehe davon aus , natürlich, dass jeder Forscher weiß alles gegenwärtig über all die Probleme bekannt, und über alle anderen Forscher, so dass dies ein Spiel von perfekter Information.)

Während jeder Iteration des Spiels wählt ein bestimmter Schauspieler eine Forschungsfrage aus, an der gearbeitet werden soll. Jeder Schauspieler ist jederzeit Schalter Fragen zulässig, und wenn ein Problem gelöst, der Nutzen für die Karriere U wird auf 0 für alle anderen Spieler fallen gelassen. Wenn ein Spieler genügend Zeit investiert und nicht das Problem zu lösen, dann , dass bestimmte Spieler von dem Versuch ist verboten, dieses Problem wieder zu lösen ... obwohl jeder anderer Spieler erlaubt ist , das Problem weiter zu arbeiten, und ein anderer Schauspieler kann in der Lage sein zu lösen es erfolgreich. Das Spiel endet, nachdem alle M Züge gemacht wurden.

Jede Runde, in der ein Forscher ein Problem ausgewählt hat, führt dazu, dass dieser Spieler dem "Moment der Wahrheit" näher kommt und möglicherweise das Problem löst, sofern die Natur dies zulässt. Ein Problem, einmal gelöst, fügt einen bestimmten Nutzen der Laufbahn der Forscher basiert auf l . Forschungstalent erhöht die Erfolgswahrscheinlichkeit, während Freizeit die Fähigkeit erhöht, in einer bestimmten Runde Fortschritte zu erzielen.

Ich bezweifle, dass es einen polynomialen Zeitalgorithmus gibt, um dies zu lösen. Ich sehe keinen Grund, warum sich Forscher darauf beschränken sollten, Nash-Gleichgewichte mit reinen Strategien zu spielen, daher würde das Problem Nash-Gleichgewichte mit gemischten Strategien beinhalten und daher schlimmstenfalls PPAD-vollständig sein, wenn Sie in Betracht ziehen, "das Problem zu lösen" bedeutet, "Nash zu finden" Gleichgewicht für das Problem. " (Wenn Sie der proaktivste Forscher sind, können Sie sich vorstellen, Ihr bevorzugtes Nash-Gleichgewicht zu berechnen und es dann allen anderen Spielern zu signalisieren. Dies gibt Ihnen die Gewissheit, dass niemand die Strategie ändern wird Profil, das Sie signalisiert haben.)

Jedenfalls ist dies die Beteiligten Antwort, die ich je geschrieben habe. Ich hoffe, dass es zumindest einen gewissen Wert. Bitte lassen Sie mich wissen, wenn jemand eine Antwort oder ihm oder Empfehlungen zur Verbesserung der es hat.

Philip Weiss
quelle
1
Philip, danke für die Antwort! Dies ist eine großartige Perspektive für das Problem. Ich frage mich: Können Sie sich einen Weg vorstellen , eine Vorstellung von „Teilinformationen“ in das Problem so hinzufügen , dass es behält seine PPAD-Vollständigkeit Status? Ein Modell dafür, dass ich als Spieler in diesem Spiel nicht unbedingt weiß, was alle meine Gegner tun (dh ich weiß nicht genau, welche Fragen sie sich stellen und welche Stärke sie zu haben glauben) Beantwortung jeder Frage)? Beeinflusst das Hinzufügen die Komplexität der Berechnung eines Nash-Gleichgewichts? (Ich weiß nicht!)
Daniel Apon
1
@ Daniel Apon: Danke für den Kommentar! Ich glaube nicht, dass es schwierig wäre, die Bedingungen zu ändern, sodass Sie einfach nicht wissen, was Ihre Gegner tun oder welche Merkmale sie haben. Der einzige Nachteil ist meiner Meinung nach, dass die Garantie für das Bestehen eines Nash-Gleichgewichts wegfällt, wenn es sich um ein Spiel mit unvollkommenen Informationen handelt. Ich weiß nicht sehr viel über das, was als bekannt ist „Stackelberg - Spiele,“ aber ich denke , dass sie zu Ihrer vorgeschlagenen Änderung relevant sein können. Ich habe mich tatsächlich gefragt, was das beste Lösungskonzept für unvollständige Informationsspiele ist ... Ich werde darüber nachdenken.
Philip White
Ich las ein wenig mehr dazu ... Ich denke , dass Bayes - Spiele hier relevant sein können, weil sie verwendet wird , mit Spielen mit unvollständiger Information zu beschäftigen. Hier ist ein Link zu Wikipedia , dass ich warf einen Blick auf: en.wikipedia.org/wiki/Bayesian_game
Philip Weiß