Pumunta sa nilalaman

Teorya ng laro

Mula sa Wikipedia, ang malayang ensiklopedya
(Idinirekta mula sa Game theory)

Ang teoriya ng laro (Ingles: game theory) ang pag-aaral ng stratehikong paggawa ng desisyon. Sa mas pormal na paglalarawan, ito "ang pag-aaral ng mga modelong matematikal ng alitan at pakikipagtulungan sa pagitan ng mga matalinong makatwirang mga tagagawa ng desisyon." [1] Ang isang alternatibong terminong iminungkahi "bilang isang mas deskriptibong pangalan para sa disiplina" ang interaktibong teoriyang desisyon.[2] Ang teoriya ng laro ay pangunahing ginagamit sa ekonomika, agham pampolitika, sikolohiya gayundin sa lohika at biolohiya. Ang paksang ito ay unang sumagot sa mga larong sumang-sero (zero-sum game) na ang pakinanabang ng isang tao ay eksaktong katumbas ng netong mga kawalan ng iba pang mga kalahok. Gayunpaman, sa kasalukuyan, ang teoriya ng laro ay lumalapat sa isang malawak na saklaw ng mga relasyon ng klase at umunlad sa isang terminong payong para sa lohikal na panig ng agham upang isama ang parehong tao at mga hindi tao gaya ng mga kompyuter. Ang mga klasikong paggamit ay kinabibilangan ng isang kahulugan ng balanse sa maraming mga laro kung saan ang bawat tao nakatuklas o nakabuo ng isang taktika na hindi matagumpay na makapagpapabuti ng mga resulta sa ibinigay na pakikitungo ng iba. Ang modernong teoriya ng laro ay nagmula sa ideya tungkol sa pag-iral ng stratehiyang-halong ekwilibria sa dalawang-taong mga larong sumang-sero at ang patunay nito ni John von Neumann. Ang orihinal na patunay ni Von Neumann ay gumamit ng teoremang nakapirmeng-punto ni Brouwer sa tuloy tuloy na mga pagmamapa tungo sa siskik na mga hanay na konbeks na naging isang pamantayang paraan sa teoriya ng laro at ekonomikang matematikal. Ang kanyang papel ay sinundan ng kanyang 1944 aklat na Theory of Games and Economic Behavior kasama ni Oskar Morgenstern na nagsaalang alang ng mga larong pakikipagtulungan ng ilang mga manlalaro. Ang ikalawang edisyon ng aklat na ito ay nagbigay ng teoriyang aksiyomatiko ng inaasahang utilidad na pumayag sa mga estadistikong matematikal at ekonomista na itrato ang paggawa ng desisyon sa ilalim ng kawalang katiyakan. Ang teoriyang ito ay malawak na pinaunlad noong mga 1950 ng maraming mga skolar. Ang teoriya ng laro ay kalaunang hayagang inilapat sa biolohiya noong mga 1970 bagaman ang parehong mga pag-unlad ay bumabalik sa hindi bababa sa mga 1930. Ang teoriya ng laro ay malawak na kinikilala bilang isang mahalagang kasangkapan sa maraming mga larangan. Ang walang mga teorista ng laro ay nagwagi ng Gantimpalang Nobel sa ekonomika at si John Maynard Smith ay pinarangalan ng Gantimpalang Crafoord para sa kanyang paglalapat ng teoriya ng laro sa biolohiya.

Pagkakatawan ng mga laro

[baguhin | baguhin ang wikitext]

Ang mga larong pinag-aaralan sa teoriya ng laro ay mahusay na inilalarawang mga bagay na matematikal. Ang isang laro ay binubuo ng isang hanay ng mga manlalaro, isang hanay ng mga galaw o stratehiya na magagamit ng mga manlalarong ito at isang spesipikasyon ng mga kabayaran (payoffs) para sa bawat kombinasyon ng mga stratehiya. Ang karamihan ng mga larong pakikipagtulungan ay itinatanghal sa isang anyong karakteristikong punsiyon samantalang ang ekstensibo at mga anyong normal ay ginagamit upang ilarawan ang mga hindi-pakikipagtulungang laro.

Anyong ekstensibo

[baguhin | baguhin ang wikitext]
Ang isang larong ekstensibo

