Rock-Paper-Scissors dan Game Theory

Gim "rock-paper-scissors" sangat bagus untuk memutuskan siapa yang harus membuang sampah. Tetapi apakah Anda memperhatikan apa yang terjadi ketika, alih-alih tiga tembakan, permainan berlanjut putaran demi putaran? Pertama, Anda memilih prinsip yang memberi Anda keuntungan, tetapi kemudian musuh dengan cepat memahaminya dan berbalik mendukungnya. Dalam proses mengubah strategi, Anda secara bertahap mencapai titik di mana tidak ada pihak yang dapat terus meningkat. Mengapa ini terjadi?

Pada 1950-an, ahli matematika John Nash membuktikan bahwa dalam setiap jenis permainan dengan jumlah pemain yang terbatas dan sejumlah opsi yang terbatas (seperti "rock-paper-scissors") selalu ada campuran strategi di mana tidak ada pemain yang dapat menunjukkan hasil yang lebih baik dengan mengubah hanya strategi Anda sendiri. Teori seperangkat strategi yang stabil, yang disebut " Nash equilibria, " merevolusi bidang teori permainan, mengubah arah pengembangan ekonomi dan cara mempelajari dan menganalisis segala sesuatu mulai dari kontrak politik hingga lalu lintas jaringan. Dia juga mengizinkan Nash untuk menerima Hadiah Nobel 1994 .

Jadi seperti apa keseimbangan Nash dalam permainan batu-kertas-gunting? Mari kita simulasikan situasi di mana Anda (Pemain A) dan lawan Anda (Pemain B) memainkan permainan lagi dan lagi. Di setiap putaran, pemenang mendapat poin, pecundang kehilangan poin, dan hasil imbang dihitung sebagai poin nol.

Misalkan Pemain B telah memilih strategi pemilihan (bodoh) di setiap putaran kertas. Setelah beberapa putaran kemenangan, kekalahan dan imbang, kemungkinan besar Anda akan melihat sistemnya dan mengembangkan strategi kontra yang menang, memilih gunting di setiap putaran. Sebut saja serangkaian strategi ini (gunting, kertas). Jika setiap putaran menghasilkan gunting terhadap kertas, maka Anda akan membuka jalan menuju kemenangan ideal.

Tetapi Pemain B segera memperhatikan pandangan ke depan dari serangkaian strategi ini. Ketika dia melihat bahwa Anda memilih gunting, ia beralih ke strategi untuk selalu memilih batu. Set strategi ini (gunting, batu) mulai menang untuk Pemain B. Tapi, tentu saja, sekarang Anda akan pergi ke kertas. Sepanjang tahap-tahap permainan ini, Pemain A dan B menggunakan apa yang disebut strategi "bersih" - satu-satunya strategi yang secara konstan dipilih dan diimplementasikan.

Jelas, keseimbangan tidak dapat dicapai di sini: untuk setiap strategi murni, misalnya, "selalu pilih batu", Anda dapat mengembangkan strategi tandingan, misalnya, "selalu pilih kertas", yang akan membuat Anda mengubah strategi lagi. Anda dan lawan Anda akan terus mengejar satu sama lain dalam lingkaran strategi.

Tetapi Anda juga dapat mencoba strategi "campuran". Misalkan daripada memilih satu strategi, Anda dapat secara acak memilih salah satu strategi murni di setiap putaran. Alih-alih "selalu memilih batu", strategi campuran mungkin terlihat seperti "dalam setengah kasus memilih batu, di setengah lainnya memilih gunting". Nash membuktikan bahwa ketika strategi campuran seperti itu dapat diterima, harus ada setidaknya satu titik keseimbangan dalam setiap permainan tersebut. Ayo temukan dia.

Apa strategi campuran yang masuk akal untuk "batu-kertas-gunting"? Tampaknya secara intuitif masuk akal bahwa "memilih batu, kertas, atau gunting dengan probabilitas yang sama." Strategi seperti itu ditulis sebagai $$$(\ frac {1} {3}, \ frac {1} {3}, \ frac {1} {3})$. Ini berarti bahwa batu, gunting dan kertas dipilih dengan probabilitas $$$\ frac {1} {3}$. Apakah strategi ini baik?

