Game Theory : Multiplayer

Game multipel (atau banyak permainan pemain atau game n-player) adalah bagian dari teori Game, yang berfokus pada permainan di mana lebih dari dua pemain berada. Hal ini dianggap sebagai permainan dengan n ≥ 2 pemain, dan setiap pemain memiliki strategi d ≥ 2 untuk dipilih. Ada banyak game multiplayer yang bisa dengan mudah berubah menjadi game 2 pemain.

Di dunia nyata orang akan menghadapi lebih sering dengan game multipemain, dibandingkan dengan game 2 pemain murni. Dalam beberapa hal, seluruh kehidupan dan bertahan di planet ini dapat dinyatakan sebagai permainan multipemain, karena setiap orang yang hidup harus memilih cara untuk bertindak (strategi) dan karena itu mempengaruhi yang lain.

Gambaran umum tentang Multiplayer

Sebelum kita sampai ke game multiplayer, mari kita meninjau singkat istilah teori permainan dasar:

• Game: Setiap rangkaian keadaan yang memiliki akibat tergantung pada tindakan dua pengambil keputusan lainnya ("pemain")

• Pemain: Pembuat keputusan strategis dalam konteks permainan

• Strategi: Rencana aksi yang lengkap yang akan dilakukan pemain diberikan serangkaian situasi yang mungkin timbul dalam permainan

• Payoff: Pembayaran yang diterima pemain dari pada hasil tertentu. Pembayarannya bisa dalam bentuk kuantitatif apapun, dari dolar sampai utilitas.

• Information Set: Informasi tersedia pada titik tertentu dalam permainan. Istilah informasi yang paling sering digunakan saat permainan memiliki komponen sekuensial.

• Equilibrium: Poin dalam permainan di mana kedua pemain telah membuat keputusan dan hasilnya tercapai.

Dalam bab ini kita akan melihat lebih dekat jenis permainan multipemain yang paling umum, seperti dilema n-player tahanan, acusi dll.

Tragedi milik umum

Gambarlah padang rumput, yang bisa digunakan para gembala untuk memberi makan ternak mereka. Diharapkan, para gembala akan berusaha memelihara ternak sebanyak mungkin di padang rumput yang sama, sehingga padang rumput penuh dalam waktu singkat dan menambahkan lebih banyak ternak akan menyebabkan penggembalaan berlebihan. Karena setiap penggembala adalah makhluk rasional, dia mencoba memaksimalkan keuntungannya, dia bertanya: "Apa gunanya menambahkan satu hewan lagi ke kawanan?" Utilitas tersebut memiliki satu komponen negatif dan satu positif:

1. Komponen positif adalah fungsi dari kenaikan satu hewan. Karena penggembala menerima semua hasil penjualan hewan tambahan tersebut, utilitas positifnya hampir bernilai +1.

2. Komponen negatif adalah fungsi penambahan overgrazing yang dibuat oleh satu hewan lagi. Namun, karena efek overgrazing dibagikan oleh semua gembala, utilitas negatif bagi pengganda pengambilan keputusan tertentu secara signifikan lebih kecil daripada komponen positifnya.

Dengan menambahkan semua komponen, penggembala rasional menyimpulkan, bahwa keputusan yang masuk akal adalah menambahkan satu ternak ke kawanan setiap waktu. Tapi karena setiap penggembala "dikunci" sebagai kesimpulan penambahan ternak yang tidak terbatas ke ternak, bidang yang sama akan hancur total dan oleh karena itu tidak akan ada padang rumput untuk memberi makan ternak.

Apa solusinya? Menurut penulis sepertinya perubahan peraturan, sehingga "cacat" bukanlah strategi dominan adalah satu-satunya solusi. Garrett Hardin menyarankan beberapa contoh bagaimana mengelolanya:

• Untuk menjual barang biasa sebagai milik pribadi, atau

• Mengalokasikan hak untuk menggunakan properti bersama (satu ekor sapi per orang max, membeli hak yang benar dll).

Aplikasi hari ini

Situasi serupa juga bisa ditemukan hari ini. Kebanyakan dari mereka bisa disebut masalah lingkungan. "Dilema bersama dianggap sebagai model untuk berbagai masalah sumber daya di masyarakat saat ini, seperti sumber air, hutan, ikan, dan sumber energi tak terbarukan seperti minyak dan batu bara."

Ada yang menyebutkan banyak potensi atau tragedi aktual:

• Mengemudi mobil - Ada banyak eksternalitas negatif dalam mengendarai mobil (polusi, emisi karbon, kecelakaan lalu lintas, dsb.)

