TEORI GAME

Permainan bentuk ekstensif

Dalam teori

permainan , permainan

bentuk

ekstensif adalah

spesifikasi permainan yang memungkinkan (seperti namanya) untuk representasi
eksplisit dari sejumlah aspek kunci, seperti urutan gerakan pemain yang
mungkin, pilihan mereka di setiap titik keputusan , (mungkin tidak sempurna )
informasi yang dimiliki setiap pemain tentang gerakan pemain lain saat mereka
membuat keputusan, dan pembayaran mereka untuk semua kemungkinan hasil
permainan. Permainan bentuk ekstensif juga memungkinkan representasi informasi
yang tidak lengkap dalam bentuk peristiwa kebetulan yang dimodelkan sebagai
" gerakan alami ". Representasi bentuk ekstensif berbeda dari bentuk normalkarena
mereka memberikan deskripsi yang lebih lengkap tentang permainan yang dimaksud,
sedangkan bentuk normal hanya meringkas permainan menjadi matriks pembayaran.

Game bentuk ekstensif terbatas

Beberapa penulis, khususnya dalam buku teks pengantar, pada awalnya
mendefinisikan permainan bentuk ekstensif hanya sebagai pohon permainan dengan
imbalan (tidak ada informasi yang tidak sempurna atau tidak lengkap), dan
menambahkan

unsur-unsur

lain

di

bab-bab

selanjutnya

sebagai

penyempurnaan. Sedangkan sisa artikel ini mengikuti pendekatan lembut ini dengan
contoh-contoh yang memotivasi, kami menyajikan di depan permainan bentuk
ekstensif yang terbatas seperti (pada akhirnya) dibangun di sini. Definisi umum ini
diperkenalkan oleh Harold W. Kuhn pada tahun 1953, yang memperluas definisi von
Neumann yang lebih awal dari tahun 1928. Mengikuti presentasi dari Hart (1992) ,
permainan bentuk ekstensif n -pemain terdiri dari yang berikut:

•Himpunan terbatas n (rasional) pemain

•Pohon berakar , disebut pohon permainan

•Setiap node terminal (daun) dari pohon permainan memiliki n -
Tuple of payoffs , artinya ada satu hasil untuk setiap pemain di akhir setiap
kemungkinan permainan

•Partisi node non-terminal dari pohon permainan di subset n +1, satu untuk
setiap pemain (rasional), dan dengan subset khusus untuk pemain fiktif
yang disebut Peluang (atau Alam) . Subset node setiap pemain disebut
sebagai "node pemain". (Dengan demikian, sebuah permainan dengan
informasi yang lengkap memiliki satu set simpul Kesempatan yang kosong.)

•Setiap node pemain Chance memiliki distribusi probabilitas di tepi
keluarnya.

•Setiap

kumpulan

node

pemain

rasional

selanjutnya

dipartisi

dalam kumpulan informasi , yang membuat pilihan tertentu tidak dapat
dibedakan oleh pemain saat bergerak, dalam arti bahwa:

oada korespondensi satu-ke-satu antara tepi keluar dari dua node

mana pun dari kumpulan informasi yang sama — sehingga
himpunan semua tepi keluar dari kumpulan informasi dipartisi
dalam

kelas-kelas

ekivalensi,

setiap

kelas

mewakili

kemungkinan pilihan untuk langkah pemain di beberapa titik—,
dan

osetiap jalur (diarahkan) di pohon dari akar ke simpul terminal

dapat melewati setiap kumpulan informasi paling banyak satu
kali

•deskripsi lengkap dari permainan yang ditentukan oleh parameter di atas
adalah pengetahuan umum di antara para pemain

Dengan demikian, sebuah permainan adalah jalur melalui pohon dari akar ke simpul
terminal. Pada setiap node non-terminal milik Peluang, cabang keluar dipilih sesuai
dengan distribusi probabilitas. Pada node pemain rasional mana pun, pemain harus
memilih salah satu kelas kesetaraan untuk sisi-sisinya, yang menentukan dengan
tepat satu sisi keluar kecuali (secara umum) pemain tidak tahu mana yang sedang
diikuti. (Pengamat luar yang mengetahui pilihan setiap pemain lain hingga saat itu,
dan realisasi gerakan Alam, dapat menentukan keunggulan dengan tepat.) Oleh
karena itu, strategi murni untuk pemain terdiri dari pemilihan — memilih dengan tepat
satu kelas tepi keluar untuk setiap informasi mengatur (miliknya). Dalam permainan
informasi sempurna, kumpulan informasinya adalahlajang . Kurang jelas bagaimana
imbalan harus ditafsirkan dalam game dengan simpul Peluang. Diasumsikan bahwa
setiap pemain memiliki fungsi utilitas von Neumann–Morgenstern yang ditentukan
untuk setiap hasil pertandingan; asumsi ini mensyaratkan setiap pemain rasional akan
mengevaluasi hasil acak apriori dengan utilitas yang diharapkan .

