Apa itu Teori Permainan Algoritma? Dijelaskan Dengan Contoh

Pada tahun 1999, ketika Nisan dan Ronen menyumbangkan ide mereka ke sebuah makalah, dunia menyaksikan konsep Desain Mekanisme Algoritma yang baru. Ia mencoba untuk meniadakan The Price of Anarchy, di mana kepentingan pribadi selalu menghasilkan sistem yang terdegradasi.

Makalah mereka membuktikan bahwa banyak pihak yang berkepentingan dapat membangun sistem yang produktif pada keseimbangan. Jadi, alih-alih melihat ekonomi yang merosot, kita akan melihat kesejahteraan sosial dan maksimalisasi pendapatan.

Algorithmic Game Theory (AGT) didasarkan pada pemahaman Algorithmic Mechanism Design (AMD) .

Sementara AMD menjelaskan bahwa kepentingan pribadi dapat menghasilkan sistem yang baik, AGT bertujuan untuk menganalisis dan merancang pengaturan strategis yang menggambarkan tindakan peserta yang mementingkan diri sendiri.

Sebelum kita melihat bagaimana AGT bekerja di lingkungan strategis, mari kita lihat bagaimana teori permainan bekerja!

Mari Memahami Teori Permainan Dengan Bantuan Contoh

Di dunia yang sempurna, di mana setiap gerakan adalah usaha yang diperhitungkan, Teori Game tidak akan masuk akal seperti sekarang ini.

Gagasan untuk menghitung langkah selanjutnya dari warga negara yang cerdas dan rasional sangat menggetarkan sekaligus menakutkan.

Teori permainan menyatakan bahwa dalam situasi sosial tertentu, pihak yang bersaing dapat membuat keputusan rasional dengan mengevaluasi validitas kemungkinan dan memperkirakan langkah bersih pesaing.

Meskipun mungkin tampak seperti pertaruhan, para ahli teori telah mengembalikan strategi yang dapat dijelaskan yang mencabut kepercayaan bahwa itu adalah pertaruhan.

Contoh yang paling sering dirujuk adalah Dilema Tahanan.

Pelajari: 8 Proyek Teratas yang Harus Dilakukan Setiap Pengembang Tanpa Gagal

Dilema Tahanan Dijelaskan

Premisnya sederhana – ketika polisi menangkap dua narapidana dan menanyai mereka tentang kejahatan itu, keduanya tidak akan memecah keheningan mereka.

Jadi, DA memutuskan untuk membuatnya lebih sederhana dengan meletakkan tiga kondisi di depan mereka, karena mereka duduk bersebelahan.

• Syarat 1: Jika tidak satu pun dari mereka mengaku melakukan kejahatan, mereka dipenjara selama enam tahun.
• Kondisi 2: Jika salah satu mengadukan yang lain, pelapor dapat berkeliaran dengan bebas sementara yang lain masuk selama sepuluh tahun.
• Syarat 3: Jika keduanya mengaku, mereka masuk penjara selama satu tahun.

Segera setelah mendengarkan kondisinya, mereka dibawa ke ruang terpisah untuk membuat keputusan.

Kami dapat mentransfer data ini dalam bentuk matriks, seperti;

Sumber

Solusi untuk masalah ini sangat mudah;

Setiap tahanan akan mempertimbangkan untuk mengatakan yang sebenarnya tentang kejahatan tersebut. Tak satu pun dari keduanya dapat dengan tegas mengatakan bahwa yang lain akan tetap diam. Jadi, menyerah pada kemungkinan, keduanya memutuskan untuk mengakui kejahatan dan hanya masuk penjara selama satu tahun.

Teori permainan adalah senjata ampuh di tangan siapa yang menggunakannya. Kita dapat menguraikan bahkan situasi yang paling kompleks dengan memahami sifat bilangan dan penempatan pengaturan sosial.

Teori Permainan Algoritma

Sekarang, perhatikan diagram Venn dari Teori Permainan dan Ilmu Komputer. Bayangkan peningkatan drastis dalam tingkat akurasi mengapa memetakan probabilitas mencapai jawaban.

Dan inilah yang dilakukan oleh Algorithmic Game Theory (AGT) !

Ini mencoba untuk memecahkan masalah modern dengan mencapai keseimbangan sempurna antara algoritma komputer dan teori permainan.

Dengan kata lain yang lebih sederhana, Algorithmic Game Theory mencoba mendefinisikan keseimbangan sosial-ekonomi antara melakukan suatu tugas. Ia juga menggunakan prinsip-prinsip Nash Equilibrium; itu menyatakan bahwa begitu para peserta menemukan strategi yang cocok untuk mereka, mereka tidak akan ingin menyimpang darinya sampai berhenti bekerja untuk keuntungan mereka.

Mari kita ambil contoh kecil untuk memahami cara kerja Algorithmic Game Theory.