Ang anyong ekstensibo ay maaaring gamitin upang ipormalisa ang mga laro na may pagsesekwensiya ng panahon ng mga galaw. Ang mga laro rito ay nilalarawan sa mga puno (gaya ng inilalarawan sa kaliwa). Dito, ang bawat berteks (o nodo) ay kumakatawan sa isang punto ng pagpipilian para sa isang manlalaro. Ang manlalaro ay tinutukoy ng isang bilang na itinala ng berteks. Ang linya sa berteks ay kumakatawan sa isang posibleng aksiyon para sa manlalarong ito. Ang mga kabayaran ay tinutukoy sa ilalim ng puno. Ang anyong ekstensibo ay maaaring makita bilang maraming manlalarong paglalaro ng isang desisyong puno.[3]

Sa larong inilarawan sa kaliwa, mayroong dalawang mga manlalaro. Ang Manlalarong 1 ang unang gumalaw at pumipili ng F o U. Nakikita ng Manlalarong 2 ang galaw ng Manlalarong 1 at pagkatapos ay pumili ng A o R. Ipagpalagay na pinili ng Manlalarong 1 ang U at pinili ng Manlalarong 2 ang A, kung gayon, ang Manlalarong 1 ay kukuha ng 8 at ang Manlalarong 2 ay kukuha ng 2.

Ang anyong ekstensibo ay maaaring bumihag ng mga larong sabay na galaw at mga larong may hindi-perpektong impormasyon. Upang ikatawan ito, ang isang tinuldukang linya ay kumokonekta sa iba't ibang mga berteks upang ikatawan ang mga ito bilang bahagi ng parehong hanay ng impormasyon (i.e. hindi alam ng mga manlalaro kung saan punto sila) o ang isang saradong linya ay iginuhit sa palibot nito.

Anyong normal

[baguhin | baguhin ang wikitext]
Ang Manlalarong 2
ay pumipili ng Kaliwa
Ang Manlalarong 2
ay pumipili ng Kanan
Ang Manlalarong 1
ay pumipili ng Itaas
4, 3 –1, –1
Ang Manlalarong 1
ay pumipili ng Ilalim
0, 0 3, 4
Anyong normal o kabayarang matriks ng isang 2-manlalarong, 2-stratehiyang laro

Ang larong normal (o anyong stratehiko) ay karaniwang ikinakatawan ng isang matriks na nagpapakita ng mga manlalaro, mga stratehiya, mga kabayaran. Sa mas pangkalahatan, ito ay maaaring ikatawan ng anumang punsiyon na nag-uugnay ng isang kabayaran para sa bawat manlalaro na may bawat posibleng kombinasyon ng mga aksiyon. Sa kasamang halimbawa, mayroong dalawang mga manlalaro. Ang isa ay pumipili ng row at isa pa ay pumipili ng column. Ang bawat manlalaro ay may dalawang mga stratehiya na tinukoy ng bilang ng mga row at bilang ng mga column. Ang mga kabayaran ay ibinibigay sa loob. Ang unang bilang ang kabayarang natanggap ng manlalaro ng row (Manlalarong 1 sa ating halimbawa). Ang ikalawa ang kabayaran para sa manlalaro ng column (Ang Manlalarong 2 sa ating halimbawa). Ipagpalagay na naglalaro ang Manlalarong 1 ng Itaas at naglalaro ang Manlalarong 2 ng Kaliwa. Kung gayon, ang Manlalarong 1 ay kukuha ng kabayaran ng 4 at ang Manlalaro 2 ay kukuha ng kabayaran na 3. Kapag ang laro ay itinanghal sa anyong normal, ipinagpapalagay na ang bawat manlalaro ay sabay na umaakto o kahit papano ay walang alam sa mga akiyon ng isa pa. Kung ang mga manlalaro ay may ilang impormasyon tungkol sa mga pagpipilian ng ibang mga manlalaro, ang laro ay karaniwang itinatanghal sa isang anyong ekstensibo. Ang bawat larong anyong ekstensibo ay may katumbas na larong anyong normal. Gayunpaman, ang transpormasyon ng anyong normal ay maaaring magresulta sa isang pagpapalaking eksponensiyal sa sukat ng representasyon na gumagawa ritong impraktikal sa komputasyon.[4]