Presentasi di atas, meskipun secara tepat mendefinisikan struktur matematis tempat
permainan dimainkan, namun mengecualikan diskusi yang lebih teknis tentang
pernyataan formalisasi tentang bagaimana permainan dimainkan seperti "seorang
pemain tidak dapat membedakan antara node dalam kumpulan informasi yang sama
saat membuat keputusan" . Ini dapat dibuat tepat menggunakan logika modal
epistemik ; lihat Shoham & Leyton-Brown (2009 , bab 13) untuk detailnya.

Gim dua pemain informasi sempurna di atas pohon gim (sebagaimana didefinisikan
dalam teori gim kombinatorial dan kecerdasan buatan ) dapat direpresentasikan
sebagai gim bentuk ekstensif dengan hasil (yaitu menang, kalah, atau seri ). Contoh
permainan tersebut termasuk tic-tac-toe , catur , dan catur tak terbatas . [1] [2] Gim di
atas pohon expectminimax , seperti gim backgammon , tidak memiliki informasi yang
tidak sempurna (semua kumpulan informasi adalah lajang) tetapi memiliki pergerakan
peluang. Misalnya, pokermemiliki gerakan peluang (kartu yang dibagikan) dan
informasi yang tidak sempurna (kartu yang diam-diam dipegang oleh pemain
lain). ( Binmore 2007 , chpt.2)

Informasi yang sempurna dan lengkap

Representasi bentuk ekstensif lengkap menentukan:

1. para pemain suatu permainan
2. untuk setiap pemain setiap kesempatan mereka harus bergerak
3. apa yang dapat dilakukan setiap pemain di setiap gerakan mereka
4. apa yang diketahui setiap pemain untuk setiap gerakan
5. imbalan yang diterima oleh setiap pemain untuk setiap kemungkinan

kombinasi gerakan

Gim yang direpresentasikan dalam bentuk ekstensif

Gim di sebelah kanan memiliki dua pemain: 1 dan 2. Angka-angka dari setiap node
non-terminal menunjukkan pemain mana yang dimiliki oleh node keputusan
tersebut. Angka-angka dari setiap simpul terminal mewakili imbalan kepada para
pemain (misalnya 2,1 mewakili imbalan 2 kepada pemain 1 dan imbalan 1 kepada
pemain 2). Label pada setiap tepi grafik adalah nama tindakan yang diwakili oleh tepi.

Node awal milik pemain 1, menunjukkan bahwa pemain 1 bergerak lebih dulu. Cara
bermain

menurut

pohon

adalah

sebagai

berikut:

pemain

1 memilih

antara U dan D ; pemain 2 mengamati pilihan pemain 1 dan kemudian memilih
antara U' dan D' . Imbalannya seperti yang ditentukan di pohon. Ada empat hasil yang
diwakili oleh empat node terminal pohon: (U,U'), (U,D'), (D,U') dan (D,D'). Imbalan
yang terkait dengan masing-masing hasil adalah sebagai berikut (0,0), (2,1), (1,2) dan
(3,1).

Jika pemain 1 memainkan D , pemain 2 akan memainkan U' untuk memaksimalkan
pembayarannya dan pemain 1 hanya akan menerima 1. Namun, jika pemain 1
memainkan U , pemain

2 memaksimalkan

pembayarannya

dengan

memainkan D' dan pemain 1 menerima 2. Pemain 1 lebih suka 2 ke 1 dan begitu juga
akan memainkan U dan pemain 2 akan memainkan D' . Ini adalah keseimbangan
sempurna subgame .

Informasi yang tidak sempurna

Keuntungan merepresentasikan permainan dengan cara ini adalah jelas urutan
permainannya. Pohon itu menunjukkan dengan jelas bahwa pemain 1 bergerak lebih
dulu dan pemain 2 mengamati gerakan ini. Namun, di beberapa permainan tidak
terjadi permainan seperti ini. Satu pemain tidak selalu mengamati pilihan yang lain
(misalnya,

gerakan

mungkin

simultan

atau

gerakan

mungkin

tersembunyi). Himpunan informasi adalah himpunan simpul keputusan sedemikian
rupa sehingga:

1. Setiap node di set milik satu pemain.
2. Saat permainan mencapai kumpulan informasi, pemain yang akan

bergerak tidak dapat membedakan antara node dalam kumpulan
informasi; yaitu jika kumpulan informasi berisi lebih dari satu simpul,
pemain yang memiliki kumpulan tersebut tidak mengetahui simpul mana
dalam kumpulan tersebut yang telah dicapai.

Dalam bentuk ekstensif, kumpulan informasi ditunjukkan dengan garis putus-putus
yang menghubungkan semua simpul di kumpulan itu atau kadang-kadang dengan
lingkaran yang ditarik di sekitar semua simpul di kumpulan itu.

Gim dengan informasi tidak sempurna yang direpresentasikan dalam bentuk ekstensif

Jika sebuah game memiliki kumpulan informasi dengan lebih dari satu anggota, game
tersebut

dikatakan

memiliki informasi

yang

tidak

sempurna . Gim

dengan informasi sempurna sedemikian rupa sehingga pada setiap tahap gim,
setiap pemain tahu persis apa yang terjadi di awal gim; yaitu setiap kumpulan
informasi adalah kumpulan tunggal . [1] [2] Game apa pun tanpa informasi sempurna
memiliki informasi yang tidak sempurna.

Permainan di sebelah kanan sama dengan permainan di atas hanya saja pemain 2
tidak mengetahui apa yang dilakukan pemain 1 ketika mereka datang untuk
bermain. Game

pertama

yang

dijelaskan

memiliki

informasi

yang

sempurna; permainan di sebelah kanan tidak. Jika kedua pemain itu rasional dan
keduanya tahu bahwa kedua pemain itu rasional dan segala sesuatu yang diketahui
oleh pemain mana pun diketahui diketahui oleh setiap pemain (yaitu pemain 1 tahu

pemain 2 tahu bahwa pemain 1 rasional dan pemain 2 tahu ini, dst. ad infinitum ),
bermain di game pertama adalah sebagai berikut: pemain 1 tahu bahwa jika mereka
bermain U , pemain 2 akan memainkan D' (karena untuk pemain 2 pembayaran 1
lebih disukai daripada pembayaran 0) dan begitu juga pemain 1 akan menerima 2.
Namun, jika pemain 1 memainkan D , pemain 2 akan memainkan U'(karena untuk
pemain 2 pembayaran 2 lebih baik daripada pembayaran 1) dan pemain 1 akan
menerima 1. Oleh karena itu, pada game pertama, keseimbangannya adalah ( U , D' )
karena pemain 1 lebih suka menerima 2 banding 1 dan begitu juga akan
memainkan U dan pemain 2 akan memainkan D' .

Di game kedua kurang jelas: pemain 2 tidak bisa mengamati gerakan pemain
1. Pemain 1 ingin membodohi pemain 2 dengan berpikir mereka telah
memainkan U ketika mereka benar-benar memainkan D sehingga pemain 2 akan
memainkan D ' dan pemain 1 akan menerima 3. Sebenarnya di game kedua
ada keseimbangan Bayesian yang sempurna dimana pemain 1 memainkan D dan
pemain 2 memainkan U' dan pemain 2 percaya bahwa pemain 1 pasti akan
memainkan D . Dalam ekuilibrium ini, setiap strategi bersifat rasional mengingat
keyakinan yang dianut dan setiap keyakinan konsisten dengan strategi yang
dimainkan. Perhatikan bagaimana ketidaksempurnaan informasi mengubah hasil
pertandingan.

Untuk

lebih

mudah

menyelesaikan

permainan

ini untuk kesetimbangan

Nash , [3] dapat

diubah

menjadi bentuk

normal . [4] Mengingat

ini adalah

permainan simultan / berurutan , pemain satu dan pemain dua masing-masing
memiliki dua strategi . [5]

•Strategi Pemain 1: {U , D}

•Strategi Pemain 2: {U' , D'}

Pemain 2

Pemain 1

Naik' (U') Bawah' (D')

Atas (U)

(0,0)

(2, 1 )

Bawah (D) ( 1 , 2 )( 3 ,1)