Mari kita kembali ke sekolah ketika kita bermain game seperti Kho-Kho, Ice & Water, Chain-Cut, dll. Masing-masing game ini memiliki desain dan mekanisme yang indah untuk dimainkan.

Mari kita pertimbangkan Ice & Water, misalnya;

• Ada beberapa pemain dan satu penangkap. Penangkap seharusnya mengubah semua orang menjadi es.
• Pemain lain memiliki kekuatan untuk mengubah seseorang kembali ke air setelah menyentuh.
• Ada zona bebas di mana para pemain dapat beristirahat selama 30 detik.

Sekarang, jika Anda perhatikan baik-baik, Anda akan melihat bahwa masing-masing aturan ini membentuk mekanisme permainan dan menentukan desainnya.

• Para pemain dapat memainkan game ini selama mereka merasa menarik. Di sini, The Nash Equilibria menjelaskan bahwa selama para pemain menemukan strategi mereka bekerja dan permainannya menarik, mereka akan bermain.
• Jatah pemain bukanlah untuk ditangkap. Dan dia bertindak berdasarkan jatah itu dengan memahami pengaturannya. Dia menerapkan pendekatan objektif-pertama, di mana dia memenangkan permainan dengan tidak tertangkap. Dan ini populer dengan sebutan Mechanism Design atau Reverse Game Theory.
• Sekarang, jika setiap pemain hanya mempertimbangkan satu motif – “Tidak tertangkap” – dan tidak mempertimbangkan bagian kedua – “menyelamatkan pemain lain”, maka konsep ini disebut Price Of Anarchy. Ini menjelaskan bagaimana efisiensi sistem apa pun akan menurun karena perilaku egois para pemain.

Sekarang, lebih banyak konsep muncul dari tiga konsep yang disebutkan di atas. Sementara mereka semua sepenuhnya atau sedang terkait dengan teori permainan, mereka menciptakan dasar fungsional untuk teori permainan algoritmik.

Lihat: 42 Ide & Topik Proyek Python yang Menyenangkan untuk Pemula

Sekarang, muncul pertanyaan: “Bagaimana kita merepresentasikan lingkungan strategis dalam hal Algoritma?”

Sekarang mari kita lihat bagaimana kita dapat menggunakan Python untuk mendefinisikan lingkungan strategis dan memahami implementasi Nashpy untuk situasi tertentu.

Bayangkan Anda sedang bermain batu-kertas-gunting dengan salah satu teman Anda. Masing-masing dari Anda memiliki salah satu dari tiga opsi;

• Batu
• Kertas
• Gunting

Dan rubrik untuk memenangkan permainan adalah

• Gunting penghancur batu
• Gunting memotong kertas
• Kertas menutupi batu

Dan ini berarti bahwa jika kedua pemain menampilkan rock, itu berarti do-overs.

Kita dapat merepresentasikannya dalam bentuk matriks 3×3 dimana Aij adalah;

Sumber

Catatan: Di sini, i dan j adalah giliran yang dimainkan oleh kedua pemain.

Di Sini,

• Nol menunjukkan bahwa Anda berdua memainkan objek yang sama (batu-batu; atau kertas-kertas)
• Satu mewakili bahwa salah satu dari Anda mengalahkan yang lain (seperti gunting batu)
• Minus One menunjukkan bahwa salah satu dari Anda kalah karena yang lain mengalahkan Anda (seperti kertas batu)

Sekarang, untuk mewakili ini di Nashpy, Anda akan menulis kode yang terlihat seperti ini;

Sumber

Pikiran Akhir

Teori Permainan Algoritmik adalah prinsip yang sempurna di dunia saat ini di mana persaingan berasal dari kepentingan pribadi, dan kemenangan adalah pencapaian kepentingan pribadi.

Jadi, sebagai manajer, guru, CXO, atau pebisnis modern, jika Anda memahami dominasi Teori Permainan Algoritmik, izinkan saya mengubah kutipan Severus Snape dari Harry Potter;

“Algorithmic Game Theory dapat mengajari Anda cara mengumpulkan ketenaran, menghasilkan kemuliaan, bahkan menghentikan kerugian.”

Memahami Algorithmic Game Theory dapat membantu Anda menangani angka dengan lebih meyakinkan dari sebelumnya. Di era saat ini, di mana kami memutuskan hal-hal hingga detail terakhir untuk mengembangkan rencana yang berkelanjutan, AGT terbukti menjadi aspek transformasional.

Kita sudah tahu bahwa Ilmu Data dapat mengubah bisnis menjadi arena yang menguntungkan, tetapi AGT memiliki kekuatan untuk meningkatkan ambang batas.

Misalkan Anda masih skeptis tentang teori permainan dan bagaimana ilmu data adalah profesi yang paling menguntungkan dan kompetitif saat ini.

Jika Anda penasaran untuk belajar tentang ilmu data, lihat Diploma PG IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan pakar industri, 1- on-1 dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.