## Syarat Perlu dan Cukup Eksistensi Solusi Permainan Dinamis Dua Orang Berjumlah Nol dengan Ketidakpastian

## Muhammad Wakhid Musthofa
Program Studi Matematika Fakultas Sains dan Teknologi UIN sunan Kalijaga Yogyakarta, Indonesia.
Korespondensi; Muhammad Wakhid Musthofa, Email: mwakhid_m@yahoo.com

## Abstrak
Artikel ini akan membahas penurunan syarat perlu dan syarat cukup agar permainan dinamis linear kuadratis dua pemain berjumlah nol dengan kehadiran ketidakpastian pada sistem mempunyai strategi optimal robust sebagai solusi  optimalnya.  Ide  untuk  menyelesaikannya  adalah  dengan  mendefinisikan  dua  buah  permainan  dinamis sedemikian sehingga ketidakpastian pada sistem hanya terjadi untuk salah satu pemainnya saja.
Kata Kunci permainan dinamis linear kuadratis; ketidakpastian pada sistem; solusi optimal robust

## Abstract
This article will discuss the reduction of the necessary and sufficient conditions so that the quadratic linear dynamic game of two players totals zero with the presence of uncertainty in the system having an optimal robust strategy as the optimal solution. The idea to solve this is to define two dynamic games so that uncertainty in the system only occurs for one of the players.
Keywords quadratic linear dynamic game; uncertainty in the system; Robust optimal solution.

## Pendahuluan
Permainan dinamis adalah bagian dari pemodelan matematika yang menggambarkan situasi persaingan antar pihak yang dibingkai dalam suatu sistem dinamik. Pihak yang bersaing dapat berupa perusahaan, negara, institusi pemerintahan maupun individu (Haurie et al 2012, Basar dan Olsder 1999). Masing- masing  pihak  berusaha  untuk  merealisasikan  tujuannya  dengan  menentukan  strategi  terbaik  dengan bentuk  mengendalikan  sistem  dinamiknya.  Dalam  model  matematika,  permainan  dinamis  disajikan dalam bentuk pasangan persamaan sistem dinamik dan fungsi biaya. Jika sistem dinamiknya berupa sistem linear dan fungsi biayanya berupa fungsi kuadratik maka permainan dinamisnya disebut bertipe linear  kuadratik  (Engwerda,  2005).  Aplikasi  dari  permainan  dinamis  dapat  dijumpai  dalam  masalah ekonomi, pemasaran produk, manajemen resiko, manajemen lingkungan dan persaingan senjata antar negara (Dockner et al 2000, Jorgensen dan Zaccour 2004).
Permainan dinamis yang dibahas dalam artikel ini adalah permainan dinamis dua pemain berjumlah nol  ( two-person  zero-sum  game)  yang  bertipe  linear  kuadratik  yang  mengakomodasi  keberadaan ketidakpastian pada sistem dinamiknya. Ketidakpastian ( uncertainty) adalah suatu hal yang hampir pasti dialami oleh semua sistem. Ketidakpastian pada sistem dapat berasal dari gangguan eksternal sistem ( disturbance), penyederhanaan sistem, dan dinamisasi sistem yang terus menerus berubah-ubah terhadap waktu  (Kaynak  dan  Denker  2010,  Zhou  dan  Doyle  1998).  Kehadiran  ketidakpastian  pada  sistem membuat  para  pemain  tidak  dapat  menggunakan  strategi  biasa,  dikarenakan  matriks-matriks  yang terlibat dalam sistem tidak dapat diketahui dengan pasti nilai eksaknya. Sebagai gantinya, para pemain harus menggunakan strategi robust. Sehingga pencarian strategi robust bagi para pemain merupakan permasalahan utama dalam permainan dinamis dengan ketidakpastian.
Artikel ini akan mencari syarat perlu dan cukup eksistensi strategi optimal robust untuk permainan dinamis dengan ketidakpastian. Dalam rangka mencari strategi optimal tersebut akan didefinisikan dua
buah permainan dinamis dengan ketidakpastian hanya melekat pada salah satu pemain. Selanjutnya, dengan menggunakan hasil dari Ho et al (1965) dapat diturunkan syarat perlu dan cukup eksistensi strategi optimal robust tersebut. van den Broek (2001) juga telah mencari eksistensi strategi optimal robust  yang  disebut  sebagai  robust  equilibria  namun  pada  ketidakpastian  sistem  yang  terbatas  dan menggunakan cara yang berbeda.
Artikel ini disajikan dengan runtutan alur sebagai berikut. Setelah pendahuluan, bagian kedua dari makalah ini menyajikan konsep permainan dinamis pada sistem nominal. Berdasar konsep tersebut, bagian  ketiga  artikel  ini  menyajikan  konsep  permainan  dinamis  dengan  ketidakpastian  sebagai pengembangan dari  konsep sebelumnya.  Pada  bagian  ini  juga disebutkan  permaslahan utama  yang akan diselesaikan dalam artikel ini. Selanjutnya, bagian keempat mengulas ide solusi dari permasalahan yaitu menurunkan syarat perlu dan cukup eksistensi strategi optimal robust untuk permainan dinamis dengan  ketidakpastian.  Teorema  eksistensi  syarat  perlu  dan  cukup  disajikan  pada  bagian    kelima. Terakhir,  bagian  enam  menyimpulkan  isi  artikel  dan  memberikan  masalah  terbuka  bagi  penelitian selanjutnya.