Anyong karakteristikong punsiyon

[baguhin | baguhin ang wikitext]

Sa mga larong nag-aangkin ng maaalis na utilidad, ang magkahiwalay na mga gantimpala ay hindi ibinibigay. Bagkus, ang punsiyong karakteristiko ay nagpapasya ng kabayaran sa bawat pagkakaisa. Ang ideya ay ang pagkakaisa na 'walang laman' ay hindi tumatanggap ng isang gantimpala. Ang pinagmulan ng anyong ito ay matatagpuan sa aklat nina John von Neumann at Oskar Morgenstern. Kung titingnan ang mga instansiyang ito, kanilang hinulaan na kapag ang pagkakaisang C ay lumilitaw, ito ay gumagawang laban sa praksiyon (N/C) kung paanog ang dalawang mga indibidwal ay naglalarao ng isang larong normal. Ang nakabalanseng kabayarang C ay isang basikong punsiyon. Bagaman may iba't ibang mga halimbawa na nakatutulong sa pagtukoy ng koalisyonal na mga halaga mula sa mga larong normal, hindi lahat ay lumilitaw na sa kanilang punsiyon ay maaaring mahango mula sa gayon. Sa pormal na paglalarawan, ang isang punsiyong karakteristiko ay nakikita bilang: (N,v), kung saan ang N ay kumakatawan sa pangkat ng mga tao at ang v:2^N-->R ay isang normal na utilidad. Ang gayong mga punsiyong karakteristiko ay lumawig upang ilarawan ang mga laro kung saan ay walang maaalis na utilidad.

Anyong punsiyong partisyon

[baguhin | baguhin ang wikitext]

Ang anyong punsiyong karakteristiko ay hindi pumapansin sa posibleng mga eksternalidad ng pormasyong koalisyon. Sa anyong punsiyong partisyon, ang kabayaran ng koalisyon ay hindi lamang nakabatay sa mga kasapi nito kundi pati sa paraang ang natitira ng mga manlalaro ay pinapartisyon o hinahati.[5]

Mga uri ng mga laro

[baguhin | baguhin ang wikitext]

Pakikipagtulungan o hindi-pakikipagtulungan

[baguhin | baguhin ang wikitext]

Ang isang laro ay isang pakikipagtulungan kung ang mga manlalaro ay may kakayahang bumuo ng nagtataling mga pangako. Halimbawa, ang sistemang legal ay nag-aatas sa mga ito na sumunod sa kanilang mga pangkat. Sa mga larong hindi pakikipagtulungan, ito ay hindi posible. Kadalasan, ipinagpapalagay na ang komunikasyon sa mga manlalaro ay pinapayagan sa mga larong pakikipagtulungan ngunit hindi sa mga larong hindi pakikipagtulungan. Gayunpaman, ang klasipikasyong ito sa dalawang binaryong mga kriterya ay kinuwestiyon at minsang itinakwil.[6] Sa dalawang mga uri ng mga laro, ang mga larong hindi pakikipagtulungan ay may kakayahang magmodelo ng mga sitwasyon sa pinakamaliit na detalye na lumilikha ng mga tiyak na resulta. Ang mga larong pakikipagtulungan ay pumopokus sa laro sa pangkalahatan. Ang malaking mga pagsisikap ay ginawa upang iugnay ang dalawang mga pakikitungo. Ang tinatawag na programang Nash ay nagpatunay na maraming mga solusyong pakikipagtulungan bilang ekwilibriang hindi pakikipagtulungan. Ang mga larong hybrid ay naglalaman ng mga elementong pakikipagtulungan at hindi pakikipagtulungan. Halimbawa, ang mga koalisyon ng mga manlalaro ay nabubuo sa isang larong pakikipagtulungan ngunit ang mga ito ay naglalaro sa isang anyong hindi pakikipagtulungan.

Simetriko at asimetriko

[baguhin | baguhin ang wikitext]
E F
E 1, 2 0, 0
F 0, 0 1, 2
Isang larong asymmetriko

