Ta ostatnia teoria gier pytanie dało mi do myślenia (to jest styczna, oczywiście): Czy jest możliwe, aby skutecznie zoptymalizować osobistą strategię wyboru pytania badawcze do pracy na wykorzystaniu teorii gier?
Aby przejść do sformalizowania pytania, przyjmuję następujące (nieformalnie) założenia:
- Równie „lubię” każdy konkretny problem dostępny dla mnie do pracy (aby uniknąć „miękkiej” (i poprawnej!) Odpowiedzi „Rób to, co lubisz!”).
- Być może uda mi się znaleźć odpowiedź na dany problem, nad którym zdecyduję się pracować. Dla każdego problemu mam pewne oszacowanie prawdopodobieństwa, jak dobrze będę w rozwiązaniu problemu (po zainwestowaniu w niego czasu).
- Moim celem jest maksymalizacja mojej wypłaty podczas oceny w dół (ubieganie się o pracę, ubieganie się o staż, ubieganie się o stypendium itp.), Co jest funkcją tego, ile problemów rozwiązuję i jak ważne lub trudne są problemy . Nie mam jasnego pojęcia o dokładnych wypłatach na problem, ale mogę dokonać rozsądnej oceny.
- Istnieje luźna odwrotna zależność między spłatą problemu a trudnością problemu. Innym stwierdzeniem mojego celu jest „rozgromienie” różnic (tj. Poszukiwanie „nisko wiszących owoców”).
- Przykładem tego ogólnego problemu jest lista pytań badawczych (być może nieskończonej liczby), do których stanowczo dołączam (bez kosztów obliczeniowych; podano jako dane wejściowe) szacunkową wartość pytania i trudność pytania. Gram w tę grę przeciwko przeciwnikowi (osobie oceniającej mnie); natura decyduje, biorąc pod uwagę prawdopodobieństwo, że rozwiążę dany problem, czy uda mi się go rozwiązać po tym, jak go spróbuję.
Aby naprawdę sformalizować to, co się dzieje (i uniknąć nieciekawych lub kłótliwych lub dyskusyjnych odpowiedzi), będę postrzegał ten problem jako grę o rozległej formie z niepełnymi informacjami i nieskończonym zestawem akcji .
Pytanie : Zakładam, że gry tego typu nie są wydajnie obliczalne. Czy jednak istnieje algorytm wielomianowy w celu maksymalizacji wypłaty? Co z PTAS?
Czy też istnieje bardziej dokładny model teoretyczny gry dla tego problemu? Jeśli tak, to samo pytanie: czy mogę (w przybliżeniu) skutecznie zmaksymalizować wypłatę? Jeśli tak to jak?
źródło
Odpowiedzi:
Spróbuję odpowiedzieć na twoje pytanie, proponując alternatywny model pytania. Zazwyczaj zadaję więcej pytań niż odpowiadam tutaj, więc mam nadzieję, że wybaczysz, jeśli moja odpowiedź nie będzie optymalna, chociaż robię co w mojej mocy.
Myślę, że sposobem na sformułowanie pytania, które byłoby optymalne dla przydatności teorii gier, byłoby przyjęcie bardziej konkurencyjnego scenariusza. Tzn. Musi istnieć konkurencja między różnymi aktorami. Zakładam więc, że:
Teraz, zakładając, że żadna współpraca nie jest możliwa, rozważ to, co będę określać jako „dynamiczną iterowaną grę”. Jest to gra, w którą gra się wielokrotnie, ale zmienia się ona nieznacznie za każdym razem.
Niech M będzie liczbą ruchów lub tur w grze. Początkowa manifestacja gry może być przedstawiona jako lista zawierająca każdego aktora (badacza) i każdy problem, nad którym mogliby pracować, oprócz wszystkich wartości związanych z każdym aktorem i każdym problemem wymienionym powyżej. (Zakładam oczywiście, że każdy badacz wie wszystko, co obecnie wiadomo o wszystkich problemach i wszystkich innych badaczach, co czyni tę grę doskonałą informacją.)
Podczas każdej iteracji gry dany aktor wybiera pytanie badawcze, nad którym ma pracować. Każdy aktor może zmieniać pytania w dowolnym momencie, a jeśli problem zostanie rozwiązany, korzyść z kariery U spada do 0 dla wszystkich innych graczy. Jeśli gracz zainwestuje wystarczającą ilość czasu i nie rozwiąże problemu, wówczas temu konkretnemu graczowi nie wolno próbować rozwiązać problemu ponownie ... chociaż każdy inny gracz może kontynuować pracę nad problemem, a inny aktor może być w stanie rozwiązać to z powodzeniem. Końce gry po wszystkich M zwojów zostały podjęte.
Każda kolejka, w której badacz wybrał problem, sprawi, że gracz będzie zbliżał się do osiągnięcia „momentu prawdy” i ewentualnie rozwiązania problemu, na co pozwala Natura. Problem raz rozwiązany dodaje pewną korzyść do kariery naukowca opartej na l . Talent badawczy zwiększa prawdopodobieństwo sukcesu, a czas wolny zwiększa zdolność do robienia postępów w danej turze.
Wątpię, czy istnieje jakiś algorytm wielomianowy do rozwiązania tego; Nie widzę powodu, dla którego badacze powinni ograniczać się do grania w czystą strategię Nasha, więc problem obejmowałby równowagę Nasha w mieszanej strategii, a co za tym idzie, byłby w najgorszym przypadku kompletny z PPAD, jeśli uważasz, że „rozwiązanie problemu” oznacza „znalezienie Nasha”. równowaga dla problemu ”. (Można sobie wyobrazić, że jeśli jesteś najbardziej aktywnym badaczem w okolicy, możesz obliczyć swoją ulubioną równowagę Nasha, a następnie zasygnalizować ją wszystkim pozostałym graczom ... dając w ten sposób pewność, że nikt nie zmieni strategii od strategii profil, który zasygnalizowałeś).
W każdym razie jest to najbardziej zaangażowana odpowiedź, jaką kiedykolwiek opublikowałem. Mam nadzieję, że ma to przynajmniej pewną wartość. Daj mi znać, jeśli ktoś ma jakąkolwiek odpowiedź, odpowiedź lub zalecenia dotyczące poprawy.
źródło