Sekilas Mengenai Game Theory part 1

hmm, pada pembahasan kali ini gw ingin menjelaskan sedikit mengenai Game Theory, bagi yang ngerti mudah2an dapat memperkaya atau bisa diberi masukan dan revisi….

mari kita mulai…

Sejarah Singkat Game Theory

• 1913  E. Zermelo menemukan teorema pertama dari game theory pada permainan catur
• 1928   John von Neumann membuktikan teorema minimax
• 1944  John von Neumann / Oskar Morgenstern’s menulis buku berjudul “Theory of Games and Economic Behavior”
• 1950-1953  John Nash menemukan Nash equilibrium
• 1972  John Maynard Smith menulis buku berjudul “Game Theory and The Evolution of Fighting”

Apa itu Game Theory?

adalah studi tentang bagaimana menentukan strategi terbaik secara matematis untuk kondisi yang diberikan dalam rangka untuk mengoptimalkan hasil,

poin-poin utama dari Game Theory adalah sbb:

• Menemukan strategi yang dapat diterima, jika tidak dapat optimal, dalam situasi konflik merupakan nilai utama dari permainan (hasil yang diharapkan)
• Abstraction riil situasi dari yang kompleks
• Game Theory sangat matematis
• Game Theory mengasumsikan semua interaksi manusia dapat dipahami dan diarahkan oleh praduga.

Mengapa Game Theory itu penting?

• Semua makhluk berakal membuat keputusan di setiap saat.
• Dibutuhkan untuk pengembangan Artificial Intelligent (AI).
• Membantu kita untuk menganalisis situasi dan merumuskan secara rasional alternatif yang dapat diterima, disesuaikan dengan keadaan.

Tipe-Tipe Game Theory

A.  Sequential vs. Simultaneous moves
B.  Single Play vs. Iterated
C.  Zero vs. non-zero sum game
D. Perfect vs. Imperfect information
E.  Cooperative vs. conflict
F.  General:
– Pure strategy
– Mixed Strategy

Zero-Sum vs Non Zero-Sum Game

A. Zero Sum game

suatu situasi di mana keuntungan atau kerugian seorang pemain persis diimbangi oleh kerugian atau keuntungan dari pemain lain. Jika total keuntungan dari para peserta ditambahkan, dan total kerugian dikurangi, maka jumlahnya adalah nol.

Poin-poin utama :

• Jumlah dari payoff tetap konstan selama permainan
• Dua belah pihak dalam konflik
• Mendapat informasi lebih selalu membantu seorang pemain

contohnya adalah melakukan Jan-Ken-pong ( Rock-Paper Scissors ), berikut ini adalah matriks dari permainan tersebut :

	Player B
Player A			0	–1	1
			1	0	–1
			–1	1	0

Apabila kedua pemain sama-sama mengeluarkan kertas, maka payoff nya adalah Nol, dan apabila pemain A mengeluarkan kertas sementara pemain B adalah gunting maka payoff nya bernilai -1 bagi pemain A, dst.

perlu dicatat bahwa matriks tersebut berdasarkan sudut pandang salah seorang pemain saja,meskipun di dalam Zero-Sum hasilnya sudah dapat diketahui (kertas kalah melawan gunting, kertas menang melawan batu, dst)

(gambar matriks diambil dari situs http://www.zweigmedia.com )

B. Non Zero-Sum Game

Berlawanan dengan Zero-Sum Game, maka pada permainan ini tidak akan ada hasil yang strictly competitive, karena payoff tidak akan konstan bagi setiap pemain.

Poin-poin utama :

• Jumlah payoff tidak konstan selama jalannya permainan
• Pemain dapat bekerjasama atau bersaing
• Mendapat informasi lebih dapat membahayakan seorang pemain.

contoh-contoh kasus dalam Non-Zero-Sum Game adalah:

a) Battle of Sexes

Ini merupakan kasus yang sangat tipikal dalam Non-Zero-Sum Game, dimana contohnya adalah sepasang Suami-Istri hendak memutuskan kemana mereka akan menghabiskan akhir pekan mereka setelah sibuk bekerja selama 5 hari. Sang Suami sangat ingin menonton pertandingan Sepak Bola karena hari itu tim luar negeri favoritnya akan menggelar pertandingan persahabatan dengan tim lokal di daerahnya, sehingga merupakan kesempatan langka. Sementara Sang Istri pada saat yang sama juga ingin menonton konser band luar negeri kesayangannya, dan hal itu juga merupakan kesempatan langka  bagi Sang Istri karena hari itu adalah hari terakhir konser terakhir band tersebut.

Keduanya sangat ingin pergi ke tempat tujuan masing-masing, tetapi keduanya juga tidak ingin meninggalkan pasangannya dan pergi sendiri-sendiri.

Payoff matriks dari kasus ini adalah :

Dari matriks di atas dapat dilihat bahwa salah satu pihak akan cenderung kurang senang apabila harus mengikuti kemauan pasangannya, dapat dilihat bahwa apabila sang istri mengikuti suaminya menonton sepak bola, maka nilai payoff nya adalah 2 sementara suaminya 3, dan juga sebaliknya. Tetapi apabila keduanya memutuskan untuk pergi sendiri-sendiri maka nilai payoff mereka masing-masing adalah 1

