Teori Game



         Teori game adalah studi tentang model matematika yang berkaitan dengan konflik maupun kerja sama antara para pembuat keputusan yang cerdas dan rasional.

    Teori game terkait dengan tindakan yang dilakukan oleh para pengambil keputusan, dan mereka menyadari bahwa pilihan tindakan yang diambil akan mempengaruhi satu sama lain.



Contoh game:

             Permainan: catur, bridge, sepakbola, dll

             Korporasi: Apple vs Samsung

             Politik: konflik antar negara

Bukan game:

             Penulis buku dengan pembacanya

             Maskapai penerbangan dengan penumpangnya


Memodelkan Game



                 Agar game dapat dimodelkan secara matematis, diperlukan 4 elemen dasar dari sebuah game:

1.                  Pemain

2.                  Tindakan

3.                  Payoff

4.                  Informasi

             Keempat elemen itu disebut juga Rules of The Game
         Para pemain berusaha memaksimalkan payoff mereka, dengan cara memilih strategi yang tepat berdasarkan informasi yang mereka miliki

    Keadaan di mana setiap pemain telah menentukan strategi yang optimal disebut kesetimbangan (equilibrium)

     Dengan mengetahui kesetimbangan dari suatu game, pemodel dapat mengetahui tindakan/strategi apa yang dipilih oleh para pemain yang terlibat, dan juga outcome dari game tersebut.





Asumsi-asumsi Dasar



1.                      Setiap pemain memiliki strategi yang berhingga banyaknya (finite), dan mungkin berbeda dengan pemain lainnya.

2.                      Setiap pemain bersikap rasional. Ia selalu berusaha memilih strategi yang memberikan hasil paling optimal untuk dirinya, berdasarkan payoff dan jenis game yang dimainkan.




Asumsi-asumsi Tambahan



Asumsi tambahan didasarkan pada jenis game yang dimainkan

1.                      Game sekuensial: pemain melakukan tindakan secara bergantian. Pemain berikutnya mengetahui (mungkin secara tidak utuh) tindakan yang diambil oleh pemain sebelumnya.

2.                      Game simultan: pemain melakukan tindakan secara bersamaan. Pada saat mengambil tindakan, pemain yang terlibat tidak mengetahui tindakan yang dipilih oleh pemain lainnya. Dalam hal ini, jeda waktu pengambilan tindakan antara sesama pemain tidak berpengaruh terhadap pilihan yang diambil oleh pemain ybs.

3.                      Game dengan informasi sempurna: pemain mengetahui dengan pasti tindakan yang diambil oleh lawannya, sebelum ia memilih tindakan asumsi ini hanya dapat dipenuhi oleh game sekuensial.

4.                      Game dengan informasi tidak sempurna: pemain tidak mengetahui tindakan yang dipilih lawannya sebelum permainan berakhir.

5.                      Game dengan informasi lengkap (bedakan dengan sempurna): pemain mengetahui payoff lawannya


6.         Game dengan informasi tidak lengkap: pemain tidak memiliki informasi lengkap tentang payoff lawannya.

7.         Game kooperatif: para pemain membuat komitmen yang mengikat (binding commitment) untuk meningkatkan outcome mereka.

8.         Game nonkooperatif: para pemain tidak membuat komitmen yang mengikat.

9.         Zero-sum game: jumlah payoff dari setiap pemain sama dengan nol. Untuk game dengan 2 pemain, besar keuntungan di satu pihak sama dengan besar kerugian di pihak lain

10.  Non-zero-sum game: tidak demikian





Payoff dari sebuah Game



             Payoff adalah sebuah bilangan yang merepresentasikan derajat hasil (utilitas) yang diinginkan oleh pemain ybs. Semakin besar nilai payoff, semakin menguntungkan bagi pemain.

             Dalam sebuah game, payoff dapat direpresentasikan dalam bentuk matriks payoff

             Untuk game non-zero-sum dengan 2 pemain, payoff direpresentasikan dalam bentuk bimatriks

             Untuk game zero-sum dengan 2 pemain, payoff dapat direpresentasikan dalam bentuk matriks dan bimatriks.









Contoh Payoff dari Zero-sum Game dengan 2 pemain





Bentuk bimatriks


Karena saling berlawanan, payoff para pemain dapat direpresentasikan dengan 1 bilangan, dengan catatan bahwa Pemain A melihatnya sebagai keuntungan, dan Pemain B melihatnya sebagai kerugian



















Pangsa pasar A bertambah 8%










Pangsa pasar B berkurang 8%






Bentuk matriks






Dilema Tahanan

