Download - Game Theory

FILM BEAUTIFUL MIND

Dalam film tersebut,John Nash menemukan idenya saat ia tertarik pada seorang gadis di café. Nash berpikir, kalau ada sejumlah laki-laki yang baku hantam satu sama lain untuk memperebutkan hati seorang gadis, bisa jadi kisah mereka akan berakhir di rumah sakit tanpa ada satu priapun yang mendapatkan si gadis. Oleh karenanya, menurut Nash masing-masing pria akan menjalankan strategi tertentu yang jitu untuk memikat si gadis. Si pria juga harus memperhatikan strategi pesaingnya. Seandainya pria lain sudah membawakan bunga, maka ia harus datang dengan pusiti atau musik. Lantas ketika ia datang dengan puisi, si pesaing pun akan mengatur strategi baru; mungkin datang dengan musik. Demikian seterusnya hinga masing-masing akan menemukan satu strategi yang ia anggap terbaik sebagai respon atas strategi yang dijalankan orang lain. Kondisi ini yang dalam teori ekonomi dikenal dengan keseimbangan Nash.

Teori permainan (game theory) adalah bagian dari ilmu pengetahuan yang berkaitan dengan

pembuatan keputusan pada saat dua pihak atau lebih berada dalam kondisi persaingan atau konflik dimana tujuannya untuk memenangkan permainan

dari pesaingnya.

Pembahasan pada materi ini dititik beratkan pada:

GOAL

• Mahasiswa dapat memahami konsep dasar pengambilan keputusan dalam situasi multi alternatif.

• Mahasiswa akan dapat mengetahui berbagai macam ilustrasi dalam penyelesaian masalah keputusan dengan metoda teori permainan.

OUTLINE

PENDAHULUAN

PENDAHULUAN

• Definisi: bagian dari ilmu pengetahuan yang berkaitan dengan pembuatan keputusan pada saat dua pihak atau lebih berada dalam kondisi persaingan atau konflik, dimana setiap lawan berkeinginan untuk mengoptimumkan keputusannya sendiri dengan kerugian lawannya.

• Contoh : kampanye iklan peluncuran produk-produk yang bersaing dan perencanaan taktik-taktik perang melawan tentara musuh.

PENDAHULUAN

• Model-model teori permainan ini dapat diklasifikasikan dalam beberapa cara, bergantung pada faktor-faktor berikut: • banyaknya pemain, • jumlah keuntungan dan kerugian, • banyaknya strategi yag dilakukan dalam

permainan

Klasifikasi Model Game Theory

• Banyaknya pemain:• Two Person Game; banyaknya pemain dua

pihak(baik individu atau kelompok)

• N Person Game; banyaknya pemain adalah N pihak (N>2)

• Jumlah keuntungan dan kerugian:• Zero-sum Game/ Constant-Sum Game; jumlah

kerugian dan keuntungan dari permainannya adalah nol

• Non Zero-sum Game; jumlah kerugian dan keuntungan dari permainannya bukan nol

Klasifikasi Model Game Theory

• Jadi, TWO PERSON ZERO SUM; sebuah permainan dengan dua pemain, dimana keuntungan satu pemain sama dengan kerugian pemain lainnya.

• Contoh dari N-person Non Zero-sum Game; sejumlah perusahaan melakukan kampanye advertensi yang intensif untuk memperoleh daerah pemasaran yang lebih besar.

ELEMEN – ELEMEN DASAR TEORI PERMAINAN

Persoalan two-person zero-sum game

Perhatikan matriks payoff berikut ini!



menyatakan outcome atau pembayaran dari strategi permainan yang berbeda



bilangan-bilangan positif ini menyatakan perolehan keuntungan bagi pihak yang ditulis pada baris sebagai pemain yang akan

memaksimumkan, dan sekaligus merupakan kerugian bagi pihak yang ditulis pada kolom sebagai pemain yang akan

meminimumkan

Strategi

• Strategi adalah tindakan pilihan• Aturan permainan menjelaskan tentang

bagaimana cara para pemain memilih strategi-strategi mereka

• Suatu strategi dinyatakan dominan apabila payoff yang ada pada suatu strategi bersifat superior (paling tinggi) dibandingkan dengan setiap payoff pada strategi lainnya

• Nilai permainan menyatakan ekspetasi outcome per permainan jika kedua pemain melakukan strategi terbaik (strategi optimum) mereka.

Strategi

• Strategi optimum adalah strategi yang menjadikan seorang pemain berada pada posisi pilihan terbaik, tanpa memperhatikan tindakan-tindakan pemain lawan.

• Tujuan model permainan adalah untuk mengidentifikasi strategi optimum bagi masing-masing pemain

TWO–PERSON, ZERO–SUM GAME