Poin penting dari kasus ini adalah adanya usaha untuk mencapai kondisi win-win sehingga tidak ada pihak yang akan dirugikan sehingga akan mendapatkan payoff maksimal. Hal tersebut dapat dicapai melalui negosiasi, ataupun kompensasi yang setimpal (misalkan Sang suami berjanji akan membelikan istrinya pakaian merk desainer terkenal apabila mau menemani dia menonton sepak bola, dsb)

b) Chicken Run

Contoh untuk kasus ini adalah, Batman dan Superman sama-sama memperebutkan Wonder Woman untuk dijadikan Istri, dimana keduanya mempunyai opsi untuk maju berkelahi, ataupun mundur dan mengaku kalah (pengecut/chicken).

Payoff matriks untuk kasus ini adaah :

Dari matriks di atas dapat dilihat bahwa apabila keduanya memutuskan untuk maju berkelahi maka keduanya akan sama – sama memperoleh payoff sebesar -5 dikarenakan siapapun yang menang pasti keduanya akan luka-luka, lalu apabila keduanya memutuskan untuk mundur maka masing-masing akan mendapat payoff sebesar -15 karena tidak ada yang berhasil menikah dengan Wonder Woman. Sementara apabila salah satu pihak saja yang mundur, maka akan memperoleh payoff sebesar -10 dan yang tetap maju akan memperoleh payoff sebesar 10 karena berhasil menikahi Wonder Woman.

Pada kasus ini, pilihan terbaik adalah untuk tetap maju dan berharap agar lawannya mundur. Karenanya, poin utama dari kasus jenis ini adalah kemampuan seorang pemain untuk menggertak pihak lawan untuk mundur dari persaingan, atau memilih untuk mengalah karena sadar bahwa dirinya tidak akan bisa mengungguli lawannya.

c) Prisonner’s Dilemma

Jenis kasus yang ketiga, contohnya adalah, pada suatu waktu ada 2 orang (si A dan si B) yang bekerja-sama dalam merampok sebuah Bank. Polisi yang mengusut kasus ini sudah bisa memastikan bahwa kedua orang tersebut lah pelakunya, tetapi sayang sekali belum ditemukan bukti yang kuat untuk menangkap keduanya. Pada suatu hari, terjadilah keberuntungan bagi pihak Polisi, dimana kedua tersangka ditangkap dan dibawa ke kantor Polisi atas tuduhan membawa senjata ilegal. Polisi yang mengusut kasus ini pun langsung menyuruh anak buah nya untuk memisahkan si A dan si B untuk diinterogasi secara terpisah, dengan kondisi kedua tersangka tidak dapat bertatap muka dan berkomunikasi dalam bentuk apapun satu sama lain.

Setelah interogasi yang cukup alot, Polisi pun menawarkan kepada si A dan si B (masih di ruangan terpisah) dengan berpura-pura sudah mempunyai bukti yang kuat atas tuduhan perampokan Bank, yaitu apabila si A mau mengakui bahwa dirinya dan si B adalah pelaku perampokan dan si B tidak mengaku, maka si A akan dibebaskan dari segala macam tuduhan sementara si B akan dikenai hukuman 10 tahun penjara, dan begitu pula sebaliknya. Sementara apabila keduanya memutuskan untuk diam dan tidak mengaku, maka masing-masing akan dikenai hukuman 6 bulan penjara atas tuduhan membawa senjata ilegal, dan apabila keduanya mengaku maka masing-masing hanya akan dikenai hukuman 5 tahun penjara.

Payoff Matriks dari kasus ini adalah :

Dari matriks di atas dapat dilihat bahwa keputusan terbaik bagi masing-masing tersangka adalah untuk mengaku dengan harapan bahwa temannya tidak akan mengaku, sehingga tersangka tersebut akan dibebaskan (mendapatkan payoff sebesar 10) dan temannya saja yang akan dipenjara selama 10 tahun (mendapatkan payoff sebesar -10). Andaikan temannya juga mengaku, maka payoff masing-masing adalah -5 karena masing-masing akan dipenjara selama 5 tahun, dan kemungkinan yang terbaik kedua adalah untuk keduanya tidak mengaku dan dipenjara selama 6 bulan saja (mendapat nilai payoff -1).

Dalam kasus ini, poin utama adalah tingkat kepercayaan terhadap partner, dimana seseorang harus bisa mengetahui seberapa jauh dia bisa mempercayai partnernya untuk, dalam contoh kasus ini, tidak mengaku sehingga keduanya hanya akan dikenai hukuman penjara selama 6 bulan saja. Tetapi tentu dalam kenyataannya tidak semudah itu, karena dalam contoh kasus ini, ada pilihan lain dimana seseorang akan mendapat payoff sebesar 10, yaitu mengaku dan berharap bahwa partnernya tidak mengaku.

*******end of part 1*******