## Permainan Dinamis Sistem Nominal
Diberikan permainan dinamis linear kuadratik dua orang berjumlah nol yang didefinisikan pada suatu sistem dinamik
1 2 X Y Y K          (1)
dengan  sebagai variabel state untuk sistem (1),
1 2 , , , X Y Y K adalah matriks-matiks dengan dimensi yang  bersesuaian,  menyatakan strategi  untuk  pemain  pertama,  adalah  strategi  untuk  pemain kedua,  dan  adalah noise bagi sistem (1). Pemain pertama bertujuan meminimalkan fungsi biaya kuadratik untuk waktu berhingga ( finite time horizon) yang disajikan oleh persamaan
    0 , T T T T T T
L R H H M N dt                      (2)
dengan T H dan H  merupakan  matriks  simetris  dan  definit  nonnegatif,  matriks , M N simetris  dan definit  positif,  dan T  menyatakan  waktu  akhir  dari  sistem  (1).  Sedangkan  pemain  kedua  bertujuan memaksimalkan fungsi biaya (2). Masalah yang ingin diselesaikan adalah mencari pasangan strategi optimal *  dan *  yang mnimimalkan fungsi biaya (2). Solusi dari masalah ini telah disajikan oleh Ho et al (1965) dalam lemma berikut.
Lemma 1.
Strategi  optimal  untuk  permainan dinamis  sistem  nominal  (1)  dengan  fungsin  biaya  (2) berupa  titik sadel ( saddle ponit)
      * 1 1 t M Y A t t      (3a)
      * 1 2 t N Y A t t     , (3b)
dan nilai dari permainan diberikan oleh persamaan
            * * 0 0 0 , 0 tr 0 0 tr T T T L m A m A M A t KC t K dt           dengan 0 T A A   merupakan solusi dari persamaan diferensial Riccati   1 1 1 1 2 2 0; T T T T A AX X A A Y M Y
Y N Y A H A T H              .

## Permainan Dinamis dengan Ketidakpastian
Permainan  dinamis  linear  kuadratis  dua  orang  berjumlah  nol  dengan  mengakomodasi  kehadiran ketidakpastian  pada  sistem  merupakan  modifikasi  dari  permainan  dinamis  sistem  nominal  dengan
menambahkan  variabel  ketidakpastian  pada  sistem  dinamiknya.  Secara  matematis,  permainan  ini didefinisikan pada sistem dinamis
      1 1 2 2
X X Y Y Y Y K                (4)
dengan
1 2 , , X Y Y    merupakan matriks-matriks ketidakpastian yang bergantung waktu pada sistem yang memenuhi
  0 0 0 , X P Q t R     1 1 1 1 , Y PQ t R   dan   2 2 2 2 , Y P Q t R   0, t  
