Jabarkan Dilema tahanan berulang dari Dilema tahanan

Jika dua pemain memainkan dilema tahanan lebih dari satu kali berurutan dan mereka dapat mengingat aksi sebelumnya dari lawan mereka dan mengubah strategi mereka berdasarkan aksi lawan, maka permainannya disebut dilema tahanan berulang (DTB).

Sebagai tambahan dari bentuk umum di atas, versi iteratif juga membutuhkan 2R > T + S, untuk mencegah pergantian kooperasi dan bertahan memberikan imbalan lebih besar daripada saling kooperasi.

Permainan DTB adalah dasar bagi beberapa teori-teori persekutuan dan kooperasi manusia.

Dengan asumsi bahwa permainan tersebut dapat memodelkan transaksi antara dua orang yang membutuhkan kepercayaan, perilaku kooperatif dalam populasi bisa dimodelkan dengan versi permainan banyak-pemain dan berulang.

Hal tersebut, konsekuensinya, telah menarik banyak ahli selama beberapa tahun.

Pada tahun 1975, Grofman dan Pool memperkirakan jumlah artikel ilmiah yang ditujukan untuk ini lebih dari 2.000.

Dilema tahanan berulang juga telah disebut sebagai "Permainan perang-damai".

Jika permainan dimainkan pasti N kali dan kedua pemain mengetahui hal tersebut, maka secara teoretis optimasi permainan adalah bertahan di semua ronde.

Satu-satunya kemungkinan ekuilibrium Nash adalah untuk selalu bertahan.

Pembuktiannya adalah induktif: salah seorang pemain bisa bertahan pada akhir permainan, karena lawan tidak memiliki kesempatan untuk menghukum pemain.

Oleh sebab itu, keduanya akan bertahan pada ronde terakhir.

Maka, pemain tentunya juga akan bertahan pada ronde kedua terakhir, karena lawan pada akhirnya akan bertahan walau apapun yang terjadi, dan seterusnya.

Hal yang sama berlaku jika lama permainan tidak diketahui tetapi memiliki batas atas yang diketahui.

Tidak seperti dilema tahanan biasa, dalam DTB strategi bertahan adalah kontra-intuitif dan gagal memprediksi perilaku dari pemain manusia.

Dalam teori ekonomi biasa, bagaimanapun, hal ini merupakan satu-satunya jawaban yang benar.

Strategi superrasional dalam DTB dengan N tetap adalah untuk berkooperasi melawan lawan yang superrasional, dan dengan batas N yang besar, hasil percobaan dari strategi-strategi sesuai dengan versi superrasional, bukan dengan teori permainan rasional.

Supaya kooperasi muncul antara pemain dalam permainan teoretis rasional, jumlah ronde N haruslah acak, atau tidak diketahui oleh pemain.

Dalam kasus ini 'selalu bertahan' bukan lagi strategi dominan, hanya sebuah ekuilibrium Nash.

Di antara hasil-hasil yang diperlihatkan oleh Robert Aumann di sebuah makalah tahun 1959, pemain rasional yang berulang kali berinteraksi dalam permainan yang panjang tak terbatas dapat mengalami hasil kooperatif.

Strategi bagi dilema tahanan berulang

Ketertarikan pada DTB disulut oleh Robert Axelrod dalam bukunya The Evolution of Cooperation (1984).

Dalam buku tersebut dia melaporkan sebuah turnamen yang diorganisirnya lewat N langkah dilema tahanan (dengan N tetap) dengan setiap partisipan harus memilih strategi mutual mereka lagi dan lagi, dan memiliki ingatan akan pilihan lawan sebelumnya.

Axelrod mengundang teman-teman akademis seluruh dunia untuk merancang strategi komputer untuk berkompetisi dalam turnamen DTB.

Program-program yang diajukan memiliki keragaman kompleksitas algoritme, sikap permusuhan awal, kapasitas untuk memaafkan, dan seterusnya.

Axelrod menemukan bahwa saat turnamen tersebut diulang selama waktu yang lama dengan banyak pemain, setiapnya dengan strategi yang berbeda, strategi tamak condong kurang baik dalam jangka panjang sementara strategi altruistik malah lebih baik, dinilai murni dari keegoisan.

Dia menggunakan hal ini untuk memperlihatkan mekanisme yang memungkinan bagi evolusi perilaku altruistik dari mekanisme yang awalnya murni egois, dengan seleksi alam.

Strategi deterministik yang menang adalah tit untuk tat, yang Anatol Rapoport kembangkan dan ajukan untuk turnamen.

Ia adalah program paling sederhana, hanya memiliki empat baris kode BASIC, dan memenangkan kontes.

Strateginya secara sederhana berkooperasi pada iterasi pertama permainan; setelah itu, pemain melakukan apa yang lawannya lakukan sebelumnya.

Bergantung pada situasi, strategi yang sedikit lebih baik adalah "tit untuk tat dengan memaafkan."

Saat lawan bertahan, pada ronde selanjutnya, si pemain terkadang tetap berkooperasi, dengan probabilitas kecil (sekitar 1-5%).