(Prisoner's Dilemma)










































Dilema Tahanan

             Polisi menangkap 2 tersangka sebuah kasus kriminal.

             Mereka diinterogasi secara terpisah, dan tidak ada komunikasi di antara mereka.

             Karena bukti-bukti belum cukup, maka polisi memberi mereka 2 pilihan: menyangkal atau mengakui keterlibatan mereka berdua.

             Jika keduanya menyangkal, maka A dan B akan mendapat hukuman penjara 1 tahun.

             Jika A menyangkal dan B mengaku, maka A akan diganjar 10 tahun penjara, dan B bebas.

             Jika A mengaku dan B menyangkal, maka A bebas dan B mendapat hukuman 10 tahun.

             Jika  keduanya  mengaku,  masing-masing  akan  diganjar 8

tahun.
















             Pilihan apakah yang diambil A dan B, agar mereka mendapat gain yang terbaik dari keadaan ini? (A dan B tidak dapat saling berkomunikasi)





































             Payoff dari masalah ini diberikan oleh tabel berikut:











ATAU:



















Bagi A:

              jika B menyangkal, A akan memilih mengaku (0 > -1)











              dan jika B mengaku, A tetap akan memilih mengaku (-8 > -10)















Bagi B:

              jika A menyangkal, B akan memilih mengaku (0 > -1)












              dan jika A mengaku, B tetap akan memilih mengaku (-8 > -10)




















     Bagi A, “mengaku” adalah strategi dominan, karena apapun strategi yang dipilih B, payoff “mengaku” untuk A selalu lebih tinggi dari payoff strategi A lainnya.

     Dengan pertimbangan serupa, B juga akan memilih “mengaku”.

     Maka outcome {mengaku,mengaku} merupakan pilihan terbaik bagi kedua tersangka
     Dalam kasus ini, terjadi kesetimbangan strategi
dominan
Dominan













Dominan






Game Kooperatif dan

Nonkooperatif

             Game kooperatif adalah suatu game yang pemainnya dapat mengadakan komitmen yang saling mengikat (binding commitment).

             Hal demikian tidak terjadi pada game nonkooperatif.

             Jika komitmennya tidak mengikat, game tidak dapat bersifat kooperatif, karena para pemain mungkin akan melanggar komitmen tersebut untuk kepentingan dirinya.

             Dilema Tahanan adalah game nonkooperatif.

             Pertanyaannya: bagaimanakah outcome-nya, jika dijadikan game kooperatif?














Dilema Tahanan Kooperatif



             Jika Napi A dan Napi B dapat mengadakan komitmen yang mengikat, maka mereka akan memilih {menyangkal, menyangkal}, dengan ganjaran masing-masing 1 tahun penjara. Dalam hal ini, outcome-nya lebih baik dibandingkan tanpa komitmen (game nonkooperatif)

             Game tetap harus bersifat simultan (A dan B bertindak secara serentak) dan informasi tidak sempurna (Baik A dan B tidak mengetahui apa pilihan lawannya, sebelum keduanya menetapkan pilihannya)

             Sebab jika A mengetahui B “menyangkal”, maka A jelas akan “mengaku”, sehingga A bebas (namun B dipenjara 10 tahun).

             Jadi, outcome dari suatu game dapat ditingkatkan jika para pemain saling kooperatif.













Strategi murni (pure strategy)



             Diberikan game antara A dan B dengan strategi dan payoff berikut:





Pemain B



1
x
y
z

Pemain A
8
4
7.5

2
7
3,5
3






             Strategi apakah yang dipililh oleh A dan B agar masing-masing memperoleh hasil yang optimal?







Strategi murni (pure strategy)



             Prinsip maximin dan minimax



Pemain B

Keuntungan


1
x
y
z
minimum
maximin
Pemain A
8
4
7.5
4
2
7
3,5
3
3



Kerugian maksimum
8
4
7.5





minimax




             Jika maximin = minimax, maka game memiliki sebuah saddle point ; dan game dikatakan setimbang (memiliki kesetimbangan / equilibrium)
             Dalam hal ini, saddle point = (1,y), dan value of game = 4

             Jika A dan B mengikuti prinsip maximin dan minimax, maka game akan mencapai kesetimbangan, di mana A memilih strategi 1, dan B
memilih strategi y





Strategi Terdominasi dan Strategi Dominan

             Strategi terdominasi adalah strategi yang inferior terhadap sejumlah strategi lain, untuk setiap strategi yang dipilih lawan (dengan kata lain, payoff strategi tersebut ≤ payoff sejumlah strategi lainnya)
             Strategi dominan adalah strategi yang memiliki payoff tertinggi dibandingkan dengan strategi lainnya. Misalkan strategi “X” adalah strategi dominan bagi pemain A, maka apapun strategi yang dipilih pemain B, pemain A tetap akan memilih strategi “X”.

             Strategi mendominasi: strategi X dikatakan mendominasi strategi Y jika payoff strategi X ≥ payoff strategi Y, untuk setiap strategi yang dipilih lawan.















             Tentukan kesetimbangan dari game dengan matriks payoff berikut, dengan mereduksi ukuran matriks terlebih dahulu! (gunakan konsep strategi dominan/terdominasi)!





Pemain B



1
x
y
z

Pemain A
8
4
7.5

2
7
3,5
3



























             Tentukan kesetimbangan dari game dengan matriks payoff berikut, dengan mereduksi ukuran matriks terlebih dahulu! (gunakan konsep strategi dominan/terdominasi)!





Pemain B




1
w
x
y
z

Pemain A
4
8
3,5
6

2
6.5
9
5.5
7




3
5.5
4
4.5
7.5


4
4.5
2.5
5
5