Misalkan strategi lawan Anda adalah "selalu memetik batu." Ini adalah strategi murni, yang dapat digambarkan sebagai $$$(1,0,0)$. Apa yang akan menjadi hasil permainan saat merekrut strategi $$$(\ frac {1} {3}, \ frac {1} {3}, \ frac {1} {3})$untuk Player A dan $$$(1,0,0)$untuk Player B?

Untuk mendapatkan gambaran yang lebih jelas tentang permainan, kita akan membangun sebuah tabel di mana probabilitas masing-masing dari sembilan hasil yang mungkin dari setiap putaran akan ditampilkan: batu di A, batu di B; batu di A, kertas di B; dan sebagainya. Pada tabel di bawah ini, baris atas menunjukkan pilihan Player B, dan kolom kiri menunjukkan pilihan Player A.

A | B	Untuk	B	N
Untuk	$$$\ frac {1} {3}$	0	0
B	$$$\ frac {1} {3}$	0	0
N	$$$\ frac {1} {3}$	0	0

Setiap elemen tabel menunjukkan probabilitas sepasang opsi yang dipilih untuk setiap putaran. Ini hanyalah produk dari probabilitas bahwa setiap pemain akan membuat pilihan yang tepat. Misalnya, probabilitas bahwa Pemain A memilih kertas sama dengan $$$\ frac {1} {3}$, dan probabilitas bahwa Pemain B memilih batu adalah 1, yaitu, probabilitas (batu di A, batu di B) adalah $$$\ frac {1} {3} \ kali 1 = \ frac {1} {3}$. Tetapi probabilitas (kertas di A, gunting di B) sama $$$\ frac {1} {3} \ kali 0 = 0$, karena kemungkinan Pemetik B untuk memilih gunting adalah nol.

Bagaimana Pemain A membuktikan dirinya dalam set strateginya? Pemain A akan memenangkan sepertiga dari waktu (kertas, batu), kehilangan sepertiga dari waktu (gunting, batu) dan sepertiga dari waktu akan menjadi hasil imbang (batu, batu). Kami dapat menghitung jumlah poin yang akan diterima Pemain A secara rata-rata di setiap babak dengan menghitung jumlah produk dari setiap hasil dengan probabilitas yang sesuai:

$$

$$\ frac {1} {3} (1) + \ frac {1} {3} (0) + \ frac {1} {3} (- 1) = 0$$

Dengan demikian, rata-rata, Pemain A akan menerima 0 poin per putaran. Anda akan menang, kalah, dan seri dengan probabilitas sama. Rata-rata, jumlah kemenangan dan kekalahan akan menyeimbangkan satu sama lain, dan pada kenyataannya, kedua pemain akan bermain seri.

Tetapi seperti yang telah kami katakan, Anda dapat meningkatkan hasil Anda dengan mengubah strategi Anda, dengan asumsi bahwa musuh tidak akan mengubah strateginya. Jika Anda memilih strategi (0,1,0) (“pilih kertas setiap kali”), maka tabel probabilitas akan terlihat seperti ini:

A | B	Untuk	B	N
Untuk	0	1	0
B	0	0	0
N	0	0	0

Di setiap putaran, Anda akan membungkus batu lawan di kertas Anda dan mendapatkan satu poin untuk setiap putaran.

Yaitu, sepasang strategi ini - $$$(\ frac {1} {3}, \ frac {1} {3}, \ frac {1} {3})$untuk A dan $$$(1,0,0)$untuk B, ini bukan ekuilibrium Nash: Anda, sebagai Pemain A, dapat meningkatkan hasil Anda dengan mengubah strategi Anda.

Seperti yang telah kita lihat, strategi murni tampaknya tidak mengarah pada keseimbangan. Tetapi bagaimana jika lawan Anda mencoba menggunakan strategi campuran, misalnya $$$(\ frac {1} {2}, \ frac {1} {4}, \ frac {1} {4})$? Ini adalah strategi “dalam setengah kasus, pilih batu; kertas dan gunting mendapatkan seperempat dari kasing. " Beginilah tabel probabilitas akan terlihat:

