Pertanyaan teori permainan baru-baru ini membuat saya berpikir (ini bersinggungan, tentu saja): Apakah mungkin untuk secara efisien mengoptimalkan strategi pribadi untuk memilih pertanyaan penelitian untuk dikerjakan menggunakan teori permainan?
Untuk menuju formalisasi pertanyaan, saya akan membuat asumsi berikut (yang dinyatakan secara informal):
- Saya sama-sama "menikmati" masalah tertentu yang tersedia untuk saya kerjakan (untuk menghindari jawaban "lunak" (dan benar!) Dari "Lakukan apa yang Anda suka!").
- Saya mungkin atau mungkin tidak berhasil menemukan jawaban untuk masalah apa pun yang saya pilih untuk saya selesaikan. Untuk masalah apa pun, saya memiliki beberapa perkiraan tentang seberapa baik saya dalam memecahkan suatu masalah (setelah menginvestasikan waktu di dalamnya).
- Tujuan saya adalah untuk memaksimalkan hasil ketika dievaluasi di garis bawah (melamar pekerjaan, melamar masa kerja, melamar beasiswa, dll.), Yang merupakan fungsi dari berapa banyak masalah yang saya selesaikan dan seberapa penting atau sulit masalah tersebut . Saya tidak memiliki gagasan yang jelas tentang imbalan tepat per masalah, tetapi saya dapat membuat perkiraan yang masuk akal.
- Ada hubungan terbalik yang longgar antara masalah hasil dan kesulitan masalah. Pernyataan lain dari tujuan saya adalah untuk "mempermainkan" perbedaan (yaitu mencari "buah yang menggantung rendah").
- Sebuah contoh dari masalah keseluruhan ini ditentukan oleh daftar pertanyaan penelitian (mungkin jumlahnya tidak terbatas), yang saya lampirkan dengan tegas (tanpa biaya komputasi; itu diberikan sebagai input) perkiraan nilai pertanyaan dan kesulitan pertanyaan. Saya memainkan game ini melawan musuh (orang yang mengevaluasi saya); alam memutuskan, mengingat kemungkinan saya memecahkan masalah yang diberikan, apakah saya menyelesaikannya dengan sukses setelah saya memilih untuk mencobanya.
Dalam upaya untuk benar-benar memformalkan apa yang terjadi (dan menghindari tanggapan yang tidak menarik atau argumentatif / diskusi), saya akan melihat masalah ini sebagai permainan bentuk luas dengan informasi yang tidak lengkap dengan set tindakan yang tak terbatas .
Pertanyaan : Saya menganggap game jenis ini tidak dapat dihitung secara efisien. Namun, apakah ada algoritma waktu polinomial untuk memaksimalkan hasil saya? Bagaimana dengan PTAS?
Atau, alternatifnya, apakah ada model teoritik permainan yang lebih akurat untuk masalah ini? Jika demikian, pertanyaan yang sama berlaku: Dapatkah saya (kurang-lebih) memaksimalkan hasil saya secara efisien? Jika ya, bagaimana caranya?
sumber
Jawaban:
Saya akan mencoba menjawab pertanyaan Anda dengan mengusulkan model alternatif untuk pertanyaan itu. Saya biasanya mengajukan lebih banyak pertanyaan daripada yang saya jawab di sini, jadi saya harap Anda akan memaafkan jika jawaban saya tidak optimal, meskipun saya melakukan yang terbaik.
Saya pikir cara mengutarakan pertanyaan yang akan optimal agar teori permainan bermanfaat adalah dengan mengasumsikan skenario yang lebih kompetitif. Yaitu, perlu ada persaingan di antara berbagai aktor yang berbeda. Jadi, saya akan menganggap yang berikut:
Sekarang, dengan asumsi tidak ada kerja sama dalam masalah apa pun adalah mungkin, pertimbangkan apa yang akan saya sebut sebagai "permainan iterasi dinamis." Ini adalah game yang dimainkan berulang kali, tetapi sedikit berubah setiap kali dimainkan.
Biarkan M menjadi jumlah gerakan, atau belokan, dalam permainan. Manifestasi awal permainan dapat direpresentasikan sebagai daftar yang berisi setiap aktor (peneliti) dan setiap masalah yang bisa mereka selesaikan, di samping semua nilai yang terkait dengan masing-masing aktor dan setiap masalah yang saya sebutkan di atas. (Saya berasumsi, tentu saja, bahwa setiap peneliti tahu segalanya yang diketahui saat ini tentang semua masalah, dan tentang semua peneliti lain, menjadikan ini permainan informasi yang sempurna.)
Selama setiap iterasi permainan, aktor tertentu memilih pertanyaan penelitian untuk dikerjakan. Setiap aktor diizinkan untuk berganti pertanyaan kapan saja, dan jika masalah dipecahkan, manfaat untuk karier U akan turun menjadi 0 untuk semua pemain lain. Jika seorang pemain menginvestasikan waktu yang cukup dan gagal untuk menyelesaikan masalah, maka pemain tersebut dilarang mencoba untuk memecahkan masalah itu lagi ... meskipun pemain lain diperbolehkan untuk terus mengerjakan masalah, dan aktor lain mungkin dapat menyelesaikan itu berhasil. Permainan berakhir setelah semua giliran M telah diambil.
Setiap belokan yang peneliti telah pilih masalah akan menyebabkan pemain lebih dekat untuk mencapai "momen kebenaran," dan mungkin memecahkan masalah, izin Alam. Suatu masalah, setelah dipecahkan, menambah manfaat tertentu bagi karier peneliti berdasarkan pada l . Bakat penelitian memperbesar kemungkinan keberhasilan, sementara waktu luang menguatkan kemampuan untuk membuat kemajuan pada gilirannya.
Saya ragu bahwa ada algoritma waktu polinomial untuk menyelesaikan ini; Saya tidak melihat alasan mengapa para peneliti harus dibatasi untuk bermain ekuilibria murni strategi-Nash, sehingga masalahnya akan melibatkan strategi campuran Nash ekuilibria dan dengan demikian menjadi yang terburuk PPAD-lengkap, jika Anda mempertimbangkan "memecahkan masalah" berarti "menemukan sebuah Nash keseimbangan untuk masalah tersebut. " (Orang bisa membayangkan bahwa jika Anda adalah peneliti paling proaktif di sekitar, Anda dapat melanjutkan dan menghitung keseimbangan Nash favorit Anda dan kemudian memberi sinyal kepada semua pemain lain ... sehingga memberi Anda keyakinan bahwa tidak ada yang akan mengubah strategi dari strategi. profil yang Anda beri tanda.)
Bagaimanapun, ini adalah jawaban yang paling terlibat yang pernah saya posting. Saya harap setidaknya ada nilainya. Harap beri tahu saya jika ada yang memberi respons atau terhadapnya atau rekomendasi untuk memperbaikinya.
sumber