Hal ini membolehkan pemulihan tak berkala dari terperangkap dalam lingkaran bertahan.

Probabilitas pastinya bergantung pada lawan.

Dengan menganalisis strategi-strategi top-skor, Axelrod menyatakan beberapa kondisi diperlukan bagi sebuah strategi untuk sukses.

Baik Kondisi paling penting yaitu strategi haruslah "baik", yakni, ia tidak akan bertahan sebelum lawannya bertahan (hal ini terkadang disebut juga dengan algoritme "optimistik"). Hampir semua strategi top-skor adalah baik; oleh karena itu, strategi yang murni egois tidak akan "menipu" lawannya, murni karena alasan egoistis.

Balas dendam Namun, Axelrod berpendapat, strategi yang sukses haruslah tidak optimis buta. Ia terkadang harus balas dendam. Salah satu contoh strategi tanpa-pembalasan adalah Selalu Kooperasi. Hal ini adalah pilihan yang buruk, karena strategi-strategi yang "keji" akan mengeksploitasi pemain seperti itu.

Memaafkan Strategi yang sukses juga harus memaafkan. Walau pemain akan membalas dendam, mereka nantinya akan kembali berkooperasi jika lawan tidak terus bertahan. Hal ini menghentikan balas dendam yang berkepanjangan, memaksimalkan poin.

Tidak iri Kualitas terakhir adalah menjadi tidak iri, yaitu tidak mencoba mendapatkan nilai lebih dari lawan (perlu diingat bahwa strategi "baik" tidak pernah memperoleh nilai lebih dari lawan).

Strategi optimal untuk DT untuk sekali main adalah bertahan; seperti yang dijelaskan di atas, hal ini benar apapun komposisi dari lawan yang terjadi.

Namun, dalam permainan DTB strategi optimal bergantung kepada strategi dari lawan, dan bagaimana mereka bereaksi terhadap bertahan dan kooperasi.

Sebagai contohnya, bayangkan sebuah populasi yang setiap orang selalu bertahan, kecuali satu yang menggunakan strategi tit-untuk-tat.

Individu tersebut sedikit dirugikan karena kalah pada giliran pertama.

Dalam populasi tersebut, strategi optimal bagi individu tersebut adalah untuk selalu bertahan.

Dalam sebuah populasi dengan sejumlah persentase selalu-bertahan dan sisanya pemain tit-untuk-tat, strategi optimal bagi seorang individu bergantung kepada persentase selalu-bertahan, dan lama permainan.

Dalam strategi yang dikenal dengan Pavlov, menang-tinggal, kalah-ganti, jika ronde terakhir menghasilkan P,P, pemain Pavlov berganti strategi di giliran selanjutnya, yang berarti P,P akan dianggap sebagai sebuah kegagalan utuk berkooperasi.

Untuk beberapa rentang parameter, Pavlov mengalahkan strategi lainnya dengan memberikan perlakuan istimewa bagi pemain lain yang mirip Pavlov.

Menurunkan strategi optimal secara umum dilakukan dengan dua cara:

Ekuilibrium Nash Bayesian: Jika distribusi statistik dari strategi lawan dapat ditentukan (misalnya 50% tit-untuk-tat, 50% selalu kooperasi) sebuah kontra-strategi optimal dapat diturunkan secara analitis.

Simulasi populasi Monte Carlo telah dilakukan, yang mana individu dengan nilai rendah mati, dan yang bernilai tinggi bereproduksi (sebuah algoritme genetis untuk menemukan strategi optimal). Campuran dari algoritme pada populasi akhir pada umumnya bergantung pada campuran pada populasi awal. Munculnya mutasi (variasi acak selama reproduksi) mengurangi kebergantungan pada populasi awal; percobaan empiris untuk sistem seperti itu condong menghasilkan pemain dengan tit-untuk-tat (lihat contohnya Chess 1988), tetapi tidak ada bukti analitis bahwa ini akan selalu terjadi.

Walaupun tit-untuk-tat dianggap sebagai strategi dasar paling kuat, sebuah tim dari Universitas Southampton di Inggris (dipimpin oleh Profesor Nicholas Jennings   dan terdiri dari Rajdeep Dash, Sarvapali Ramchurn, Alex Rogers, Perukrishnen Vytelingum) mengenalkan sebuah strategi baru pada peringatan ke-20 kompetisi DTB, yang membuktikan lebih sukses daripada tit-untuk-tat.

Strategi ini bergantung pada kooperasi antara program untuk mendapatkan poin tertinggi untuk sebuah program tunggal.

Universitas tersebut mengajukan 60 program untuk kompetisi, yang dirancang untuk mengenali satu sama lain lewat sekumpulan lima sampai sepuluh gerakan pada saat mulai.

Sekali dikenali, satu program akan selalu kooperasi dan yang lainnya akan bertahan, memastikan jumlah poin maksimal bagi yang bertahan.

Jika program tersebut menyadari bahwa ia bermain dengan pemain bukan dari Southampton, ia akan terus menerus bertahan supaya meminimalkan nilai dari program lawan.