dengan , , 1, 2 i i P R i  adalah matriks-matriks konstan bernilai real yang diketahui dengan dimensi yang sesuai, dan , 1, 2 i Q i  menyatakan parameter ketidakpastian dari sistem yang memenuhi
. T i i Q Q I  (5)
Pemain pertama ingin meminimalkan fungsi biaya kuadratik (2), sedangkan sebaliknya pemain kedua ingin memaksimalkan fungsi biaya tersebut.
Terdapatnya ketidakpastian dalam permainan dinamis (4,2) menyebabkan solusi optimal permainan dalam  bentuk  titik  sadel  sebagaimana  dalam  persamaan  (3)  tidak  dapat  ditemukan.  Untuk menyelesaikan masalah tersebut didefinisikan strategi optimal robust sebagai berikut.
Definisi 1.
Diberikan permainan dinamis yang disertai dengan ketidakpastian pada sistem yang disajikan dengan persamaan  dinamik  (4)  dan  fungsi  biaya  (2).  Suatu  pasangan    strategi   * * ,   untuk  permainan dinamis  (4,2)  disebut  strategi  optimal robust  jika  terdapat  dua  nilai  skalar * L  dan * L  sedemikian sehingga dua buah pertidaksamaan berikut dipenuhi
  * * min ,
L L      ,   * * max , L L      .
Pada permainan dinamis (4,2), jika kedua pemain menggunakan strategi optimal robust   * * ,   maka  untuk  semua state  dan  untuk  suatu  ketidakpastian  yang  diperkenankan  bagi  sistem 1 2 , , X Y Y    , dipenuhi pertidaksamaan berikut
  * * * * , L L L      
dengan * * L L    . Selanjutnya nilai skalar * L  disebut nilai atas permainan dan * L  disebut nilai bawah permainan.
Berdasarkan Definisi 1 di atas, jika pemain pertama menggunakan strategi optimal robust maka ia tidak  akan pernah  menderita kekalahan  melebihi  nilai * L  ,  sedangkan untuk  pemain  kedua  jika  ia menggunakan strategi optimal robust maka ia dapat menjamin pendapatannya tidak kurang dari * L  . Untuk itu, perlu dicari syarat perlu dan syarat cukup eksistensi dari strategi optimal robust sehingga permainan dinamis (4,2) mempunyai penyelesaian optimal.

## Konstruksi 2 Permainan Dinamis
Ide untuk mencari syarat perlu dan syarat cukup eksistensi strategi optimal robust untuk permainan dinamis (4,2) adalah dengan membentuk dua buah permainan dinamis linear kuadratis yang difungsikan sebagai  alat  bantu.  Pembentukan  permainan  dinamis  ini  dimaksudkan  untuk  memecah  keberadaan ketidakpastian pada sistem, yang pada awalnya ketidakpastian muncul pada dua pihak pemain menjadi hanya muncul pada satu pihak pemain saja. Hal tersebut disajikan dengan dua permasalahan permainan dinamis berikut.
Masalah  1.  Permainan  dinamis  antara  pemain  pertama  dengan  strategi  melawan  pemain  kedua dengan strategi   T T     . Berarti, dalam hal ini ketidakpastian hanya terjadi pada strategi untuk pemain kedua saja. Permainan ini dapat disajikan dengan persamaan dinamik
  1 2 X Y Y P K          (6)
dengan   0 1 2 P P P P  dan       0 0 1 1 2 2 Q t R Q t R Q t R      
         . Fungsi biaya untuk permainan dinamis ini diberikan oleh persamaan
   
0 , T T T T T T
L R H H M N dt                          (7)
dengan
2 0 0 0 T H H R R     , 2 1 1 1 T M M R R     , dan
2 2 2 2 2 0 2 1 2 2 0 0 0 0
0 0 0 0 0 0 0 0 T N R R I N I I                      ,
untuk suatu skalar 0, 1, 2 i i    .
Didefinisikan   0 0 0 Q t R    ,   1 1 1 Q t R    ,  dan   2 2 2 Q t R    .  Berdasarkan  Persamaan  (5)
diperoleh
    0 0 0 0 , T T R R          1 1 1 1 , T T R R      dan     2 2 2 2 T T R R      . (8)