PURE – STRATEGY GAME

Permainan yang posisi pilihan terbaiknya bagi setiap pemain dicapai dengan memilih satu strategi tunggal

(strategi murni)


Pemain A yang akan memaksimumkan akan mengidentifikasi strategi

optimumya dengan menggunakan criteria maksimin, sedangkan pemain B

yang akan meminimumkan akan mengidentifikasi strategi optimumnya

dengan menggunakan criteria minimaks.


• Jika nilai maksimin = minimaks maka permainan selesai (disebut saddle point)

• Jika maksimin ≠minimaks permainan harus diselesaikan dengan strategi campuran (mixed-strategy game)


Contoh: Dua buah perusahaan sedang dlm proses perencanaan strategi advertensi masing-masing.

Struktur strategi dan payoff-nya sebagai berikut:

PERUSAHAAN B

B1 B2 B3

Perusahaan

A

A1 1 9 2

A2 8 5 4

Carilah nilai permainan dan strateginya!


Jawab: cari nilai maksiminnya dan minimaksnya.Struktur strategi dan payoff-nya sbb:

Minimaks = maksimin,

Jadi strategi optimum bagi A adalah A2 dan strategi untuk B adalah B3, dengan nilai permainan 4.

Perusahaan B Minimum

BarisB1 B2 B3

Perusahaan

A

A1 1 9 2 1

A2 8 5 4* 4 maksimin

Maksimum

Kolom

8 9 4

minimaks

MIXED – STRATEGY GAME

Pada game yang tidak mempunyai saddle point, penyelesaiannya harus

dilakukan dengan menggunakan strategi campuran.


Perhatikan matriks payoff dari suatu game berikut ini:

Perusahaan B

B1 B2 B3

Perusahaan

A

1 0 -2 2

2 5 4 -3

3 2 3 -4


Struktur strategi dan payoff-nya sbb:

maksimin ≠ nilai minimaks, maka permainan di atas tidak mempunyai saddle point

Perusahaan B Minimum

barisB1 B2 B3

Perusahaan

A

1 0 -2 2 -2 <MAKSIMIN

2 5 4 -3 -3

3 2 3 -4 -4

Maksimum

Kolom

5 4 2

MINIMAKS


• pada permainan yang tidak mempunyai saddle point ini para pemain dapat memainkan seluruh strateginya sesuai dengan set probabilitas yang telah ditetapkan.

Xi = probabilitas pemain A memilih strategi i (i = 1,2,…,m)

Yi = probabilitas pemain B memilih strategi j (j = 1,2,…,n)

∑ xi = ∑ xj = 1

X1, Yj ≥ 0 untuk setiap I dan j


Dalam bentuk matriks:

Solusi persoalan strategi campuran ini masih didasarkan pada kriteria maksimin dan minimaks.

B

Y1 Y2 ……... Yn

A

X1 a11 a12 a1n

X2 a21 a22 a2n

. . . .

. . . .

. . . .

Xm am1 am2 amn


• Secara matematis:• Pemain A akan memilih :

xi (xi ≥ 0, ∑ xi = 1) yang menghasilkan:

v_ = maks xi {min (∑a11 xi , ∑ a12xi,……., ∑ ainxi)}• Pemain B akan memilih :

yj (yj ≥ 0, ∑ yj = 1) yang menghasilkan:

v- = min yj {maks (∑a1j yj , ∑ a2jyj,……., ∑ amjyj)}


• Jika xi dan yj berkorespondensi dgn solusi optimum maka v_ = v-

• Jika xi* dan yj* =solusi optimum maka ekspektasi optimum dari permainan:v* = , ∑ ∑ aij xi*yj*

• Mixed strategy game dpt diselesaikan dgn cara grafis dan dgn menggunakan program linier.

SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)

• Syarat penggunaan: salah seorang dari pemain hanya mempunyai 2 buah strategi.

B

Y1 Y2 ……... Yn

AX1 a11 a12 a1n

X2=1-X1 a21 a22 a2n


• Berdasarkan strategi murni dari B, maka ekspektasi payoff untuk A adalah:

Strategi

murni B

Ekspektasi payoff A

1 (a11-a21)X1+a21

2 (a12-a22)X1+a22

. .

N (a1n-a2n)X1+a2n


• Berdasarkan kriteria minimaks untuk permainan dengan strategi campuran, pemain A harus memilih nilai X1 yang akan memaksimumkan ekspetasi payoff minimumnya. Hal ini dpt dicari dgn cara menggambarkan fungsi-fungsi X1.


matriks payoff:

Carilah nilai permainan ini dan strateginya.

Contoh:


Berdasarkan strategi murni dari B, maka ekspektasi payoff untuk A adalah:

Jawab