Ang isang larong simetriko ay isang laro kung saan ang mga kabayaran sa paglalaro ng isang partikular na stratehiya ay nakabatay lamang sa ibang mga stratehiyang ginamit hindi sa kung sino ang naglalaro ng mga ito. Kung ang mga identidad ng mga manlalaro ay mababago nang hindi mababago ang kabayaran sa mga stratehiya, kung gayon ang isang laro ay simetriko. Marami sa mga karaniwang pinag-aaralang mga larong 2×2 ay simetriko. Ang pamantayang mga representasyon ng laro ng manok, ang dilemma ng bilanggo at ang pangangaso ng usa ay lahat simettriko. Ang ilang mga skolar ay tumuturing sa ilang mga larong asimetriko bilang mga halimbawa rin ng mga larong ito. Gayunpaman, ang pinaka-karaniwang mga kabayaran ng mga larong ito ay simetriko. Ang pinaka-karaniwang pinag-aaralang mga larong asimetriko ang mga laro kung saan walang magkatulad na mga hanay na stratehiya para sa parehong mga manlalaro. Halimbawa, ang larong ultimatum at ang parehong laro ng diktador ay may iba't ibang mga stratehiya para sa parehong mga laro ngunit maaaring asimetriko. Halimbawa, ang larong inilalarawan sa kanan ay asimetriko sa kabila ng pagkakaroon ng magkatulad na mga hanay na stratehiya para sa parehong mga manlalaro.

Larong sumang-sero at larong hindi-sumang sero

[baguhin | baguhin ang wikitext]
A B
A  –1, 1 3, –3
B 0, 0  –2, 2
Isang larong sumang-sero

Ang mga larong sumang-sero ay isang espesyal na kaso ng mga larong konstanteng-suma kung saan ang mga pagpipilian ng mga manlalaro ay hindi magpapataas o hindi magpapababa ng mga makukuhang mapagkukunan. Sa mga larong sumang-sero, ang kabuuang pakinabang sa lahat ng mga manlalaro ng laro para sa bawat kombinasyon ng mga stratehiya ay palaging dumadagdag sa sero (sa mas inpormal na paglalarawan, ang isang manlalaro ay nakikinabang lamang sa parehong kawalan ng iba). Ang poker ay nagbibigay halimbawa sa larong sumang-sero (kung hindi papansinin ang posibilidad ng putol ng bahay) dahil ang isa ay nananalo ng eksakto sa halaga ng pagkatalo ng kalaban nito. Ang ibang mga larang sumang-sero ay kinabibilangan ng mga pagtutugmang pennies at karamihan ng mga klasikong larong tabla kabilang ang Go at chess. Ang mga maraming larong pinag-aaralan ng mga teorista ng laro (kabilang ang inpamosong dilemma ng bilanggo) ay mga larong hindi-sumang-sero dahil ang kalalabasan ay may netong mga resultang mas malaki o maliit sa sero. Sa hindi pormal na paglalarawan, sa mga larong hindi-sumang-sero, ang isang pakinabang ng isang manlalaro ay hindi kinakailangang tumugon sa pagkatalo ng isa pa. Ang mga larong konstanteng-suma ay tumutugon sa mga gawain tulad ng pagnanakaw at pagsusugal ngunit hindi pundamental na sitwasyong ekonomiko kung saan mayroong mga potensiyal (mga pakinabang mula sa kalakalan). Posibleng baguhin ang anumang laro sa isang (posibleng asimetriko) larong sumang-sero sa pamamagitan ng pagdaragdag ng karagdagang manlalarong dummy (na kadalasang tinatawag na "the board") na ang mga pagkatalo ay nagpupuno ng netong mga pagkapanalo ng mga manlalaro.

Larong sabay at sunod sunod

[baguhin | baguhin ang wikitext]