Selanjutnya, fungsi biaya (7) dapat disajikan sebagai
                   0 2 2 0 0 0 0 0 1 1 1 1 1 0 2 2 2 2 2 2 , . T T T T T T T T T T T T T L R H H M N dt R R R R R R R dt          
              
 
                                Dikarenakan 0  , 1  , dan 1  memenuhi Persamaan (8) maka persamaan berikut dipenuhi
    , , L L       , (9)
dengan   , L   merupakan nilai dari fungsi biaya (2). Persamaan (9) dapat ditulis sebagai
    , , , L L        . (10)
Berdasarkan Persamaan (10) didapat     max , , max , L L     
    , Dan     max max , , max , L L           . (11)
Persamaan (11) dapat ditulis sebagai     max , , max , L L          . (12)
Jika *  adalah  strategi  optimal  bagi  pemain  pertama  dalam  permainan  dinamis  (6,7),  maka *  mempunyai bentuk (Basar dan Berhard 2000)
  * min max , L       .
Sehingga berdasarkan persamaan (9) dan (12) maka dipenuhi
    * min max , min max , L L L    
        .
Jadi, untuk Masalah 1 di atas, dipenuhi pertidaksamaan
  * * max , L L      ,
untuk semua ketidakpastian yang diperkenankan bagi sistem.
Masalah 2. Permainan dinamis antara pemain pertama dengan strategi   T T     melawan pemain kedua  dengan  strategi  .  Berarti,  dalam  hal  ini  ketidakpastian  hanya  terjadi  pada  strategi  untuk pemain pertama saja. Permainan ini dapat disajikan dengan persamaan dinamik   1 2 X Y P Y K          , (13)
dengan fungsi biaya untuk pemain pertama disajikan oleh persamaan
    0 , T T T T T T
L R H H M N dt                          (14)
dengan 2 0 0 0 T H H R R      , 2 2 2 2 T N N R R      , dan 2 1 1 1 2 0 2 1 2 2 0 0 0 0
0 0
0 0 0 0 0 0 T M R R I M I I             
            untuk suatu skalar 0, 1, 2 i i    .  Fungsi biaya kuadratik (14) dapat ditulis sebagai
                   0 2 2 0 0 0 0 0 1 1 1 1 1 0 2 2 2 2 2 2 , . T T T T T T T T T T T T T L R H H M N dt R R R R R R R dt          
                
                               
Selanjutnya, dikarenakan 0  , 1  , dan 1  memenuhi Persamaan (8) maka persamaan berikut dipenuhi
    , , L L       (15)
dengan   , L   merupakan nilai dari fungsi biaya (2). Persamaan (15) dapat ditulis sebagai
    , , , L L        . (16)
Berdasarkan Persamaan (16) didapat
    min , , min , L L          Dan
    min min , , min , L L           (17) Persamaan (17) dapat ditulis sebagai     min , min , L L         (18)
Jika *  adalah  strategi  optimal  bagi  pemain  kedua  dalam  permainan  dinamis  (13,14),  maka *  mempunyai bentuk (Basar dan Berhard 2000)
  * max min , L       . Sehingga berdasarkan persamaan (15) dan (18) maka dipenuhi
    * max min , max min , L L L    
        .
Jadi, untuk Masalah 2 di atas, dipenuhi pertidaksamaan
  * * min , L L      ,
untuk semua ketidakpastian yang diperkenankan.
Solusi dari Masalah 1 dan Masalah 2 di atas dapat diperoleh dengan menggunakan Lemma 1.

## Syarat Perlu dan Cukup Permainan Dinamis dengan Ketidakpastian
Pada bagian ini akan diturunkan syarat perlu dan syarat cukup eksistensi strategi optimal robust sebagai solusi  dari  permainan  dinamis  (4,2).  Berdasarkan  hasil  yang  telah  diperoleh  dalam  Masalah  1  dan Masalah 2, dan berdasarkan Lemma 1, diperoleh teorema berikut.
Teorema 1.
Diberikan  permainan  dinamis  dua  pemain  berjumlah  nol  yang  disertai  dengan  ketidakpastian  yang disajikan dengan persamaan dinamik (4) dan fungsi biaya (2). Strategi optimal robust untuk permainan dinamis (4,2) adalah
    * 1 1 M Y A t t        (19)
    * 1 2 N Y A t t       (20)
