Mencari Ekuilibrium Nash dan Sekuensial dari Permainan Bentuk Ekstensif Dua Pemain Berjumlah Nol

MAURI ERICSON SOMBOWADILE, Prof. Dr. Salmah, M.Si.

2018 | Skripsi | S1 MATEMATIKA

Permainan bentuk ekstensif adalah formalisasi matematis dari suatu permainan diskrit (seperti catur, poker, dsb.). Definisinya diperluas dari definisi standar dalam literatur, sehingga grafnya tidak harus berupa pohon. Untuk membawanya ke bentuk familiar permainan yang grafnya berupa pohon, didefinisikan unravelling dan perfect-recall unravelling dari suatu permainan. Teorema Kuhn dibuktikan tetap berlaku untuk definisi permainan yang lebih luas ini. Ekuilibrium Nash dan sekuensial didefinisikan, dan untuk kasus permainan terdiri atas dua pemain dan berjumlah nol, program linear yang berkorespondensi dengan pencarian kedua ekuilibrium ini dibentuk. Dalam proses itu, didefinisikan pula bentuk normal dan bentuk barisan suatu permainan bentuk ekstensif. Sebelum dibentuknya program linear, suatu permainan dapat disederhanakan terlebih dahulu. Dibahas eliminasi strategi-strategi terdominasi dari suatu permainan strategis dan kaitannya dengan rationalizability. Selain itu, didefinisikan suatu versi diperumum dari induksi mundur, yang bekerja untuk permainan ekstensif baik yang perfect-information maupun yang tidak. Dibuktikan bahwa induksi mundur versi ini mempertahankan semua ekuilibrium sekuensial dari semua permainan bentuk ekstensif.

An extensive-form game is a mathematical formalization of a discrete game (such as chess, poker, etc.). Its definition is generalized from the standard definition in literature, to a version in which its graph is not required to be a tree. To convert a game to the familiar form where its graph is a tree, the unravelling and perfect-recall unravelling of a game are defined. Kuhn�¢ï¿½ï¿½s theorem is proved to still hold for this generalized definition of a game. Nash and sequential equilibria are defined, and for the case where the game is two-player and zero-sum, the linear programs corresponding to finding both kinds of equilibria are formed. In this process, the normal and sequence form of an extensive-form game are defined. Before forming a linear program, a game can first be simplified. The elimination of dominated strategies of a strategic-form game, and its correspondence to the notion of rationalizability, are discussed. In addition, a generalized version of backward induction, that works both for extensive-form games that are perfect-information and those that are not, is defined. It is then proved that this version of backward induction preserves all sequential equilibria of any extensive-form game.

Kata Kunci : permainan bentuk ekstensif, ekuilibrium sekuensial, rationalizability, teorema Kuhn, induksi mundur