Ang mga larong sabay ang mga laro kung saan ang parehong mga manlalaro ay sabay na gumagalaw o kung ang mga ito ay hindi gumagalaw ng sabay, ang kalaunang mga manlalaro ay walang kamalayan sa mga aksiyon ng mas naunang mga manlalaro (na gumagawa sa mga itong epektibong sabay). Ang mga larong sekwensiyal (o larong dinamiko) ang mga laro kung saan ang mga kalaunang manlalaro ay may ilang kaalaman tungkol sa mga mas naunang aksiyon. Ito ay hindi kinakailangang isang perpektong impormasyon tungkol sa bawat aksiyon ng mga mas naunang manlalaro. Ito ay maaaring labis na kaunting kaalaman. Halimbawa, ang isang manlalaro ay maaaring makaalam na ang mas naunang manlalaro ay hindi gumanap ng isang partikular na aksiyon samantalang hindi nito alam kung alin sa mga ibang makukuhang aksiyon ng unang manlalaro ay aktuwal na naganap. Ang pagkakaiba sa pagitan ng sabay at sekwensiyal na mga laro ay nabibihag sa iba't ibang mga representasyong tinatalakay sa itaas. Sa kadalasan, ang anyong normal ay ginagamit upang ikatawan ang mga larong sabay at ang anyong ekstensibo ay ginagamit upang ikatawan ang mga larong sekwensiyal. Ang transpormasyon ng ekstensibong laro tungo sa anyong normal ay isang daan na ang ibig sabihin ang maraming mga larong anyong ekstensibo ay tumutugon sa parehong anyong normal. Dahil dito, ang mga nosyon ng ekwilibrium para sa mga larong sabay ay hindi sapat sa pangangatwiran tungo sa mga larong sekwensiyal.

Perpektong impormasyon at hindi perpektong impormasyon

[baguhin | baguhin ang wikitext]
Ang isang laro ng hindi perpektong impormasyon (ang tinuldukang linyan ay kumakatawan sa kaignorantehan sa bahagi ng Manlalarong 2 na pormal na tinatawag na hanay ng impormasyon)

Ang isang mahalagang pang-ilalim na hanay ng mga larong sekwensiyal ay binubuo ng mga laro ng perpektong impormasyon. Ang isang laro ay isang perpektong impormasyon kung alam ng lahat ng mga manlalaro ang mga galaw na nakaraang ginawa ng ibang lahat na mga manlalaro. Kaya, ang tanging mga larong sekwensiyal ang mga laro ng perpektong impormasyon dahil ang mga manlalaro sa mga larong sabay ay walang alam sa mga aksiyon ng ibang mga manlalaro. Ang karamihang mga laro na pinag-aaralan sa teoriya ng laro ang mga larong hindi perpektong impormasyon. Ang mga interesanteng halimbawa ng mga larong perpektong impormasyon ay kinabibilangan ng larong ultimatum at larong centipede. Ang mga larong paglilibang ng perpektong impormasyon ay kinabibilangan ng chess, go, at mancala. Maraming mga laro ng kard ay mga laro ng hindi perpektong impormasyon gaya halimbawa ng poker at tulay na kontrata. Ang perpektong impormasyon ay kadalasang ikinalilito sa kompletong impormasyon na isang parehong konsepto. Ang kompletong impormasyon ay nag-aatas na alam ng bawat manlalaro ang mga stratehiya at kabayarang makukuha sa ibang mga manlalaro ngunit hindi kinakailangang mga aksiyong kinuha. Ang mga laro ng hindi kompletong impormasyon ay maaaring mapaliit gayunpaman sa mga laro ng hindi perpektong impormasyon sa pamamagitan ng pagpapakilala ng mga galaw sa kalikasan.[7]

Mga larong kombinatoryal

[baguhin | baguhin ang wikitext]

Ang mga laro kung saan ang kahirapan sa paghahanap ng stratehiyang optimal ay nagmumula mula sa pagiging marami ng mga posibleng galaw na tinatawag na mga larong kombinatoryal. Ang mga halimbawa nito ay kinabibilangan ng chess at go. Ang mga larong kinasasangkutan ng hindi perpekto o hindi kompletong impormasyon ay maaari ring magkaroon ng isang malakas na katangiang kombinatoryal halimbawa sa larong backgammon. Walang teoriyang nagkakaisa sa pagsagot mga elementong kombinaoryal sa mga laro. Gayunpaman, mayroon mga kasangkapang matematikal na maaaring lumutas ng mga problemang partikular at sumagot sa ilang mga pangkalahatang tanong.[8]

