Teori permainan

Teori permainan (bahasa Inggris: game theory) adalah bagian dari ilmu matematika yang mempelajari interaksi antar agen yang bersifat rasional. Setiap keputusan atau strategi yang dipilih oleh agen akan memiliki hasil yang berbeda (payoff) pada agen kompetitor.^[1] Pertama kali dikembangkan sebagai cabang tersendiri dari ilmu matematika oleh Oskar Morgenstern dan John von Neumann, cabang ilmu ini telah berkembang sedemikian pesat hingga melahirkan banyak tokoh peraih nobel, seperti John Nash (AS), Reinhard Selten (Jerman), dan John Harsanyi (AS) pada tahun 1999 dan Thomas Schelling (AS), Robert Aumann (Israel) pada tahun 2005, dan Leonid Hurwicz (Amerika Serikat) pada tahun 2007.

Dasar teori permainan

Permodelan teori permainan paling mudah biasanya dimodelkan dalam bentuk matriks payoff atau pohon keputusan. Pada dasarnya, teori permainan diasumsikan semua agen bersifat rasional. Rasionalitas yang dimaksud adalah dimana setiap agen diasumsikan memutuskan strategi untuk memaksimalkan payoff dari agen itu sendiri yang tergantung pada pengetahuan dari agen terhadap strategi kompetitor.^[2] Variabel-variabel yang diformulasikan pada teori permainan mencakup keputusan (strategi) dari setiap agen dan payoff yang berupa hasil dari pengambilan keputusan tersebut. Apabila digambarkan pada agen ${\displaystyle A}$ dan ${\displaystyle B}$, maka agen ${\displaystyle A}$ dapat memiliki strategi ${\displaystyle S_{1}^{A}}$, ${\displaystyle S_{2}^{A}}$, ..., sampai ${\displaystyle S_{n}^{A}}$ dan agen ${\displaystyle B}$ memiliki strategi ${\displaystyle S_{1}^{B}}$, ${\displaystyle S_{2}^{B}}$, ..., sampai ${\displaystyle S_{m}^{B}}$. Kemungkinan hasil atau payoff yang diperoleh agen ${\displaystyle A}$ dan ${\displaystyle B}$ dapat berjumlah ${\displaystyle n\times m}$. Diketahui bahwa agen ${\displaystyle A}$ dan agen ${\displaystyle B}$ memiliki Payoff berupa ${\displaystyle f_{A}(S_{n}^{A},S_{m}^{B})}$ dan ${\displaystyle f_{B}(S_{m}^{B},S_{n}^{A})}$. ${\displaystyle f_{A}(S_{n}^{A},S_{m}^{B})}$ adalah fungsi payoff dari agen ${\displaystyle A}$ mempertimbangkan strategi Agen ${\displaystyle A}$ (${\displaystyle S_{n}^{A}}$) yang ke ${\displaystyle n}$ dan strategi Agen ${\displaystyle B}$ (${\displaystyle S_{m}^{B}}$) yang ke ${\displaystyle m}$. Tabel matriks payoff dari agen ${\displaystyle A}$ dan ${\displaystyle B}$ adalah sebagai berikut:

		Agen ${\displaystyle B}$
		${\displaystyle S_{1}^{B}}$	${\displaystyle S_{2}^{B}}$	...	${\displaystyle S_{m}^{B}}$
Agen ${\displaystyle A}$	${\displaystyle S_{1}^{A}}$	${\displaystyle f_{A}(S_{1}^{A},S_{1}^{B}),f_{B}(S_{1}^{B},S_{1}^{A})}$	${\displaystyle f_{A}(S_{1}^{A},S_{2}^{B}),f_{B}(S_{2}^{B},S_{1}^{A})}$	...	${\displaystyle f_{A}(S_{1}^{A},S_{m}^{B}),f_{B}(S_{m}^{B},S_{1}^{A})}$
	${\displaystyle S_{2}^{A}}$	${\displaystyle f_{A}(S_{2}^{A},S_{1}^{B}),f_{B}(S_{1}^{B},S_{2}^{A})}$	${\displaystyle f_{A}(S_{2}^{A},S_{2}^{B}),f_{B}(S_{2}^{B},S_{2}^{A})}$	...	${\displaystyle f_{A}(S_{2}^{A},S_{m}^{B}),f_{B}(S_{m}^{B},S_{2}^{A})}$
	...	...	...	...	...
	${\displaystyle S_{n}^{A}}$	${\displaystyle f_{A}(S_{n}^{A},S_{1}^{B}),f_{B}(S_{1}^{B},S_{n}^{A})}$	${\displaystyle f_{A}(S_{n}^{A},S_{2}^{B}),f_{B}(S_{2}^{B},S_{n}^{A})}$		${\displaystyle f_{A}(S_{n}^{A},S_{m}^{B}),f_{B}(S_{m}^{B},S_{n}^{A})}$