A | B	Untuk	B	N
Untuk	$$$\ frac {1} {6}$	$$$\ frac {1} {12}$	$$$\ frac {1} {12}$
B	$$$\ frac {1} {6}$	$$$\ frac {1} {12}$	$$$\ frac {1} {12}$
N	$$$\ frac {1} {6}$	$$$\ frac {1} {12}$	$$$\ frac {1} {12}$

Dan di sini adalah tabel "hadiah" dari sudut pandang Pemain A; ini adalah jumlah poin yang diperoleh oleh Pemain A di setiap hasil.

A | B	Untuk	B	N
Untuk	0	-1	1
B	1	0	-1
N	-1	1	0

Dengan menggunakan perkalian, kami menggabungkan dua tabel untuk menghitung jumlah rata-rata poin yang diperoleh oleh Pemain A untuk setiap putaran.

$$

$$\ frac {1} {6} (0) + \ frac {1} {12} (- 1) + \ frac {1} {12} (1) + \ frac {1} {6} (1) + \ frac {1} {12} (0) + \ frac {1} {12} (- 1) + \ frac {1} {6} (- 1) + \ frac {1} {12} (1) + \ frac {1} {12} (0) = 0$$

Rata-rata, Pemain A kembali mendapatkan 0 poin per putaran. Seperti sebelumnya, serangkaian strategi ini, $$$(\ frac {1} {3}, \ frac {1} {3}, \ frac {1} {3})$untuk A dan $$$(\ frac {1} {2}, \ frac {1} {4}, \ frac {1} {4})$untuk B, menghasilkan undian.

Tetapi seperti sebelumnya, Anda, sebagai Pemain A, dapat meningkatkan hasil Anda dengan mengubah strategi: melawan strategi Pemain B $$$(\ frac {1} {2}, \ frac {1} {4}, \ frac {1} {4})$Pemain A harus memilih $$$(\ frac {1} {4}, \ frac {1} {2}, \ frac {1} {4})$. Berikut ini tabel probabilitas:

A | B	Untuk	B	N
Untuk	$$$\ frac {1} {8}$	$$$\ frac {1} {16}$	$$$\ frac {1} {16}$
B	$$$\ frac {1} {4}$	$$$\ frac {1} {8}$	$$$\ frac {1} {8}$
N	$$$\ frac {1} {8}$	$$$\ frac {1} {16}$	$$$\ frac {1} {16}$

dan inilah hasil akhir untuk A:

$$

$$\ frac {1} {8} (0) + \ frac {1} {16} (- 1) + \ frac {1} {16} (1) + \ frac {1} {4} (1) + \ frac {1} {8} (0) + \ frac {1} {8} (- 1) + \ frac {1} {8} (- 1) + \ frac {1} {16} (1) + \ frac {1} {16} (0) = \ frac {1} {16}$$

Yaitu, serangkaian strategi ini - $$$(\ frac {1} {4}, \ frac {1} {2}, \ frac {1} {4})$untuk A dan $$$(\ frac {1} {2}, \ frac {1} {4}, \ frac {1} {4})$untuk B - memberikan rata-rata Player A oleh $$$\ frac {1} {16}$poin per putaran. Setelah 100 pertandingan, Pemain A akan unggul 6,25 poin. Pemain A memiliki insentif besar untuk mengubah strategi. Itu adalah serangkaian strategi $$$(\ frac {1} {3}, \ frac {1} {3}, \ frac {1} {3})$untuk A dan $$$(\ frac {1} {2}, \ frac {1} {4}, \ frac {1} {4})$untuk B juga bukan ekuilibrium Nash.

Tapi sekarang mari kita lihat beberapa strategi $$$(\ frac {1} {3}, \ frac {1} {3}, \ frac {1} {3})$untuk A dan $$$(\ frac {1} {3}, \ frac {1} {3}, \ frac {1} {3})$untuk B. Berikut adalah tabel probabilitas yang sesuai:

A | B	Untuk	B	N
Untuk	$$$\ frac {1} {9}$	$$$\ frac {1} {9}$	$$$\ frac {1} {9}$
B	$$$\ frac {1} {9}$	$$$\ frac {1} {9}$	$$$\ frac {1} {9}$
N	$$$\ frac {1} {9}$	$$$\ frac {1} {9}$	$$$\ frac {1} {9}$

Berkat simetri, kami dapat dengan cepat menghitung hasil keseluruhan:

$$

$$\ frac {1} {9} (0) + \ frac {1} {9} (- 1) + \ frac {1} {9} (1) + \ frac {1} {9} (1) + \ frac {1} {9} (0) + \ frac {1} {9} (- 1) + \ frac {1} {9} (- 1) + \ frac {1} {9} (1) + \ frac {1} {9} (0) = 0$$

Dan lagi Anda dan lawan Anda datang seri. Tetapi perbedaannya di sini adalah tidak ada pemain yang memiliki insentif untuk mengubah strategi! Jika Pemain B akan pergi ke strategi yang tidak seimbang, di mana satu opsi - katakanlah, batu - dipilih lebih sering daripada yang lain, maka Pemain A hanya akan mengubah strateginya dan memilih kertas lebih sering. Pada akhirnya, ini akan mengarah pada hasil keseluruhan yang positif untuk Pemain A di setiap babak. Inilah yang terjadi ketika Pemain A memilih strategi $$$(\ frac {1} {4}, \ frac {1} {2}, \ frac {1} {4})$melawan strategi Player B. $$$(\ frac {1} {2}, \ frac {1} {4}, \ frac {1} {4})$.

Tentu saja, jika Pemain A pindah dari $$$(\ frac {1} {3}, \ frac {1} {3}, \ frac {1} {3})$untuk strategi yang tidak seimbang, Pemain B juga akan dapat mengambil keuntungan. Oleh karena itu, tidak ada pemain yang dapat meningkatkan hasil mereka hanya dengan mengubah strategi mereka sendiri. Permainan itu mencapai keseimbangan Nash.

Terbukti oleh Nash, fakta bahwa permainan semacam itu memiliki keseimbangan yang sama sangat penting karena beberapa alasan. Salah satu alasannya adalah bahwa banyak situasi dari kehidupan nyata dapat dimodelkan sebagai permainan. Ketika sekelompok orang dipaksa untuk memilih antara keuntungan pribadi dan kolektif - misalnya, dalam negosiasi atau dalam proses persaingan untuk sumber daya bersama - Anda dapat melihat bahwa strategi digunakan dan kemenangan dievaluasi. Karya Nash telah memiliki dampak yang sangat besar, sebagian berkat sifat model matematika yang ada di mana-mana ini.

Alasan lain adalah bahwa keseimbangan Nash, dalam arti tertentu, adalah hasil positif bagi semua pemain. Ketika keseimbangan ini tercapai, tidak ada pemain yang dapat meningkatkan hasil mereka dengan mengubah strategi mereka sendiri. Mungkin ada hasil kolektif yang bisa dicapai ketika semua pemain bertindak dalam kerja sama yang sempurna, tetapi jika Anda hanya bisa mengendalikan diri sendiri, maka keseimbangan Nash akan menjadi hasil terbaik yang bisa Anda raih.

Oleh karena itu, orang dapat berharap bahwa "permainan" seperti paket insentif ekonomi, kode pajak, ketentuan kontrak, dan desain jaringan akan mengarah pada kesetimbangan Nash di mana individu yang bertindak demi kepentingan mereka sendiri akan muncul dengan hasil yang sesuai untuk semua orang dan sistem menjadi stabil. Tetapi ketika memainkan permainan seperti itu, apakah masuk akal untuk mengasumsikan bahwa para pemain secara alami mencapai keseimbangan Nash?

Ada godaan untuk berpikir demikian. Dalam permainan kami "rock-paper-scissors" kami dapat langsung menebak bahwa tidak ada satu pun pemain yang bisa bermain lebih baik, kecuali dengan bermain secara kebetulan. Tetapi sebagian hal ini terjadi karena preferensi semua pemain diketahui oleh semua pemain lain: semua orang tahu seberapa besar masing-masing akan menang dan kalah dengan masing-masing hasil. Tetapi bagaimana jika preferensi lebih tersembunyi dan kompleks?