Ang mga laro ng perpektong impormasyon ay pinag-aaralan sa teoriyang laro na kombinatoryal na umunlad sa mga nobelang representasyon, e.g. mga bilang na surreal gayundin din ang kombinatoryal at alhebraikong (at stratehiyang nagnanakaw ng argumento) mga paraang pagpapatunay upang lutasin ang mga ilang uri kabilang ang mga paikot ikot na mga laro na maaaring magresulta sa walang hangganang mahabang mga sekwensiya ng mga galaw. Ang mga pamamaraang ito ay sumasagot sa mga laro na mas mataas na kompleksidad na kombinatoryal kesa sa mga karaniwang itinuturing na tradisyonal o ekonomikong teoriya ng laro.[9][10] Ang isang karaniwang laro na nalutas sa paraang ito ang hex. Ang isang kaugnay na larangan ng pag-aaral na humahango sa teoriyang komputasyonal na kompleksidad ang kompleksidad ng laro na nauukol sa pagtatantiya ng kahirapang komputasyonal ng paghahanap ng mga optimal na stratehiya.[11]

Ang pagsasaliksik sa Intelihensiyang Artipisyal ay sumagot sa parehong perpekto at hindi perpektong (o hindi kompletong) mga larong impormasyon na may labis na masalimuot na mga istrakturang kombinatoryal (tulad ng chess, go o backgammon) kung saan walang mapapatunayang mga stratehiyang optimal ang natagpuan. Ang mga praktikal na solusyon ay kinasasangkutan ng mga komputsasyonal na heuristika tulad ng pagtatabas na alpha-beta o paggamit ng artipisyal na neural network na sinanay ng pagpapapalakas na pagkatuto (reinforcement learning) na gumagawa sa mga larong mas mapangasisiwaan sa pagsasanay na pagkukuwenta.[8][12]

Walang hangganang mahabang mga laro

[baguhin | baguhin ang wikitext]

Ang mga laro kung paanong pinag-aaralan ng mga ekonomista at mga manlalaro ng larong tunay na daigdig ay pangkalahatang nagtatapos sa may hangganang maraming mga galaw. Ang purong matematika ay hindi labis na tinatakdaan at ang mga teorista ng hanay sa partikular ay nag-aaral ng mga laro na tumatagal sa walang hangganang maraming mga galaw na ang ang nanalo (o iba pang kabayaran) ay hindi alam hanggang pagkatapos na lahat na ang mga galaw ay nakumpleto. Ang pokus ng atensiyon ay karaniwang hindi labis sa kung ano ang pinakamahusay na paraan na maglaro ng gayong laro ngunit simpleng kung ang isa o iba pang manlalaro ay may mananalong stratehiya. Maaaring patunayan gamit ang aksiyoma ng pagpili na mayroong mga laro kahit sa perpektong impormasyon at kung ang tanging mga kalalabasan ay panalo o talo kung saan wala sa mga manlalaro ang may stratehiyang mananalo. Ang pag-iral ng gayong mga stratehiya para sa matalinong dinisenyong mga laro ay mahalagang mga konsekwensiya sa teoriyang deskriptibong hanay.

Mga larong diskreto at tuloy tuloy

[baguhin | baguhin ang wikitext]

Ang karamihan ng teoriya ng laro ay nauukol sa may hangganan, diskretong mga laro na may hangganan bilang ng mga manlalaro, galaw, pangyayari, kalalabasan etc. Gayunpaman, maraming mga konsepto ay maaaring palawigin. Ang mga larong tuloy tuloy ay pumapayag sa mga manlalaro na pumili ng isang stratehiya mula sa isang hanay ng tuloy tuloy na stratehiya. Halimbawa, ang kompetisyong Cournot ay karaniwang minomodelo na ang mga stratehiya ng mga manlalaro ay anumang hindi negatibong mga kantidad kabilang ang mga praksiyonal na kantidad.

Mga larong diperensiyal

[baguhin | baguhin ang wikitext]

Ang mga larong diperensiyal gaya ng tuloy tuloy na larong pagpupursige at pagtakas ay mga larong tuloy tuloy kung saan ang ebolusyon ng mga bariabulo ng estado ng mga manlalaro ay pinangangasiwaan ng mga ekwasyong diperensiyal. Ang problema ng paghahanap ng optimal na stratehiya sa isang larong diperensiyal ay malapit na kaugnay ng teoriyang optimal na kontrol. Sa partikular, mayroon dalawang uri ng mga stratehiya: ang stratehiyang bukas na loop ay matatagpuan gamit ang prinsipyong maksimum ni Pontryagin samantalang ang mga stratehiyang saradong loop ay matatagpuan gamit ang paraang ekwasyong Hamilton-Jacobi-Bellman.

