...

Teori Game - Universitas Gunadarma

by user

on
Category: Documents
0

views

Report

Comments

Transcript

Teori Game - Universitas Gunadarma
Teori Game
(Game Theory/Teori Permainan)
Teori Game, Ahmad Sabri, Universitas Gunadarma
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.
Teori Game, Ahmad Sabri, Universitas Gunadarma
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
Teori Game, Ahmad Sabri, Universitas Gunadarma
Memodelkan Game
•
Agar game dapat dimodelkan secara
matematis, diperlukan 4 elemen dasar dari
sebuah game:
1.
2.
3.
4.
•
Pemain
Tindakan
Payoff
Informasi
Keempat elemen itu disebut juga Rules of The
Game
Teori Game, Ahmad Sabri, Universitas Gunadarma
• 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.
Teori Game, Ahmad Sabri, Universitas Gunadarma
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.
Teori Game, Ahmad Sabri, Universitas Gunadarma
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
Teori Game, Ahmad Sabri, Universitas Gunadarma
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
Teori Game, Ahmad Sabri, Universitas Gunadarma
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.
Teori Game, Ahmad Sabri, Universitas Gunadarma
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 B
berkurang 8%
8%, -8%
Pangsa pasar A
bertambah 8%
Bentuk
matriks
Teori Game, Ahmad Sabri, Universitas Gunadarma
Dilema Tahanan
(Prisoner's Dilemma)
Teori Game, Ahmad Sabri, Universitas Gunadarma
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.
Teori Game, Ahmad Sabri, Universitas Gunadarma
• Pilihan apakah yang diambil A dan B, agar
mereka mendapat gain yang terbaik dari
keadaan ini? (A dan B tidak dapat saling
berkomunikasi)
Teori Game, Ahmad Sabri, Universitas Gunadarma
• Payoff dari masalah ini diberikan oleh
tabel berikut:
ATAU:
Teori Game, Ahmad Sabri, Universitas Gunadarma
Bagi A:
• jika B menyangkal, A akan memilih
mengaku (0 > -1)
• dan jika B mengaku, A tetap akan memilih
mengaku (-8 > -10)
Teori Game, Ahmad Sabri, Universitas Gunadarma
Bagi B:
• jika A menyangkal, B akan memilih
mengaku (0 > -1)
• dan jika A mengaku, B tetap akan memilih
mengaku (-8 > -10)
Teori Game, Ahmad Sabri, Universitas Gunadarma
• 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
Teori Game, Ahmad Sabri, Universitas Gunadarma
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?
Teori Game, Ahmad Sabri, Universitas Gunadarma
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.
Teori Game, Ahmad Sabri, Universitas Gunadarma
Strategi murni (pure strategy)
• Diberikan game antara A dan B dengan
strategi dan payoff berikut:
Pemain A
1
2
x
8
7
Pemain B
y
4
3,5
z
7.5
3
• Strategi apakah yang dipililh oleh A dan B agar
masing-masing memperoleh hasil yang optimal?
Teori Game, Ahmad Sabri, Universitas Gunadarma
Strategi murni (pure strategy)
•
Prinsip maximin dan minimax
Pemain B
Keuntungan
x
y
z
minimum
1
8
4
7.5
4
maximin
Pemain A
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
Teori Game, Ahmad Sabri, Universitas Gunadarma
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.
Teori Game, Ahmad Sabri, Universitas Gunadarma
• Tentukan kesetimbangan dari game dengan
matriks payoff berikut, dengan mereduksi
ukuran matriks terlebih dahulu! (gunakan
konsep strategi dominan/terdominasi)!
Pemain A
1
2
x
8
7
Teori Game, Ahmad Sabri, Universitas Gunadarma
Pemain B
y
4
3,5
z
7.5
3
• Tentukan kesetimbangan dari game dengan
matriks payoff berikut, dengan mereduksi
ukuran matriks terlebih dahulu! (gunakan
konsep strategi dominan/terdominasi)!
Pemain A
1
2
3
4
w
4
6.5
5.5
4.5
Pemain B
x
8
9
4
2.5
Teori Game, Ahmad Sabri, Universitas Gunadarma
y
3,5
5.5
4.5
5
z
6
7
7.5
5
Fly UP