Kami akan memiliki matriks dua kali dua dengan hasil unik untuk setiap kombinasi
gerakan. Dengan menggunakan permainan bentuk normal, sekarang dimungkinkan
untuk memecahkan permainan dan mengidentifikasi strategi dominan untuk kedua
pemain.

•Jika pemain 1 bermain Atas (U), pemain 2 lebih suka bermain Bawah (D')
(Hasil 1>0)

•Jika pemain 1 bermain Bawah (D), pemain 2 lebih suka bermain Atas (U')
(Hasil 2>1)

•Jika pemain 2 bermain Atas (U'), pemain 1 lebih suka bermain Bawah (D)
(Hasil 1>0)

•Jika pemain 2 bermain Bawah (D'), pemain 1 lebih memilih bermain Bawah
(D) (3>2)

Preferensi ini dapat ditandai di dalam matriks, dan setiap kotak di mana kedua pemain
memiliki preferensi memberikan keseimbangan nash. Permainan khusus ini memiliki
solusi tunggal (D,U') dengan hasil (1,2).

Dalam game dengan ruang aksi tak terbatas dan informasi tidak sempurna, kumpulan
informasi non-tunggal direpresentasikan, jika perlu, dengan menyisipkan garis putus-
putus yang menghubungkan titik akhir (non-nodal) di belakang busur yang dijelaskan
di atas

atau

dengan

menghancurkan

busur

itu sendiri. Dalam kompetisi

Stackelberg yang dijelaskan di atas, jika pemain kedua tidak mengamati gerakan
pemain pertama, permainan tidak lagi sesuai dengan model Stackelberg; itu akan
menjadi kompetisi Conot .

Informasi tidak lengkap

Mungkin seorang pemain tidak tahu persis apa hadiah dari permainan itu atau jenis
apa lawan mereka. Game

semacam

ini

memiliki informasi

yang

tidak

lengkap . Dalam bentuk ekstensif direpresentasikan sebagai permainan dengan
informasi yang lengkap tetapi tidak sempurna dengan menggunakan apa yang
disebut transformasi Harsanyi . Transformasi ini memperkenalkan pada permainan
gagasan tentang pilihan alam atau pilihan Tuhan. Pertimbangkan permainan yang
terdiri dari pemberi kerja yang mempertimbangkan apakah akan mempekerjakan
pelamar kerja. Kemampuan pelamar kerja mungkin salah satu dari dua hal: tinggi atau
rendah. Tingkat kemampuan mereka acak; mereka memiliki kemampuan rendah
dengan probabilitas 1/3 atau kemampuan tinggi dengan probabilitas 2/3. Dalam hal
ini, akan lebih mudah untuk memodelkan alam sebagai pemain lain yang memilih
kemampuan pelamar berdasarkan probabilitas tersebut. Namun alam tidak memiliki
imbalan apa pun. Pilihan alam diwakili dalam pohon permainan oleh simpul yang tidak
terisi. Tepi yang berasal dari simpul pilihan alam diberi label dengan probabilitas
kejadian yang diwakilinya.

Gim dengan informasi yang tidak lengkap dan tidak sempurna direpresentasikan dalam bentuk ekstensif

Permainan di sebelah kiri adalah salah satu informasi yang lengkap (semua pemain
dan hadiah diketahui semua orang) tetapi informasi yang tidak sempurna (majikan
tidak tahu gerakan alam apa itu.) Node awal ada di tengah dan tidak diisi , jadi alam
bergerak lebih dulu. Alam memilih dengan probabilitas yang sama tipe pemain 1 (yang
dalam permainan ini sama saja dengan memilih imbalan dalam subgame yang
dimainkan), baik t1 atau t2. Pemain 1 memiliki kumpulan informasi berbeda untuk
ini; yaitu pemain 1 mengetahui tipe mereka (ini tidak perlu terjadi). Namun, pemain 2
tidak memperhatikan pilihan alam. Mereka tidak mengetahui tipe pemain 1; namun,
dalam game ini mereka mengamati tindakan pemain 1; yaitu ada informasi yang
sempurna. Memang, sekarang tepat untuk mengubah definisi informasi lengkap di
atas: pada setiap tahap dalam permainan,oleh para pemain lainnya . Dalam hal
informasi

pribadi,

setiap

pemain

mengetahui

apa

yang

dimainkan

oleh

alam. Kumpulan informasi direpresentasikan seperti sebelumnya dengan garis putus-
putus.

Dalam game ini, jika alam memilih t1 sebagai tipe pemain 1, game yang dimainkan
akan seperti game pertama yang dijelaskan, kecuali bahwa pemain 2 tidak
mengetahuinya

(dan

fakta

bahwa

ini memotong

set informasi

mereka

mendiskualifikasi dari status subgame ). Ada satu yang memisahkan kesetimbangan
Bayesian sempurna ; yaitu keseimbangan di mana jenis yang berbeda melakukan hal
yang berbeda.

Jika kedua jenis memainkan aksi yang sama (pooling), ekuilibrium tidak dapat
dipertahankan. Jika keduanya bermain D , pemain 2 hanya dapat membentuk
keyakinan bahwa mereka berada di salah satu simpul dalam kumpulan informasi
dengan probabilitas 1/2 (karena ini adalah peluang untuk melihat salah satu
jenis). Pemain 2 memaksimalkan hasil mereka dengan memainkan D' . Namun, jika
mereka memainkan D' , tipe 2 lebih memilih untuk memainkan U . Ini tidak bisa
menjadi keseimbangan. Jika kedua jenis memainkan U , pemain 2 kembali
membentuk keyakinan bahwa mereka berada di salah satu simpul dengan probabilitas
1/2. Dalam hal ini pemain 2 memainkan D' , tetapi tipe 1 lebih memilih untuk
memainkan D .

Jika

tipe

1 memainkan U dan

tipe

2 memainkan D , pemain

2 akan

memainkan D' tindakan apa pun yang mereka amati, tetapi tipe 1 lebih
memilih D . Maka satu-satunya keseimbangan adalah dengan tipe 1 bermain D , tipe
2 bermain U dan pemain 2 bermain U' jika mereka mengamati D dan mengacak jika
mereka mengamati U . Melalui tindakan mereka, pemain 1 telah memberi isyarat tipe
mereka kepada pemain 2.

Definisi formal

Ruang aksi tak terbatas

Mungkin saja seorang pemain memiliki kemungkinan tindakan yang tak terbatas untuk
dipilih pada simpul keputusan tertentu. Perangkat yang digunakan untuk mewakili ini
adalah busur yang menghubungkan dua sisi yang menonjol dari simpul keputusan
yang dimaksud. Jika ruang aksi adalah kontinum antara dua angka, angka pembatas
bawah dan atas masing-masing ditempatkan di bagian bawah dan atas busur,
biasanya dengan variabel yang digunakan untuk menyatakan hasil. Jumlah simpul
keputusan tak terbatas yang dapat dihasilkan diwakili oleh satu simpul yang
ditempatkan di tengah busur. Perangkat serupa digunakan untuk merepresentasikan
ruang aksi yang, meski tidak terbatas, cukup besar untuk terbukti tidak praktis untuk
direpresentasikan dengan keunggulan untuk setiap aksi.

Gim dengan ruang aksi tak terbatas yang direpresentasikan dalam bentuk luas

Pohon di sebelah kiri mewakili permainan seperti itu, baik dengan ruang aksi tak
terbatas ( bilangan nyata apa pun antara 0 dan 5000) atau dengan ruang aksi yang
sangat besar (mungkin bilangan bulat apa pun antara 0 dan 5000). Ini akan ditentukan
di tempat lain. Di sini, akan dianggap sebagai yang pertama dan, untuk konkretnya,
akan

dianggap

mewakili

dua

perusahaan

yang

terlibat

dalam kompetisi

Stackelberg . Imbalan untuk perusahaan diwakili di sebelah kiri, dengan

Dan

sebagai strategi yang mereka adopsi dan

Dan

sebagai beberapa konstanta

(di sini biaya marjinal untuk setiap perusahaan). Keseimbangan sempurna Nash
subgame dari game ini dapat ditemukan dengan mengambil turunan parsial
pertama dari setiap fungsi pembayaran sehubungan dengan variabel strategi

pengikut (perusahaan 2) (

) dan menemukan fungsi respons terbaiknya ,

. Proses yang sama dapat dilakukan untuk pemimpin kecuali bahwa dalam
menghitung keuntungannya, ia mengetahui bahwa perusahaan 2 akan memainkan
respons

di atas

sehingga

ini dapat

disubstitusikan

ke dalam

masalah

maksimisasinya. Ini kemudian dapat dipecahkan

dengan mengambil turunan

pertama, menghasilkan

. Memasukkan ini ke dalam fungsi respons terbaik

perusahaan 2,

Dan

adalah kesetimbangan Nash sempurna subgame.