Ang isang partikular na kaso ng mga larong diperensiyal ang mga laro na may randomang horison ng panahon.[13] Sa gayong mga laro, ang terminal na panahon ay isang randomang bariabulo na may ibinigay na punsiyong distribusyong probabilidad. Kaya ang mga manlalaro ay nagmamaksima ng ekpektansiyang matematikal ng punsiyong gastos. Ipinakita na ang binagong problemang optimisasyon ay maaaring muling ipormula bilang isang diniskwentong larong diperensiyal sa loob ng isang walang hangganang panahong interbal.

Mga larong maraming-manlalaro at populasyon

[baguhin | baguhin ang wikitext]

Ang mga larong may arbitraryo ngunit may hangganang bilang ng mga manlalaro ay kadalasang tinatawag na mga larong n-tao.[14]. Ang teoriyang evolusyonaryong laro ay tumuturing sa mga larong kinsasangkutan ng isang populasyon ng mga tagagawa ng desisyon kung saan ang prekwensiya kung saan ang isang partikular na desisyon ay ginawa ay maaaring magbago sa loob ng panahon bilang tugon sa mga desisyong ginawa ng lahat ng mga indibiwal sa populasyon. Sa biolohiya, ito ay nilalayon mag-modelo ng biolohikal na ebolusyon kung saan ang ang nakaprogramang henetikong organismo ay nagpapasa kasama ng kanilang mga pagpoprogramang stratehiya sa kanilang mga supling. Sa ekonomika, ang parehong teoriya ay nilalayon na bumihag ng mga pagbabago sa populasyon dahil ang mga tao ay gumagampan ng papel sa laro ng maraming mga beses sa loob ng kanilang panahon ng buhay at may kamalayang (at marahila ay makatwiran) na naglilipat ng mga stratehiya.[15]

Mga kalalabasang stokastiko (at relasyon sa ibang mga larangan)

[baguhin | baguhin ang wikitext]

Ang mga problema ng indibidwal na desiyon na may mga kalalabasang stokastiko ay minsang itinuturing na mga larong isang manlalaro. Ang mga sitwasyong ito ay hindi itinuturing na larong teoretikal ng ilang mga may akda. Ang mga ito ay maaaring imodelo gamit ang mga parehong kasangkapan sa loob ng mga kaugnay na disiplina ng teoriyang desisyon, mga operasyong pagsasaliksik, at mga area ng Intelihensiyang Artipisyal, partikular na ang pagpaplanong AI (na may kawalang katiyakan) at sistemang maraming ahente. Bagaman ang mga larangang ito ay may iba't ibang mga motibator, ang matematika na nasasangkot ay malaking pareho, e.g, gamit ang mga prosesong desisyong Markov (MDP). Ang mga kalalabasang stokastiko ay maaari ring imodelo sa mga termino ng teoriya ng laro sa pamamagitan ng pagdaragdag ng isang randomang umaasal na manlalaro na gumagawa ng mga "galaw na tsansa" na tinatawag ring galaw sa kalikasan.[16] Ang manlalarong ito ay hindi karaniwang itinuturing na ikatlong manlalaro na kundi isang larong dalawang manlalaro ngunit tanging nagsisilbi upang magbigay ng pagikot ng dice kung inaatasan ng laro. Para sa ilang mga problema, ang ilang mga pakikitungo sa pagmomodelo ng mga kalalabasang stokastiko ay maaaring tumungo sa iba't ibang mga solusyon. Halimbawa, ang pagkakaiba sa pakikitungo sa pagitan ng MDP at solusyong minimaks ay ang huli ay tumuturing sa kasong masahol kesa sa hanay ng mga galaw adbersaryal kesa sa pangangatwiran sa ekspektasyon tungkol sa mga galaw na ito sa ibinigay na nakapirmeng distribusyong probabilidad. Ang pakikitungong minimaks ay maaaring mapakinabangan kung saan ang mga modelong stokastiko ay hindi makukuha ngunit maaaring labis na magtantiya ng labis na hindi malamang (ngunit magastos) na mga pangyayari na dramatikong umiimpluwensiya sa stratehiya sa gayong mga eksena kung ipinagpapalagay na ang kalaban ay magpupwersa ng gayong pangyayari.[17] Ang mga pangkalahatang modelo na kinabibilangan ng lahat ng mga elemento ng kalalabasang stokastiko, mga kalaban at parsiyal o maingay na obserbabilidad (ng mga galaw ng ibang mga manlalaro) ay pinag-aralan rin. Ang pamantayang ginto ay itinuturing na parsiyal na mapagmamasdang larong stokastiko (POSG) ngunit kaunting mga problemang realistiko ay magagawang komputasyonal sa representasyong POSG. [17]