Penyelesaian atau solusi dari permasalahan ini disebut ini keseimbangan Nash (Nash Equilibrium) apabila setiap agen sudah mencapai payoff maksimum tergantung dari strategi agen lain dan seluruh agen tidak dapat lagi merubah strateginya. Keseimbangan Nash ditemukan oleh John Forbes Nash Jr. dalam studinya yang berjudul Noncooperative games^[3]. Sebagai contoh, permasalahan dilema tahanan (prisoner's dilemma) adalah penerapan teori permainan untuk dua tahanan yang sedang diinterogasi. Tahanan ${\displaystyle A}$ dan ${\displaystyle B}$ ditangkap karena kejahatan yang dilakukan mereka secara bersamaan oleh penegak hukum. Setiap tahanan yang diinterogasi memiliki dua strategi yaitu mengakui kejahatannya atau tidak. Payoff dari kedua tahanan ini adalah lama tahanan akan dipenjara. Setiap strategi yang dilakukan akan menghasilkan payoff yang berbeda-beda untuk setiap Tahanan. Jika dimodelkan dengan matriks payoff, strategi dan payoff kedua tahanan adalah berikut ini:

		Pengakuan Tahanan ${\displaystyle B}$
		Mengaku ${\displaystyle (S_{1}^{B})}$	Tidak ${\displaystyle (S_{2}^{B})}$
Pengakuan Tahanan ${\displaystyle A}$	Mengaku ${\displaystyle (S_{1}^{A})}$	${\displaystyle f_{A}(S_{1}^{A},S_{1}^{B})=}$ 3 tahun ${\displaystyle f_{B}(S_{1}^{B},S_{1}^{A})=}$ 3 tahun	${\displaystyle f_{A}(S_{1}^{A},S_{2}^{B})=}$ bebas ${\displaystyle f_{B}(S_{2}^{B},S_{1}^{A})=}$ 5 tahun
	Tidak ${\displaystyle (S_{2}^{A})}$	${\displaystyle f_{A}(S_{2}^{A},S_{1}^{B})=}$ 5 tahun ${\displaystyle f_{B}(S_{1}^{B},S_{2}^{A})=}$ bebas	${\displaystyle f_{A}(S_{2}^{A},S_{2}^{B})=}$ 1 tahun ${\displaystyle f_{B}(S_{2}^{B},S_{2}^{A})=}$ 1 tahun

Contoh matriks payoff menunjukan efek dari penetapan setiap strategi tahanan ${\displaystyle A}$ dan ${\displaystyle B}$ terhadap lama mereka akan dipenjara. Sebagai contoh, Jika tahanan ${\displaystyle A}$ mengakui perbuatannya dan tahanan ${\displaystyle B}$ tidak, maka tahanan ${\displaystyle A}$ akan bebas dan tahanan ${\displaystyle B}$ dipenjara selama 5 tahun. Berdasar dari konsep keseimbangan Nash, jika tahanan ${\displaystyle B}$ memilih mengaku, maka respon terbaik tahanan ${\displaystyle A}$ adalah juga mengakui perbuatannya. Jika tahanan ${\displaystyle B}$ memilih untuk tidak mengakui, respon terbaik tahanan ${\displaystyle A}$ adalah masih mengakui perbuatannya. Apapun strategi yang dipilih tahanan ${\displaystyle B}$, tahanan ${\displaystyle A}$ sebaiknya memilih untuk mengakui perbuatannya. Hal ini pun juga berlaku untuk tahanan ${\displaystyle B}$. Jika tahanan ${\displaystyle A}$ memilih mengaku, maka respon terbaik tahanan ${\displaystyle B}$ adalah juga mengakui perbuatannya. Jika tahanan ${\displaystyle A}$ memilih untuk tidak mengakui, respon terbaik tahanan ${\displaystyle B}$ adalah masih mengakui perbuatannya. Alhasil, kedua tahanan akan memilih untuk mengakui perbuatannya. Hal ini disebut keseimbangan Nash dimana kedua tahanan yang sudah mengaku tidak lagi dapat memperbaharui strateginya. Akhirnya kedua tahanan memiliki payoff berupa dipenjara selama 3 tahun. Kondisi permainan yang dilakukan juga termasuk kedalam permainan nonkooperatif (Noncooperative game), dimana semua agen rasional berkompetisi tanpa ada interaksi antar mereka. Jika kedua tahanan memilih untuk berinteraksi, maka satu-satunya payoff paling optimal diperoleh jika keduanya tidak mengaku. Mereka akan hanya dipenjara selama satu tahun. Skema interaksi ini dinamakan permainan kooperatif (Cooperative game).

Selain dimodelkan dengan matriks payoff, permainan dapat dimodelkan dengan menggunakan pohon keputusan (Decision tree). Penggunaan pohon keputusan dalam teori permainan dapat merujuk kepada permainan sekuensial (Sequential game) dan permainan extensive form. Jika diaplikasikan pada permainan dilema tahanan, strategi tahanan ${\displaystyle A}$ yang dari tahanan ${\displaystyle B}$ dapat dilihat pada gambar pohon keputusan.