Strategi

murni B

Ekspektasi

payoff A

1 -5 X1+ 5

2 -6 X1+ 4

3 5 X1+ -3


Jawab

-

-

-

-

-

-

-

-

-3

4

5

0maksimin

1 x1

Ekspektasi payoff

-

-

-

-

-

-

-2

2

3

1

-1

-

-


Maksimim ekspetasi payoff V = maks xi { min (5 – 5x1), (4 – 6x1), (-3 + 5x1) }

V = maks xi { min (4 – 6x1), (-3 + 5x1) }

Jawab


• Titik potong dicari secara aljabar biasa:4 – 6x1 = -3 + 5x1

11x1 = 7

X1* = 7/11

Karena x1* + x2* = 1, maka x2* = 4/11

Jawab


• Mencari koordinat Y:v = v* = -3 + 5(7/11) = 2/11

v* = dan v* = ∑∑aijxiyj.

sehingga: y1*(5-5x1) + y2*(4-6x1) + y3*(-3+5x1) = 2/11

20/11y1* + 2/11 y2* + 2/11 y3* = 2/11

dengan y1* + y2* + y3* = 1

Jawab


Dalam hal ini, persamaan ∑ aij xi yang tidak melewati titik maksimim berkorespondensi dengan yj* = 0 (supaya tidak menaikkan expected payoff); karena itu, y1* = 0 sehingga y2* + y3* = 1 atau y3* = 1- y2* masukan pada persamaan (1), didapat:

jika x1 = 0 4y2* - 3y3* = 2/11 ; x1

x1 = 1 -2y2* + 2y3* = 2/11 ; x2

sehingga di dapat: y3* = 6/11

y2* = 5/11

Jawab


Dengan demikian, maka solusi optimum untuk kedua pemain adalah:

Pemain A: (x1, x2) = (7/11, 4/11)

Pemain B: (y1,y2,y3) = (0, 5/11, 6/11)

dengan nilai game v* = 2/11

Jawab

SOLUSI PROGRAM LINIER PERMAINAN (m x n)

Seperti dikemukakan di muka, kriteria maksimim dapat di formulasikan sebagai

Maks {min i1 xi, i2, …, in xi }

Dimana I = 1 dan xi ≥ 0 i = 1, …, m

Jika v = min ( i1 xi, i2 xi, …, in )


Matriks payoff dari suatu permainan sebagai berikut:

Tentukanlah strategi optimum untuk masing-masing pemain!

Contoh:

B

1 2 3

1 3 -1 -3

A 2 -3 3 -1

3 -4 -3 3


Dari matriks payoff di atas kita tahu bahwa nilai maksiminnya adalah -3 sehingga nilai permainannya dapat berharga negative atau nol.

Karena itu, diperlukan suatu konstanta k yang harganya paling sedikit sama dengan nilai maksimin yang negative itu.

Konstanta k itu kemudian ditambahkan kepada seluruh elemen matriks.

Jawab:


Misalnya digunakan K = 5, maka matriksnya menjadi:

Jawab:

B

1 2 3

1 8 4 2

A 2 2 8 4

3 1 2 8


Formulasi program linier untuk pemain B adalah:

Maks. W = Y1 + Y2 + Y3

s/t 8Y1 + 4Y2 + 2Y3 ≤ 1

2Y1 + 8Y2 + 4Y3 ≤ 1

Y1 + 2Y2 + 8Y3 ≤ 1

Y1, Y2, Y3 ≥ 0

Jawab:


Setelah formulasi di atas diselesaikan dengan metode simpleks, maka didapat tabel optimum sebagai berikut:

Jawab:

Basis Y1 Y2 Y3 S1 S2 S3 solusi

W 0 0 0 5/49 11/196 1/14 45/196

Y1

Y2

Y3

1 0 0 1/7 -1/14 O

0 1 0 -3/196 31/196 -1/14

0 0 1 -1/98 -3/98 1/7

1/14

11/196

5/49


Strategi optimum untuk pemain A diperoleh dari solusi dual persoalan di atas, maka:

Z = w = 45/196, X1 = 5/49, X2 = 11/196, X3 = 11/45

Sehingga:

X1* = X1/z = 20/45

X2* = X2/z = 11/45

X3* = X3/z = 14/45

Jawab:

LATIHAN SOAL

Soal 1.

Diketahui matriks payoff sebagai berikut:

Carilah nilai permainan ini dan strateginya!

B

1 2 3

A1 2 -3 -4

2 -6 -1 1

Soal 2.

Pertimbangkan permainan (2x4) berikut ini.

Carilah nilai permainan A dan B!

B

1 2 3 4

A1 2 2 3 -1

2 4 3 2 6

Download - Game Theory

Top Related