• Pertumbuhan populasi manusia - Pertumbuhan populasi manusia yang tidak terkontrol dapat menyebabkan populasi berlebih (masalah saat ini dapat dilihat di China)

• Air - Air sangat tercemar oleh emisi industri dan sumber lainnya.

• Air - mirip dengan masalah udara

• Hutan - Perbatasan hutan bekas tebangan

• Frekuensi radio - Frekuensi tidak berlisensi yang digunakan untuk komunikasi nirkabel rentan terhadap penggunaan pemancar daya tinggi secara berlebihan

• Spam email - Spamming menurunkan kegunaan sistem email dan meningkatkan biaya untuk semua pengguna internet sambil memberikan keuntungan hanya untuk kelompok kecil individu.

Permainan kooperatif adalah permainan dimana dua kelompok pemain (koalisi) dapat memberlakukan perilaku kooperatif. Permainan ini agak persaingan antara koalisi pemain ketimbang antar pemain sendiri.

Koalisi

Koalisi adalah bagian dari rangkaian pemain. Bentuk koalisi untuk mengkoordinasikan strategi dan menyetujui bagaimana total hasil akan dibagi antar anggota.

Misalkan P adalah set dari pemain dan ada pemain N dalam sistem, N juga disebut koalisi besar. Koalisi dilambangkan dengan huruf besar: S, T, U, dll. Koalisi yang terbentuk S ⊆ P dan koalisi kontra SC adalah:

Sc = P - S = S^' ­_p

Secara umum, jika ada pemain N dalam game, ada 2N kemungkinan koalisi.

Contoh permainan 3 pemain:

P = { P₁,P₂,P₃ }

Ada 23 = 8 kemungkinan koalisi:

• Koalisi besar itu sendiri: { P₁,P₂,P₃}

• 3 koalisi satu pemain: { P₁ } { P₂ } { P₃ }

• 3 koalisi dua pemain: {P₁, P₂}  {P₁,P₃}  {P₂,P₃}

• Koalisi kosong: ∅

Fungsi karakteristik

Cara sederhana untuk melihat permainan kooperatif adalah melihat persaingan antara dua "pemain": Koalisi S dan koalisi koalisi SC.

Mari kita pertimbangkan permainan N-player, di mana P = {P1 ... PN} dan Xi adalah strategi yang ditetapkan untuk pemain Pi. Pertandingan juga tidak memiliki koalisi kosong. Oleh karena itu kita bisa membuat bi-matrix dengan baris dan kolom yang sesuai dengan strategi gabungan murni pemain di S (atau SC). Matriks memiliki entri sebagai pasangan angka. Dimana angka pertama adalah jumlah hadiah dari koalisi S dan yang kedua adalah jumlah hadiah dari koalisi koalisi SC.

Nilai maksimum untuk koalisi S dalam bi-matriks disebut fungsi karakteristik S dan dilambangkan dengan v (S).

Teorema Superaditivitas

Teorema Superaditivitas dapat dijelaskan secara samar-samar sebagai berikut: "Ada kekuatan dalam persatuan." Ini menyatakan, bahwa nilai persatuan tidak kurang dari jumlah koalisi yang memisahkan nilai-nilai:

Biarkan S dan T menguraikan koalisi:

v(S u T) >= v(S) + v(T)

Tuduhan

Misalkan sebuah koalisi terbentuk dalam game N-orang. Setiap pemain dalam game ini ingin tahu, seberapa besar keuntungannya, jika dia membentuk koalisi. Jumlah keuntungan yang masuk ke pemain membentuk angka N-tuple x. Vektor N-tuple x harus memenuhi dua syarat:

• Rasionalitas individu: Untuk semua pemain

• Rasionalitas kolektif: Kita punya

Jika N-tupel memenuhi syarat, maka disebut imputasi.

Imputasi

Jika ada imputasi, yang didominasi oleh beberapa koalisi, tidak akan pernah terbentuk secara permanen. Akan selalu ada kecenderungan koalisi ini untuk bubar dan digantikan oleh satu, yang memberi anggotanya bagian yang lebih besar.

Imputasi yang tidak didominasi oleh imputasi lain melalui koalisi disebut inti.

"Jika sebuah imputasi x berada pada intinya, tidak ada kelompok pemain yang memiliki alasan untuk membentuk koalisi dan mengganti x. Oleh karena itu, intinya adalah "konsep solusi" dari permainan koperasi N-orang. Seperti yang akan kita lihat, konsep solusi ini tidak apa-apa asalkan intinya tidak kosong. "

Salah satu bentuk game Multiplayer 

Referensi :

http://www.simulace.info/images/Multiplayer-games.docx