Bayangkan sebuah permainan baru di mana Pemain B mendapat tiga poin ketika ia menang melawan gunting, dan satu poin untuk kemenangan lainnya. Ini akan mengubah strategi campuran: Pemain B akan sering memilih batu, berharap untuk hadiah tiga kali lipat ketika Pemain A memilih gunting. Dan meskipun perbedaan poin tidak secara langsung memengaruhi hadiah Pemain A, perubahan yang dihasilkan dalam strategi Pemain B akan mengarah pada strategi kontra baru A.

Dan jika masing-masing hadiah Pemain B akan berbeda dan disembunyikan, maka Pemain A akan membutuhkan waktu untuk mencari tahu strategi Pemain B. Harus ada banyak putaran sebelum menebak Pemain A, katakanlah seberapa sering Pemain B memilih batu untuk dipahami seberapa sering ia perlu memilih kertas.

Sekarang bayangkan 100 orang bermain gunting batu-kertas, dan masing-masing dari mereka memiliki hadiah rahasia yang berbeda, masing-masing tergantung pada berapa banyak dari 99 lawan mereka yang mereka menangkan dengan batu, gunting atau kertas. Berapa banyak waktu yang dibutuhkan untuk menghitung frekuensi yang tepat untuk memilih batu, gunting atau kertas yang diperlukan untuk mencapai titik keseimbangan? Kemungkinan besar, banyak. Mungkin lebih dari permainan itu sendiri akan bertahan. Mungkin lebih lama dari masa hidup alam semesta itu sendiri!

Paling tidak, sama sekali tidak jelas bahwa bahkan pemain yang benar-benar rasional dan bijaksana yang memilih strategi yang baik dan bertindak untuk kepentingan mereka sendiri akan mendapatkan keseimbangan dalam permainan sebagai hasilnya. Ide ini mendasari artikel yang diterbitkan online pada tahun 2016 . Ini membuktikan bahwa tidak ada solusi umum di semua game yang bisa mengarah pada setidaknya keseimbangan Nash. Ini bukan untuk mengatakan bahwa pemain ideal tidak pernah berusaha untuk mencapai keseimbangan dalam permainan - seringkali mereka benar-benar berjuang. Itu hanya berarti bahwa tidak ada alasan untuk percaya bahwa jika pemain sempurna memainkan permainan, keseimbangan akan tercapai.

Ketika kita mengembangkan jaringan transportasi, kita dapat berharap bahwa semua pemain, yaitu pengemudi dan pejalan kaki, yang masing-masing berusaha menemukan jalan pulang tercepat, secara kolektif mencapai keseimbangan di mana tidak ada yang bisa dimenangkan dengan memilih rute yang berbeda. Kita dapat berharap bahwa tangan tak terlihat John Nash akan membimbing mereka sedemikian rupa sehingga kepentingan kompetitif dan bersama mereka - memilih rute sesingkat mungkin sambil menghindari kemacetan lalu lintas - akan menciptakan keseimbangan.

Tapi permainan rock-paper-scissors kami dengan kompleksitas yang semakin meningkat menunjukkan bahwa harapan seperti itu mungkin tidak menjadi kenyataan. Tangan yang tak terlihat bahkan mungkin mengendalikan beberapa permainan ini, tetapi permainan lain menolaknya, memikat para pemain ke dalam perangkap persaingan tanpa akhir untuk mendapatkan kemenangan yang selalu di luar jangkauan.

Latihan

1. Say Player B bermain dengan strategi campuran $$$(\ frac {1} {2}, \ frac {1} {2}, 0)$. Strategi campuran apa yang harus dipilih A untuk memaksimalkan jumlah kemenangannya dalam jangka panjang?
2. Say Player B bermain dengan strategi campuran $$$(\ frac {1} {6}, \ frac {2} {6}, \ frac {3} {6})$. Strategi campuran apa yang harus dipilih A untuk memaksimalkan jumlah kemenangannya dalam jangka panjang?
3. Bagaimana dinamika permainan berubah jika setiap pemain mendapat poin untuk seri?