Ito ang mga laro na ang laro ay isang pag-unlad ng mga patakaran ng isa pang laro na pinupuntirya o paksang laro. Ang metalaro ay naghahangad na imaksima ang halagang utilidad ng hanay ng patakaran na binuo. Ang teoriya ng mga metalaro ay kaugnay ng teoriyang disenyong mekanismo. Ang terminong analisis ng metalaro ay ginagamit rin upang tukuyin ang isang praktikal na pakikitungong binuo ni Nigel Howard[18] kung saan ang sitwasyon ay binalangkas bilang isang larong stratehiko kung saan ang mga may hawak ng taya ay sumusubok na tuparin ang kanilang mga layunin sa pamamagitan ng mga opsiyon makukuha nila. Ang mga kalaunang pag-unlad ay tumungo sa pormulasyon ng analisis ng konprontasyon.

Mga sanggunian

[baguhin | baguhin ang wikitext]
  1. Roger B. Myerson (1991). Game Theory: Analysis of Conflict, Harvard University Press, p. 1. Chapter-preview links, pp. vii-xi.
  2. R. J. Aumann ([1987] 2008). "game theory," Introduction, The New Palgrave Dictionary of Economics, 2nd Edition. Abstract.
  3. (Fudenberg & Tirole 1991, p. 67)
  4. (Leyton-Brown & Shoham 2008, p. 35)
  5. (Thrall & Lucas 1963).
  6. (Harsanyi 1974)
  7. (Leyton-Brown & Shoham 2008, p. 60)
  8. 8.0 8.1 Jörg Bewersdorff (2005). Luck, logic, and white lies: the mathematics of games. A K Peters, Ltd. pp. ix-xii and chapter 31. ISBN 978-1-56881-210-6.{{cite book}}: CS1 maint: date auto-translated (link)
  9. Albert, Michael H.; Nowakowski, Richard J.; Wolfe, David (2007). Lessons in Play: In Introduction to Combinatorial Game Theory. A K Peters Ltd. pp. 3–4. ISBN 978-1-56881-277-9.{{cite book}}: CS1 maint: date auto-translated (link)
  10. Beck, József (2008). Combinatorial games: tic-tac-toe theory. Cambridge University Press. pp. 1–3. ISBN 978-0-521-46100-9.{{cite book}}: CS1 maint: date auto-translated (link)
  11. Robert A. Hearn; Erik D. Demaine (2009). Games, Puzzles, and Computation. A K Peters, Ltd. ISBN 978-1-56881-322-6.{{cite book}}: CS1 maint: date auto-translated (link)
  12. M. Tim Jones (2008). Artificial Intelligence: A Systems Approach. Jones & Bartlett Learning. pp. 106–118. ISBN 978-0-7637-7337-3.{{cite book}}: CS1 maint: date auto-translated (link)
  13. Petrosjan, L.A. and Murzov, N.V. (1966). Game-theoretic problems of mechanics. Litovsk. Mat. Sb. 6, 423–433 (in Russian).
  14. (Luce & Raiffa 1957)
  15. (Webb 2007)
  16. (Osborne & Rubinstein 1994)
  17. 17.0 17.1 Hugh Brendan McMahan (2006), Robust Planning in Domains with Stochastic Outcomes, Adversaries, and Partial Observability, CMU-CS-06-166, pp. 3-4
  18. (Howard 1971)