jika  dan  hanya  jika  terdapat  skalar 0, 1, 2 i i    yang  menghasilkan  matriks-matriks , , H N M   
yang definit positif, dengan
0 T A A     memenuhi persamaan diferensial Riccati
    1 1 1 1 2 2 0 T T T A A X X A H A Y M Y Y P N Y P A                     (21)
dan 0 T A A     memenuhi persamaan diferensial Riccati
    1 1 1 1 2 2 0 T T T
A A X X A H A Y P M Y P Y N Y A                     . (22)
Lebih lanjut, nilai dari permainan dinamis tersebut adalah L yang memenuhi pertidaksamaan       * * , , , L L L          
dengan   * , L    merupakan nilai bawah permainan dan diberikan oleh persamaan
         
* 0 0 0 0 , 0 0 T T
T L k A k trA M tr A t KC t K dt               (23)
dan   * , L    merupakan nilai atas permainan dan diberikan oleh persamaan
         
* 0 0 0 0 , 0 0 T
T T L k A k trA M tr A t KC t K dt               . (24)
Bukti:
Persamaan (19), (21), dan (24) diperoleh dengan menyelesaikan Masalah 1 dengan menggnakan Lemma 1.  Sedangkan  Persamaan  (20),  (22),  dan  (23)  diperoleh  dengan  menyelesaikan  Masalah  2  dengan menggnakan Lemma 1.

## Kesimpulan
Dalam artikel ini telah diturunkan syarat perlu dan syarat cukup permainan dinamis linear kuadratis dua pemain berjumlah nol dengan kehadiran ketidakpastian pada sistem. Dapat dilihat pada Teorema 1  bahwa  dalam  menentukan  syarat  perlu  dan  cukup  pada  permainan  tersebut  eksistensi  skalar 0, 1, 2 i i    dan solusi dari persamaan diferensial Riccati (21) dan (22) memegang peranan yang cukup  penting.  Dua  hal  inilah  yang  akan  menyusun  strategi  optimal robust  sebagai  solusi  dari permainan dinamis tersebut.
Pembahasan  dalam  artikel  ini  masih  terbatas  pada  permainan  dinamis  fungsi  kontinu  dan  pada domain waktu yang berhingga ( finite time horizon). Sehingga pengembangan solusi permainan dinamis
baik  untuk  fungsi  diskret  maupun  untuk  domain  waktu  yang  takberhingga  ( infinite  time  horizon) merupakan masalah terbuka yang dapat diteliti lebih lanjut.

## Referensi
[1] Basar, T. dan Bernhard, P. H  Optimal Control and Related Minimax Design Problem , Modern Birkhäuser Classics,
Boston, 1995.
[2] Basar, T. and Olsder, G. J. Dynamic Noncooperative Game Theory , Academic Press SIAM, New York, 1999.
[3] Broek, v. d. Uncertainty in Differential Game , Ph.D Thesis, Tilburg University, Netherlands, 2001.
[4] Dockner, E., Jorgensen, S., Long, N. v. and Sorger, G. Differential Games in Economic and Management Science , Cambridge University Press, Cambridge, 2000.
[5] Engwerda, J. C. Linear Quadratic Dynamic Optimization and Differential Games , John Wiley & Sons, West Sussex, 2005.
[6] Haurie, A., Krawczyk, J. dan Zaccour, G. Games and Dynamic Games , Vol. 1, World Scientific Publishing Company, Singapore, 2012.
[7] Ho, Y. C., Bryson, A. E., dan Baron, S. Differential Games and Optimal Pursuit-Evasion Strategies, IEEE Transaction on Automatic Control , AC-10, 1965.
[8] Jorgensen, S. dan Zaccour, G. Differential Games in Marketing , Springer, 2004.
[9] Kaynak, O. dan Denker, A. Discrete-time Sliding Mode Control in the Presence of System Uncertainty, International Journal of Control , vol. 57, no. 5, 2010.
[10] Zhou, K. dan Doyle, J. C. Essentials of Robust Control , Prentice-Hall, New Jersey, 1998.

## THIS PAGE INTENTIONALLY LEFT BLANK